§8.3.1, p. 69 (corrected) — the lasso block update is 0 iff ‖Aᵢᵀv‖_∞ ≤ λ/ρ
ProvedBoydADMM.ModelFit.lasso_block_zero_test_correctedadmmlassooptimality-conditionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , , and . In the feature-split lasso the -update minimizes with . Then is a minimizer of
over if and only if
The test lets a serial implementation skip the blocks whose features are not used.
Corrected statement. The book prints the test with the Euclidean norm, . That is the test for the group-lasso term of §8.3.2, and it is false for the term: with , and the minimizer is although . The correct test, stated here, uses , the dual norm of .
Formalization Note "" is read as " is a minimizer"; uniqueness of the minimizer is not claimed (the objective need not be strictly convex). is lam in Lean.
Preamble
import Mathlib import Definitions.Def_BoydADMM_ModelFit_Basic open Matrix
Formal statement
namespace BoydADMM.ModelFit
/-- §8.3.1, p. 69, corrected: `0` minimizes `(ρ/2)‖Aᵢxᵢ − v‖₂² + λ‖xᵢ‖₁` iff
`‖Aᵢᵀv‖_∞ ≤ λ/ρ` (the book prints `‖·‖₂`, which is false for the ℓ1 block term). -/
theorem lasso_block_zero_test_corrected {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(v : EuclideanSpace ℝ (Fin m)) (ρ lam : ℝ) (hρ : 0 < ρ) (hlam : 0 < lam) :
IsMinOn (fun x : EuclideanSpace ℝ (Fin n) =>
ρ / 2 * ‖Matrix.toEuclideanLin A x - v‖ ^ 2 + lam * l1norm x) Set.univ 0 ↔
∀ j, |Matrix.toEuclideanLin Aᵀ v j| ≤ lam / ρ := by sorry
end BoydADMM.ModelFit
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. 69, §8.3.1 (printed with ‖·‖₂; corrected to ‖·‖_∞)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.