Lemma 3.2, p. 10 — (I + W − 2W̃)(x^{k+1} − x*) + W̃(x^{k+1} − x^k) = −U(q^{k+1} − q*) − α[∇f(x^k) − ∇f(x*)]
ProvedExtraConsensus.Linear.lemma_3_2decentralized-optimizationextrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Under Assumptions 1–3, let be the symmetric positive semidefinite square root of , let satisfy the optimality conditions (3.1)–(3.2) with , let be the EXTRA iterates from any and . Then for every
This recursion is the basis of the whole convergence analysis; in the linear-rate proof it is used twice, in (3.24) and in (3.32).
Formalization Note The standing Assumptions 1–3 of §3 are kept as hypotheses, as in the paper; is any stacked variable satisfying (3.2), as on the page.
Preamble
import Mathlib import Definitions.Def_ExtraConsensus_Linear_Model
Formal statement
namespace ExtraConsensus.Linear
open Matrix
/-- Shi–Ling–Wu–Yin, arXiv:1404.6264v4, Lemma 3.2, p. 10 (under the standing Assumptions 1–3 of §3):
for any pair `(𝐪*, 𝐱*)` satisfying the optimality conditions (3.1)–(3.2) with `𝐪* = U𝐩`,
`(I + W − 2W̃)(𝐱^{k+1} − 𝐱*) + W̃(𝐱^{k+1} − 𝐱ᵏ) = −U(𝐪^{k+1} − 𝐪*) − α[∇𝐟(𝐱ᵏ) − ∇𝐟(𝐱*)]`. -/
theorem lemma_3_2 {n p : ℕ} (hn : 0 < n) (Gr : SimpleGraph (Fin n))
(W Wt U : Matrix (Fin n) (Fin n) ℝ) (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ) (Lf α : ℝ)
(hA1 : MixingAssumption Gr W Wt) (hA2 : ExtraConsensus.Sublinear.ConvexLipschitzGrad f Lf) (hA3 : ExtraConsensus.Sublinear.SolutionExists f)
(hUs : Uᵀ = U) (hUpsd : U.PosSemidef) (hU2 : U * U = Wt - W)
(qs xs : ExtraConsensus.Sublinear.Stack n p) (hopt : ExtraConsensus.Sublinear.IsOptimalPair U α f qs xs) (x0 : ExtraConsensus.Sublinear.Stack n p) :
let x := ExtraConsensus.Sublinear.extraIter α W Wt f x0
let q := ExtraConsensus.Sublinear.qSeq U x
∀ k : ℕ, ExtraConsensus.Sublinear.mix (1 + W - (2 : ℝ) • Wt) (x (k + 1) - xs) + ExtraConsensus.Sublinear.mix Wt (x (k + 1) - x k)
= -(ExtraConsensus.Sublinear.mix U (q (k + 1) - qs)) - α • (ExtraConsensus.Sublinear.gradF f (x k) - ExtraConsensus.Sublinear.gradF f xs) := by sorry
end ExtraConsensus.Linear
Source
Shi, Ling, Wu & Yin, arXiv:1404.6264v4, Lemma 3.2, eq. (3.4), p. 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.