Complexity Analysis of the Lasso Regularization Path

Abstract

The regularization path of the Lasso can be shown to be piecewise linear, making it possible to "follow" and explicitly compute the entire path. We analyze in this paper this popular strategy, and prove that its worst case complexity is exponential in the number of variables. We then oppose this pessimistic result to an (optimistic) approximate analysis: We show that an approximate path with at most O(1/sqrt(epsilon)) linear segments can always be obtained, where every point on the path is guaranteed to be optimal up to a relative epsilon-duality gap. We complete our theoretical analysis with a practical algorithm to compute these approximate paths.

To appear in the proceedings of 29th International Conference on Machine Learning (ICML 2012)

References in corpus (11)

• 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
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Piecewise linear regularized solution paths

Cited by in corpus (22)

• Lasso Screening Rules via Dual Polytope Projection
• Screening Tests for Lasso Problems
• Mind the duality gap: safer rules for the Lasso
• An Equivalence between the Lasso and Support Vector Machines
• More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming
• DECOrrelated feature space partitioning for distributed sparse regression
• Nonsmooth Implicit Differentiation for Machine Learning and Optimization
• Combined l_1 and greedy l_0 penalized least squares for linear model selection
• Clustering with feature selection using alternating minimization, Application to computational biology
• Root-finding Approaches for Computing Conformal Prediction Set
• Robust supervised classification and feature selection using a primal-dual method
• Safe Grid Search with Optimal Complexity
• Regularization Path of Cross-Validation Error Lower Bounds
• Quantum Algorithms for the Pathwise Lasso
• The Well Tempered Lasso
• Dictionary learning for fast classification based on soft-thresholding
• Aggregation of supports along the Lasso path
• Efficient Clustering of Correlated Variables and Variable Selection in High-Dimensional Linear Models
• Modeling high dimensional multichannel brain signals
• Fast tree inference with weighted fusion penalties
• A Greedy Homotopy Method for Regression with Nonconvex Constraints
• An Algorithmic Framework for Computing Validation Performance Bounds by Using Suboptimal Models