Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§8.3.2, pp. 69–70 — the group-lasso block update is 0 iff ‖Aᵢᵀv‖₂ ≤ λ/ρ, else (AᵢᵀAᵢ + νI)⁻¹Aᵢᵀv with ν‖xᵢ‖₂ = λ/ρ

Proved
BoydADMM.ModelFit.group_lasso_block_update

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

admmgroup-lassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1ridge-regression

In the feature-split group lasso, each xix_ixi​-update minimizes a function of the form

h(x)=ρ2∥Aix−v∥22+λ∥x∥2,x∈Rni,h(x)=\frac{\rho}{2}\|A_ix-v\|_2^2+\lambda\|x\|_2,\qquad x\in\mathbb R^{n_i},h(x)=2ρ​∥Ai​x−v∥22​+λ∥x∥2​,x∈Rni​,

where Ai∈Rm×niA_i\in\mathbb R^{m\times n_i}Ai​∈Rm×ni​, v∈Rmv\in\mathbb R^mv∈Rm, ρ>0\rho>0ρ>0 and λ>0\lambda>0λ>0 (note the ℓ2\ell_2ℓ2​ norm is not squared). For ν>0\nu>0ν>0 write x(ν)=(AiTAi+νI)−1AiTvx(\nu)=(A_i^TA_i+\nu I)^{-1}A_i^Tvx(ν)=(AiT​Ai​+νI)−1AiT​v. Then:

  1. 000 minimizes hhh if and only if ∥AiTv∥2≤λ/ρ\|A_i^Tv\|_2\le\lambda/\rho∥AiT​v∥2​≤λ/ρ; and in that case 000 is the only minimizer.
  2. If ∥AiTv∥2>λ/ρ\|A_i^Tv\|_2>\lambda/\rho∥AiT​v∥2​>λ/ρ, then
    • there is exactly one ν>0\nu>0ν>0 with ν ∥x(ν)∥2=λ/ρ\nu\,\|x(\nu)\|_2=\lambda/\rhoν∥x(ν)∥2​=λ/ρ;
    • for every ν>0\nu>0ν>0 with ν ∥x(ν)∥2=λ/ρ\nu\,\|x(\nu)\|_2=\lambda/\rhoν∥x(ν)∥2​=λ/ρ, the point x(ν)x(\nu)x(ν) minimizes hhh;
    • every minimizer xxx of hhh has the form x=x(ν)x=x(\nu)x=x(ν) for some ν>0\nu>0ν>0 with ν∥x∥2=λ/ρ\nu\|x\|_2=\lambda/\rhoν∥x∥2​=λ/ρ.

So in both cases hhh has a unique minimizer, which is 000 exactly when ∥AiTv∥2≤λ/ρ\|A_i^Tv\|_2\le\lambda/\rho∥AiT​v∥2​≤λ/ρ and otherwise a ridge-regression solution whose parameter ν\nuν is pinned down by ν∥xi∥2=λ/ρ\nu\|x_i\|_2=\lambda/\rhoν∥xi​∥2​=λ/ρ and can be found by a one-parameter search.

This is the closed form behind the xix_ixi​-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 ν\nuν". The statement asserts existence and uniqueness of that ν\nuν 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 AiTAiA_i^TA_iAiT​Ai​ is assumed). (AiTAi+νI)−1(A_i^TA_i+\nu I)^{-1}(AiT​Ai​+νI)−1 is Mathlib's matrix inverse, which is the true inverse for ν>0\nu>0ν>0. λ\lambdaλ is lam in Lean.

Preamble
import Mathlib
import Definitions.Def_BoydADMM_ModelFit_Basic

open Matrix
Formal statement
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
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), pp. 69–70, §8.3.2
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me