Conformal prediction is a general method that converts almost any point
predictor to a prediction set. The resulting set keeps good statistical
properties of the original estimator under standard assumptions, and guarantees
valid average coverage even when the model is misspecified. A main challenge in
applying conformal prediction in modern applications is efficient computation,
as it generally requires an exhaustive search over the entire output space. In
this paper we develop an exact and computationally efficient conformalization
of the Lasso and elastic net. The method makes use of a novel piecewise linear
homotopy of the Lasso solution under perturbation of a single input sample
point. As a by-product, we provide a simpler and better justified online Lasso
algorithm, which may be of independent interest. Our derivation also reveals an
interesting accuracy-stability trade-off in conformal inference, which is
analogous to the bias-variance trade-off in traditional parameter estimation.
The practical performance of the new algorithm is demonstrated using both
synthetic and real data examples.

本文提供了一种精确且计算有效的基于 Lasso 和弹性网络的确认化方法，并揭示了确认推断中的准确性 - 稳定性权衡，其类似于传统参数估计中的偏差 - 方差权衡。

使用分段线性同伦快速精确收缩套索

Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy

State-of-the-art subspace clustering methods are based on expressing each
data point as a linear combination of other data points while regularizing the
matrix of coefficients with $\ell_1$, $\ell_2$ or nuclear norms. $\ell_1$
regularization is guaranteed to give a subspace-preserving affinity (i.e.,
there are no connections between points from different subspaces) under broad
theoretical conditions, but the clusters may not be connected. $\ell_2$ and
nuclear norm regularization often improve connectivity, but give a
subspace-preserving affinity only for independent subspaces. Mixed $\ell_1$,
$\ell_2$ and nuclear norm regularizations offer a balance between the
subspace-preserving and connectedness properties, but this comes at the cost of
increased computational complexity. This paper studies the geometry of the
elastic net regularizer (a mixture of the $\ell_1$ and $\ell_2$ norms) and uses
it to derive a provably correct and scalable active set method for finding the
optimal coefficients. Our geometric analysis also provides a theoretical
justification and a geometric interpretation for the balance between the
connectedness (due to $\ell_2$ regularization) and subspace-preserving (due to
$\ell_1$ regularization) properties for elastic net subspace clustering. Our
experiments show that the proposed active set method not only achieves
state-of-the-art clustering performance, but also efficiently handles
large-scale datasets.

本文研究了弹性网络正则化器的几何性质，使用其导出可扩展且可证明正确的主动集方法，以找到最佳系数，并提供了弹性网络子空间聚类中连接性和保子空间性之间平衡的理论解释和几何解释，实验证明所提出的主动集方法不仅实现了最先进的聚类性能，还能有效地处理大规模数据集。

基于 Oracle 的可扩展弹性网络子空间聚类主动集算法

Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace  Clustering

We derive a novel norm that corresponds to the tightest convex relaxation of
sparsity combined with an $\ell_2$ penalty. We show that this new {\em
$k$-support norm} provides a tighter relaxation than the elastic net and is
thus a good replacement for the Lasso or the elastic net in sparse prediction
problems. Through the study of the $k$-support norm, we also bound the
looseness of the elastic net, thus shedding new light on it and providing
justification for its use.

通过研究 $k$-support 范数，我们证明它是稀疏预测问题中 Lasso 或 elastic net 的很好替代品，并提供了弹性网络使用的理由和界限。

$k$- 支撑范数的稀疏预测

Sparse Prediction with the $k$-Support Norm

We consider ``one-at-a-time'' coordinate-wise descent algorithms for a class
of convex optimization problems. An algorithm of this kind has been proposed
for the $L_1$-penalized regression (lasso) in the literature, but it seems to
have been largely ignored. Indeed, it seems that coordinate-wise algorithms are
not often used in convex optimization. We show that this algorithm is very
competitive with the well-known LARS (or homotopy) procedure in large lasso
problems, and that it can be applied to related methods such as the garotte and
elastic net. It turns out that coordinate-wise descent does not work in the
``fused lasso,'' however, so we derive a generalized algorithm that yields the
solution in much less time that a standard convex optimizer. Finally, we
generalize the procedure to the two-dimensional fused lasso, and demonstrate
its performance on some image smoothing problems.

本文介绍了 “逐一” 坐标下降算法及其在 $ L_1 $- 惩罚回归（套索）、garotte 和弹性网络等相关方法中的应用，证明了该算法可以与广泛应用的 LARS（或同伦）过程竞争，在大规模 lasso 问题中引起了不少关注。但注意到它并不适用于 “融合 Lasso”，所以论文提出了一个广义算法，在比标准的凸优化器运行时间更短的时间内得出了解决方案。最后，将该过程推广到二维融合 Lasso，并展示了其在一些图像平滑问题上的性能。