The Trimmed Lasso: Sparsity and Robustness

Abstract

Nonconvex penalty methods for sparse modeling in linear regression have been a topic of fervent interest in recent years. Herein, we study a family of nonconvex penalty functions that we call the trimmed Lasso and that offers exact control over the desired level of sparsity of estimators. We analyze its structural properties and in doing so show the following: 1) Drawing parallels between robust statistics and robust optimization, we show that the trimmed-Lasso-regularized least squares problem can be viewed as a generalized form of total least squares under a specific model of uncertainty. In contrast, this same model of uncertainty, viewed instead through a robust optimization lens, leads to the convex SLOPE (or OWL) penalty. 2) Further, in relating the trimmed Lasso to commonly used sparsity-inducing penalty functions, we provide a succinct characterization of the connection between trimmed-Lasso- like approaches and penalty functions that are coordinate-wise separable, showing that the trimmed penalties subsume existing coordinate-wise separable penalties, with strict containment in general. 3) Finally, we describe a variety of exact and heuristic algorithms, both existing and new, for trimmed Lasso regularized estimation problems. We include a comparison between the different approaches and an accompanying implementation of the algorithms.

32 pages (excluding appendix); 4 figures

References in corpus (18)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• SLOPE - Adaptive variable selection via convex optimization
• Least quantile regression via modern optimization
• Global solutions to folded concave penalized nonconvex learning
• Efficient DC Algorithm for Constrained Sparse Optimization
• Sparse Estimation with Strongly Correlated Variables using Ordered Weighted L1 Regularization
• Convergence of a Scholtes-type Regularization Method for Cardinality-Constrained Optimization Problems with an Application in Sparse Robust Portfolio Optimization

Cited by in corpus (5)

• Scalable Holistic Linear Regression
• Pursuit of the Cluster Structure of Network Lasso: Recovery Condition and Non-convex Extension
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• M-estimation with the Trimmed l1 Penalty
• Principal Component Hierarchy for Sparse Quadratic Programs