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.

Getting started: the LASSO

The LASSO is the prototypical problem regreg is built for:

β^(λ)=argminβ∈Rp  12∥Y−Xβ∥22+λ∥β∥1.\hat\beta(\lambda) = \text{argmin}_{\beta \in \mathbb{R}^p} \; \frac{1}{2}\|Y - X\beta\|^2_2 + \lambda \|\beta\|_1 .

The objective splits into a smooth part (the loss, whose gradient we can evaluate) and a nonsmooth part (the penalty, whose proximal map we can evaluate). regreg represents each part by an object and hands the pair to a proximal gradient solver (FISTA). This page walks through each piece and checks the answer against first-order optimality conditions and against scikit-learn.

The loss

rr.squared_error(X, Y) is the function β↦12∥Y−Xβ∥22\beta \mapsto \frac{1}{2}\|Y - X\beta\|^2_2. It is a smooth atom (the quadratic μ↦12∥μ−Y∥22\mu \mapsto \frac{1}{2}\|\mu - Y\|_2^2) composed with the linear map β↦Xβ\beta \mapsto X\beta.

affine_smooth (20,)

Every smooth object exposes smooth_objective(beta, mode), which returns the value (mode='func'), the gradient (mode='grad') or both (mode='both'). The solver calls only this method, so any function implementing it can be used as a loss.

np.float64(739.7900938805902)

The same function is available as a Gaussian GLM, rr.glm.gaussian(X, Y), which also accepts case weights and offsets (see the losses page). Its value and gradient coincide with squared_error.

The penalty

rr.l1norm(p, lagrange=lam) is the function β↦λ∥β∥1\beta \mapsto \lambda\|\beta\|_1 on Rp\mathbb{R}^p. What makes it an atom is that its proximal map,

prox(z)=argminβ  L2∥β−z∥22+λ∥β∥1,\text{prox}(z) = \text{argmin}_\beta \; \frac{L}{2}\|\beta - z\|^2_2 + \lambda\|\beta\|_1,

is available in closed form: soft-thresholding at λ/L\lambda/L. The quadratic term is represented by an rr.identity_quadratic(L, center, linear_term, constant), i.e. L2∥β−μ∥22+ηTβ+γ\frac{L}{2}\|\beta - \mu\|^2_2 + \eta^T\beta + \gamma.

Loading...

Solving the problem

rr.simple_problem(loss, penalty) pairs one smooth function with one atom, and solve runs FISTA with backtracking. The main controls are tol (relative change in objective at which to stop) and min_its/max_its. The solution is returned and also stored in problem.coefs, which is used as the starting point of the next call to solve.

array([ 2.669, -1.823, 0.976, 0.949, 0. , -0. , 0. , -0. , -0. , 0. , -0. , -0. , -0. , -0. , -0. , -0. , 0. , -0. , 0. , -0. ])

Checking the KKT conditions

The solution is characterized by 0∈∇ℓ(β^)+λ ∂∥β^∥10 \in \nabla \ell(\hat\beta) + \lambda\,\partial\|\hat\beta\|_1, i.e. with g=XT(Xβ^−Y)g = X^T(X\hat\beta - Y),

gj=−λ sign(β^j) if β^j≠0,∣gj∣≤λ if β^j=0.g_j = -\lambda\, \text{sign}(\hat\beta_j) \text{ if } \hat\beta_j \neq 0, \qquad |g_j| \le \lambda \text{ if } \hat\beta_j = 0.
active set size 4, max |g_j + lam sign(b_j)| on active set = 9.73e-13, max |g_j| off active set = 19.559 (lam = 20.0)

The bound (constrained) form

Every seminorm atom can instead be used as a constraint. rr.l1norm(p, bound=delta) is the indicator of the ball {β:∥β∥1≤δ}\{\beta: \|\beta\|_1 \le \delta\}, and the problem

minimizeβ  12∥Y−Xβ∥22subject to ∥β∥1≤δ\text{minimize}_\beta \; \frac{1}{2}\|Y - X\beta\|^2_2 \quad \text{subject to } \|\beta\|_1 \le \delta

is solved the same way; the proximal map is now projection onto the ℓ1\ell_1 ball.

The two forms trace out the same set of solutions. If β^\hat\beta solves the Lagrange form at λ\lambda, it solves the bound form with δ=∥β^∥1\delta = \|\hat\beta\|_1. Conversely, if β^\hat\beta solves the bound form (with the constraint active), the corresponding Lagrange multiplier is λ=∥XT(Y−Xβ^)∥∞\lambda = \|X^T(Y - X\hat\beta)\|_\infty, read off from the KKT conditions above.

max |beta_lagrange - beta_bound| = 1.1879386363489175e-14
recovered lagrange parameter: 19.999999999999478

Duality and the conjugate

The convex conjugate of λ∥⋅∥1\lambda\|\cdot\|_1 is the indicator of the ℓ∞\ell_\infty ball of radius λ\lambda; more generally the conjugate of a seminorm in Lagrange form is its dual norm in bound form, and vice versa. regreg returns this as penalty.conjugate.

supnorm((20,), bound=20.000000, offset=None)
supnorm((20,), lagrange=6.417672, offset=None)

Fenchel duality gives the LASSO dual

maximizer  YTr−12∥r∥22subject to ∥XTr∥∞≤λ,\text{maximize}_r \; Y^T r - \frac{1}{2}\|r\|^2_2 \quad \text{subject to } \|X^T r\|_\infty \le \lambda,

whose solution is the residual r^=Y−Xβ^\hat r = Y - X\hat\beta. The constraint is exactly the conjugate atom, so we can check dual feasibility with penalty.conjugate.nonsmooth_objective(..., check_feasibility=True) (which returns 0 inside the set and ∞\infty outside), and check that the duality gap vanishes.

dual feasible: True
scaled up residual feasible: False
primal value 185.56568727, dual value 185.56568727, |gap| 3.3e-12

(The residual sits on the boundary of the dual feasible set, since some constraints ∣xjTr^∣≤λ|x_j^T \hat r| \le \lambda are active; scaling it by 1.01 leaves the set. The gap is zero only up to the solver tolerance, so it can come out slightly negative.)

Adding a ridge term: the elastic net

A quadratic κ2∥β∥22\frac{\kappa}{2}\|\beta\|^2_2 is an identity_quadratic(kappa, 0, 0, 0). Quadratics of this form are handled exactly inside the proximal map, so adding one costs nothing. It can be passed to solve (it is used for that call only) or attached to the atom (or loss) when constructing it. Both give the elastic net

minimizeβ  12∥Y−Xβ∥22+λ∥β∥1+κ2∥β∥22.\text{minimize}_\beta \; \frac{1}{2}\|Y - X\beta\|^2_2 + \lambda \|\beta\|_1 + \frac{\kappa}{2}\|\beta\|^2_2 .
active set size 6, max |g_j + lam sign(b_j)| on active set = 4.58e-12, max |g_j| off active set = 18.191 (lam = 20.0)
array([ 2.520e+00, -1.716e+00, 8.740e-01, 9.170e-01, 0.000e+00, -0.000e+00, 0.000e+00, 0.000e+00, -0.000e+00, -0.000e+00, -0.000e+00, -0.000e+00, 0.000e+00, -0.000e+00, -0.000e+00, -1.000e-03, -0.000e+00, -0.000e+00, 0.000e+00, -3.200e-02])

Comparison with scikit-learn

sklearn.linear_model.Lasso minimizes

12n∥Y−Xβ∥22+α∥β∥1,\frac{1}{2n}\|Y - X\beta\|^2_2 + \alpha\|\beta\|_1 ,

which is the regreg objective divided by nn, so α=λ/n\alpha = \lambda / n. Likewise ElasticNet minimizes 12n∥Y−Xβ∥22+αρ∥β∥1+α(1−ρ)2∥β∥22\frac{1}{2n}\|Y - X\beta\|^2_2 + \alpha\rho\|\beta\|_1 + \frac{\alpha(1-\rho)}{2}\|\beta\|^2_2, so αρ=λ/n\alpha\rho = \lambda/n and α(1−ρ)=κ/n\alpha(1-\rho) = \kappa/n. We turn off the intercept, since our problem has none.

lasso: max |regreg - sklearn| = 3.6415315207705135e-14
elastic net: max |regreg - sklearn| = 4.374278717023117e-14

A solution path by warm starts

Solutions change continuously in λ\lambda, so solving over a decreasing grid of λ\lambda values, starting each fit from the previous solution, is cheap. For λ≥λmax⁡=∥XTY∥∞\lambda \ge \lambda_{\max} = \|X^TY\|_\infty the solution is zero. The lagrange attribute of the atom can be changed in place, and problem.coefs carries the warm start from one call to the next.

path point 25 : max |regreg - sklearn| = 8.46136155932542e-07
<Figure size 700x400 with 1 Axes>