(6), p. 415 — the average tracker equals the average stochastic gradient: ȳ_k = (1/n) Σᵢ gᵢ(x_{i,k}, ξ_{i,k})
ProvedStochGradTrack.Const.tracking_identitydistributed-optimizationgradient-trackingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let have unit column sums, , and run DSGT (4) with constant stepsize from any deterministic , with . Then for every and every realization of the noise,
This is why is called a tracker: the network average of the trackers equals the average of the current stochastic gradients, so once the trackers agree each of them approximately follows the averaged gradient.
Formalization Note. The identity is pathwise and uses only from Assumptions 1–4, which are therefore not hypotheses here. The page writes without the index ; the recursion (4) and this statement use .
Preamble
import Mathlib import Definitions.Def_StochGradTrack_Const_Model
Formal statement
namespace StochGradTrack.Const
open MeasureTheory ProbabilityTheory Matrix
theorem tracking_identity {n p m : ℕ} {Ω : Type*} (α : ℝ) (W : Matrix (Fin n) (Fin n) ℝ)
(g : Fin n → E p → E m → E p) (ξ : ℕ → Fin n → Ω → E m) (x0 : Stack n p)
(hcol : ∀ j, ∑ i, W i j = 1) :
∀ k ω, avg (ys (fun _ => α) W g ξ x0 k ω) = (n : ℝ)⁻¹ • ∑ i, g i (xs (fun _ => α) W g ξ x0 k ω i) (ξ k i ω) := by sorry
end StochGradTrack.Const
Source
Pu & Nedić, Math. Program. 187 (2021), (6), p. 415
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.