Abstract
Lasso, or $\ell^1$ regularized least squares, has been explored extensively for its remarkable sparsity properties. It is shown in this paper that the solution to Lasso, in addition to its sparsity, has robustness properties: it is the solution to a robust optimization problem. This has two important consequences. First, robustness provides a connection of the regularizer to a physical property, namely, protection from noise. This allows a principled selection of the regularizer, and in particular, generalizations of Lasso that also yield convex optimization problems are obtained by considering different uncertainty sets. Secondly, robustness can itself be used as an avenue to exploring different properties of the solution. In particular, it is shown that robustness of the solution explains why the solution is sparse. The analysis as well as the specific results obtained differ from standard sparsity results, providing different geometric intuition. Furthermore, it is shown that the robust optimization formulation is related to kernel density estimation, and based on this approach, a proof that Lasso is consistent is given using robustness directly. Finally, a theorem saying that sparsity and algorithmic stability contradict each other, and hence Lasso is not stable, is presented.
Introduction
Standard least-squares regression is notoriously sensitive to noise and outliers. To mitigate this, researchers typically add a regularizer to the objective function. Lasso, which utilizes an $\ell_1$ penalty, has become the gold standard for high-dimensional data because it produces "sparse" solutions—models where most feature weights are zero. This effectively performs automatic feature selection, making the resulting models more interpretable and computationally efficient.
However, the choice of the $\ell_1$ norm is often treated as a heuristic—a convex proxy for the computationally intractable $\ell_0$ norm. This paper addresses a fundamental gap in the literature: Is there a deeper physical or geometric reason why Lasso works? By reframing Lasso through the lens of robust optimization, the authors provide a principled justification for the $\ell_1$ penalty and reveal a fundamental trade-off between model sparsity and algorithmic stability.
The Robust Optimization Framework
The core contribution of this work is the proof that Lasso is not just a clever trick for sparsity, but the mathematically optimal solution to a robust optimization problem. Instead of minimizing the standard residual, the authors formulate a min-max problem:
$$\min_{\beta} \max_{\Delta A \in \mathcal{U}} \| y - (A + \Delta A)\beta \|_2$$
In this formulation, the data matrix $A$ is subject to perturbations $\Delta A$ within an uncertainty set $\mathcal{U}$. The authors define a specific type of uncertainty called feature-wise uncoupled uncertainty, where each feature (column of the data matrix) can be perturbed independently within a bounded norm.
Theorem 1 formally establishes that this robust regression problem is mathematically identical to the Lasso objective. This reveals that the $\ell_1$ penalty is the natural consequence of protecting a model against independent noise in the features. This "robustness in disguise" provides a physical connection for the regularizer, allowing practitioners to select regularization parameters based on the expected noise level in their data.
Geometric Intuition for Sparsity
Beyond justifying the $\ell_1$ norm, the robust framework provides a new geometric explanation for why Lasso produces sparse solutions. From a robustness perspective, a feature’s weight becomes zero if there exists a "malicious" perturbation within the allowed bounds that makes that feature orthogonal to the signal.
Essentially, if a feature could be noise, a robust algorithm ignores it. The authors provide new geometric conditions (Theorems 5 and 6) showing that "nearly orthogonal" features are assigned zero weight because they are effectively indistinguishable from noise under the robust framework. This differs from standard sparsity results by focusing on the relationship between the uncertainty set and the feature geometry.
The Sparsity-Stability Trade-off
One of the paper's most striking findings is a "no-free-lunch" theorem regarding algorithmic stability. Uniform stability measures how much a model's predictions change when a single training sample is removed. High stability is generally desirable for generalization and consistency.
However, Theorem 9 proves that any algorithm that encourages sparsity (like Lasso) is inherently unstable. If an algorithm is sensitive enough to "zero out" a feature based on the data, it will necessarily produce significantly different results if the data changes slightly. The authors show that the uniform stability bound of Lasso does not diminish as more data is added, representing a fundamental conflict between the desire for sparse models and the need for stable algorithms.
Consistency and Generalization
The authors further connect robust optimization to Kernel Density Estimation (KDE). They demonstrate that the robust formulation is equivalent to minimizing the worst-case expected error over a class of distributions that includes KDEs. This provides a novel, robustness-based path to proving that Lasso is statistically consistent, reinforcing its theoretical foundations from a frequentist perspective.
Conclusion
By reinterpreting Lasso as a robust optimization problem, this paper moves beyond heuristic justifications for $\ell_1$ regularization. This framework allows for the design of "principled" regularizers by creating custom uncertainty sets that reflect specific physical properties of a domain—such as sensor calibration errors or genomic sequencing noise. While the proven instability of sparse models suggests caution in certain applications, the robust perspective provides a powerful toolkit for understanding and extending regression techniques in the presence of uncertainty.
Summary updated