Coverage for src/cvxcla/_lasso_cla.py: 100%
42 statements
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:36 +0000
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:36 +0000
1"""The equality-constrained LASSO ``A beta = 0``, traced through the leverage CLA.
3The LASSO homotopy of :mod:`cvxcla.lasso` starts from ``beta = 0`` and needs every
4constraint row slack there, so it cannot carry equality rows: an equality row is
5active from the start and the path cannot be seeded one coordinate at a time. The
6Critical Line Algorithm has no such restriction, and under ``Sigma = X^T X`` and
7``mu = X^T y`` it traces the same curve (Schmelzer and Hastie, "The Critical Line
8Algorithm and the Constrained LASSO: One Curve, Two Literatures",
9arXiv:2609.25704).
11With homogeneous constraints the route is Corollary 2 of that note. At a fixed
12gross-exposure cap ``c`` the tilt sweep of the capped program
14 min 1/2 w^T Sigma w - lam mu^T w s.t. ||w||_1 <= c, A w = 0
16is the budget-indexed path rescaled, ``w(lam) = lam * beta`` with
17``||beta||_1 = c / lam``, and by Theorem 1 the budget-indexed path is the
18constrained LASSO path. So one leverage-capped CLA trace with ``c = 1`` gives
19every LASSO breakpoint as ``beta = w / lam``, in order: ``lam = inf`` is
20``beta = 0``, and the cap's release is the constrained least-squares fit. A box of
21``+/- 2 c`` makes the CLA well posed and never binds, since ``|w_i| <= ||w||_1 <= c``.
22A sign constraint ``beta_j >= 0`` or ``beta_j <= 0`` puts that coefficient's bound at
23``0``, which is homogeneous as well, so signs may be set on any of the coefficients.
25The CLA's tilt is not the LASSO penalty. The penalty at a breakpoint is read off
26the KKT conditions of the LASSO on the segment that leaves it:
27``(X^T y - X^T X beta)_F = lam_L s_F + A_F^T nu``, over the segment's free set
28``F`` with signs ``s_F``. The matrix ``[s_F, A_F^T]`` has full column rank at
29every non-degenerate active set, so the least-squares solution is exact.
31With more features than observations the Gram is singular. The free set then
32outgrows its rank before the fit interpolates, and the CLA solves those segments
33through the whole bordered KKT system, which the active rows keep nonsingular (see
34:func:`cvxcla._checks.guard_degeneracy`). Once the fit interpolates the penalty is
35zero, and the least-squares fits are not unique: the CLA goes on through other
36interpolating fits of larger ``l1`` norm, which are not on the LASSO path, so the path
37ends at the first of them.
38"""
40from __future__ import annotations
42import itertools
44import numpy as np
45from numpy.typing import NDArray
46from scipy.optimize import linprog # type: ignore[import-untyped]
48from .cla import CLA
49from .errors import CLAError
50from .operators import QuadraticForm
52#: A penalty this far below the first one, relative, is zero: the fit interpolates.
53_INTERPOLATES = 1e-10 # pragma: no mutate
55#: One LASSO breakpoint as ``(lam, beta, active)``; :mod:`cvxcla.lasso` wraps it.
56BreakpointData = tuple[float, NDArray[np.float64], NDArray[np.bool_]]
59def _max_correlation(
60 xty: NDArray[np.float64],
61 a: NDArray[np.float64],
62 lower: NDArray[np.float64],
63 upper: NDArray[np.float64],
64) -> float:
65 """Return ``max xty^T beta`` over ``||beta||_1 <= 1``, ``A beta = 0`` and the signs.
67 Zero means ``beta = 0`` is optimal at every penalty, so the path is one point.
68 """
69 n = xty.shape[0]
70 legs = np.hstack([np.eye(n), -np.eye(n)])[:, np.concatenate([upper > 0, lower < 0])]
71 result = linprog(
72 c=-(xty @ legs),
73 A_ub=np.ones((1, legs.shape[1])),
74 b_ub=np.ones(1),
75 A_eq=a @ legs,
76 b_eq=np.zeros(a.shape[0]),
77 bounds=(0.0, None),
78 method="highs",
79 )
80 return float(-result.fun)
83def _penalty(
84 quad: QuadraticForm,
85 xty: NDArray[np.float64],
86 a: NDArray[np.float64],
87 beta: NDArray[np.float64],
88 free: NDArray[np.bool_],
89 signs: NDArray[np.float64],
90) -> float:
91 """Solve the LASSO stationarity on ``free`` for the penalty ``lam_L``.
93 Args:
94 quad: The Gram form ``X^T X``.
95 xty: The linear term ``X^T y``.
96 a: The equality rows.
97 beta: The coefficients at the breakpoint.
98 free: The support of the segment leaving the breakpoint.
99 signs: The signs of ``beta`` on that segment (length ``n``).
101 Returns:
102 The penalty, clamped at zero against round-off at the least-squares end.
103 """
104 residual = (xty - quad.matvec(beta))[free]
105 system = np.hstack([signs[free][:, None], a[:, free].T])
106 solution = np.linalg.lstsq(system, residual, rcond=None)[0]
107 return max(float(solution[0]), 0.0)
110def equality_path(
111 quad: QuadraticForm,
112 xty: NDArray[np.float64],
113 a: NDArray[np.float64],
114 lower: NDArray[np.float64],
115 upper: NDArray[np.float64],
116 tol: float,
117) -> list[BreakpointData]:
118 """Trace the LASSO path under ``A beta = 0`` and sign constraints via one leverage-capped CLA.
120 Args:
121 quad: The Gram form ``X^T X`` as a :class:`QuadraticForm`.
122 xty: The linear term ``X^T y``.
123 a: The equality rows ``(m, n)`` of ``A beta = 0``.
124 lower: Per-coefficient lower bounds, each ``0`` (``beta_j >= 0``) or ``-inf``.
125 upper: Per-coefficient upper bounds, each ``0`` (``beta_j <= 0``) or ``inf``.
126 tol: Below this, the largest feasible correlation counts as zero.
128 Returns:
129 The breakpoints ``(lam, beta, active)`` from ``lam_max`` down to the
130 constrained least-squares fit at ``lam = 0``. With a singular Gram (more
131 features than observations) that fit is not unique, and the path ends at the
132 limit ``lam -> 0+``, the first breakpoint at which the fit interpolates.
134 Raises:
135 ValueError: If the CLA cannot trace the problem (e.g. a degenerate first
136 vertex, or a free block that is singular on the constraints' null space).
137 """
138 n = xty.shape[0]
139 if _max_correlation(xty, a, lower, upper) <= tol:
140 return [(0.0, np.zeros(n), np.zeros(n, dtype=bool))]
142 try:
143 cla = CLA(
144 mean=xty,
145 covariance=quad,
146 lower_bounds=np.where(lower < 0, -2.0, 0.0),
147 upper_bounds=np.where(upper > 0, 2.0, 0.0),
148 a=a,
149 b=np.zeros(a.shape[0]),
150 leverage=1.0,
151 )
152 except ValueError as err:
153 msg = f"the equality-constrained LASSO could not be traced through the leverage CLA: {err}"
154 # Keep the error's kind (infeasible, degenerate, ...) when the CLA classified it.
155 raise (type(err) if isinstance(err, CLAError) else ValueError)(msg) from err
157 tps = cla.turning_points
158 path: list[BreakpointData] = []
159 # Segment k runs from turning point k to k + 1; the last one ends at the CLA's
160 # lambda = 0 endpoint w = 0, which has no beta of its own and is not recorded.
161 for hi, lo in itertools.pairwise(tps):
162 if np.isinf(hi.lamb):
163 # The first segment holds the maximum-return vertex, so beta runs along
164 # the ray from 0 through it and carries the vertex's signs.
165 beta, signs = np.zeros(n), np.sign(hi.weights)
166 else:
167 # w is affine in lambda on the segment, so this is beta at its midpoint,
168 # where every free coordinate is strictly nonzero.
169 beta = hi.weights / hi.lamb
170 signs = np.sign((hi.weights + lo.weights) / (hi.lamb + lo.lamb))
171 penalty = _penalty(quad, xty, a, beta, hi.free, signs)
172 if path and penalty <= _INTERPOLATES * path[0][0]:
173 # The fit interpolates: this is the end of the LASSO path. With more features
174 # than observations the least-squares fit is not unique, and the CLA goes on
175 # through other interpolating fits of larger l1 norm, which are not on it.
176 path.append((0.0, beta, hi.free.copy()))
177 break
178 path.append((penalty, beta, hi.free.copy()))
179 return path