Eq. (3.5), p. 10 — summed EXTRA: x^{k+1} = W̃x^k − Σ_{t≤k}(W̃ − W)x^t − α∇f(x^k)
ProvedExtraConsensus.Linear.eq_3_5decentralized-optimizationextrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be matrices, , and let be the EXTRA iterates started at any . Summing the EXTRA iterations through gives, for every ,
This summed form expresses EXTRA as a gradient step corrected by the accumulated consensus error ; it is the starting point of Lemma 3.2.
Formalization Note The identity is purely algebraic and holds for every and every , so no assumption is stated.
Preamble
import Mathlib import Definitions.Def_ExtraConsensus_Linear_Model
Formal statement
namespace ExtraConsensus.Linear
open Matrix
/-- Shi–Ling–Wu–Yin, arXiv:1404.6264v4, eq. (3.5), p. 10: summing EXTRA's iterations,
`𝐱^{k+1} = W̃𝐱ᵏ − ∑_{t=0}^{k} (W̃ − W)𝐱ᵗ − α∇𝐟(𝐱ᵏ)` for every `k`. -/
theorem eq_3_5 {n p : ℕ} (W Wt : Matrix (Fin n) (Fin n) ℝ)
(f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ) (α : ℝ) (x0 : ExtraConsensus.Sublinear.Stack n p) :
let x := ExtraConsensus.Sublinear.extraIter α W Wt f x0
∀ k : ℕ, x (k + 1) = ExtraConsensus.Sublinear.mix Wt (x k) - ∑ t ∈ Finset.range (k + 1), ExtraConsensus.Sublinear.mix (Wt - W) (x t)
- α • ExtraConsensus.Sublinear.gradF f (x k) := by sorry
end ExtraConsensus.Linear
Source
Shi, Ling, Wu & Yin, arXiv:1404.6264v4, proof of Lemma 3.2, eq. (3.5), p. 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.