§6.4, p. 43 — lasso ADMM: ,
ProvedBoydADMM.L1.lasso_updatesadmmlassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1soft-thresholding
Let , , , and .
- The vector is the unique minimizer over of
- For every , the vector with components is the unique minimizer over of
With , and these are the x- and z-updates of scaled-form ADMM for the lasso, minimize , split as with . The x-update is a ridge regression; is always invertible because .
Formalization Note The regularization weight is called lam. The book takes ; the statement is made for , which contains it. Part 2 holds for every , in particular for . is the referenced platform definition HighDimStat.SparseLinear.l1Norm, .
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_Basic import Definitions.Def_HighDimStat_SparseLinear_L1Norm open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.4, p. 43: for `ρ > 0` and `λ ≥ 0` (called `lam`),
(1) `(AᵀA + ρI)⁻¹(Aᵀb + ρ(z − u))` is the unique minimizer of
`(1/2)‖Ax − b‖₂² + (ρ/2)‖x − z + u‖₂²` over `x`, and
(2) for every `x`, the vector with components `S_{λ/ρ}(x_i + u_i)` is the unique minimizer of
`λ‖z'‖₁ + (ρ/2)‖x − z' + u‖₂²` over `z'`. -/
theorem lasso_updates {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin m))
(lam ρ : ℝ) (hlam : 0 ≤ lam) (hρ : 0 < ρ) (z u : EuclideanSpace ℝ (Fin n)) :
IsUniqueMinimizerOn
(fun x : EuclideanSpace ℝ (Fin n) =>
(1 / 2) * ‖Matrix.toEuclideanLin A x - b‖ ^ 2 + (ρ / 2) * ‖x - z + u‖ ^ 2) Set.univ
(Matrix.toEuclideanLin (Aᵀ * A + ρ • (1 : Matrix (Fin n) (Fin n) ℝ))⁻¹
(Matrix.toEuclideanLin Aᵀ b + ρ • (z - u))) ∧
∀ x : EuclideanSpace ℝ (Fin n),
IsUniqueMinimizerOn
(fun z' : EuclideanSpace ℝ (Fin n) =>
lam * HighDimStat.SparseLinear.l1Norm (WithLp.ofLp z') +
(ρ / 2) * ‖x - z' + u‖ ^ 2) Set.univ
(WithLp.toLp 2 fun i => BoydADMM.Prox.softThreshold (lam / ρ) (x i + u i)) := by sorry
end BoydADMM.L1
Source
Boyd, Parikh, Chu, Peleato, Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn. 3(1) (2011), p. 43, §6.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.