Robust Regression and Lasso

By Huan Xu, Constantine Caramanis, Shie Mannor. 2008

317 citations recorded by the source corpus.

Lasso, or l1 regularized least squares, has been explored extensively for its remarkable sparsity properties. In this paper it is shown 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. Second, robustness can itself be used as an avenue for 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 is proved which states that sparsity and algorithmic stability contradict each other, and hence Lasso is not stable.

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Conditional variance penalties and domain shift robustness (2017, background): “The distributionally robust targets (1) can often be expressed in penalized form; see Gao et al. (2017); Sinha et al. (2017); Xu et al. (2009).”
Robustness and Regularization of Support Vector Machines (2008, background): “The connection of robustness and regularization in the SVM context is important for the following reasons.”
Robustness and generalization (2010, methodology): “Later on, Xu et al. (2009a, 2010b) showed that both Support Vector Machines (SVMs) and Lasso have robust optimization interpretation, i.e., they can be reformulated as min h∈H max (δ1,...,δn)∈Δ n∑ i=1 l(h, zi + δi), for some Δ and H.”
Anchor regression: Heterogeneous data meet causality (2018, neutral): “a (weighted) ridge penalty is optimal for prediction under perturbations. This is well known in the measurement errors literature, see for example Fuller [2009]. A similar result holds for the Lasso [Xu et al., 2009]. 2 Population anchor regression We now discuss properties of the population version”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “Another line of recent work considers robustness in the high-dimensional setting ([27, 36, 8, 3, 24]) In this version, our focus is on general stochastic optimization in presence of outliers.”
Kernel Methods and Machine Learning (2014, background): “It is worth mentioning that an alternative linear PR formulated under a worst-case consideration reduces to a LASSO-type problem [308].”
Recent advances in robust optimization: An overview (2014, background): “Xu et al. (2010) consider l(1) regularized least squares ( " lasso " ) and show that the solution to Lasso, in addition to its sparsity, has robustness properties, in the sense that it is the solution to a robust optimization problem.”
Robust Wasserstein profile inference and applications to machine learning (2016, methodology): “The methods proposed here differ subtly: While the papers [53, 54] add deterministic perturbations of a certain size to the predictor vectors X to quantify uncertainty, the Distributionally Robust Representations that we derive measure perturbations in terms of deviations from the empirical distribu”
A distributional interpretation of robust optimization (2010, unknown): “(5”
Distributionally Robust Logistic Regression (2015, methodology): “In the context of support vector machines and Lasso, there have been several recent attempts to give ad hoc regularization techniques a robustness interpretation [23, 24].”
A Minimax Approach to Supervised Learning (2016, background): “Another type of minimax, but non-probabilistic, argument for the robustness of lasso-like regression algorithms can be found in [29, 30].”
Towards Out-Of-Distribution Generalization: A Survey (2021, background): “Xu et al. [128] show the equivalence between robust linear regression with feature perturbations and the Least Absolute Shrinkage and Selection Operator(LASSO), and Yang et al. [129] and Bertsimas et al. [130] make further extensions.”
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach (2016, background): “tes how robust optimization regularizes the problem. The connection between robust optimization and regularization has been a folk theorem. For support vector machines and lasso regression, Xu et al. [70, 71] noted a formal equivalence between robustiﬁcation and regularization for certain uncertaint”
Wasserstein Distributional Robustness and Regularization in Statistical Learning (2017, background): “It has been shown that norm penalty regularization has a robust-optimization interpretation in some special cases, including linear/matrix regression (Xu et al. 2009a, Bertsimas and Copen-haver 2017), and support vector machine (Xu et al. 2009b).”
A Kernel Perspective for Regularizing Deep Neural Networks (2018, unknown): “In particular, Xu et al. (2009b) show that the penalized and robust objectives are equivalent in the case of the hinge loss with linear predictors, when the data is non-separable.”
On Regularization and Robustness of Deep Neural Networks (2018, background): “In particular, we study the connection between adversarial training under `2 perturbations and penalizing with the RKHS norm, in a similar vein to Xu et al. (2009b); from a statistical point of view, we extend margin-based generalization bounds in the spirit of Bartlett et al. (2017); Boucheron et…”
CAUSALITY FROM A DISTRIBUTIONAL ROBUSTNESS POINT OF VIEW (2018, methodology): “If using squared-error loss as loss function in a regression setting, [5] show that an appropriately chosen robust optimization problem is equivalent to to `1-penalized regression for sparse highdimensional inference [6].”