§8.3.1, p. 69 — feature-split lasso: z̄^{k+1} = (b + ρAx̄^{k+1} + ρu^k)/(N + ρ)
ProvedBoydADMM.ModelFit.feature_split_lasso_zbar_updateadmmfeature-splittinglassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , , and , where is the average of the partial predictors and the single scaled dual variable. For the lasso loss the -update of feature-split ADMM minimizes
A point minimizes this function if and only if
This is the closed form that makes the gathering step of the feature-split lasso a single vector operation.
Formalization Note The objective is the -update displayed on p. 68 with the lasso loss of §8.1.1 (p. 62). The statement is an equivalence, so it includes existence and uniqueness. is taken as a given vector; how it is formed from the blocks does not matter for this identity.
Preamble
import Mathlib import Definitions.Def_BoydADMM_ModelFit_Basic open Matrix
Formal statement
namespace BoydADMM.ModelFit
/-- §8.3.1, p. 69: for the lasso loss `l(w) = (1/2)‖w‖₂²`, the feature-split `z̄`-update of p. 68
has the unique solution `z̄ = (b + ρ Ax̄ + ρ u)/(N + ρ)`. -/
theorem feature_split_lasso_zbar_update {N m : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
(b Axbar u zb : EuclideanSpace ℝ (Fin m)) :
IsMinOn (fun z : EuclideanSpace ℝ (Fin m) =>
1 / 2 * ‖(N : ℝ) • z - b‖ ^ 2 + (N : ℝ) * ρ / 2 * ‖z - Axbar - u‖ ^ 2) Set.univ zb ↔
zb = (1 / ((N : ℝ) + ρ)) • (b + ρ • Axbar + ρ • u) := 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 (with the z̄-update of p. 68)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.