§7.1.1: for the proximal step is soft thresholding
ProvedBoydADMM.Consensus.l1_prox_soft_thresholdadmmconsensuslassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1soft-thresholding
Let , , and . With , the proximal step of the regularized consensus -update,
has the unique solution
where is soft thresholding.
Formalization Note The book prints ; the intended reading, forced by the proximal form of the -update displayed just above it on the same page, is , which is what is stated. is named lam in Lean. The statement is an "iff" (existence and uniqueness of the minimizer).
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.1.1, p. 52 (sign corrected): for `g(z) = λ‖z‖₁` with `λ > 0` (`lam` in Lean), the
proximal step `argmin_z (λ‖z‖₁ + (Nρ/2)‖z − x̄^{k+1} − (1/ρ)ȳ^k‖²)` has the unique solution
`z = S_{λ/Nρ}(x̄^{k+1} + (1/ρ)ȳ^k)`, componentwise. The book prints `x̄^{k+1} − (1/ρ)ȳ^k`. -/
theorem l1_prox_soft_threshold {n N : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
(lam : ℝ) (hlam : 0 < lam)
(x y : Fin N → EuclideanSpace ℝ (Fin n)) (z : EuclideanSpace ℝ (Fin n)) :
(∀ z' : EuclideanSpace ℝ (Fin n),
lam * ∑ j, |z j| + ((N : ℝ) * ρ / 2) * ‖z - avg x - (1 / ρ) • avg y‖ ^ 2 ≤
lam * ∑ j, |z' j| + ((N : ℝ) * ρ / 2) * ‖z' - avg x - (1 / ρ) • avg y‖ ^ 2) ↔
∀ j, z j = BoydADMM.Prox.softThreshold (lam / ((N : ℝ) * ρ)) ((avg x + (1 / ρ) • avg y) j) := by sorry
end BoydADMM.Consensus
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. 52, §7.1.1 (example g(z) = λ‖z‖₁; the book prints x̄^{k+1} − (1/ρ)ȳ^k, corrected to +)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.