Complexity Analysis of the Lasso Regularization Path

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.

• Publication year

  2012

• Venue

  International Conference on Machine Learning

• Publication date

  2012-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1205.0079
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse Convex Optimization Methods for Machine Learning

  2011influential reference
• Approximating parameterized convex optimization problems

  2010influential reference
• An Exponential Lower Bound on the Complexity of Regularization Paths

  2009cited by this paper
• Piecewise linear regularized solution paths

  2007cited by this paper
• Recovery of exact sparse representations in the presence of bounded noise

  2005cited by this paper
• Convex Optimization

  2004cited by this paper
• The Entire Regularization Path for the Support Vector Machine

  2004cited by this paper
• Convex Analysis and Nonlinear Optimization: Theory and Examples. Jonathan M. Borwein and Adrian S. Lewis, Springer, New York, 2000

  2003influential reference
• A new approach to variable selection in least squares problems

  2000cited by this paper
• On the LASSO and its Dual

  2000cited by this paper
• Penalized Regressions: The Bridge versus the Lasso

  1998cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Portfolio Selection

  1971cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• Ein Verfahren zur Lösung parameterabhängiger, nichtlinearer Maximum-Probleme

  1962influential reference
• ACTIVITY ANALYSIS OF PRODUCTION AND ALLOCATION

  1952cited by this paper
• XLII. On certain fundamental principles of scientific inquiry

  1921cited by this paper
• © Institute of Mathematical Statistics, 2004 LEAST ANGLE REGRESSION

  year unknowncited by this paper

• Choose Your Model Size: Any Compression by a Single Gradient Descent

  2025cites this paper
• Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks

  2025cites this paper
• Robust Paths: Geometry and Computation

  2025cites this paper
• Choose Your Model Size: Any Compression of Large Language Models Without Re-Computation

  2025cites this paper
• Scalable Quantum Error Mitigation with Neighbor-Informed Learning

  2025cites this paper
• A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions

  2025cites this paper
• Automatic optical depth parametrization in radiative transfer model RTTOV v13 via LASSO-induced sparsity

  2025cites this paper
• AI-Driven Prediction of Cardio-Oncology Biomarkers Through Protein Corona Analysis.

  2025cites this paper
• Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks

  2024cites this paper
• Beyond Discretization: Learning the Optimal Solution Path

  2024cites this paper
• Lipschitz stability of least-squares problems regularized by functions with $\mathcal{C}^2$-cone reducible conjugates

  2024influential citation
• Variational Mode Decomposition and Linear Embeddings are What You Need For Time-Series Forecasting

  2024cites this paper
• A new Linear Time Bi-level ℓ1,∞ projection ; Application to the sparsification of auto-encoders neural networks

  2024cites this paper
• The Solution Path of SLOPE

  2024influential citation
• Integrated path stability selection.

  2024cites this paper
• Geometric Characterizations of Lipschitz Stability for Convex Optimization Problems

  2024influential citation
• New Bounds for Hyperparameter Tuning of Regression Problems Across Instances

  2023influential citation
• A Novel Integer Linear Programming Approach for Global L0 Minimization

  2023influential citation
• Saddle-to-saddle dynamics in diagonal linear networks

  2023cites this paper
• Quantum Algorithms for the Pathwise Lasso

  2023influential citation
• UAV-Aided Lifelong Learning for AoI and Energy Optimization in Nonstationary IoT Networks

  2023cites this paper
• Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation

  2023influential citation
• Solution Path of Time-varying Markov Random Fields with Discrete Regularization

  2023cites this paper
• Bounded p values in parametric programming-based selective inference

  2023influential citation
• A Unified Framework for Pattern Recovery in Penalized and Thresholded Estimation and its Geometry

  2023cites this paper
• Conformalization of Sparse Generalized Linear Models

  2023cites this paper
• Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

  2023influential citation
• New Methods for Parametric Optimization via Differential Equations

  2023cites this paper
• A confidence machine for sparse high‐order interaction model

  2022cites this paper
• Linear-step solvability of some folded concave and singly-parametric sparse optimization problems

  2022cites this paper
• Statistical inference for the dynamic time warping distance, with application to abnormal time-series detection

  2022cites this paper
• LASSO for streaming data with adaptative filtering

  2022influential citation
• Lasso Monte Carlo, a variation on multi fidelity methods for high-dimensional uncertainty quantification

  2022cites this paper
• Benchopt: Reproducible, efficient and collaborative optimization benchmarks

  2022cites this paper
• Automatic differentiation of nonsmooth iterative algorithms

  2022cites this paper
• Towards a Unified Framework for Uncertainty-aware Nonlinear Variable Selection with Theoretical Guarantees

  2022cites this paper
• Fast Feature Selection with Fairness Constraints

  2022cites this paper
• Root-finding approaches for computing conformal prediction set

  2021cites this paper
• Continuation Path with Linear Convergence Rate

  2021cites this paper
• On the structure of regularization paths for piecewise differentiable regularization terms

  2021cites this paper
• Risk Factor Identification in Heterogeneous Disease Progression with L1-Regularized Multi-state Models

  2021cites this paper
• Penalized Cox’s proportional hazards model for high-dimensional survival data with grouped predictors

  2021cites this paper
• Cardinality Minimization, Constraints, and Regularization: A Survey

  2021cites this paper
• Fast and More Powerful Selective Inference for Sparse High-order Interaction Model

  2021influential citation
• Efficient and Modular Implicit Differentiation

  2021cites this paper
• More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming

  2021influential citation
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning

  2021cites this paper
• The Hessian Screening Rule

  2021cites this paper
• Spectral Dependence

  2021cites this paper
• Unbalanced Optimal Transport through Non-negative Penalized Linear Regression

  2021cites this paper
• Nonsmooth Implicit Differentiation for Machine Learning and Optimization

  2021cites this paper
• Efficient path algorithms for clustered Lasso and OSCAR

  2020cites this paper
• Detection of Change Points in Piecewise Polynomial Signals Using Trend Filtering

  2020cites this paper
• Learning sparse deep neural networks using efficient structured projections on convex constraints for green AI

  2020cites this paper
• A fast homotopy algorithm for gridless sparse recovery

  2020influential citation
• An Exact Solution Path Algorithm for SLOPE and Quasi-Spherical OSCAR

  2020cites this paper
• Fast Parallel Algorithms for Statistical Subset Selection Problems

  2019cites this paper
• A safe reinforced feature screening strategy for lasso based on feasible solutions

  2019cites this paper
• Robust supervised classification and feature selection using a primal-dual method

  2019cites this paper
• Using Benson's Algorithm for Regularization Parameter Tracking

  2019influential citation
• Fast Parallel Algorithms for Feature Selection

  2019cites this paper
• Mixed Integer Programming For Sparse Coding: Application to Image Denoising

  2019cites this paper
• Grid-Free DOD and DOA Estimation for MIMO Radar via Duality-Based 2D Atomic Norm Minimization

  2019cites this paper
• The Geometry of Sparse Analysis Regularization

  2019cites this paper
• Solving Fused Penalty Estimation Problems via Block Splitting Algorithms

  2019cites this paper
• Post-Pareto Analysis and a New Algorithm for the Optimal Parameter Tuning of the Elastic Net

  2019cites this paper
• Méthodes de descente par coordonnée pour les problèmes d’optimisation convexes non-dérivables Coordinate descent methods for non-differentiable convex optimisation problems

  2019cites this paper
• Complexity and Applications of the Homotopy Principle for Uniformly Constrained Sparse Minimization

  2019influential citation
• Homotopy Methods for Linear Optimization Problems with Sparsity Penalty and Applications

  2018cites this paper
• On the Complexity of the Weighted Fused Lasso

  2018cites this paper
• Safe optimization algorithms for variable selection and hyperparameter tuning

  2018influential citation
• Safe Grid Search with Optimal Complexity

  2018cites this paper
• On high dimensional regression : computational and statistical perspectives École Normale Supérieure

  2018cites this paper
• The Well Tempered Lasso

  2018influential citation
• Preference learning for machine translation

  2018cites this paper
• ST ] 3 1 M ay 2 01 6 Aggregation of supports along the Lasso path

  2018cites this paper
• On the Complexity of the Weighted Fussed Lasso

  2018cites this paper
• Modeling High-Dimensional Multichannel Brain Signals

  2017cites this paper
• Lasso-Path and Taut String Algorithm for One-Dimensional Total Variation Regularization

  2017cites this paper
• The design of a cloud-based tracker platform based on system-of-systems service architecture

  2017influential citation
• Clustering with feature selection using alternating minimization, Application to computational biology

  2017cites this paper
• Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence

  2017cites this paper
• Clustering with feature selection using alternating minimization, Application to computational biology

  2017cites this paper
• Acceleration Methods for Classic Convex Optimization Algorithms

  2017cites this paper
• Joint fall and aspect angle recognition using fine-grained micro-Doppler classification

  2017cites this paper
• Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence

  2017cites this paper
• Mairal Large-Scale Machine Learning and Applications Soutenue le 4 octobre 2017

  2017influential citation
• Efficient block boundaries estimation in block-wise constant matrices: An application to HiC data

  2017cites this paper
• Sharp oracle inequalities in aggregation and shape restricted regression

  2016influential citation
• HONES: A Fast and Tuning-free Homotopy Method For Online Newton Step

  2016cites this paper
• A primal-dual homotopy algorithm for ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{1}$$\end{document}-minim

  2016cites this paper
• Distributed Feature Selection in Large n and Large p Regression Problems

  2016cites this paper
• HOP: An Efficient Homotopy Method for Online Anisotropic Projection

  2016cites this paper
• DECOrrelated feature space partitioning for distributed sparse regression

  2016cites this paper
• Self-regularized causal structure discovery for trajectory-based networks

  2016cites this paper
• Aggregation of supports along the Lasso path

  2016cites this paper
• Generalized LASSO with under-determined regularization matrices

  2016cites this paper
• Interrelationships of Service Orchestrations

  2016cites this paper
• Generalized LASSO with underdetermined regularization matrices

  2016cites this paper
• Efficient Clustering of Correlated Variables and Variable Selection in High-Dimensional Linear Models

  2016cites this paper