Coverage for src/cvxcla/lasso.py: 100%
137 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"""LASSO / LARS regularisation path as a parametric active-set problem.
3This module shows that the Critical Line Algorithm's machinery is not specific to
4portfolios: the *same* ``cvxcla.pathtracer.trace`` loop, the *same*
5``QuadraticForm`` operator, and the *same* Bland event selection trace the LASSO
6homotopy. Only the problem-specific glue (the segment solve and what an event
7means) differs.
9The two are closer than analogues. Under ``Sigma = X^T X`` and ``mu = X^T y`` the
10constrained LASSO path ``beta(lam)`` solves the gross-exposure-capped Markowitz
11program ``min 1/2 w^T Sigma w - mu^T w`` s.t. ``||w||_1 <= c`` at
12``c = ||beta(lam)||_1``, under the same linear constraints, and the two paths share
13their breakpoints wherever ``c`` is strictly decreasing (Schmelzer and Hastie,
14"The Critical Line Algorithm and the Constrained LASSO: One Curve, Two
15Literatures", arXiv:2609.25704, Theorem 1). With homogeneous constraints, the
16tilt sweep of ``CLA(leverage=c)`` is that path rescaled,
17``w_c(lam) = lam * beta`` with ``||beta||_1 = c / lam`` (Corollary 2).
19The LASSO solves, for a response ``y`` and design matrix ``X``,
21 minimize 1/2 ||y - X beta||^2 + lam ||beta||_1
23and its minimiser ``beta(lam)`` is continuous and piecewise linear in the penalty
24``lam``. On a segment where the active set ``A`` (the support) and the signs
25``s_A`` are fixed,
27 beta_A(lam) = (X_A^T X_A)^{-1} (X_A^T y - lam s_A) = alpha_A - lam * beta_slope_A
28 correlation(lam) = X^T (y - X beta(lam)) = p + lam * q
30with ``|correlation_j| <= lam`` off the support and ``correlation_j = lam s_j`` on
31it. The role played by the covariance ``Sigma`` and mean ``mu`` in the CLA is
32played here by the Gram matrix ``H = X^T X`` (wrapped in ``DenseCovariance``) and
33the vector ``X^T y``.
35**Constraints.** Like the CLA, the path tracer admits general linear inequality
36constraints ``G beta <= h``. An active row enters the reduced KKT system exactly as
37in the CLA (the bordered Schur complement of ``cla.py``), and the generalised
38correlation that drives the enter/leave events carries the active-row multipliers,
39``correlation(lam) = X^T y - H beta(lam) - G_S^T eta(lam)``. The constrained path is
40still piecewise linear (a quadratic loss under a polyhedral penalty *and* polyhedral
41constraints; cf. Rosset and Zhu). The homotopy needs ``h > 0`` so the path can start
42from ``beta = 0`` with every row slack -- the same first vertex as the unconstrained
43LASSO; a row with ``h = 0``, such as the ordering of a monotone fit, or with ``h < 0``,
44which excludes ``beta = 0``, goes through the penalty form instead (see
45:mod:`cvxcla._lasso_bounded`). Homogeneous equality
46constraints ``A beta = 0`` are traced by a different route: one leverage-capped CLA,
47rescaled (see :mod:`cvxcla._lasso_cla`).
49Event families, mirroring the CLA's "move to / leave a bound":
51* **leave** -- an active coefficient reaches zero: ``lam = alpha_j / beta_slope_j``.
52* **enter** -- an inactive (generalised) correlation reaches ``+/-lam``.
53* **activate** -- a slack inequality row's residual ``G_r beta - h_r`` reaches zero.
54* **release** -- an active row's multiplier ``eta_r`` reaches zero.
55"""
57from __future__ import annotations
59from bisect import bisect_right
60from dataclasses import dataclass, field
61from functools import cached_property
62from typing import cast
64import numpy as np
65from numpy.typing import NDArray
67from ._builders import LassoBuilder
68from ._lasso import LassoSegment, LassoState, scan_events, solve_segment
69from ._lasso_bounded import bounded_path
70from ._lasso_cla import equality_path
71from ._lasso_validate import (
72 validate_bounds,
73 validate_constraints,
74 validate_design_inputs,
75 validate_equality,
76 validate_operator_inputs,
77)
78from .operators import DenseCovariance, GramCovariance, QuadraticForm
79from .pathtracer import InequalityConstrained, trace
82@dataclass(frozen=True)
83class Breakpoint:
84 """A vertex of the piecewise-linear LASSO path.
86 Attributes:
87 lam: The penalty value at this breakpoint.
88 beta: The coefficient vector ``beta(lam)``.
89 active: Boolean mask of the support (non-zero coefficients) on the
90 segment leaving this breakpoint towards smaller ``lam``.
91 """
93 lam: float
94 beta: NDArray[np.float64]
95 active: NDArray[np.bool_]
98@dataclass
99class Lasso(InequalityConstrained):
100 """The LASSO regularisation path, traced as a parametric active-set problem.
102 Constructing a ``Lasso`` traces the entire path from ``lam_max`` (where
103 ``beta = 0``) down to ``lam = 0`` (the least-squares fit on the final support,
104 subject to any active constraints), storing the breakpoints in ``path``. The
105 walk is driven by the same ``cvxcla.pathtracer.trace`` loop as the Critical Line
106 Algorithm.
108 Optional linear inequality constraints ``G beta <= h`` (with ``h > 0``) are
109 traced through the same bordered solve as the CLA's ``G w <= h`` rows; rows with
110 ``h = 0`` (homogeneous, e.g. a monotone fit) or ``h < 0`` (excluding ``beta = 0``)
111 through the penalty form.
112 Homogeneous equality constraints ``A beta = 0`` (sum-to-zero, contrasts), with
113 or without signs on any of the coefficients, are traced instead through one
114 leverage-capped CLA under ``Sigma = X^T X`` and ``mu = X^T y``, which traces the
115 same curve (Schmelzer and Hastie, arXiv:2609.25704, Theorem 1 and Corollary 2);
116 see :mod:`cvxcla._lasso_cla`. Per-coefficient bounds ``lower <= beta <= upper``
117 (caps, and signs on some of the coefficients) and equality rows with a nonzero
118 right-hand side ``A beta = b`` are traced through the CLA in the penalty form,
119 whose tilt is the penalty itself, together with any rows ``G beta <= h``; see
120 :mod:`cvxcla._lasso_bounded`. Each route takes combinations of its constraints.
122 The quadratic form may be given either as a dense design ``(x, y)`` (the usual
123 case, ``H = X^T X``) or, via :meth:`from_operator`, as a ``QuadraticForm``
124 operator with the linear term ``X^T y``. The operator route lets a structured
125 form, a diagonal-plus-low-rank factor model or a kernel, drive the path in
126 ``O(nk)`` per step without forming the ``n x n`` Gram matrix, exactly as on the
127 portfolio side.
129 Attributes:
130 x: Design matrix of shape ``(m, n)`` (``None`` in operator mode).
131 y: Response vector of shape ``(m,)`` (``None`` in operator mode).
132 g: Optional inequality matrix ``(p, n)`` of ``G beta <= h``; ``None`` means
133 the plain LASSO.
134 h: Optional inequality right-hand side ``(p,)``. A zero entry is a homogeneous
135 row, such as the ordering of a monotone fit, and a negative one a row that
136 excludes ``beta = 0``, such as a floor ``-beta_j <= -l_j``; both are traced
137 through the penalty form (see :mod:`cvxcla._lasso_bounded`).
138 nonneg: When ``True``, restrict to the non-negative LASSO ``beta >= 0``;
139 the default ``False`` traces the ordinary signed path.
140 gram: When ``True``, drive the path with the ``GramCovariance`` data-matrix
141 backend (Woodbury solves in the ``m``-dimensional observation space),
142 never materialising the ``n x n`` Gram ``X^T X`` — the win in the
143 ``n >> m`` regime. The default ``False`` forms the dense Gram.
144 tol: Tolerance for event selection and the validity window.
145 path: The discovered breakpoints, populated on construction.
146 quad_form: Optional ``QuadraticForm`` operator ``H`` (operator mode).
147 linear: Optional linear term ``X^T y`` of shape ``(n,)`` (operator mode).
148 a: Optional equality matrix ``(m, n)`` of ``A beta = b``. With ``b = 0`` and
149 bounds that are only signs (``0`` or infinite) it is traced by the leverage
150 CLA; with more features than observations that path ends where the fit first
151 interpolates. With a finite bound or ``g``/``h`` it is relaxed and
152 extrapolated (see :mod:`cvxcla._lasso_bounded`).
153 b: Optional right-hand side ``(m,)`` of ``A beta = b``; ``None`` means
154 ``b = 0``. A nonzero ``b`` needs a unique smallest-``l1`` point on
155 ``A beta = b`` (true for generic ``A`` and ``b``) to start from.
156 lower: Optional per-coefficient lower bounds ``(n,)``, each ``<= 0``
157 (``-inf`` for none, ``0`` for ``beta_j >= 0``).
158 upper: Optional per-coefficient upper bounds ``(n,)``, each ``>= 0``
159 (``inf`` for none, ``0`` for ``beta_j <= 0``).
160 """
162 x: NDArray[np.float64] | None = None
163 y: NDArray[np.float64] | None = None
164 g: NDArray[np.float64] | None = None
165 h: NDArray[np.float64] | None = None
166 nonneg: bool = False # pragma: no mutate
167 gram: bool = False # pragma: no mutate
168 tol: float = 1e-9 # pragma: no mutate
169 path: list[Breakpoint] = field(default_factory=list)
170 quad_form: QuadraticForm | None = None # pragma: no mutate
171 linear: NDArray[np.float64] | None = None # pragma: no mutate
172 a: NDArray[np.float64] | None = None # pragma: no mutate
173 b: NDArray[np.float64] | None = None # pragma: no mutate
174 lower: NDArray[np.float64] | None = None # pragma: no mutate
175 upper: NDArray[np.float64] | None = None # pragma: no mutate
177 def __post_init__(self) -> None:
178 """Validate shapes and trace the full LASSO path.
180 Raises:
181 ValueError: If ``x`` is not 2d, ``y``'s length does not match ``x``, the
182 constraint shapes are inconsistent, an ``h`` entry is in ``(0, tol]``,
183 a bound excludes ``beta_j = 0`` (pass it as a row of ``G beta <= h``
184 instead), or the CLA cannot trace the problem.
185 """
186 if self.quad_form is not None or self.linear is not None:
187 self.linear = validate_operator_inputs(self.quad_form, self.linear, self.x, self.y)
188 else:
189 validate_design_inputs(self.x, self.y)
190 validate_constraints(self.g, self.h, self.dimension, self.tol)
191 if self.a is not None:
192 self.a = validate_equality(self.a, self.dimension)
193 if self.via_cla:
194 self.path.extend(Breakpoint(lam, beta, active) for lam, beta, active in self._cla_path())
195 return
196 trace(self)
198 @property
199 def via_cla(self) -> bool:
200 """Whether the path is traced by a CLA rather than the homotopy.
202 The homotopy starts from ``beta = 0`` with every constraint slack, so equality
203 rows, their right-hand side, per-coefficient bounds, homogeneous rows
204 ``g_r beta <= 0`` and rows that exclude ``beta = 0`` (``h_r < 0``) go through a
205 CLA instead.
206 """
207 rows_not_slack = self.h is not None and bool(np.any(np.asarray(self.h) <= 0))
208 return rows_not_slack or any(v is not None for v in (self.a, self.b, self.lower, self.upper))
210 def _cla_path(self) -> list[tuple[float, NDArray[np.float64], NDArray[np.bool_]]]:
211 """Route a problem with equality rows or bounds to the CLA that takes it.
213 Homogeneous rows with signs only go to the leverage CLA, everything else,
214 inequality rows ``G beta <= h`` included, to the penalty form, which relaxes a
215 homogeneous ``A beta = 0`` there (the leverage CLA cannot rescale a finite
216 bound or a row).
217 """
218 lower, upper, b = validate_bounds(self.lower, self.upper, self.b, self.a, self.nonneg, self.dimension)
219 a = np.zeros((0, self.dimension)) if self.a is None else self.a
220 signs_only = bool(np.isin(lower, [0.0, -np.inf]).all() and np.isin(upper, [0.0, np.inf]).all())
221 if a.shape[0] and not b.any() and signs_only and self.g is None:
222 return equality_path(self.quad, self.xty, a, lower, upper, self.tol)
223 return bounded_path(self.quad, self.xty, a, b, lower, upper, self.tol, self.g, self.h)
225 @classmethod
226 def problem(cls, x: NDArray[np.float64], y: NDArray[np.float64]) -> LassoBuilder[Lasso]:
227 """Start a fluent :class:`cvxcla._builders.LassoBuilder` for a LASSO path.
229 The LASSO counterpart of :meth:`cvxcla.cla.CLA.problem`: chain
230 ``.inequality(G, h)`` or ``.equality(A)`` and finish with ``.trace()``. The builder maps onto the
231 constructor arguments and adds no modelling power.
233 ``cls`` is handed to the builder as the class it should construct, which is
234 what lets the builder live in a leaf module that never imports this one.
236 Args:
237 x: Design matrix of shape ``(m, n)``.
238 y: Response vector of shape ``(m,)``.
240 Returns:
241 A :class:`cvxcla._builders.LassoBuilder` whose ``.trace()`` returns a
242 traced ``Lasso``.
243 """
244 return LassoBuilder(x, y, solver=cls)
246 @classmethod
247 def from_operator(
248 cls,
249 quad: QuadraticForm,
250 xty: NDArray[np.float64],
251 *,
252 g: NDArray[np.float64] | None = None,
253 h: NDArray[np.float64] | None = None,
254 a: NDArray[np.float64] | None = None,
255 nonneg: bool = False,
256 tol: float = 1e-9,
257 ) -> Lasso:
258 """Trace a LASSO path with the quadratic form supplied as an operator.
260 The regression counterpart of :class:`cvxcla.cla.CLA` accepting a
261 ``QuadraticForm`` covariance. Instead of a dense design ``X``, pass the Gram
262 operator ``H`` (anything implementing :class:`QuadraticForm`, for example a
263 :class:`cvxcla.operators.FactorCovariance` or a kernel) together with the
264 linear term ``X^T y``. The homotopy reaches ``H`` only through ``matvec`` and
265 ``solve_free``, so a diagonal-plus-low-rank factor model or a kernel traces
266 the path in ``O(nk)`` per step without ever forming the ``n x n`` matrix,
267 exactly as on the portfolio side. For the path to coincide with the
268 design-matrix LASSO one needs ``H = X^T X`` and ``xty = X^T y``
269 (Theorem 1); any positive-semidefinite operator whose free blocks are
270 positive definite traces a well-defined path.
272 Args:
273 quad: The quadratic form ``H`` as a :class:`QuadraticForm` operator.
274 xty: The linear term ``X^T y`` of shape ``(n,)``.
275 g: Optional inequality matrix of ``G beta <= h``.
276 h: Optional inequality right-hand side; a zero entry is a homogeneous row,
277 a negative one excludes ``beta = 0``.
278 a: Optional equality matrix of ``A beta = 0`` (not combined with ``g``).
279 nonneg: Restrict the path to ``beta >= 0``.
280 tol: Tolerance for event selection and the validity window.
282 Returns:
283 A traced :class:`Lasso` whose ``path`` holds the breakpoints.
284 """
285 return cls(
286 quad_form=quad,
287 linear=np.asarray(xty, dtype=np.float64),
288 g=g,
289 h=h,
290 a=a,
291 nonneg=nonneg,
292 tol=tol,
293 )
295 @cached_property
296 def quad(self) -> QuadraticForm:
297 """The Gram matrix ``X^T X`` as a ``QuadraticForm`` backend (cached: ``X`` is fixed).
299 With ``gram=True`` the data-matrix backend is used instead of forming the
300 ``n x n`` Gram: it solves through the Woodbury identity in the
301 ``m``-dimensional observation space and never materialises an ``n x n``
302 matrix, the win in the high-dimensional ``p >> n`` regime (more features than
303 observations). ``GramCovariance`` represents ``X_c^T X_c / (m-1)``, so scaling
304 the data by ``sqrt(m-1)`` recovers ``X^T X`` exactly for a **centred** design
305 (the standard LASSO convention; pass a column-centred ``x``).
306 """
307 if self.quad_form is not None:
308 return self.quad_form
309 # Not operator mode, so __post_init__ guarantees a design matrix.
310 x = cast("NDArray[np.float64]", self.x)
311 if self.gram:
312 m = x.shape[0]
313 return GramCovariance(x * np.sqrt(m - 1.0))
314 return DenseCovariance(x.T @ x)
316 @cached_property
317 def xty(self) -> NDArray[np.float64]:
318 """The linear data ``X^T y`` (the analogue of the CLA's expected returns; cached)."""
319 if self.linear is not None:
320 return self.linear
321 # Not operator mode, so __post_init__ guarantees a design (x, y).
322 x = cast("NDArray[np.float64]", self.x)
323 y = cast("NDArray[np.float64]", self.y)
324 return x.T @ y
326 @property
327 def dimension(self) -> int:
328 """Number of features ``n`` (the problem dimension for the path tracer)."""
329 if self.x is not None:
330 return int(self.x.shape[1])
331 return int(self.xty.shape[0])
333 @property
334 def lam_max(self) -> float:
335 """The smallest penalty at which ``beta = 0`` is optimal: ``||X^T y||_inf``.
337 With ``h > 0`` every inequality row is slack at ``beta = 0`` (zero
338 multiplier), so the unconstrained threshold is unchanged. Equality rows
339 ``A beta = 0``, homogeneous inequality rows and bounds do change it: the
340 correlation that can enter is the part of ``X^T y`` outside the row space of
341 ``A``, so the threshold is read off the traced path instead.
342 """
343 if self.via_cla:
344 return self.path[0].lam
345 return float(np.max(np.abs(self.xty)))
347 def begin(self) -> tuple[float, LassoState]:
348 """Record the all-zero solution at the start penalty and enter the first coordinate.
350 For the plain or inequality-constrained LASSO the start is
351 ``lam_max = ||X^T y||_inf`` and the most-correlated coordinate enters with its
352 sign. Under the non-negative restriction ``beta >= 0`` the l1 penalty becomes
353 the linear term ``lam * 1^T beta``, only positive correlations can enter, so
354 the start is ``lam_max = max_j (X^T y)_j`` and the coordinate enters with sign
355 ``+``. When no coordinate can enter (e.g. every correlation is non-positive
356 under ``beta >= 0``), ``beta = 0`` is optimal for all ``lambda`` and the path
357 is the single point.
358 """
359 n = self.dimension
360 xty = self.xty
361 rows_active = np.zeros(self.g_matrix.shape[0], dtype=bool)
362 if self.nonneg:
363 lam_max = float(np.max(xty)) if n else 0.0
364 j0, s0 = int(np.argmax(xty)), 1.0
365 else:
366 lam_max = self.lam_max
367 j0 = int(np.argmax(np.abs(xty)))
368 s0 = float(np.sign(xty[j0]))
370 self.path.append(Breakpoint(max(lam_max, 0.0), np.zeros(n), np.zeros(n, dtype=bool)))
371 active = np.zeros(n, dtype=bool)
372 signs = np.zeros(n)
373 if lam_max > self.tol:
374 active[j0] = True
375 signs[j0] = s0
376 return max(lam_max, 0.0), LassoState(active, signs, rows_active, max(lam_max, 0.0))
378 def segment(self, state: LassoState) -> LassoSegment:
379 """Solve the affine segment for the current support, signs, and active rows.
381 Delegates to :func:`cvxcla._lasso.solve_segment`; see there for the
382 bordered Schur solve that admits active inequality rows.
383 """
384 return solve_segment(self.quad, self.xty, self.g_matrix, self.h_vector, state)
386 def event_matrix(self, state: LassoState, segment: LassoSegment) -> NDArray[np.float64]:
387 """Return the ``(n + p, 4)`` matrix of candidate critical lambdas.
389 Delegates to :func:`cvxcla._lasso.scan_events`; see there for the
390 coordinate (leave/enter) and inequality-row (activate/release) events.
391 """
392 return scan_events(self.dimension, self.g_matrix, self.h_vector, self.tol, self.nonneg, state, segment)
394 def step(self, state: LassoState, segment: LassoSegment, sec: int, direction: int, lam: float) -> LassoState:
395 """Record the breakpoint at ``lam`` after flipping coordinate or row ``sec``.
397 For a coordinate (``sec < n``): direction 0 removes it from the support, 1/2
398 add it with sign ``+1``/``-1``. For an inequality row (``sec >= n``):
399 direction 0 activates the row, 1 releases it. The path is continuous across
400 the flip, so the recorded coefficients are the old segment at ``lam``.
401 """
402 n = self.dimension
403 active = state.active.copy()
404 signs = state.signs.copy()
405 rows_active = state.rows_active.copy()
406 if sec < n:
407 if direction == 0:
408 active[sec] = False
409 signs[sec] = 0.0
410 else:
411 active[sec] = True
412 signs[sec] = 1.0 if direction == 1 else -1.0
413 else:
414 rows_active[sec - n] = direction == 0
416 beta = segment.alpha - lam * segment.beta_slope
417 self.path.append(Breakpoint(lam, beta, active.copy()))
418 return LassoState(active, signs, rows_active, lam)
420 def finish(self, state: LassoState, segment: LassoSegment) -> None:
421 """Record the ``lam = 0`` endpoint: the least-squares fit on the final support."""
422 self.path.append(Breakpoint(0.0, segment.alpha.copy(), state.active.copy()))
424 def solution(self, lam: float) -> NDArray[np.float64]:
425 """Evaluate the piecewise-linear path at penalty ``lam``.
427 Args:
428 lam: The penalty value at which to evaluate ``beta``.
430 Returns:
431 The coefficient vector ``beta(lam)``, by linear interpolation between
432 the bracketing breakpoints (clamped to the path's endpoints).
433 """
434 ordered = sorted(self.path, key=lambda bp: bp.lam)
435 if lam <= ordered[0].lam:
436 return ordered[0].beta
437 if lam >= ordered[-1].lam:
438 return ordered[-1].beta
439 # Strictly inside the range, so lo.lam <= lam < hi.lam and hi.lam > lo.lam.
440 idx = bisect_right([bp.lam for bp in ordered], lam)
441 lo, hi = ordered[idx - 1], ordered[idx]
442 weight = (lam - lo.lam) / (hi.lam - lo.lam)
443 return (1.0 - weight) * lo.beta + weight * hi.beta