Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis

Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis Sulaiman A. Alghunaim Department of Electrical Engineering, Kuwait University

arXiv:2608.16271v1 [math.OC] 17 Aug 2026

sulaiman.alghunaim@ku.edu.kw

Abstract We study decentralized stochastic gradient tracking over a time-varying network of N agents under a uniform window-mixing condition. Products of τ consecutive doubly stochastic mixing matrices contract disagreement by a factor λ < 1, although individual matrices need not contract disagreement strictly and individual communication graphs may be disconnected. We construct a time-varying quadratic norm that turns this window contraction into an exact one-step Lyapunov identity. This leads to coupled one-step recursions for the centroid and disagreement errors, without unrolling the dynamics over communication windows. For smooth strongly convex objectives, √ the e leading stochastic term is O(1/(N K)); for smooth convex objectives, it is O(1/ N K). Both match their centralized mini-batch counterparts and yield linear speedup after a network-dependent transient.

1

Introduction

In decentralized optimization, a group of agents minimizes a global objective by combining local computation with communication restricted to network neighbors; no central node collects the data or the iterates [1,2]. Problems of this form arise in multi-agent coordination, formation control, and flocking [3–5], in distributed model-predictive control [6], and in distributed estimation and adaptive processing over sensor networks [2,7]. The time-varying regime is the practically important one: mobility, scheduling, link failures, and bandwidth constraints all cause the communication graph to change from one iteration to the next.

1.1

Problem and algorithm

Problem. We study the following distributed stochastic optimization problem:

minimize d x∈R

f (x) ≜

N 1 X fi (x), N i=1

1

fi (x) ≜ E [Fi (x; ξi )] ,

(1)

over a decentralized network of N agents. Each agent i has access only to its private local objective fi : Rd → R and to stochastic samples ξi used to evaluate gradients of the loss function Fi (·; ξi ); the stochasticity may represent local data sampling or measurement noise. By exchanging information only with their current neighbors, the agents seek a common solution to (1) without requiring a central coordinator. TV-GT algorithm. Gradient tracking [8–10] augments decentralized gradient descent [1, 2] with a dynamic estimate of the aggregate gradient to eliminate a bias caused by differences among local objectives. In this work, we study stochastic gradient tracking (GT) over time-varying communication graphs. At iteration k, agent i communicates with its current k k N > 0 only if agent j is a neigh}j=1 , where wij neighbors according to the mixing weights {wij k bor of agent i at time k or j = i, and wij = 0 otherwise. Each agent i maintains a local primal variable xki ∈ Rd and a gradient-tracking variable gik ∈ Rd , and performs xk+1 = i

N X

k wij (xkj − αgjk )

(2a)

k k wij gj + ∇Fi (xk+1 ; ξik+1 ) − ∇Fi (xki ; ξik ), i

(2b)

j=1

gik+1 =

N X j=1

with initialization gi0 = ∇Fi (x0i ; ξi0 ) and x0i ∈ Rd . The communication graph and the mixing k } may vary with k and are assumed to satisfy Assumption 2. weights {wij

1.2

Related work

Decentralized optimization over time-varying networks dates back to early distributed subgradient methods. The works [1, 11] analyze distributed (sub)gradient methods over graph sequences for which connectivity is required only over bounded communication windows, while the individual graphs may be disconnected. Most later work on time-varying networks adopts this window-based connectivity model. More recently, [12] analyzes decentralized SGD (DSGD) under general time-varying topologies and shows that DSGD achieves a leading variance term reduced by a factor proportional to the number of agents, i.e., linear speedup. DSGD, however, does not correct the bias induced by heterogeneous local objectives. Consequently, with constant stepsizes its error generally contains a persistent heterogeneity-dependent term, while exact convergence typically requires diminishing stepsizes [13]. Gradient tracking (GT) removes this steady-state bias by dynamically tracking the aggregate gradient [8,9]. Many works have analyzed GT over time-varying networks [9,10,14,15]. These works, however, focus on deterministic gradients and establish exact convergence under window-based connectivity, but do not address our stochastic gradient noise setting. Recent work has begun to address stochastic GT over time-varying graphs [16–18]. The work [16] imposes an expected-connectivity condition at each communication round, whereas [17] considers graph sequences with finite-time consensus. The work [18] replaces exact finite-time consensus by an approximate variant under symmetric doubly stochastic mixing. 2

These settings do not cover Assumption 2, which allows nonsymmetric mixing matrices, disconnected individual graphs, and an arbitrary window contraction factor λ < 1. Directed networks, where double stochasticity is generally unavailable, are handled by a modified family of GT methods [19, 20]. The work [19] extends NEXT to time-varying directed graphs through the push-sum-based SONATA framework, while [20] extends push– pull methods [21, 22] to time-varying directed networks and establishes linear convergence for strongly convex objectives; see also [23]. These results, however, focus on deterministic gradients. Stochastic GT over time-varying directed graphs has also been considered recently [24,25]. Push-sum, gradient tracking, and momentum are combined in [24], under the requirement that the communication graph be strongly connected at every iteration; [25] pairs push–pull gradient tracking with heavy-ball momentum and likewise assumes strong connectivity of every individual graph. Neither analysis covers the mixing model of Assumption 2, which permits individual graphs to be disconnected. Beyond the differences in network assumptions and convergence guarantees, our analysis also differs from prior work in how the time-varying network is handled. Analyses based directly on window contraction typically unroll the error over complete communication windows while also accounting for the associated partial-window terms; see, e.g., [12, 18]. We instead work in a time-varying quadratic norm under which the window-mixing condition of Assumption 2 already forces a strict decrease at every single iteration. This construction builds on classical converse-Lyapunov theory for stable time-varying systems and is closely related to the Lyapunov–Stein equation and converse Lyapunov results for linear time-varying systems [26–28]. Related ideas have also been used in networked control to combine joint connectivity with time-varying quadratic Lyapunov functions [29–31]. However, these works consider continuous-time dynamics and problems different from (1). Here, we apply this construction directly to the discrete-time disagreement mixing process underlying stochastic gradient tracking and use the resulting time-varying quadratic norm to control the coupled primal–tracking errors.

1.3

Contributions

This paper analyzes stochastic gradient tracking (2) under the uniform window-mixing condition in Assumption 2: every product of τ consecutive mixing matrices contracts disagreement by a factor λ < 1, while the individual matrices are required only to be nonnegative and doubly stochastic. In particular, individual communication graphs may be disconnected and need not provide contraction at every iteration. • One-step analysis under window contraction. We associate the time-varying mixing process with a quadratic Lyapunov norm whose defining identity gives a strict decrease at every iteration. This holds even when the individual mixing matrices are not strictly contractive. After scaling the tracking variable appropriately, the same norm controls the primal and tracking disagreements jointly. The resulting analysis

3

works directly at the iteration level and avoids unrolling the recursion over communication windows. This route differs from existing window-based analyses; we are not aware of prior work that applies this converse-Lyapunov construction to stochastic gradient tracking over time-varying networks. • Finite-time guarantees for strongly convex and convex objectives. For smooth e 2 /(N K)), where σ 2 strongly convex objectives, the leading stochastic term is O(σ bounds the gradient-noise variance. For √ smooth convex objectives, we obtain an ergodic bound with leading term O(σ/ N K). These terms match the corresponding centralized mini-batch rates and yield linear speedup in the number of agents. • Explicit network dependence. We characterize explicitly how the convergence bounds depend on the window length τ and the window contraction factor λ. In the τ3 strongly convex case, the coefficient of the higher-order stochastic term scales as (1−λ) 3, and the admissible stepsize and transient length are also characterized explicitly in terms of τ and 1 − λ. These expressions make explicit how long the network-dependent transient lasts before the centralized rate takes over.

2

Assumptions and error dynamics

In this section, we first state the assumptions on the objective functions, communication network, and stochastic gradients. We then derive the centroid and disagreement dynamics that form the basis of the convergence analysis.

2.1

Assumptions

Assumption 1 (Functions). Each local objective fi is L-smooth and µ-strongly convex for some 0 ≤ µ ≤ L, where µ = 0 corresponds to the convex case. We assume that f admits a minimizer and let x⋆ denote any minimizer of f . For the strongly convex case (µ > 0), we define the condition number κ ≜ Lµ . Assumption 2 (Network). The sequence {Wk }k≥0 is deterministic, and each Wk ∈ RN ×N k is nonnegative and doubly stochastic (wij ≥ 0, Wk 1 = 1, 1T Wk = 1T ). Define Π≜

1 T 11 , N

f ≜ W − Π. W k k

(3)

There exist an integer τ ≥ 1 and a constant λ ∈ [0, 1) such that every product of τ consecutive mixing matrices contracts disagreement: f W k+τ −1:k

2

≤ λ,

for all k ≥ 0,

(4)

f ≜W fW f f where W t:s t t−1 · · · Ws , t ≥ s. We define the τ -window spectral gap by ∆λ ≜ 1 − λ ∈ (0, 1].

4

Assumption 2 is a uniform window-mixing condition: contraction is required only over products of τ consecutive mixing matrices, while an individual matrix Wk need not contract disagreement. Consequently, the communication graph may be disconnected at individual iterations. The parameters τ and ∆λ quantify the effect of the time-varying network on the convergence rate: smaller τ and larger ∆λ correspond to faster information mixing. Remark 1 (Aligned-window contraction). Condition (4) requires contraction for windows starting at every iteration. A closely related formulation imposes contraction only on aligned blocks {ℓτ0 , . . . , (ℓ + 1)τ0 − 1}, ℓ ≥ 0, as in the deterministic setting considered in [12]. Every window of length 2τ0 −1 contains at least one complete aligned τ0 -block. Since the remaining doubly stochastic mixing factors are nonexpansive, aligned τ0 -window contraction with factor λ < 1 implies (4) with (τ, λ) = (2τ0 − 1, λ); see also [10]. We let F k denote the information available immediately before the stochastic samples k {ξik }N i=1 are drawn at iteration k; in particular, F contains the initialization and all iterates and stochastic samples generated up to iteration k − 1. k Assumption 3 (Gradient noise). Conditioned on F k , the samples ξ1k , . . . , ξN are mutually independent and, for every i, satisfy

h

i

(5a)

∇Fi (xki ; ξik ) − ∇fi (xki )



(5b)

E ∇Fi (xki ; ξik ) − ∇fi (xki ) | F k = 0 

E

2

| F k ≤ σ2.

The initial iterates {x0i }N i=1 are deterministic.

2.2

Network form

Network notation. For the analysis, we write (2) in stacked form. Define

x ≜ col{x1 , . . . , xN } ∈ RN d

(6a)

g ≜ col{g1 , . . . , gN } ∈ R

(6b)

Nd ∇F(x; ξ) ≜ col{∇Fi (xi ; ξi )}N i=1 ∈ R Nd ∇f (x) ≜ col{∇fi (xi )}N i=1 ∈ R

(6c)

Nd

Wk ≜ Wk ⊗ Id .

(6d) (6e)

TV-GT algorithm. With the notation above, (2) becomes

xk+1 = Wk (xk − αgk )

(7a)

gk+1 = Wk gk + ∇F(xk+1 ; ξk+1 ) − ∇F(xk ; ξk ),

(7b)

with g0 = ∇F(x0 ; ξ0 ) and arbitrary x0 . We now separate the network dynamics into the evolution of the network centroid and the disagreement among the agents. 5

2.3

Centroid and disagreement

Change of coordinates. Define

yk ≜ gk − ∇F(xk ; ξk ).

(8)

The initialization of g0 implies y0 = 0. This change of coordinates removes the difference of consecutive stochastic gradients from the tracking recursion. Substituting (8) into (7) gives xk+1 = Wk (xk − α∇F(xk ; ξk ) − αyk )

(9a)

yk+1 = Wk yk − (I − Wk )∇F(xk ; ξk ).

(9b)

For the centroid and disagreement analysis, define 1 T Π ≜ Π ⊗ Id = 11 ⊗ Id N f ⊗I f ≜W −Π=W W k d k k 

x̄k ≜



(10a) (10b)

1 T 1 (1 ⊗ Id )xk = xki N N i=1 N X

(10c)

N 1 X ∇f (x ) ≜ ∇fi (xki ) N i=1

(10d)

k

b k ≜ (I − Π)xk x

(10e)

u ≜ ∇f (x ) − ∇f (x ), k

k

⋆

⋆

x ≜1⊗x

e k ≜ yk + ∇f (x⋆ ) y

(10f)

⋆

(10g)

vk ≜ ∇F(xk ; ξk ) − ∇f (xk ),

v̄ k ≜

1 T (1 ⊗ Id )vk . N

(10h)

Lemma 1 (Centroid and disagreement dynamics). The centroid evolves as x̄k+1 = x̄k − α∇f (xk ) − αv̄ k ,

(11)

while the disagreement satisfies k f (x b k+1 = W e k − αuk − αvk ) x k b − αy

(12a)

f y − (I − W )(u + v ). =W k k

(12b)

e k+1

y

ek

k

k

Proof. By double stochasticity, N1 (1T ⊗ Id )Wk = N1 (1T ⊗ Id ). Averaging (9b) and using y0 = 0 therefore gives N1 (1T ⊗ Id )yk = 0, k ≥ 0. Therefore, averaging (9a) and using (10h) gives (11). For the disagreement dynamics, note that x⋆ minimizes f , Π∇f (x⋆ ) = 0, and hence e k = 0. Moreover, ∇F(xk ; ξ k ) = ∇f (x⋆ ) + uk + vk . Applying I − Π to (9a) and using Πy f gives (12a). Finally, substituting yk = y e k − ∇f (x⋆ ) into (9b) yields (I − Π)Wk = W k e k+1 = Wk y e k − (I − Wk )(uk + vk ). y k f y e k = 0, Wk y ek = W Since Πy k e , which gives (12b).

6

(13)

The centroid recursion (11) is independent of the particular mixing matrix Wk ; the effect of the communication network is therefore captured through the coupled disagreement dynamics (12).

2.4

Joint disagreement dynamics

To balance the primal and tracking disagreements, define the scaled tracking disagreement zk ≜

α k e , y η

η≜

∆λ . 2τ

(14)

Using (12), the two disagreement variables evolve as 



f b k+1 = W b k − ηzk − αuk − αvk x k x f zk − α (I − W )(uk + vk ). zk+1 = W k k η

(15a) (15b)

The scaling in (14) is introduced solely for the analysis. Its specific choice ensures that, once 2 the one-step Lyapunov dissipation coefficient δ = 1−λ is established below, we have η ≤ δ/2. τ This allows the coupling between the primal and tracking disagreements to be absorbed by the network dissipation in the joint Lyapunov recursion.

3

One-step Lyapunov analysis

This section builds, from the window-mixing condition alone, a time-varying quadratic norm in which the disagreement dynamics dissipate at every iteration; the remainder of the GT analysis is carried out in that norm.

3.1

Time-varying quadratic Lyapunov norm

Define the state-transition matrix of the lifted disagreement mixing process by Ψ(t, s) ≜ For each k ≥ 0, define Pk ≜

 f f f W t−1 Wt−2 · · · Ws ,

t > s,

 I,

t = s.

∞ X

Ψ(k + r, k)T Ψ(k + r, k).

(16)

(17)

r=0

The quadratic form induced by Pk measures the accumulated future disagreement energy starting from time k. The window contraction ensures that this series is finite and uniformly bounded.

7

Lemma 2 (Time-varying quadratic mixing norm). Under Assumption 2, define Rk ≜ δPk ,

δ≜

1 − λ2 . τ

(18)

Then, for every k ≥ 0, δI ⪯ Rk ⪯ I,

(19a)

k+1 Wk = Rk − δI.

(19b)

f TR W k

f

Moreover, with ∆λ ≜ 1 − λ, ∆λ (1 + λ) 2∆λ ∆λ ≤δ= ≤ , τ τ τ

0<δ≤

1 ≤ 1. τ

(20)

Proof. See Appendix B.1. Equation (19b) implies that the time-varying quadratic Lyapunov function Vk (q) ≜ f qk gives the exact ∥q∥2Rk applied to the homogeneous disagreement dynamics qk+1 = W k one-step decrease Vk+1 (qk+1 ) = Vk (qk ) − δ∥qk ∥2 . f need not contract disagreement in the Euclidean norm at every iteraThus, although W k tion, it is strictly dissipative in the time-varying Lyapunov norm: the window-scale mixing property reappears as a per-iteration decrease.

Remark 2 (Converse Lyapunov construction). The construction of Pk is motivated by classical converse-Lyapunov arguments for stable linear time-varying systems and is closely related to the Lyapunov–Stein equation and converse Lyapunov theory [26–28]. Related ideas have also appeared in continuous-time multi-agent systems [30, 31]. Here, we apply this construction directly to the discrete-time disagreement process underlying stochastic gradient tracking. f ∥ ≤ λ < 1, Remark 3 (Per-step contraction). When τ = 1, Assumption 2 implies ∥W k 2 f q∥2 ≤ for every k ≥ 0. Hence, the Euclidean norm itself yields the one-step decrease ∥W k λ2 ∥q∥2 = ∥q∥2 − (1 − λ2 )∥q∥2 . Therefore, in this case, a time-varying quadratic norm is not needed to obtain a per-iteration contraction. The construction in Lemma 2 is useful for the genuinely window-based case τ > 1.

3.2

Coupled error recursions

Using the scaled variable in (14), define b k ∥2R + 2∥zk ∥2R Ek ≜ ∥x k k

(21a)

b k ∥2 + 2∥zk ∥2 , Eek ≜ ∥x

(21b)

8

and let f ≜ E ∥x̄k − x⋆ ∥2 X k 1 1 Ek ≜ E[Ek ], Eek ≜ E[Eek ]. N N

By (19a), δ Eek ≤ Ek ≤ Eek , and hence Ek ≤ Eek ≤

1 e . b k ∥2 ≤ E E ∥x k N

Ek , δ

Finally, define Q≜1+

8 32τ 2 . = 1 + η2 ∆2λ

(22a) (22b) (23) (24) (25)

Lemma 3 (Coupled centroid–disagreement error). Under Assumptions 1–3, if 0 < α ≤ 1 , then, for every k ≥ 0, 4L 3αL e α2 σ 2 Ek + 2 N 2 2  δ 10α QL f Ek+1 ≤ Ek − Eek + Xk + Eek + α2 Qσ 2 . 4 δ

f f X k+1 ≤ (1 − µα)Xk +

(26a) (26b)

Proof. See Appendix B.2. What Lemma 3 exploits is that a single time-varying matrix Rk can serve as the quadratic b k and the scaled tracking disagreement zk . The norm for both the primal disagreement x k k e makes the primal–tracking coupling sufficiently small relative to the scaling z = (α/η)y network decrement. Through the identity (19b), the window-contraction assumption shows up as a one-step decrease of the combined energy Ek .

4

Convergence results

We now give our main convergence results.

4.1

Strongly convex result

Theorem 1 (One-step contraction). Suppose Assumptions 1–3 hold with µ > 0. If δ √ , 320 L Qκ

(27)

µα α2 σ 2 16α3 LQσ 2 Vk + + . 2 N δ

(28)

0 < α ≤ ᾱ ≜ √ f + ωE , ω ≜ 16αL . Then define Vk ≜ X k k δ 

Vk+1 ≤ 1 −



9

Proof. See Appendix B.3. The preceding one-step recursion yields the following finite-horizon guarantee. Corollary 1 (Transient rate and linear speedup). Suppose the conditions in Theorem 1 hold. Then, for every horizon K ≥ 1, there exists a horizon-dependent stepsize such that K

⋆ 2

E ∥x̄ − x ∥

e ≤O

σ2 τ 3σ2 c(1 − λ)2 K + + C exp − 0 N K (1 − λ)3 K 2 κ3/2 τ 2

!!

(29)

,

3

f + 16ᾱL ∥x b 0 ∥2 + 322ᾱ L ∥∇f (x⋆ )∥2 is independent where c > 0 is an absolute constant, C0 ≜ X 0 δN η δN e of K, and O(·) hides logarithmic factors and constants depending on µ and L. Moreover, linear speedup is achieved ! 2 σ e E ∥x̄K − x⋆ ∥2 ≤ O (30) NK

after transient time !

N κτ 3 κ3/2 τ 2 e Ktransient = O + . (1 − λ)2 (1 − λ)3

(31)

Proof. See Appendix B.4. The leading term in (29) matches the centralized stochastic rate obtained by averaging N independent stochastic gradients, and therefore gives linear speedup in the number of agents. The network affects only the higher-order term and the transient period through the window length τ and the window spectral gap 1 − λ. Thus, individual graphs may be disconnected, as permitted by Assumption 2, without changing the leading statistical term. Remark 1 shows that the same conclusion applies to the standard aligned-window model after a constant-factor increase in the window length. When σ = 0, Theorem 1 with a constant admissible stepsize gives geometric convergence to the exact solution. Corollary 2 (Consensus error). Let the conditions of Theorem 1 hold, and let α = αK be the horizon-dependent stepsize (93d) used in Corollary 1. Then, for every K ≥ 1, τ 3σ2 τ 2 E0 c (1 − λ)2 K 1 e b K ∥2R ≤ O E ∥x + + C K exp − 0 K N (1 − λ)3 K 2 (1 − λ)2 K 2 κ3/2 τ 2 where c > 0 is an absolute constant. Proof. See Appendix B.5.

10

!!

,

(32)

4.2

Convex result

For the convex case (µ = 0), define the expected function gap Fek ≜ E[f (x̄k ) − f (x⋆ )].

(33)

The following lemma gives the convex counterpart of Lemma 3. Lemma 4 (Convex centroid–disagreement recursion). Suppose Assumptions 1–3 hold with µ = 0. If 0 < α ≤ 1/(4L), then, for every k ≥ 0, α2 σ 2 3αL e Ek + , 2 N 20α2 QL e 10α2 QL2 e δ Fk + Ek + α2 Qσ 2 . Ek+1 ≤ Ek − Eek + 4 δ δ

f f e X k+1 ≤ Xk − αFk +

(34a) (34b)

Proof. See Appendix B.6. Theorem 2 (Convex finite-horizon bound). Suppose Assumptions 1–3 hold with µ = 0. If δ (35) 0 < α ≤ αcvx ≜ √ √ , 480 L Q then, for every K ≥ 1, X L 1 K−1 b k ∥2 E[f (x̄k ) − f (x⋆ )] + E ∥x K k=0 N 



f 8X 40LE0 8ασ 2 40α2 QLσ 2 0 ≤ + + + . 3αK δK 3N δ

(36)

Proof. See Appendix B.7. Corollary 3 (Convex rate and linear speedup). Suppose the conditions of Theorem 2 hold. Then there exists a horizon-dependent stepsize such that X 1 K−1 L b k ∥2 E[f (x̄k ) − f (x⋆ )] + E ∥x K k=0 N 

τ σ σ =O √ + NK 1 − λ K 



2

2/3



!

f τ 2X τ Ē0 0 + + , 2 (1 − λ) K (1 − λ)K

(37)



b 0 ∥2R + 2αcvx where Ē0 ≜ N1 ∥x ∥∇f (x⋆ )∥2R0 . 0 η2

Proof. See Appendix B.8.

√ The leading term in (37) scales as O(σ/ N K) and is independent of the network parameters, matching the centralized mini-batch stochastic-gradient rate. The remaining terms decay faster with K and capture the effect of the time-varying network. In particular, 11

comparing each network-dependent term with the  leading statistical term shows that they N 3τ 6 become lower order after Ktransient = O (1−λ)6 . Hence, beyond this network-dependent √ transient, the convergence rate is dominated by the centralized term O(σ/ N K), and the method achieves linear speedup in the number of agents despite the time-varying network. In the noiseless case, setting σ = 0 in (36) and using a constant admissible stepsize gives O(τ 2 /((1 − λ)2 K)). f = b 0 = 0 and X Remark 4 (Consensual initialization). If x0i = x0 for every i, then x 0 2 2α ⋆ 2 0 ⋆ 2 cvx ∥x − x ∥ . Moreover, Ē0 = η2 N ∥∇f (x )∥R0 . Thus, the local-gradient heterogeneity at the solution enters only through the K −1 initialization term in (37).

5

Conclusion and future directions

This paper analyzed stochastic gradient tracking over deterministic time-varying networks under a window-mixing condition that permits individual communication graphs to be disconnected. The time-varying quadratic Lyapunov construction converts contraction over communication windows into a one-step decrease, leading to finite-time guarantees for both strongly convex and convex objectives. In both cases, the dominant statistical term matches the corresponding centralized mini-batch rate after a network-dependent transient. Future work includes extending the one-step Lyapunov framework to random communication graphs, smooth nonconvex objectives, and time-varying directed push–pull methods. In particular, whether time-varying push–pull admits linear speedup is open; even for static networks such guarantees appeared only recently [32].

12

Appendices A

Auxiliary results

We first collect the basic mixing and stochastic-noise consequences of the main assumptions that are used in the proofs. We also recall a standard bound for the centroid error. Proposition 1 (Properties of the mixing matrices). Under Assumption 2, for every k ≥ 0 and every t ≥ s ≥ 0, k≥0

f ∥W k+τ −1:k ∥2 ≤ λ,

(38a)

f ∥ ≤1 ∥W t:s 2 ∥I − Wk ∥2 ≤ 2,

(38b) (38c)

f f where W t:s ≜ Wt:s ⊗ Id = Wt Wt−1 · · · Ws − Π.

Proof. Since Wk is nonnegative and doubly stochastic, ∥Wk ∥1 = ∥Wk ∥∞ = 1. Hence ∥Wk ∥2 ≤

q

∥Wk ∥1 ∥Wk ∥∞ = 1.

(39)

Moreover, double stochasticity implies ΠWk = Wk Π = Π. Therefore, f = (W − Π)(W W t:s t t−1 − Π) · · · (Ws − Π) = Wt Wt−1 · · · Ws − Π.

(40)

Since the product Wt · · · Ws is also nonnegative and doubly stochastic, f ∥ = ∥(I − Π)W · · · W ∥ ≤ 1. ∥W t:s 2 N t s 2

(41)

The bound ∥IN − Wk ∥2 ≤ 2 then follows from the triangle inequality. For the lifted matrices, f ⊗ I , and hence W f f =W f W k k d t:s = Wt:s ⊗ Id . Using ∥A ⊗ Id ∥2 = ∥A∥2 , all the corresponding lifted bounds follow immediately from the scalar-matrix bounds and Assumption 2. Proposition 2 (Gradient-noise bounds). Under Assumption 3, for every k ≥ 0, h

i

h

E ∥vk ∥2 | F k ≤ N σ 2 , Proof. Write

i

E ∥v̄ k ∥2 | F k ≤

σ2 . N

vik ≜ ∇Fi (xki ; ξik ) − ∇fi (xki ),

(42) (43)

k so that vk = col{v1k , . . . , vN }. By conditional unbiasedness and the bounded-variance ask k sumption, E[vi | F ] = 0 and E[∥vik ∥2 | F k ] ≤ σ 2 . Therefore,

E[∥vk ∥2 | F k ] =

N X

E[∥vik ∥2 | F k ] ≤ N σ 2 .

i=1

13

(44)

k Moreover, for v̄ k = N1 N i=1 vi , conditional independence and zero conditional means imply that the cross terms vanish, and hence

P

E[∥v̄ k ∥2 | F k ] =

N 1 X σ2 k 2 k . E[∥v ∥ | F ] ≤ i N 2 i=1 N

(45)

The following lemma provides the basic bound for the centroid error. 1 Lemma 5 (Centroid error inequality). Under Assumptions 1–3, if 0 < α ≤ 4L , then, for every k ≥ 0,

E ∥x̄k+1 − x⋆ ∥2 ≤ (1 − µα) E ∥x̄k − x⋆ ∥2 − α E[f (x̄k ) − f (x⋆ )] 3αL α2 σ 2 b k ∥2 + + E ∥x . 2N N

(46)

Proof. The proof is standard; see, e.g., [33, Lemma 3]. Conditioning on F k and using E[v̄ k | F k ] = 0 in (11) gives h

i

E ∥x̄k+1 − x⋆ ∥2 F k = x̄k − x⋆ − α∇f (xk )

2

h

+ α2 E ∥v̄ k ∥2 F k

i

E

D

≤ ∥x̄k − x⋆ ∥2 − 2α x̄k − x⋆ , ∇f (xk ) + α2 ∥∇f (xk )∥2 +

α2 σ 2 , N

(47)

where the last inequality follows from (42). We first bound the inner-product term. For each agent i, µ-strong convexity of fi implies: D

E

fi (x⋆ ) ≥ fi (xki ) + ∇fi (xki ), x⋆ − xki +

µ k ∥x − x⋆ ∥2 . 2 i

(48)

µ k ∥x − x⋆ ∥2 . 2 i

(49)

Rearranging gives E

D

xki − x⋆ , ∇fi (xki ) ≥ fi (xki ) − fi (x⋆ ) +

Using x̄k − x⋆ = xki − x⋆ + x̄k − xki , we obtain D

E

E

D

D

x̄k − x⋆ , ∇fi (xki ) = xki − x⋆ , ∇fi (xki ) + x̄k − xki , ∇fi (xki ) E

D

≥ fi (xki ) − fi (x⋆ ) + ∇fi (xki ), x̄k − xki +

E

µ k ∥x − x⋆ ∥2 . 2 i

(50)

On the other hand, the L-smoothness of fi gives: D

E

fi (x̄k ) ≤ fi (xki ) + ∇fi (xki ), x̄k − xki + 14

L k ∥x̄ − xki ∥2 . 2

(51)

Equivalently, D

L k ∥x − x̄k ∥2 . 2 i

(52)

µ k L ∥xi − x⋆ ∥2 − ∥xki − x̄k ∥2 . 2 2

(53)

E

fi (xki ) + ∇fi (xki ), x̄k − xki ≥ fi (x̄k ) − Substituting this bound into (50) yields D

E

x̄k − x⋆ , ∇fi (xki ) ≥ fi (x̄k ) − fi (x⋆ ) +

Averaging (53) over i = 1, . . . , N and recalling ∇f (xk ) = N1 D

E

x̄k − x⋆ , ∇f (xk ) ≥ f (x̄k ) − f (x⋆ ) +

k i=1 ∇fi (xi ), gives

PN

N N µ X L X ∥xki − x⋆ ∥2 − ∥xk − x̄k ∥2 . 2N i=1 2N i=1 i

(54)

The standard variance decomposition gives N X

∥xki − x⋆ ∥2 =

i=1

N X

∥xki − x̄k ∥2 + N ∥x̄k − x⋆ ∥2

i=1

(55)

≥ N ∥x̄k − x⋆ ∥2 , where we used

k k i=1 (xi − x̄ ) = 0. Applying these relations to (54) gives

PN

D

E

x̄k − x⋆ , ∇f (xk ) ≥ f (x̄k ) − f (x⋆ ) +

b k ∥2 = where we used ∥x

L µ k b k ∥2 , ∥x̄ − x⋆ ∥2 − ∥x 2 2N

(56)

k 2 k i=1 ∥xi − x̄ ∥ . Next, decompose the average local gradient as

PN

∇f (xk ) = ∇f (x̄k ) +

N   1 X ∇fi (xki ) − ∇fi (x̄k ) . N i=1

(57)

Using ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 , Jensen’s inequality, and L-smoothness, ∥∇f (xk )∥2 ≤ 2∥∇f (x̄k )∥2 +

N 2 X ∥∇fi (xki ) − ∇fi (x̄k )∥2 N i=1





≤ 4L f (x̄k ) − f (x⋆ ) +

2L2 k 2 b ∥ , ∥x N

(58)

where we also used ∥∇f (x̄k )∥2 ≤ 2L(f (x̄k ) − f (x⋆ )). Substituting (56) and (58) into (47) gives h

i





E ∥x̄k+1 − x⋆ ∥2 F k ≤ (1 − µα)∥x̄k − x⋆ ∥2 − 2α − 4α2 L f (x̄k ) − f (x⋆ ) +

αL + 2α2 L2 k 2 α2 σ 2 b ∥ + ∥x . N N



(59)

Since α ≤ 1/(4L),

3αL . 2 Applying these bounds in (59) and taking total expectation proves (46). 2α − 4α2 L ≥ α,

αL + 2α2 L2 ≤

15

(60)

B

Proofs of the main results

B.1

Proof of Lemma 2

Proof. Write r = ℓτ + t, where ℓ, t are integers with ℓ ≥ 0 and 0 ≤ t < τ . The transition Ψ(k + r, k) defined in (16) can then be decomposed into ℓ complete blocks of length τ and one remaining block of length t < τ . By Assumption 2, every complete τ -block contracts disagreement by at most λ, whereas the remaining block is nonexpansive since each doubly f ∥ ≤ 1. Hence, stochastic mixing matrix satisfies ∥W j 2 ∥Ψ(k + r, k)∥2 ≤ λℓ = λ⌊r/τ ⌋ ,

(61)

where, when λ = 0, the usual convention λ0 = 1 is used. Consequently, Ψ(k + r, k)T Ψ(k + r, k) ⪯ λ2⌊r/τ ⌋ I.

(62)

Since the r = 0 term in (17) is I, we have Pk ⪰ I. Using (62) for the upper bound and writing each r ≥ 0 uniquely as r = ℓτ + t gives I ⪯ Pk = ⪯

∞ X r=0 ∞ X

Ψ(k + r, k)T Ψ(k + r, k) λ2⌊r/τ ⌋ I

r=0

=

∞ τX −1 X

λ2ℓ I

ℓ=0 t=0 ∞ X

=τ

λ2ℓ I =

ℓ=0

1 τ I = I. 1 − λ2 δ

(63)

Multiplying (63) by δ and recalling Rk = δPk yields (19a). Now we show (19b). For r ≥ 1, by the definition in (16), the transition matrix can be factored as f . Ψ(k + r, k) = Ψ(k + r, k + 1)W (64) k Separating the r = 0 term in (17), for which Ψ(k, k) = I, and using (64) gives Pk = I +

∞ X

Ψ(k + r, k)T Ψ(k + r, k)

r=1

fT =I+W

∞ X

k

!

Ψ(k + r, k + 1)T Ψ(k + r, k + 1)

f . W k

(65)

r=1

Introducing the change of index r′ = r − 1, the summation in (65) satisfies ∞ X

Ψ(k + r, k + 1)T Ψ(k + r, k + 1)

r=1

=

∞ X

Ψ(k + 1 + r′ , k + 1)T Ψ(k + 1 + r′ , k + 1) = Pk+1 .

r′ =0

16

(66)

Consequently,

f TP f Pk = I + W k k+1 Wk .

(67)

Multiplying (67) by δ and recalling Rk = δPk yields (19b). Finally, from the definition of δ, δ=

∆λ (1 + λ) 1 − λ2 = . τ τ

(68)

Since λ ∈ [0, 1), we have 1 ≤ 1 + λ < 2, and hence ∆λ 2∆λ ≤δ≤ . τ τ

(69)

Moreover, 0 < 1 − λ2 ≤ 1 and τ ≥ 1, so 0 < δ ≤ τ1 ≤ 1. This proves (20).

B.2

Proof of Lemma 3

Proof. Equation (26a) follows from (46) and (24) after dropping the nonnegative functiongap term. We next establish the disagreement recursion by first recalling from (15) that 

Define

f b k+1 = W b k − ηzk − αuk − αvk , x k x



(70a)

f zk − α (I − W )(uk + vk ). zk+1 = W k k η

(70b)

f TR f Hk ≜ W k k+1 Wk = Rk − δI.

(71)

By (19a) and (19b), 0 ⪯ Hk ⪯ Rk ⪯ I. Moreover, (14), (18), and (20) imply η=

δ 1 δ ≤ ≤ . 2(1 + λ) 2 2

(72)

Consider first the homogeneous part of (70). Using (71), its one-step energy is h k k 2 f (x f k 2 Ek+1 ≜ ∥W k b − ηz )∥Rk+1 + 2∥Wk z ∥Rk+1

b k − ηzk ∥2H + 2∥zk ∥2H = ∥x k k b k ∥2 − 2δ∥zk ∥2 − 2η(x b k )T Hk zk + η 2 ∥zk ∥2H . = Ek − δ∥x k

(73)

b k )T Hk zk | ≤ ∥x b k ∥2H + ∥zk ∥2H , Hk ⪯ I, and (72) gives Using 2|(x k k h b k ∥2 − (2δ − η − η 2 )∥zk ∥2 ≤ Ek − (δ − η)∥x Ek+1

b k ∥2 + 2∥zk ∥2 ) ≤ Ek − (δ − η)(∥x δ ≤ Ek − Eek . 2

17

(74)

b k , zk , and uk are F k -measurable, while E[vk | F k ] = 0. Hence, conditioning The variables x on F k and expanding the two terms in Ek+1 , the cross terms involving vk vanish, and we obtain k k k 2 f (x E[Ek+1 | F k ] = W k b − ηz − αu )

Rk+1

f zk − α (I − W )uk +2 W k k η

2 Rk+1

2 k k 2 . Rk+1 + 2 ∥(I − Wk )v ∥Rk+1 F η

"

#

f vk ∥2 + α E ∥W 2

k

(75)

For any positive semidefinite matrix R, vectors a, b, and β > 0, Young’s inequality gives 1 1+ ∥b∥2R . β !

∥a + b∥2R ≤ (1 + β)∥a∥2R +

(76)

Applying (76) with β = δ/4 to each of the first two terms yields !

δ Eh E[Ek+1 | F ] ≤ 1 + 4 k+1 !   4 2 2 k 2 k 2 f u ∥ + 1+ α ∥W k Rk+1 + 2 ∥(I − Wk )u ∥Rk+1 δ η " # 2 2 k 2 k 2 k f + α E ∥Wk v ∥Rk+1 + 2 ∥(I − Wk )v ∥Rk+1 F . η k

(77)

f ∥ ≤ 1, and ∥I − W ∥ ≤ 2, for any vector q, Since Rk+1 ⪯ I, ∥W k 2 k 2

8 2 2 2 2 Rk+1 + 2 ∥(I − Wk )q∥Rk+1 ≤ 1 + 2 ∥q∥ = Q∥q∥ . η η !

f q∥2 ∥W k

(78)

Therefore, using (74) and (42), δ 4 δ Ek − Eek + 1 + α2 Q∥uk ∥2 + α2 QN σ 2 E[Ek+1 | F k ] ≤ 1 + 4 2 δ δ 5α2 Q k 2 ≤ Ek − Eek + ∥u ∥ + α2 QN σ 2 . (79) 4 δ In the last inequality, we used Ek ≤ Eek to bound (δ/4)Ek ≤ (δ/4)Eek , discarded the nonpositive term −(δ 2 /8)Eek , and used 0 < δ ≤ 1 to obtain 1 + 4/δ ≤ 5/δ. For the gradient gap, split each entry of uk = ∇f (xk ) − ∇f (x⋆ ) at x̄k and use L-smoothness: !

∥uk ∥2 ≤ 2

N X

!



∥∇fi (xki ) − ∇fi (x̄k )∥2 + 2

i=1 2 bk 2



N X

∥∇fi (x̄k ) − ∇fi (x⋆ )∥2

i=1

≤ 2L ∥x ∥ + 2N L ∥x̄ − x ∥ . 2

k

⋆ 2

Taking expectations, dividing by N , and using (24) yields 1 f +E e ). E ∥uk ∥2 ≤ 2L2 (X k k N Taking total expectation in (79), dividing by N , and substituting (81) gives (26b). 18

(80) (81)

B.3

Proof of Theorem 1

Proof. Since κ = L/µ, the stepsize cap in (27) can be written as s

µδ 2 . 320QL3

(82)

µδ 2 1 1 ≤ . ≤√ 3 320QL 4L 320L

(83)

δ ᾱ = √ = √ 320 L Qκ Since µ ≤ L, 0 < δ ≤ 1, and Q ≥ 1, this gives s

α≤ Moreover, 4 ≤

√

√ 320 Q κ3/2 together with (82) yields δ δ ≤ , √ 4µ 320 L Qκ

(84)

1 , 4L

(85)

ᾱ = √ and therefore α≤ For compactness, write

χ≜

δ . 4µ

α≤

10α2 QL2 . δ

(86)

f + ωE , ω = 16αL , and (26) gives By (83), Lemma 3 applies, using Vk = X k k δ

Vk+1 ≤



f + ωE 1 − µα + ωχ X k

+

3αL ωδ − + ωχ Eek k + 2 4 "



α2 σ 2 + ωα2 Qσ 2 . N

#

(87)

The stepsize condition also gives ωχ =

160α3 QL3 µα ≤ . δ2 2

(88)

Hence, 1−µα +ωχ ≤ 1− µα . Moreover, ωδ/4 = 4αL, while (88) and µ ≤ L give ωχ ≤ αL/2. 2 Therefore, 3αL ωδ − + ωχ ≤ −2αL. (89) 2 4 Hence, using these in (87), we get f + ωE − 2αLE e Vk+1 ≤ (1 − µα )X k k k 2 2 2 α σ + + ωα2 Qσ 2 . N

19

(90)

Since Ek ≤ Eek by (24), 2αL Ek ω ! δ Ek =ω 1− 8   µα ≤ω 1− Ek , 2 



ωEk − 2αLEek ≤ ω 1 −

(91)

where the last inequality follows from (85). Finally, ωα2 Qσ 2 =

16α3 LQσ 2 . δ

(92)

Substituting (91) and (92) into (90) proves (28).

B.4

Proof of Corollary 1

For completeness, define the technical stepsize and initialization quantities used in the proof: δ √ 320 L Qκ 32ᾱ3 L f + 16ᾱL ∥x b 0 ∥2 + ∥∇f (x⋆ )∥2 C0 ≜ X 0 2 δN η δN ( ) 2 µ N C0 K TK ≜ max e, 2σ 2 ) ( 2 ln TK , ᾱ . αK ≜ min µK

(93a)

ᾱ ≜ √

(93b) (93c) (93d)

Here, the choice TK ≥ e ensures ln TK ≥ 1 and hence a strictly positive candidate stepsize. Proof. By Theorem 1, µα α2 σ 2 16α3 LQσ 2 Vk+1 ≤ 1 − Vk + + 2 N δ 





holds whenever 0 < α ≤ ᾱ. Iterating (94) and using K−1 1 − µα t=0 2 1 − t ≤ e−t , gives   2ασ 2 32α2 LQσ 2 µαK V0 + VK ≤ exp − + . 2 µN µδ P

(94) t

2 ≤ µα , together with

(95)

Since y0 = 0, (10g) and (14) give z0 = (α/η)∇f (x⋆ ). Hence, using R0 ⪯ I, E0 ≤

1 0 2 2α2 b ∥ + ∥x ∥∇f (x⋆ )∥2 . N η2N 20

(96)

f ≤ V in (95) gives Then V0 ≤ C0 , and using X K K

µαK K ≤ C0 exp − 2 



f X

+

2ασ 2 32α2 LQσ 2 + . µN µδ

(97)

Set α = αK . Since αK ≤ 2 ln TK /(µK), the two stochastic terms in (97) satisfy 2αK σ 2 4σ 2 ln TK ≤ , µN µ2 N K 2 LQσ 2 32αK 128LQσ 2 ln2 TK ≤ . µδ µ3 δK 2

(98a) (98b)

If αK = 2 ln TK /(µK), then µαK K C0 exp − 2 



=

C0 (93c) 2σ 2 ≤ 2 . TK µ NK

(99)

If instead αK = ᾱ, we retain the exponentially decaying initialization term. Consequently, f ≤ X K

2(1 + 2 ln TK )σ 2 128LQσ 2 ln2 TK + µ2 N K µ3 δK 2   µᾱK + C0 exp − . 2

(100)

It remains to expose the network dependence. From (20) and (25) 1−λ δ=Θ , τ !

!

τ2 Q=Θ . (1 − λ)2

(101)

More explicitly, since τ ≥ 1 and ∆λ ≤ 1, 32τ 2 33τ 2 ≤ Q ≤ . ∆2λ ∆2λ

(102)

τ3 Q τ3 16 3 ≤ ≤ 33 3 . ∆λ δ ∆λ

(103)

Combining (20) and (102) yields

Thus the first two terms in (100) give the first two terms in (29), up to logarithmic factors and constants depending on µ and L. For the initialization term, using δ ≥ ∆λ /τ and Q ≤ 33τ 2 /∆2λ from (102), µᾱ δ ∆2λ ∆2λ √ = √ ≥ ≥ , √ 2 206 κ3/2 τ 2 2 320 Q κ3/2 2 320 · 33 κ3/2 τ 2 21

(104)





so exp(−µᾱK/2) ≤ exp −c (1−λ)2 K/(κ3/2 τ 2 ) with c = 1/206. This proves the exponential term in (29). Finally, we determine when the network-dependent and initialization terms become lower order than the centralized statistical term. Ignoring logarithmic factors, the first two stochastic terms in (100) scale as LQσ 2 σ2 and , µ2 N K µ3 δK 2 respectively. Requiring the network-dependent term to be no larger than the centralized term gives LQσ 2 σ2 ≲ µ3 δK 2 µ2 N K LQ Q ⇐⇒ K≳N = Nκ . µδ δ Since Qδ = Θ



τ3 (1−λ)3



N κτ 3 (1−λ)3



µᾱK C0 exp − 2



e , this yields K = O



. For the initialization term, we require σ2 . µ2 N K

(106)

1 µ2 N C 0 K K≳ log . µᾱ σ2

(107)



Equivalently,

(105)

≲

!

Thus, up logarithmic factors, the initialization transient is determined by 1/(µᾱ). Using  to  κ3/2 τ 2 1 = Θ (1−λ)2 , we obtain µᾱ ! 3/2 2 κ τ e K=O . (108) (1 − λ)2 Combining the two requirements gives (31).

B.5

Proof of Corollary 2

Proof. Define

δ r ≜1− , 8

Under the stepsize condition,

ρ≜1−

µα . 2

10α2 QL2 δ ≤ . δ 8

Hence, using Ek ≤ Eek in (26b), Ek+1 ≤ rEk +

10α2 QL2 f Xk + α2 Qσ 2 . δ 22

(109)

Theorem 1 also gives f ≤ ρk C + X k 0

2ασ 2 32α2 LQσ 2 + . µN µδ

(110)

Iterating (109) gives X 10α2 QL2 K−1 C0 rK−1−k ρk δ k=0

EK ≤ rK E0 +

8α2 Qσ 2 160α3 QL2 σ 2 2560α4 Q2 L3 σ 2 + + + . δ µN δ 2 µδ 3

(111)

By (85), µα/2 ≤ δ/8, so r ≤ ρ and K−1 X

rK−1−k ρk ≤ KρK−1 .

k=0

Set α = αK . Since αK ≤ 2 ln TK /(µK) and αK ≤ ᾱ, the three noise terms in (111) satisfy 3 4 2 QL2 σ 2 2560αK Q2 L3 σ 2 8αK Qσ 2 160αK + + δ µN δ 2 µδ 3 ! ! √ 2 3 2 2 Q σ Qσ τ σ e e =O + =O , δK 2 δN K 2 (1 − λ)3 K 2

(112)

where we used

√ 2560ᾱ2 Q2 L3 8Q 80Qκ 160ᾱQL2 = , = , 2 3 µδ δ µδ δ and (103). For the initialization term, 1 − t ≤ e−t and supx>0 x2 e−x = 4e−2 give 256e−2 E0 τ 2 E0 rK E0 ≤ = O . δ2K 2 (1 − λ)2 K 2 !

(113)

It remains to bound the cross term. Since 2 δ 10αK QL2 ≤ ≤ 1, δ 32κ

if αK = 2 ln TK /(µK), then ρK−1 ≤ and hence, by (93c),

e1/8 , TK

2 10αK QL2 τ 3σ2 K−1 e C0 Kρ =O . δ (1 − λ)3 K 2

!

(114)

If αK = ᾱ, then 2 10αK QL2 (1 − λ)2 K C0 KρK−1 ≤ e1/8 C0 K exp − . δ 206 κ3/2 τ 2

!

b K ∥2R ≤ EK proves (32). Combining these bounds with N1 E ∥x K

23

(115)

B.6

Proof of Lemma 4

Proof. Lemma 5 remains valid after setting µ = 0. Therefore, f f e X k+1 ≤ Xk − αFk +

3αL α2 σ 2 b k ∥2 + E ∥x . 2N N

(116)

e from (24) proves (34a). b k ∥2 ≤ E Using N1 E ∥x k Now for the disagreement recursion, we know that for every convex L-smooth function h and all x, y, ∥∇h(x) − ∇h(y)∥2 ≤ 2L (h(x) − h(y) − ⟨∇h(y), x − y⟩) . (117)

Recall that uk = ∇f (xk ) − ∇f (x⋆ ). Splitting each local gradient difference at x̄k and using ∥p + q∥2 ≤ 2∥p∥2 + 2∥q∥2 gives ∥u ∥ ≤ 2 k 2

N X

∥∇fi (xki ) − ∇fi (x̄k )∥2

i=1 N X

+2

∥∇fi (x̄k ) − ∇fi (x⋆ )∥2 .

(118)

b k ∥2 . ∥∇fi (xki ) − ∇fi (x̄k )∥2 ≤ 2L2 ∥x

(119)

i=1

The first sum satisfies 2

N X i=1

Applying (117) to the second sum with x = x̄k and y = x⋆ gives 2

N X

∥∇fi (x̄k ) − ∇fi (x⋆ )∥2

i=1

≤ 4L

N  X

D

fi (x̄k ) − fi (x⋆ ) − ∇fi (x⋆ ), x̄k − x⋆

E

i=1





= 4N L f (x̄k ) − f (x⋆ ) ,

(120)

⋆ ⋆ where we used N i=1 ∇fi (x ) = N ∇f (x ) = 0. Combining (118)–(120), taking expectations, 1 k 2 e b ∥ ≤ Ek yields and using N E ∥x

P

1 E ∥uk ∥2 ≤ 2L2 Eek + 4LFek . N

(121)

The argument leading to (79) uses only the network and noise assumptions and therefore remains unchanged. Taking total expectation in (79) and dividing by N gives δ 5α2 Q Ek+1 ≤ Ek − Eek + E ∥uk ∥2 + α2 Qσ 2 . 4 δN Substituting (121) into (122) proves (34b). 24

(122)

B.7

Proof of Theorem 2

Proof. Since δ ≤ 1 and Q ≥ 1, the stepsize condition (35) implies α ≤ 1/(4L), so Lemma 4 f ≥ 0, and dividing by αK gives applies. Summing (34a) from k = 0 to K − 1, using X K f X X 1 K−1 X 3L K−1 ασ 2 0 Fek ≤ + Eek + . K k=0 αK 2K k=0 N

(123)

δ δ 10α2 QL2 ≤ ≤ . δ 48 8

(124)

δ 20α2 QL e Ek+1 ≤ Ek − Eek + Fk + α2 Qσ 2 . 8 δ

(125)

Moreover, (35) implies

Therefore, (34b) gives

Summing, using EK ≥ 0, and dividing by K yields 2 2 X X 1 K−1 8E0 160α2 QL K−1 e + 8α Qσ . Eek ≤ + F k K k=0 δK δ2K δ k=0

(126)

Substituting (126) into (123) gives f X X 1 K−1 X 12LE0 240α2 QL2 K−1 0 Fek ≤ Fek + + K k=0 αK δK δ2K k=0

12α2 QLσ 2 ασ 2 + + . δ N

(127)

1 240α2 QL2 ≤ . δ2 2

(128)

f X 1 K−1 2X 24LE0 24α2 QLσ 2 2ασ 2 0 e Fk ≤ + + + . K k=0 αK δK δ N

(129)

Again by (35),

Hence

Multiplying (126) by L and using

gives

160α2 QL2 1 ≤ δ2 3

(130)

X X L K−1 8LE0 1 K−1 8α2 QLσ 2 Eek ≤ + Fek + . K k=0 δK 3K k=0 δ

(131)

25

Adding K1

k=0 Fk to (131) and then applying (129) yields

PK−1 e

 X  1 K−1 Fek + LEek K k=0

≤

f 40LE0 8ασ 2 40α2 QLσ 2 8X 0 + + + . 3αK δK 3N δ

(132)

e , which proves (36). b k ∥2 ≤ E Finally, Fek = E[f (x̄k ) − f (x⋆ )] and N1 E ∥x k

B.8

Proof of Corollary 3

Proof. Since y0 = 0, definitions (10g) and (14) give z0 = Hence

1 E0 = N

α ∇f (x⋆ ). η

(133)

2α2 b 0 ∥2R + ∥x ∥∇f (x⋆ )∥2R0 0 2

!

≤ Ē0 ,

η

(134)

for every α ≤ αcvx . Choose s f  NX

fδ X 0 0 , σ 2 K 15QLσ 2 K

αK ≜ min 

!1/3

 

, αcvx  .

(135)

Using Theorem 2 and (134), we have RK ≤

40LĒ0 A 2 + BαK + CαK + , αK δK

where RK denotes the left-hand side of (36) and A≜

f 8X 0 , 3K

B≜

8σ 2 , 3N

C≜

40QLσ 2 . δ

The choice (135) is equivalently αK = min

s  A  A 1/3 

Therefore, BαK ≤ and

√ AB,

B

,

C

 

, αcvx . 

2 CαK ≤ A2/3 C 1/3 ,

√ A A ≤ AB + A2/3 C 1/3 + . αK αcvx 26

(136)

Substituting these bounds into (136) gives √ A 40LĒ0 + . RK ≤ 2 AB + 2A2/3 C 1/3 + αcvx δK

(137)

Finally, !

Q τ3 =Θ , δ (1 − λ)3

Lτ 2 1 =Θ , αcvx (1 − λ)2 !

τ 1 =Θ . δ 1−λ 



Applying these relations to (137) proves (37).

References [1] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009. [2] A. H. Sayed, “Adaptation, learning, and optimization over neworks,” Foundations and Trends in Machine Learning, vol. 7, no. 4-5, pp. 311–801, 2014. [3] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988– 1001, 2003. [4] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms and theory,” IEEE Transactions on Automatic Control, vol. 51, no. 3, pp. 401–420, 2006. [5] O. Shorinwa, T. Halsted, J. Yu, and M. Schwager, “Distributed optimization methods for multi-robot systems: Part 1—a tutorial [tutorial],” IEEE Robotics & Automation Magazine, vol. 31, no. 3, pp. 121–138, 2024. [6] J. F. Mota, J. M. Xavier, P. M. Aguiar, and M. Püschel, “Distributed ADMM for model predictive control and congestion control,” in Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 5110–5115, 2012. [7] I. D. Schizas, A. Ribeiro, and G. B. Giannakis, “Consensus in Ad Hoc WSNs with noisy links—Part I: Distributed estimation of deterministic signals,” IEEE Transactions on Signal Processing, vol. 56, no. 1, pp. 350–364, 2008. [8] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in Proceedings of the IEEE Conference on Decision and Control (CDC), (Osaka, Japan), pp. 2055–2060, 2015. [9] P. Di Lorenzo and G. Scutari, “NEXT: In-network nonconvex optimization,” IEEE Transactions on Signal and Information Processing over Networks, vol. 2, no. 2, pp. 120–136, 2016. [10] A. Nedic, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597– 2633, 2017.

27

[11] S. S. Ram, A. Nedic, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” Journal of Optimization Theory and Applications, vol. 147, no. 3, pp. 516–545, 2010. [12] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized SGD with changing topology and local updates,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 119, (Virtual/online), pp. 5381–5393, PMLR, July 2020. [13] K. Yuan, S. A. Alghunaim, B. Ying, and A. H. Sayed, “On the influence of bias-correction on distributed stochastic optimization,” IEEE Transactions on Signal Processing, vol. 68, pp. 4352–4367, 2020. [14] A. Sundararajan, B. Van Scoy, and L. Lessard, “Analysis and design of first-order distributed optimization algorithms over time-varying graphs,” IEEE Transactions on Control of Network Systems, vol. 7, no. 4, pp. 1597–1608, 2020. [15] M. Maros and J. Jaldén, “A geometrically converging dual method for distributed optimization over time-varying graphs,” IEEE Transactions on Automatic Control, vol. 66, no. 6, pp. 2465– 2479, 2020. [16] Y. Huang, J. Xu, J. Chen, and K. H. Johansson, “Beyond scaffold: A unified spatio-temporal gradient tracking method,” arXiv preprint arXiv:2512.01732, 2025. [17] E. D. H. Nguyen, X. Jiang, B. Ying, and C. A. Uribe, “On graphs with finite-time consensus and their use in gradient tracking,” SIAM Journal on Optimization, vol. 35, no. 2, pp. 872–898, 2025. [18] A. Fainman and S. Vlaski, “On the convergence of decentralized stochastic gradient-tracking with finite-time consensus,” IEEE Transactions on Signal Processing, 2026. [19] G. Scutari and Y. Sun, “Distributed nonconvex constrained optimization over time-varying digraphs,” Mathematical Programming, vol. 176, no. 1-2, pp. 497–544, 2019. [20] F. Saadatniaki, R. Xin, and U. A. Khan, “Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices,” IEEE Transactions on Automatic Control, vol. 65, no. 11, pp. 4769–4780, 2020. [21] R. Xin and U. A. Khan, “A linear algorithm for optimization over directed graphs with geometric convergence,” IEEE Control Systems Letters, vol. 2, no. 3, pp. 315–320, 2018. [22] S. Pu, W. Shi, J. Xu, and A. Nedić, “Push–pull gradient methods for distributed optimization in networks,” IEEE Transactions on Automatic Control, vol. 66, no. 1, pp. 1–16, 2020. [23] A. Nedić, D. T. A. Nguyen, and D. T. Nguyen, “AB/Push-Pull method for distributed optimization in time-varying directed networks,” Optimization Methods and Software, vol. 40, no. 5, pp. 1044–1071, 2025. [24] Y. Chen, A. Hashemi, and H. Vikalo, “Accelerated distributed stochastic nonconvex optimization over time-varying directed networks,” IEEE Transactions on Automatic Control, vol. 70, no. 4, pp. 2196–2211, 2024.

28

[25] D. T. A. Nguyen, S. Wang, D. T. Nguyen, A. Nedich, and H. V. Poor, “Decentralized federated learning with gradient tracking over time-varying directed networks,” arXiv preprint arXiv:2409.17189, 2024. [26] P. Stein, “Some general theorems on iterants,” Journal of Research of the National Bureau of Standards, vol. 48, no. 1, p. 82, 1952. [27] B. Anderson and J. B. Moore, “Detectability and stabilizability of time-varying discrete-time linear systems,” SIAM Journal on Control and Optimization, vol. 19, no. 1, pp. 20–32, 1981. [28] R. Geiselhart, R. H. Gielen, M. Lazar, and F. R. Wirth, “An alternative converse Lyapunov theorem for discrete-time systems,” Systems & Control Letters, vol. 70, pp. 49–59, 2014. [29] Y. Su and J. Huang, “Stability of a class of linear switching systems with applications to two consensus problems,” IEEE Transactions on Automatic Control, vol. 57, no. 6, pp. 1420–1430, 2012. [30] W. Liu and J. Huang, “Adaptive leader-following consensus for a class of higher-order nonlinear multi-agent systems with directed switching networks,” Automatica, vol. 79, pp. 84–92, 2017. [31] Z. Liu and J. Huang, “Distributed Nash equilibrium seeking in aggregative games over jointly connected and weight-balanced networks,” IEEE Transactions on Automatic Control, vol. 70, no. 5, pp. 3486–3493, 2025. [32] L. Liang, G. Luo, and K. Yuan, “On the linear speedup of the push-pull method for decentralized optimization over digraphs,” arXiv preprint arXiv:2506.18075, 2025. [33] S. A. Alghunaim and K. Yuan, “An enhanced gradient-tracking bound for distributed online stochastic convex optimization,” Signal Processing, vol. 217, p. 109345, 2024.

29

Related documents

• Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis#620676
• Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis#618997
• Limit theorems for stochastic gradient descent in high-dimensional single-layer networks#675881
• Conditioned stochastic stability of equilibrium states on uniformly expanding repellers#984019
• Data-Driven Covariance Steering with Output Feedback#1109793