(48), p. 22 — the equivalent recursion x(k+1) = R̃(k)(x(k) − αh(k)), h(k+1) = R̃(k)h(k) + V(k+1)⁻¹(∇f(x(k+1)) − ∇f(x(k)))
ProvedDIGing.Push.relation_48directed-graphsdistributed-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1push-sum
Let the mixing matrices satisfy Assumption 7, and let be a run of Push-DIGing with any step size . Write for the push-sum weights, , and . Then for every
This is the form of Push-DIGing on which the whole convergence analysis rests: it has the shape of DIGing with the row stochastic matrices in place of the doubly stochastic .
Formalization Note Assumption 7 includes the self-weight (disclosed in the Setting file); it is what makes every positive, so that . Assumption 6 is not needed.
Preamble
import Mathlib import Definitions.Def_DIGing_Undir_Common import Definitions.Def_DIGing_Push_Setting
Formal statement
namespace DIGing.Push
theorem relation_48 {n p : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(A : ℕ → Finset (Fin n × Fin n)) (C : ℕ → Matrix (Fin n) (Fin n) ℝ)
(h7 : Assumption7 A C) (α : ℝ) (u x y : ℕ → DIGing.Undir.Stack n p)
(hrun : IsPushDIGingRun f C α u x y) :
∀ k, x (k + 1) = DIGing.Undir.mix (Rt C k) (x k - α • hSeq C y k) ∧
hSeq C y (k + 1) = DIGing.Undir.mix (Rt C k) (hSeq C y k) +
(fun i => (vSeq C (k + 1) i)⁻¹ • (DIGing.Undir.gradStack f (x (k + 1)) - DIGing.Undir.gradStack f (x k)) i) := by sorry
end DIGing.Push
Source
arXiv:1607.03218v3, §5, display (48), p. 22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.