3.9 Lasso along a regularization path
The lasso is L1-regularized least squares,
minimize ½‖A x − b‖₂² + λ‖x‖₁
It mirrors the SCS lasso example. The L1 term is handled with the standard absolute-value trick: introduce t with |x_i| ≤ t_i (two linear inequalities each) and minimize Σ t_i. Over w = (x, t) this is the quadratic cone program
minimize ½ wᵀP w + c(λ)ᵀ w
subject to x_i − t_i ≤ 0, −x_i − t_i ≤ 0
where P carries AᵀA on the x block and
c(λ) = (−Aᵀb, λ·1). Crucially, only c changes with λ, so
we build one solver and solver-update! its c as we sweep the path,
warm starting each re-solve —
The data is A = [[1 0] [0 1] [1 1]], b = (1, 2, 0.5), giving AᵀA = [[2 1] [1 2]] and Aᵀb = (1.5, 2.5). Variables are w = (x₀, x₁, t₀, t₁).
(require scs)
(provide run-example)
3.9.1 The fixed data: P, constraints, and c(λ)
P holds AᵀA in the x block (upper triangle) and zeros on the t block:
(define P (scs:sparse-matrix 4 4 '(0 0 2) '(0 1 1) '(1 1 2)))
The constraint matrix encodes x_i − t_i ≤ 0 and −x_i − t_i ≤ 0:
(define G (scs:matrix 4 4 1 0 -1 0 -1 0 -1 0 0 1 0 -1 0 -1 0 -1))
Only the objective depends on λ: c(λ) = (−Aᵀb, λ, λ).
3.9.2 Sweeping the path
We build the solver at the first λ, solve it cold, then for each subsequent λ call solver-update! with the new c and re-solve (warm started automatically). The result is a list of (λ flag x) rows.
(define (run-example [lambdas '(0.1 0.3)]) (define s (make-solver #:A G #:b #(0.0 0.0 0.0 0.0) #:c (cost (car lambdas)) #:P P #:cone (make-cone #:positive 4) #:settings (make-settings #:eps-abs 1e-9 #:eps-rel 1e-9))) (for/list ([lambda (in-list lambdas)] [step (in-naturals)]) (define r (cond [(zero? step) (solver-solve! s)] [else (solver-update! s #:c (cost lambda)) (solver-solve! s)])) (define x (scs-result-x r)) (list lambda (scs-result-exit-flag r) (vector (vector-ref x 0) (vector-ref x 1)))))
Running it.
Larger λ shrinks x toward zero:
(run-example) ; ((0.1 1 #(0.1333 1.1333)) (0.3 1 #(0.0667 1.0667)))