Skip to main content

solow_regression/
penalized.rs

1//! Penalised linear-regression estimators: [`Ridge`], [`Lasso`], and
2//! [`ElasticNet`].
3//!
4//! All three fit the linear model `y = X β + ε` under a convex penalty
5//! on the coefficient vector `β`:
6//!
7//! | Estimator | Objective |
8//! | --- | --- |
9//! | [`Ridge`] | `‖y − Xβ‖² / (2n) + α · ‖β‖²` |
10//! | [`Lasso`] | `‖y − Xβ‖² / (2n) + α · ‖β‖₁` |
11//! | [`ElasticNet`] | `‖y − Xβ‖² / (2n) + α · (ρ · ‖β‖₁ + ½(1 − ρ) · ‖β‖²)` |
12//!
13//! `Ridge` is solved in closed form via a Cholesky factor of
14//! `XᵀX + α · I`. `Lasso` and `ElasticNet` use the **coordinate
15//! descent** algorithm of Friedman-Hastie-Tibshirani (2010) — the
16//! algorithm the reference ships in `linear_model.Lasso` and
17//! `linear_model.ElasticNet` — which is provably convergent for convex
18//! objectives and empirically the fastest deterministic solver on
19//! dense inputs.
20//!
21//! # Intercept
22//!
23//! When `fit_intercept = true`, the estimator centres `y` and each
24//! column of `X` before fitting and computes the intercept from the
25//! sample means afterwards. The reported [`Ridge::intercept`],
26//! [`Lasso::intercept`], and [`ElasticNet::intercept`] correspond to
27//! the raw-feature model.
28//!
29//! # Standardisation
30//!
31//! Penalised models are scale-sensitive. The default is *not* to
32//! standardise; wrap the caller in a
33//! [`solow-preprocessing::StandardScaler`](https://docs.rs/solow-preprocessing/latest/solow_preprocessing/struct.StandardScaler.html)
34//! if that's what you want, and remember to unwind the scaling on the
35//! reported coefficients.
36//!
37//! # References
38//!
39//! * Hoerl, A. E., & Kennard, R. W. (1970). *Ridge regression: Biased
40//!   estimation for nonorthogonal problems.* Technometrics 12(1), 55-67.
41//! * Tibshirani, R. (1996). *Regression shrinkage and selection via
42//!   the lasso.* JRSS-B 58(1), 267-288.
43//! * Zou, H., & Hastie, T. (2005). *Regularization and variable
44//!   selection via the elastic net.* JRSS-B 67(2), 301-320.
45//! * Friedman, J., Hastie, T., & Tibshirani, R. (2010). *Regularization
46//!   paths for generalized linear models via coordinate descent.*
47//!   Journal of Statistical Software 33(1), 1-22.
48
49use ndarray::{Array1, ArrayView1, ArrayView2};
50use solow_core::{numeric::NeumaierSum, Error, Result};
51
52// ---------------------------------------------------------------------------
53// Ridge
54// ---------------------------------------------------------------------------
55
56/// L²-penalised linear regression.
57#[derive(Clone, Debug)]
58pub struct Ridge {
59    /// Fitted coefficients `β` (length `p`).
60    pub coef: Array1<f64>,
61    /// Fitted intercept.
62    pub intercept: f64,
63    /// Penalty strength used during fit.
64    pub alpha: f64,
65    /// Whether the fit included an intercept.
66    pub fit_intercept: bool,
67}
68
69impl Ridge {
70    /// Fit `Ridge(α, fit_intercept)` on `(y, x)`.
71    ///
72    /// Solves `(XᵀX + α · I) β = Xᵀy` by Cholesky (positive definite for
73    /// α > 0), then recovers the intercept from the sample means.
74    /// Complexity `O(n · p² + p³)`.
75    pub fn fit(
76        y: ArrayView1<'_, f64>,
77        x: ArrayView2<'_, f64>,
78        alpha: f64,
79        fit_intercept: bool,
80    ) -> Result<Self> {
81        if y.len() != x.nrows() || x.ncols() == 0 {
82            return Err(Error::Shape(format!(
83                "Ridge::fit: shape mismatch (y: {}, x: {}×{})",
84                y.len(),
85                x.nrows(),
86                x.ncols()
87            )));
88        }
89        if !(alpha >= 0.0 && alpha.is_finite()) {
90            return Err(Error::Value(format!(
91                "Ridge::fit: alpha must be finite and ≥ 0 (got {alpha})"
92            )));
93        }
94        let (n, p) = (x.nrows(), x.ncols());
95        // Optional centering.
96        let mut x_c = x.to_owned();
97        let mut y_c = y.to_owned();
98        let (mean_x, mean_y) = if fit_intercept {
99            let mut mx = Array1::<f64>::zeros(p);
100            for j in 0..p {
101                mx[j] = compensated_mean(x.column(j).iter().copied(), n);
102            }
103            let my = compensated_mean(y.iter().copied(), n);
104            for j in 0..p {
105                let mj = mx[j];
106                for i in 0..n {
107                    x_c[[i, j]] -= mj;
108                }
109            }
110            for i in 0..n {
111                y_c[i] -= my;
112            }
113            (mx, my)
114        } else {
115            (Array1::<f64>::zeros(p), 0.0)
116        };
117        // A = XᵀX + α·I  (p × p)
118        // b = Xᵀy         (p)
119        let mut a = vec![vec![0.0_f64; p]; p];
120        let mut b = vec![0.0_f64; p];
121        for i in 0..n {
122            for j in 0..p {
123                let xj = x_c[[i, j]];
124                b[j] += xj * y_c[i];
125                for k in j..p {
126                    a[j][k] += xj * x_c[[i, k]];
127                }
128            }
129        }
130        for j in 0..p {
131            for k in 0..j {
132                a[j][k] = a[k][j];
133            }
134            a[j][j] += alpha;
135        }
136        let beta_vec = cholesky_solve(&a, &b)?;
137        let coef = Array1::from(beta_vec);
138        let intercept = if fit_intercept {
139            let mut s = 0.0_f64;
140            for j in 0..p {
141                s += coef[j] * mean_x[j];
142            }
143            mean_y - s
144        } else {
145            0.0
146        };
147        Ok(Self {
148            coef,
149            intercept,
150            alpha,
151            fit_intercept,
152        })
153    }
154
155    /// Predict `X β + b` for every row of `x`.
156    pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
157        if x.ncols() != self.coef.len() {
158            return Err(Error::Shape(format!(
159                "Ridge::predict: expected {} columns, got {}",
160                self.coef.len(),
161                x.ncols()
162            )));
163        }
164        let mut out = Array1::<f64>::zeros(x.nrows());
165        for i in 0..x.nrows() {
166            let mut s = self.intercept;
167            for j in 0..x.ncols() {
168                s += self.coef[j] * x[[i, j]];
169            }
170            out[i] = s;
171        }
172        Ok(out)
173    }
174}
175
176// ---------------------------------------------------------------------------
177// Lasso — coordinate descent
178// ---------------------------------------------------------------------------
179
180/// L¹-penalised linear regression by coordinate descent.
181#[derive(Clone, Debug)]
182pub struct Lasso {
183    /// Fitted coefficients.
184    pub coef: Array1<f64>,
185    /// Fitted intercept.
186    pub intercept: f64,
187    /// Penalty strength.
188    pub alpha: f64,
189    /// Whether the fit included an intercept.
190    pub fit_intercept: bool,
191    /// Number of outer coordinate-descent sweeps that ran.
192    pub n_iter: usize,
193    /// Whether the final sweep's max coordinate change fell below `tol`.
194    pub converged: bool,
195}
196
197impl Lasso {
198    /// Fit with default settings (`max_iter = 1000`, `tol = 1e-4`).
199    pub fn fit(
200        y: ArrayView1<'_, f64>,
201        x: ArrayView2<'_, f64>,
202        alpha: f64,
203        fit_intercept: bool,
204    ) -> Result<Self> {
205        Self::fit_with(y, x, alpha, fit_intercept, 1000, 1e-4)
206    }
207
208    /// Full-configuration fit.
209    pub fn fit_with(
210        y: ArrayView1<'_, f64>,
211        x: ArrayView2<'_, f64>,
212        alpha: f64,
213        fit_intercept: bool,
214        max_iter: usize,
215        tol: f64,
216    ) -> Result<Self> {
217        // Reduce to ElasticNet with `l1_ratio = 1`.
218        let en = ElasticNet::fit_with(y, x, alpha, 1.0, fit_intercept, max_iter, tol)?;
219        Ok(Self {
220            coef: en.coef,
221            intercept: en.intercept,
222            alpha,
223            fit_intercept,
224            n_iter: en.n_iter,
225            converged: en.converged,
226        })
227    }
228
229    /// Predict on a new feature matrix.
230    pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
231        predict_linear(&self.coef, self.intercept, x, "Lasso")
232    }
233}
234
235// ---------------------------------------------------------------------------
236// ElasticNet — coordinate descent
237// ---------------------------------------------------------------------------
238
239/// Elastic-net penalised linear regression by coordinate descent.
240///
241/// `l1_ratio ∈ [0, 1]` mixes the two penalties:
242/// `α · (l1_ratio · ‖β‖₁ + ½ · (1 − l1_ratio) · ‖β‖²)`. `l1_ratio = 1`
243/// reduces to `Lasso`; `l1_ratio = 0` reduces to `Ridge` (though the
244/// dedicated `Ridge` implementation is faster for that case).
245#[derive(Clone, Debug)]
246pub struct ElasticNet {
247    /// Fitted coefficients.
248    pub coef: Array1<f64>,
249    /// Fitted intercept.
250    pub intercept: f64,
251    /// Penalty strength.
252    pub alpha: f64,
253    /// L¹ vs L² mixing.
254    pub l1_ratio: f64,
255    /// Whether the fit included an intercept.
256    pub fit_intercept: bool,
257    /// Number of outer coordinate-descent sweeps that ran.
258    pub n_iter: usize,
259    /// Whether the final sweep's max coordinate change fell below `tol`.
260    pub converged: bool,
261}
262
263impl ElasticNet {
264    /// Fit with default settings.
265    pub fn fit(
266        y: ArrayView1<'_, f64>,
267        x: ArrayView2<'_, f64>,
268        alpha: f64,
269        l1_ratio: f64,
270        fit_intercept: bool,
271    ) -> Result<Self> {
272        Self::fit_with(y, x, alpha, l1_ratio, fit_intercept, 1000, 1e-4)
273    }
274
275    /// Full-configuration fit.
276    ///
277    /// # Convergence
278    ///
279    /// Coordinate descent on the ElasticNet objective is provably
280    /// convergent for `alpha ≥ 0`, `l1_ratio ∈ [0, 1]`. Convergence
281    /// is monitored via the maximum absolute change in any coordinate
282    /// across a full sweep; the fit terminates when this falls below
283    /// `tol` or `max_iter` sweeps have run (whichever first).
284    pub fn fit_with(
285        y: ArrayView1<'_, f64>,
286        x: ArrayView2<'_, f64>,
287        alpha: f64,
288        l1_ratio: f64,
289        fit_intercept: bool,
290        max_iter: usize,
291        tol: f64,
292    ) -> Result<Self> {
293        if y.len() != x.nrows() || x.ncols() == 0 {
294            return Err(Error::Shape(format!(
295                "ElasticNet::fit_with: shape mismatch (y: {}, x: {}×{})",
296                y.len(),
297                x.nrows(),
298                x.ncols()
299            )));
300        }
301        if !(alpha >= 0.0 && alpha.is_finite()) {
302            return Err(Error::Value(format!(
303                "ElasticNet::fit_with: alpha must be finite and ≥ 0 (got {alpha})"
304            )));
305        }
306        if !(0.0..=1.0).contains(&l1_ratio) {
307            return Err(Error::Value(format!(
308                "ElasticNet::fit_with: l1_ratio must be in [0, 1] (got {l1_ratio})"
309            )));
310        }
311        let (n, p) = (x.nrows(), x.ncols());
312        let n_f = n as f64;
313
314        // Centre for the intercept fit.
315        let mut x_c = x.to_owned();
316        let mut y_c = y.to_owned();
317        let mean_x: Array1<f64>;
318        let mean_y: f64;
319        if fit_intercept {
320            let mut mx = Array1::<f64>::zeros(p);
321            for j in 0..p {
322                mx[j] = compensated_mean(x.column(j).iter().copied(), n);
323            }
324            mean_y = compensated_mean(y.iter().copied(), n);
325            for j in 0..p {
326                let mj = mx[j];
327                for i in 0..n {
328                    x_c[[i, j]] -= mj;
329                }
330            }
331            for i in 0..n {
332                y_c[i] -= mean_y;
333            }
334            mean_x = mx;
335        } else {
336            mean_x = Array1::<f64>::zeros(p);
337            mean_y = 0.0;
338        }
339
340        // Precompute the column norms `‖x_j‖² / n` — they are the
341        // coordinate-descent step's denominator.
342        let mut col_norms = vec![0.0_f64; p];
343        for j in 0..p {
344            let mut s = NeumaierSum::new();
345            for i in 0..n {
346                s.add(x_c[[i, j]] * x_c[[i, j]]);
347            }
348            col_norms[j] = s.finish() / n_f;
349        }
350
351        let l1 = alpha * l1_ratio;
352        let l2 = alpha * (1.0 - l1_ratio);
353        let mut beta = Array1::<f64>::zeros(p);
354        // Residual vector `r = y_c - X β` — maintained incrementally.
355        let mut r = y_c.clone();
356
357        let mut n_iter = 0usize;
358        let mut converged = false;
359        for it in 0..max_iter {
360            n_iter = it + 1;
361            let mut max_change = 0.0_f64;
362            for j in 0..p {
363                let denom = col_norms[j] + l2;
364                if denom <= 0.0 {
365                    continue;
366                }
367                // Add back β_j · x_j to the residual so the coordinate update sees the
368                // "partial residual" `r + β_j · x_j`.
369                let bj = beta[j];
370                if bj != 0.0 {
371                    for i in 0..n {
372                        r[i] += bj * x_c[[i, j]];
373                    }
374                }
375                // Compute z_j = (1/n) · x_jᵀ r.
376                let mut z = NeumaierSum::new();
377                for i in 0..n {
378                    z.add(x_c[[i, j]] * r[i]);
379                }
380                let z_j = z.finish() / n_f;
381                // Soft-threshold.
382                let new_bj = soft_threshold(z_j, l1) / denom;
383                // Update residual to reflect the new coefficient.
384                if new_bj != 0.0 {
385                    for i in 0..n {
386                        r[i] -= new_bj * x_c[[i, j]];
387                    }
388                }
389                let change = (new_bj - bj).abs();
390                if change > max_change {
391                    max_change = change;
392                }
393                beta[j] = new_bj;
394            }
395            if max_change < tol {
396                converged = true;
397                break;
398            }
399        }
400
401        let intercept = if fit_intercept {
402            let mut s = 0.0_f64;
403            for j in 0..p {
404                s += beta[j] * mean_x[j];
405            }
406            mean_y - s
407        } else {
408            0.0
409        };
410        Ok(Self {
411            coef: beta,
412            intercept,
413            alpha,
414            l1_ratio,
415            fit_intercept,
416            n_iter,
417            converged,
418        })
419    }
420
421    /// Predict.
422    pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
423        predict_linear(&self.coef, self.intercept, x, "ElasticNet")
424    }
425}
426
427// ---------------------------------------------------------------------------
428// Small helpers
429// ---------------------------------------------------------------------------
430
431fn soft_threshold(z: f64, lambda: f64) -> f64 {
432    if z > lambda {
433        z - lambda
434    } else if z < -lambda {
435        z + lambda
436    } else {
437        0.0
438    }
439}
440
441fn predict_linear(
442    coef: &Array1<f64>,
443    intercept: f64,
444    x: ArrayView2<'_, f64>,
445    label: &str,
446) -> Result<Array1<f64>> {
447    if x.ncols() != coef.len() {
448        return Err(Error::Shape(format!(
449            "{label}::predict: expected {} columns, got {}",
450            coef.len(),
451            x.ncols()
452        )));
453    }
454    let mut out = Array1::<f64>::zeros(x.nrows());
455    for i in 0..x.nrows() {
456        let mut s = intercept;
457        for j in 0..x.ncols() {
458            s += coef[j] * x[[i, j]];
459        }
460        out[i] = s;
461    }
462    Ok(out)
463}
464
465fn compensated_mean<I: IntoIterator<Item = f64>>(it: I, n: usize) -> f64 {
466    let mut acc = NeumaierSum::new();
467    for v in it {
468        acc.add(v);
469    }
470    acc.finish() / n as f64
471}
472
473/// Symmetric-positive-definite Cholesky solve.
474fn cholesky_solve(a: &[Vec<f64>], b: &[f64]) -> Result<Vec<f64>> {
475    let n = a.len();
476    // Copy and factor.
477    let mut l = vec![vec![0.0_f64; n]; n];
478    for i in 0..n {
479        for j in 0..=i {
480            let mut s = a[i][j];
481            for k in 0..j {
482                s -= l[i][k] * l[j][k];
483            }
484            if i == j {
485                if s <= 0.0 {
486                    return Err(Error::Value(
487                        "Ridge: Cholesky failed — matrix is not positive definite".into(),
488                    ));
489                }
490                l[i][j] = s.sqrt();
491            } else {
492                l[i][j] = s / l[j][j];
493            }
494        }
495    }
496    // Forward: L z = b.
497    let mut z = vec![0.0_f64; n];
498    for i in 0..n {
499        let mut s = b[i];
500        for k in 0..i {
501            s -= l[i][k] * z[k];
502        }
503        z[i] = s / l[i][i];
504    }
505    // Backward: Lᵀ x = z.
506    let mut x = vec![0.0_f64; n];
507    for i in (0..n).rev() {
508        let mut s = z[i];
509        for k in (i + 1)..n {
510            s -= l[k][i] * x[k];
511        }
512        x[i] = s / l[i][i];
513    }
514    Ok(x)
515}
516
517#[cfg(test)]
518mod tests {
519    use super::*;
520    use approx::assert_abs_diff_eq;
521    use ndarray::array;
522
523    #[test]
524    fn ridge_reduces_to_ols_at_alpha_zero() {
525        // y = 2 + 3x with no noise.
526        let x = array![[1.0], [2.0], [3.0], [4.0], [5.0]];
527        let y = array![5.0, 8.0, 11.0, 14.0, 17.0];
528        let r = Ridge::fit(y.view(), x.view(), 0.0, true).unwrap();
529        assert_abs_diff_eq!(r.intercept, 2.0, epsilon = 1e-9);
530        assert_abs_diff_eq!(r.coef[0], 3.0, epsilon = 1e-9);
531    }
532
533    #[test]
534    fn ridge_shrinks_coefficients_as_alpha_grows() {
535        let x = array![[1.0], [2.0], [3.0], [4.0], [5.0]];
536        let y = array![5.0, 8.0, 11.0, 14.0, 17.0];
537        let a = Ridge::fit(y.view(), x.view(), 0.0, true).unwrap().coef[0];
538        let b = Ridge::fit(y.view(), x.view(), 100.0, true).unwrap().coef[0];
539        assert!(
540            b.abs() < a.abs(),
541            "|β(α=100)| = {b} should shrink below |β(0)| = {a}"
542        );
543    }
544
545    #[test]
546    fn lasso_at_large_alpha_zeroes_all_coefficients() {
547        let x = array![[1.0, 0.5], [2.0, -0.3], [3.0, 1.2], [4.0, -0.8]];
548        let y = array![2.0, 4.0, 6.0, 8.0];
549        // A very strong penalty forces every β_j = 0.
550        let l = Lasso::fit(y.view(), x.view(), 1e6, true).unwrap();
551        for &b in l.coef.iter() {
552            assert_abs_diff_eq!(b, 0.0, epsilon = 1e-9);
553        }
554        // Intercept absorbs the mean of y = 5.
555        assert_abs_diff_eq!(l.intercept, 5.0, epsilon = 1e-9);
556    }
557
558    #[test]
559    fn lasso_recovers_linear_signal_at_small_alpha() {
560        // y = 3 · x1 + 0 · x2 + 1 (intercept). Small α should keep β_1
561        // close to 3 and shrink β_2 close to 0.
562        let x = array![[1.0, 5.0], [2.0, -3.0], [3.0, 4.0], [4.0, 0.0], [5.0, 2.0]];
563        let y = array![4.0, 7.0, 10.0, 13.0, 16.0];
564        let l = Lasso::fit_with(y.view(), x.view(), 0.01, true, 5000, 1e-6).unwrap();
565        assert!((l.coef[0] - 3.0).abs() < 0.1, "coef[0] = {}", l.coef[0]);
566        assert!(l.coef[1].abs() < 0.1, "coef[1] = {}", l.coef[1]);
567    }
568
569    #[test]
570    fn elastic_net_interpolates_between_ridge_and_lasso() {
571        let x = array![[1.0, 5.0], [2.0, -3.0], [3.0, 4.0], [4.0, 0.0], [5.0, 2.0]];
572        let y = array![4.0, 7.0, 10.0, 13.0, 16.0];
573        let en_lasso_like = ElasticNet::fit(y.view(), x.view(), 0.5, 1.0, true).unwrap();
574        let en_ridge_like = ElasticNet::fit(y.view(), x.view(), 0.5, 0.0, true).unwrap();
575        // Lasso-like should shrink coef[1] closer to zero than the ridge-like fit.
576        assert!(
577            en_lasso_like.coef[1].abs() <= en_ridge_like.coef[1].abs() + 1e-9,
578            "expected the l1-like fit to shrink coef[1] at least as much as the l2-like fit"
579        );
580    }
581}