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

1"""LASSO / LARS regularisation path as a parametric active-set problem. 

2 

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. 

8 

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). 

18 

19The LASSO solves, for a response ``y`` and design matrix ``X``, 

20 

21 minimize 1/2 ||y - X beta||^2 + lam ||beta||_1 

22 

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, 

26 

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 

29 

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``. 

34 

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`). 

48 

49Event families, mirroring the CLA's "move to / leave a bound": 

50 

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""" 

56 

57from __future__ import annotations 

58 

59from bisect import bisect_right 

60from dataclasses import dataclass, field 

61from functools import cached_property 

62from typing import cast 

63 

64import numpy as np 

65from numpy.typing import NDArray 

66 

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 

80 

81 

82@dataclass(frozen=True) 

83class Breakpoint: 

84 """A vertex of the piecewise-linear LASSO path. 

85 

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 """ 

92 

93 lam: float 

94 beta: NDArray[np.float64] 

95 active: NDArray[np.bool_] 

96 

97 

98@dataclass 

99class Lasso(InequalityConstrained): 

100 """The LASSO regularisation path, traced as a parametric active-set problem. 

101 

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. 

107 

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. 

121 

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. 

128 

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 """ 

161 

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 

176 

177 def __post_init__(self) -> None: 

178 """Validate shapes and trace the full LASSO path. 

179 

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) 

197 

198 @property 

199 def via_cla(self) -> bool: 

200 """Whether the path is traced by a CLA rather than the homotopy. 

201 

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)) 

209 

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. 

212 

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) 

224 

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. 

228 

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. 

232 

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. 

235 

236 Args: 

237 x: Design matrix of shape ``(m, n)``. 

238 y: Response vector of shape ``(m,)``. 

239 

240 Returns: 

241 A :class:`cvxcla._builders.LassoBuilder` whose ``.trace()`` returns a 

242 traced ``Lasso``. 

243 """ 

244 return LassoBuilder(x, y, solver=cls) 

245 

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. 

259 

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. 

271 

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. 

281 

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 ) 

294 

295 @cached_property 

296 def quad(self) -> QuadraticForm: 

297 """The Gram matrix ``X^T X`` as a ``QuadraticForm`` backend (cached: ``X`` is fixed). 

298 

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) 

315 

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 

325 

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]) 

332 

333 @property 

334 def lam_max(self) -> float: 

335 """The smallest penalty at which ``beta = 0`` is optimal: ``||X^T y||_inf``. 

336 

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))) 

346 

347 def begin(self) -> tuple[float, LassoState]: 

348 """Record the all-zero solution at the start penalty and enter the first coordinate. 

349 

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])) 

369 

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)) 

377 

378 def segment(self, state: LassoState) -> LassoSegment: 

379 """Solve the affine segment for the current support, signs, and active rows. 

380 

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) 

385 

386 def event_matrix(self, state: LassoState, segment: LassoSegment) -> NDArray[np.float64]: 

387 """Return the ``(n + p, 4)`` matrix of candidate critical lambdas. 

388 

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) 

393 

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``. 

396 

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 

415 

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) 

419 

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())) 

423 

424 def solution(self, lam: float) -> NDArray[np.float64]: 

425 """Evaluate the piecewise-linear path at penalty ``lam``. 

426 

427 Args: 

428 lam: The penalty value at which to evaluate ``beta``. 

429 

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