§6.4.2, p. 45 — the group-lasso z-update is block soft thresholding
ProvedBoydADMM.L1.group_lasso_z_updateadmmgroup-lassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1proximal-operator
Let and be partitioned into blocks , and let , . The block vector with blocks
where (with ) is vector soft thresholding, is the unique minimizer over all block vectors of
With and this is the z-update of ADMM for the group lasso, whose regularizer is separable across blocks but not within them.
Formalization Note The book prints in the block update; since is partitioned like , the intended term is the block , which is what is stated. The block sizes are arbitrary (nb : Fin N → ℕ), and blocks are indexed from . is called lam; the book takes , the statement allows .
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_Basic open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.4.2, p. 45: let `x = (x_1, …, x_N)` and `u = (u_1, …, u_N)` be partitioned into blocks
`x_i, u_i ∈ ℝ^{n_i}`. For `λ ≥ 0` (called `lam`) and `ρ > 0`, the block vector with blocks
`S_{λ/ρ}(x_i + u_i)` (vector soft thresholding) is the unique minimizer of
`λ ∑_i ‖z_i‖₂ + (ρ/2) ∑_i ‖x_i − z_i + u_i‖₂²` over all block vectors `z`. -/
theorem group_lasso_z_update {N : ℕ} (nb : Fin N → ℕ) (lam ρ : ℝ) (hlam : 0 ≤ lam) (hρ : 0 < ρ)
(x u : (i : Fin N) → EuclideanSpace ℝ (Fin (nb i))) :
IsUniqueMinimizerOn
(fun z : (i : Fin N) → EuclideanSpace ℝ (Fin (nb i)) =>
lam * ∑ i, ‖z i‖ + (ρ / 2) * ∑ i, ‖x i - z i + u i‖ ^ 2) Set.univ
(fun i => blockSoftThreshold (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. 45, §6.4.2 (group lasso, block soft thresholding)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.