Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Regularization paths

The regreg.paths subpackage computes solutions of penalized problems of the form

β^(λ)=argminβ  ℓ(Xβ)+λα P(β)+λ(1−α)2∑jcjβj2\hat\beta(\lambda) = \text{argmin}_{\beta} \; \ell(X\beta) + \lambda \alpha \, P(\beta) + \frac{\lambda(1-\alpha)}{2} \sum_j c_j \beta_j^2

over a decreasing sequence λ1>λ2>⋯>λK\lambda_1 > \lambda_2 > \dots > \lambda_K. Here ℓ\ell is a loss of the linear predictor (Gaussian, logistic, probit, cloglog, Poisson, Cox, Huber, ...), PP is a (weighted) ℓ1\ell_1, group lasso or sparse group lasso penalty, α∈(0,1]\alpha \in (0,1] is the elastic net mixing parameter and cjc_j are the ridge weights (elastic_net_param). With α=1\alpha=1 (the default) this is the lasso, group lasso, etc.

A path computation has three ingredients:

  1. a path object, which describes the loss, design and penalty. These live in regreg.paths.lasso, group_lasso, sparse_group_lasso, sparse_group_block and mixed_lasso, and are built by module-level constructors such as lasso.gaussian(X, Y, weights) or group_lasso.logistic(X, Y, groups, weights=...);

  2. a sequence of Lagrange parameters, usually from default_lagrange_sequence;

  3. a driver: strong_rules or warm_start (in regreg.paths) or basil (in regreg.paths.basil).

Note the import locations: regreg.paths.basil and regreg.paths.cross_validate are submodules, so the functions must be imported from them.

A lasso path

We simulate a sparse linear model with five nonzero coefficients.

The path object stores the solution at λ=∞\lambda = \infty (the “null” solution, here β=0\beta=0) as path.solution, and the gradient of the loss there as path.grad_solution. The smallest λ\lambda for which the null solution is optimal, λmax⁡\lambda_{\max}, is the dual norm of this gradient; for the lasso with squared error loss 12∥Y−Xβ∥22\frac{1}{2}\|Y-X\beta\|_2^2 it is ∥XTY∥∞\|X^TY\|_\infty. default_lagrange_sequence returns nstep log-spaced values from λmax⁡\lambda_{\max} down to lagrange_proportion ×λmax⁡\times \lambda_{\max}.

(array([631.084251 , 538.42079512, 459.36331347]), np.float64(0.010000000000000004))

Every driver takes the path object, the sequence and the initial (solution, gradient) pair at lagrange[0]. strong_rules returns a dictionary; its 'beta' entry has one row per value of λ\lambda.

(30, 30)
<Figure size 700x450 with 1 Axes>

Three drivers, one path

All three should give the same path. We also compare with a direct solve of each problem using rr.simple_problem.

strong_rules  max |beta - direct| = 2.50e-09
warm_start    max |beta - direct| = 4.80e-05
basil         max |beta - direct| = 4.09e-05
max |strong_rules - warm_start| = 4.80e-05
max |basil - warm_start|        = 4.83e-05

Before a step is accepted, the drivers check the KKT conditions on all variables. An inactive variable fails the check when ∣∇jℓ(Xβ^)∣>(1+ϵ) λ|\nabla_j \ell(X\hat\beta)| > (1 + \epsilon)\,\lambda, and then joins the working set. The tolerance ϵ\epsilon is kkt_tol, with default 1e-6. It is an attribute of the path object (path.kkt_tol), and the drivers also take it as an argument. A looser value saves little time and can leave a variable that is just about to enter at zero for a step. Earlier versions used 1%, which gave errors of order 10-3 near entry points (gh-99). The KKT checks of the active variables (check_active=True) use their own, looser, tolerance, as they depend on how accurately each subproblem is solved.

strong_rules agrees with the direct solves to the solver tolerance at every λ\lambda. The 10-5-level errors of warm_start and basil come from the stopping rule of their solves, which is not as strict as inner_tol suggests.

[0.0e+00 2.7e-10 2.2e-10 1.1e-10 1.0e-10 2.8e-10 4.9e-11 1.2e-10 3.6e-10
 2.1e-10 3.6e-10 7.6e-10 6.4e-10 4.1e-11 5.5e-10 5.3e-10 1.3e-09 1.5e-10
 3.0e-10 5.1e-10 2.8e-11 2.6e-10 1.5e-10 7.4e-11 3.6e-10 1.1e-10 2.3e-10
 2.5e-09 3.7e-10 2.2e-09]

Elastic net

Set alpha < 1 for the elastic net. Pass the same alpha to default_lagrange_sequence, which divides the sequence by α\alpha so that it still starts at the first λ\lambda where a variable enters.

elastic net, max |path - direct| = 5.55e-10

Unpenalized variables: a group lasso path

Variables with penalty weight 0 are unpenalized. They are fitted in the null solution (by solving the problem with only those variables) and kept in every subproblem. Here the first group of three variables is unpenalized; the other five groups get the usual weight ∣g∣\sqrt{|g|}.

The null solution is the least squares fit on the unpenalized group:

[1.11616196 1.23184926 0.78500781] [1.11615923 1.23185397 0.78499189]
[[1 0 0 0 0 0]
 [1 1 0 0 0 0]
 [1 1 0 0 0 0]
 [1 1 0 0 0 0]
 [1 1 0 0 0 0]]
group lasso, max |path - direct| = 7.88e-11
<Figure size 700x450 with 1 Axes>

A logistic lasso path

The other losses work the same way. To include an intercept, add a column of ones and give it weight 0.

-0.08004333775520663 -0.0800427076735365
fraction of deviance explained at smallest lambda: 0.352
logistic, max |path - direct| = 3.18e-09
<Figure size 700x450 with 1 Axes>

Cross-validation

cross_validate(path_obj, lagrange_seq, ...) fits the path on each training fold (by default with strong_rules; change it with path_fitter) and scores the linear predictor on the held-out fold. The default score is the mean squared error; pass score=f(linpred, y) for anything else. It returns the mean and standard deviation of the score over folds, for each λ\lambda.

The folds can be given as

The training loss is rescaled by n/ntrainn / n_{\text{train}} so that the same λ\lambda sequence is comparable across folds and with the full-data fit.

lambda minimizing CV error: 13.61 (lambda_max = 631.1), CV MSE 1.066
<Figure size 700x450 with 1 Axes>

The same call with a scikit-learn splitter, and with grouped cases (say, ten cases per subject):

KFold:      lambda_min = 16.34
GroupKFold: lambda_min = 13.61

Finally, refit at the selected λ\lambda: the path’s row imin is the solution there.

selected variables: [ 0  1  2  3  4  7 20 22 23 27]
estimates: [ 3.03 -1.95  1.33  0.88 -0.36  0.04  0.01  0.01  0.02  0.14]