← All papers
First page of CLASSO: a practical primal path-following algorithm for the constrained LASSO

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

Michael Hobson, Luke Butcher, Lindley Lentati

stat.CO Oct 12, 2026 · v1 stat.ML
The well-posedness, piecewise-affine path finiteness and termination theorems, plus counterexamples, are formalised in Lean 4 against Mathlib with no admitted proofs.
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.

Path-following for the LASSO under general linear equality and inequality constraints. The prior method of Gaines et al. requires a full-row-rank condition on binding constraints, and that condition often fails, for example under sign constraints.

CLASSO obtains the local direction from a quadratic programme on an augmented active set. The QP determines which zero coefficients leave zero and which weakly active inequalities stay binding. The method follows a minimum-norm certificate along a lexicographic rate to guarantee finite traversal. The theory, including the piecewise-affine structure without a constraint qualification and termination within an explicit bound, is machine-checked in Lean 4 with Mathlib.

On the 31 nontrivial synthetic cases with n ≥ p, sampled relative objective differences from reference solves are below 1e-9 in magnitude. The floating-point implementation agrees with an exact rational one on all 210 small test problems. Checks of all 580 recorded segments found no missed interior event, and all checked KKT residuals were within the stated tolerances.