Lemma 2, p. 10 — mean estimate equals mean decision
ProvedAggGameNet.Gossip.lemma_2aggregate-trackingconsensusgossipp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and update each estimate by , where is obtained by the pairwise gossip matrix. For every realization and every ,
This identity keeps the tracked average equal to the actual average throughout the gossip run.
Formalization Note The source assumes that every matrix has unit column sums. The displayed gossip matrix has that property directly, so the theorem specializes the lemma to this mission's matrices. Only the estimate recursion is assumed; no projected-gradient condition is needed.
Preamble
import Mathlib import Definitions.Def_AggGameNet_Gossip_Setting open MeasureTheory Filter Finset open scoped BigOperators
Formal statement
namespace AggGameNet.Gossip
theorem lemma_2 {N n : ℕ} (hN : 0 < N) {Ω : Type*}
(I J : ℕ → Ω → Fin N)
(x v : ℕ → Ω → Fin N → AggGameNet.Sync.E n)
(h0 : ∀ ω, v 0 ω = x 0 ω)
(hrec : ∀ ω k i,
v (k + 1) ω i = vhat I J v k ω i + x (k + 1) ω i - x k ω i) :
∀ ω k, yavg v k ω = (1 / (N : ℝ)) • ∑ i, x k ω i := by sorry
end AggGameNet.Gossip
Source
Koshal, Nedić, Shanbhag, Distributed Algorithms for Aggregative Games on Graphs, arXiv:1605.00267v2, Lemma 2, p. 10; gossip matrix (26), p. 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.