Eq. (3.5), p. 10 — summed EXTRA: x^{k+1} = W̃x^k − Σ_{t≤k}(W̃ − W)x^t − α∇f(x^k)
ProvedExtraConsensus.Sublinear.eq_3_5decentralized-optimizationextragradient-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the EXTRA iterates for any step size , any mixing matrices , any functions ( denotes the gradient) and any start . Summing the iterations 1 through gives, for every ,
This rewrites the two-step recursion of EXTRA as a one-step update with a cumulative correction term, the form on which Lemma 3.2 rests.
Preamble
import Mathlib import Definitions.Def_ExtraConsensus_Sublinear_Model
Formal statement
namespace ExtraConsensus.Sublinear
open Matrix Filter Topology Asymptotics
/-- Eq. (3.5), p. 10. Summing the EXTRA iterations: for every `k`,
`𝐱^{k+1} = W̃𝐱ᵏ − Σ_{t=0}^{k} (W̃ − W)𝐱ᵗ − α∇𝐟(𝐱ᵏ)`, where `𝐱 = extraIter α W W̃ f 𝐱⁰`. -/
theorem eq_3_5 {n p : ℕ} (W Wt : Matrix (Fin n) (Fin n) ℝ)
(f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ) (α : ℝ) (x0 : Stack n p) :
let x := extraIter α W Wt f x0
∀ k : ℕ, x (k + 1) =
mix Wt (x k) - ∑ t ∈ Finset.range (k + 1), mix (Wt - W) (x t) - α • gradF f (x k) := by sorry
end ExtraConsensus.Sublinear
Source
Shi, Ling, Wu & Yin, arXiv:1404.6264v4, §3.1, 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.