CLASSO: a practical primal path-following algorithm for the constrained LASSO

Abstract

We present CLASSO, a path-following method for the LASSO subject to general linear equality and inequality constraints. The local direction is obtained from a quadratic programme on an augmented active set, which determines both the coefficients that leave zero and the weakly active inequalities that remain binding. For a positive-definite Hessian and a nonempty feasible set, this programme has a unique primal minimiser, even when the binding constraint rows are dependent, and gives the local derivative of the solution path. The construction recovers the LASSO-modified LARS direction without constraints, and over the full cone gives the segment leaving the origin. We prove that the primal path is piecewise affine with finitely many kinks, without a constraint qualification or unique multipliers. A finite path does not imply a finite traversal: re-certifying at each kink can fail to terminate. CLASSO instead follows the minimum-norm certificate along a lexicographic rate; we prove that this rule reaches $λ=0$ in exact arithmetic within an explicit bound and traverses the whole path. These results are machine-checked in Lean~4, and the floating-point implementation agrees with an exact rational one on all $210$ small test problems. We assess the implementation on a $39$-case synthetic suite and six constrained versions of the diabetes benchmark. On the $31$ nontrivial synthetic cases with $n\ge p$, sampled relative objective differences from numerical reference solves are below $10^{-9}$ in magnitude; unnormalised endpoint differences reach $1.5\times10^{-7}$ in magnitude. For $n<p$, matched differences range from $-3.6\times10^{-7}$ to $2\times10^{-9}$ across five ridge strengths. Across the synthetic and diabetes benchmarks, checks of all $580$ recorded segments found no missed interior event and all checked KKT residuals within the stated tolerances.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computation

• arXiv preprint · 12 October 2026

  Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

  Hwanwoo Kim, Jungwoo Hong and Kyungjae Lee
• arXiv preprint · 13 October 2026

  A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes

  Zhongyang Li
• arXiv preprint · 12 October 2026

  Locally adaptive step sizes for Hamiltonian Monte Carlo methods

  Jimmy Huy Tran, Tore Selland Kleppe and Nawaf Bou-Rabee
• arXiv preprint · 13 October 2026

  Theoretical and Practical Advances in Hierarchical Bayesian Deep Learning Methodology

  Neil K. Chada, Simon Cotter, Kody J. H. Law and 1 other
• arXiv preprint · 14 October 2026

  MCMC Can See Can't See

  Daniel Matsui Smola

All new papers in Computation