§8.3.2, pp. 69–70 — the group-lasso block update is 0 iff ‖Aᵢᵀv‖₂ ≤ λ/ρ, else (AᵢᵀAᵢ + νI)⁻¹Aᵢᵀv with ν‖xᵢ‖₂ = λ/ρ
ProvedBoydADMM.ModelFit.group_lasso_block_updateIn the feature-split group lasso, each -update minimizes a function of the form
where , , and (note the norm is not squared). For write . Then:
- minimizes if and only if ; and in that case is the only minimizer.
- If , then
- there is exactly one with ;
- for every with , the point minimizes ;
- every minimizer of has the form for some with .
So in both cases has a unique minimizer, which is exactly when and otherwise a ridge-regression solution whose parameter is pinned down by and can be found by a one-parameter search.
This is the closed form behind the -update of distributed group lasso: each block either drops out entirely or solves a ridge problem with a data-dependent ridge parameter.
Formalization Note The book writes "the solution", "the value of ". The statement asserts existence and uniqueness of that and characterizes every minimizer, rather than assuming either; uniqueness of the minimizer in case 1 and case 2 is then a consequence, not a hypothesis (no invertibility of is assumed). is Mathlib's matrix inverse, which is the true inverse for . is lam in Lean.
import Mathlib import Definitions.Def_BoydADMM_ModelFit_Basic open Matrix
namespace BoydADMM.ModelFit
/-- §8.3.2, pp. 69–70 (goal): the minimizer of `h(x) = (ρ/2)‖Aᵢx − v‖₂² + λ‖x‖₂` is `0` iff
`‖Aᵢᵀv‖₂ ≤ λ/ρ`; otherwise it is `(AᵢᵀAᵢ + νI)⁻¹Aᵢᵀv` for the value `ν > 0` with
`ν‖xᵢ‖₂ = λ/ρ`. -/
theorem group_lasso_block_update {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(v : EuclideanSpace ℝ (Fin m)) (ρ lam : ℝ) (hρ : 0 < ρ) (hlam : 0 < lam) :
(IsMinOn (groupLassoObj ρ lam A v) Set.univ 0 ↔
‖Matrix.toEuclideanLin Aᵀ v‖ ≤ lam / ρ) ∧
(‖Matrix.toEuclideanLin Aᵀ v‖ ≤ lam / ρ →
∀ x, IsMinOn (groupLassoObj ρ lam A v) Set.univ x → x = 0) ∧
(lam / ρ < ‖Matrix.toEuclideanLin Aᵀ v‖ →
(∃! ν : ℝ, 0 < ν ∧ ν * ‖ridgeSol A ν v‖ = lam / ρ) ∧
(∀ ν : ℝ, 0 < ν → ν * ‖ridgeSol A ν v‖ = lam / ρ →
IsMinOn (groupLassoObj ρ lam A v) Set.univ (ridgeSol A ν v)) ∧
(∀ x, IsMinOn (groupLassoObj ρ lam A v) Set.univ x →
∃ ν : ℝ, 0 < ν ∧ ν * ‖x‖ = lam / ρ ∧ x = ridgeSol A ν v)) := by sorry
end BoydADMM.ModelFit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.