On Federated Averaging with Partial Participation under a General Variance Condition

1

On Federated Averaging with Partial Participation under a General Variance Condition Ziming Wang, Kun Huang, Karl Henrik Johansson, and Shi Pu

arXiv:2611.14239v1 [math.OC] 10 Nov 2026

Abstract In this paper, we study the convergence of Federated Averaging (FedAvg) with partial participation under a general variance condition. In each communication round, the server samples S of the n clients uniformly at random without replacement. The stochastic gradients are assumed to satisfy the so-called ABC condition, which allows their variance to grow with the local objective gaps. For smooth objectives, we establish a finite-time stationarity bound in terms of the heterogeneity P nonconvex ⋆ ⋆ ⋆ measure σf⋆ := f ⋆ − n1 n i=1 fi and the client sampling factor IS := (n − S)/(n − 1). Here, f and fi denote the infima of the global average objective and client i’s local objective, respectively. The bound exhibits a linear speedup in the number of sampled clients S and recovers the full-participation result when S = n. Under diminishing stepsizes, we further prove that the gradient norm converges to zero both in expectation and almost surely. Notably, compared with existing analyses of FedAvg with partial participation, our results require no additional data heterogeneity assumption such as bounded gradient dissimilarity (BGD), and the sampling-induced term in our bound is not amplified by the number of local updates at the leading order. The importance of removing the BGD assumption is illustrated by an example that is smooth and lower bounded but violates BGD, yet is covered by our analysis. Index Terms Distributed optimization, federated learning, general variance condition, partial client participation.

I. I NTRODUCTION Federated learning (FL) trains a shared model across clients while keeping each client’s raw data local. It has been applied to autonomous driving [1], [2], large-scale training [3], and natural language processing [4], [5]. In FL, the clients collaboratively solve n 1X min f (x) := fi (x), (1) n i=1 x∈Rd where n is the number of clients and fi : Rd → R is the local objective available only to client i ∈ [n]P := {1, . . . , n}. Typical mi examples of fi include the expected risk fi (x) = Eξ∼Di [Fi (x; ξ)] and the empirical risk fi (x) = m1i j=1 fij (x), where Di is the local data distribution, Fi (x; ξ) is the loss of model x on sample ξ, and fij (x) := Fi (x; ξij ) is the loss on the j-th local sample ξij . Since client data typically follow different distributions, the local objectives fi generally differ across clients. This data heterogeneity is a central concern in FL. A classical algorithm for solving (1) is Federated Averaging (FedAvg) [6]. We consider FedAvg with partial client participation: in each communication round, the server samples S of the n clients uniformly at random without replacement. Each sampled client performs Q local stochastic gradient updates starting from the current global model, and the server averages the resulting local models. Partial participation is motivated by limited server bandwidth and intermittent client availability [7], [8]. Convergence analyses for FedAvg typically impose conditions on both the stochastic gradient noise and the data heterogeneity. Let gi (x; ξi ) be an unbiased stochastic gradient of fi (x). A commonly used noise condition is the relaxed growth condition [9], h i 2 2 Eξi ∥gi (x; ξi ) − ∇fi (x)∥ ≤ σ 2 + η 2 ∥∇fi (x)∥ , ∀x ∈ Rd , (2) for some constants σ, η ≥ 0. In particular, its special case η = 0 (bounded variance) has been widely adopted [10], [11]. To model and control data heterogeneity, one typically imposes the bounded gradient dissimilarity (BGD) condition (see, e.g., [12], [13]): n 1X ∥∇fi (x) − ∇f (x)∥2 ≤ ζ 2 + ψ 2 ∥∇f (x)∥2 , ∀x ∈ Rd , (3) n i=1 where ζ, ψ ≥ 0 are constants. The left-hand side of (3) vanishes for all x if and only if all fi have identical gradients. The constants ζ and ψ quantify the level of data heterogeneity. Ziming Wang and Kun Huang contribute equally to this work. Ziming Wang and Shi Pu are with the School of Data Science, The Chinese University of Hong Kong, Shenzhen, China. Kun Huang and Karl Henrik Johansson are with the Department of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, and Digital Futures, Stockholm, Sweden. (emails:

zimingwang2@link.cuhk.edu.cn, kunhuang@kth.se, kallej@kth.se, pushi@cuhk.edu.cn)

2

Both conditions can be restrictive. The relaxed growth condition (2) can fail for simple finite-sum problems [14], [15]. Moreover, BGD can fail even when all fi are smooth and lower bounded: Theorem 1 constructs such local objectives for which no finite pair (ζ, ψ) satisfies (3). To our knowledge, however, existing analyses of FedAvg with partial participation still rely on BGD (or a stronger condition) together with bounded variance. Specifically, client sampling introduces an additional error that scales with the gradient dissimilarity, and these analyses (e.g., [10]) control this error through BGD. Beyond FedAvg, the methods in [16], [17] avoid BGD under partial participation, but they still assume bounded variance. More importantly, they require clients to retain auxiliary variables across rounds. In contrast, FedAvg is stateless and well suited to cross-device FL, where clients participate infrequently and stored optimization variables can become stale [8]. The above observations motivate us to establish convergence guarantees for FedAvg with partial participation under a more general noise model and without BGD-type assumptions. The ABC condition [14], [15], [18] provides such a noise model: h i 2 Eξi ∥gi (x; ξi ) − ∇fi (x)∥ ≤ C [fi (x) − fi⋆ ] + D, (4) where C, D ≥ 0 are constants and fi⋆ := inf x fi (x); see Assumption 2. For smooth and lower bounded fi , the squared gradient norm is controlled by the local objective gap, so (2) implies (4). The converse need not hold [14], [15]. Thus, the ABC condition covers a strictly broader class of stochastic gradient oracles. Pn Regarding data heterogeneity, BGD can be avoided. Let f ⋆ := inf x f (x) and σf⋆ := f ⋆ − n1 i=1 fi⋆ . If each fi is L-smooth and lower bounded, the left-hand side of (3) is at most 2L[f (x) − f ⋆ + σf⋆ ]; see Lemma 1. Since σf⋆ is finite whenever each fi is lower bounded, this bound remains valid even when BGD fails [14]. In this paper, we prove that FedAvg with partial participation converges to stationarity under the ABC condition (4), without BGD-type assumptions. The main difficulty is that the aggregated update is affected by two sources of randomness. The first is the stochastic gradient noise along the local trajectories, which scales with the local objective gaps. The second is client sampling, whose error scales with the gradient dissimilarity. Without BGD, this dissimilarity is bounded in terms of 2L[f (x) − f ⋆ + σf⋆ ], which may grow even when ∥∇f (x)∥2 stays bounded. We separate the two sources by assigning a virtual local trajectory to every client, and bound the gradient dissimilarity by f (x) − f ⋆ and σf⋆ . The resulting bound quantifies the effect of partial participation through the sampling factor IS := (n − S)/(n − 1), which vanishes under full participation. Moreover, the client-sampling error in our bound is not amplified by the number of local updates. TABLE I C OMPARISON OF CONVERGENCE RESULTS OF F EDAVG FOR SMOOTH NONCONVEX OBJECTIVES . Paper

Heterogeneity

Noise

Rate

Assumption

Measure

(ζ 2 , 0)-BGD

ζ2

a.s.

Full Participation (S = n) [19]

(σ 2 , 0)

[10]

(σ 2 , 0)

(ζ 2 , 0)-BGD

ζ2

[20]

(σ 2 , 0)

(ζ 2 , ψ 2 )-BGD

ζ 2 , ψ2

[21]

(σ 2 , η 2 )

(ζ 2 , ψ 2 )-BGD

ζ 2 , ψ2

[14]

ABC

None

σf⋆ (a)

(ζ 2 , 0)-BGD

ζ2

1+σ 2 √ nQT  1+σ 2 O √  nQT  1+σ 2 O √  nQT  1+σ 2 O √ nQT ! r D+Cσ ⋆ +C f nQT

O





N



O

N N N Y

Partial Participation (S < n) [10] This Work

(σ 2 , 0) ABC

None

σf⋆

 O r O

1+σ 2 √ SQT

+

D+Cσ ⋆ +C f SQT

√ (b) IS ζ 2 Q √ ST

r +

(1+σ ⋆ )IS f ST

N ! Y

Noise: (σ 2 , η 2 ) means E∥gi (x; ξ) − ∇fi (x)∥2 ≤ σ 2 + η 2 ∥∇fi (x)∥2 ; ABC refers to (4). Heterogeneity: (ζ 2 , ψ 2 )-BGD refers to (3). Rate: only leading-order P terms in T are reported. Problem-dependent constants and numerical constants are omitted. a.s.: almost sure convergence under P 2 t αt = ∞ and t αt < ∞. P (a) ⋆ ⋆ 1 σf = f − n fi⋆ with f ⋆ = inf x f (x) and fi⋆ = inf x fi (x). (b) IS = (n − S)/(n − 1) is the sampling factor.

A. Related Works Most convergence analyses of FedAvg control data heterogeneity through the BGD condition (3); see, e.g., [10], [12], [19]– [21]. Other works avoid BGD by adopting alternative heterogeneity measures, such as the average drift at the optimum [22] and σf⋆ [14], [23]. The measure σf⋆ is used in [23] under strong convexity and bounded second moments of the stochastic gradients. It is shown in [14] that σf⋆ suffices to analyze nonconvex FedAvg under the ABC condition, but only for full participation. A different line of work modifies FedAvg to mitigate heterogeneity: SCAFFOLD [11] corrects client drift with control variates, FedProx [24] adds a proximal term to the local objectives, and FedPD [13] adopts a primal-dual formulation. The effect of client sampling on convergence has been widely studied. For strongly convex objectives, FedAvg has pbeen analyzed under client sampling both with and without replacement [23]. For smooth nonconvex objectives, a rate of O( Q/(ST ))

3

has been established for FedAvg with partial participation [10]. Other works design optimal client sampling rules that better approximate the full-client update [25] and handle arbitrary participation patterns [17]. These results are mainly developed under bounded variance or BGD-type assumptions, whereas our analysis requires neither. FL is closely related to decentralized optimization, where clients exchange information with their neighbors over a connected network instead of through a central server. Classical decentralized methods include DSGD [26], [27], gradient tracking [28]– [31], and exact diffusion/D2 [32]–[34]. Their local-update variants are studied in [35]–[38], and local momentum tracking further attains the optimal communication complexity [39]. The stochastic versions of these methods are typically analyzed under bounded variance or the relaxed growth condition (2). Decentralized methods under the ABC condition (4) have been studied in [40], [41], but without local updates. B. Main Contribution The main contribution of this work is three-fold. First, we establish a finite-time stationarity guarantee for FedAvg with partial participation under the ABC condition (4) without BGD-type assumptions. In particular, with S sampled clients per round, Q local updates, and T total communication rounds, the leading terms of the bound on min0≤t<T E∥∇f (xt )∥2 are s O

  q L∆f (D + Cσf⋆ + C∆f ) + L ∆f + ∆f σf⋆ SQT

r

 IS  , ST

where ∆f := f (x0 ) − f ⋆ . The first term stems from the stochastic gradient noise and exhibits a linear speedup in S and Q. The second term captures √ term √ the effect of client sampling and is independent of Q. By comparison, the corresponding sampling in [10] grows as Q under their stepsize choice. Under full participation, IS = 0 and the bound recovers the O(1/ nQT ) rate of [14]. To the best of our knowledge, this is the first guarantee for FedAvg with partial participation that requires neither bounded variance nor BGD-type assumptions; see Table I. Second, under diminishing stepsizes, we show that ∥∇f (xt )∥ converges to 0 both in expectation and almost surely. To the best of our knowledge, this is the first almost sure convergence result for FedAvg with partial participation in the nonconvex setting. It establishes an asymptotic stationarity guarantee for the last iterate and complements the finite-time bound above. Third, we show that the BGD condition (3) is indeed restrictive: it excludes certain problems that satisfy the smoothness and lower boundedness assumptions. Specifically, Theorem 1 constructs a one-dimensional example with two clients whose local objectives are smooth and lower bounded. However, no finite pair (ζ, ψ) satisfies (3) in this example, even though the data heterogeneity measured by σf⋆ is at most 1/2. Hence, within this setting, our analysis covers a strictly larger class of problems compared to BGD-based convergence guarantees. II. F EDAVG WITH PARTIAL PARTICIPATION : A LGORITHM AND P RELIMINARY A NALYSIS In this section, we describe FedAvg with partial participation, state the standing assumptions, introduce the heterogeneity measure, and develop the auxiliary estimates used in its convergence analysis. A. Algorithm and Virtual Trajectories Algorithm 1 summarizes FedAvg with partial participation. In each communication round t, the server samples a subset St of S clients uniformly at random without replacement and sends the current global model xt to them. Each sampled client starts from xt , performs Q local stochastic gradient steps with the common stepsize αt , and returns its final local model. The server then averages these models to obtain xt+1 . The unselected clients remain idle: they neither perform local computation nor keep any local state across rounds, since a client selected in a later round k > t simply restarts from xk . This participation model reflects practical constraints such as intermittent connectivity and limited client-side resources [6], [42]. For each selected client i ∈ St , its local recursion can be written as ℓ ℓ ℓ xℓ+1 i,t = xi,t − αt gi (xi,t ; ξi,t ) = xt − αt

ℓ X

j gi (xji,t ; ξi,t ),

(5)

j=0 ℓ where ℓ ∈ {0, 1, . . . , Q − 1}, t ≥ 0 and ξi,t denotes the random sample1 used by the stochastic gradient oracle of client i at local step ℓ of round t. Consequently, the server update can be expressed as Q−1

xt+1 = xt − αt Gt ,

Gt :=

1 XX ℓ gi (xℓi,t ; ξi,t ). S

(6)

i∈St ℓ=0

For the analysis, we associate each client with a virtual local trajectory at every communication round, regardless of whether ℓ the client is selected. Similar ideas also appear in [10], [23]. To this end, we regard the samples ξi,t as defined for all clients 1 For instance, a data sample or mini-batch drawn from D . i

4

Algorithm 1 FedAvg with Partial Participation 1: Server input: initial x0 , number of communication rounds T and number of participating clients S. 2: Client input: number of local updates Q and stepsize sequence {αt }t≥0 . 3: for t = 0, 1, . . . , T − 1 do 4: Server samples St uniformly without replacement, |St | = S 5: Send xt to all clients i ∈ St 6: for Client i ∈ St in parallel do 7: Receive xt from server and set x0i,t = xt . 8: for ℓ = 0, 1, . . . , Q − 1 do ℓ 9: Query a stochastic gradient gi (xℓi,t ; ξi,t ). ℓ+1 ℓ ℓ ℓ 10: Update xi,t = xi,t − αt gi (xi,t ; ξi,t ). 11: end for 12: end for P 13: Server aggregates xt+1 = S1 i∈St xQ i,t . 14: end for 15: Output xT .

i ∈ [n], including those not selected at round t. However, only the samples of the selected clients enter the algorithm. For each client i ∈ [n], define the virtual local trajectory x e0i,t = xt ,

ℓ x eℓ+1 eℓi,t − αt gi (e xℓi,t ; ξi,t ), i,t = x

ℓ = 0, . . . , Q − 1.

By construction, the virtual trajectories extend the actual local iterates to all clients: ( xℓ+1 i ∈ St , i,t , x eℓ+1 i,t = ℓ ℓ ℓ x ei,t − αt gi (e xi,t ; ξi,t ), i ∈ / St . Consequently, the aggregated direction can be written as Q−1

Gt =

1 XX ℓ gi (e xℓi,t ; ξi,t ), S i∈St ℓ=0

that is, Gt is the average of S directions sampled without replacement from the finite population { potential client directions. This representation is the basis of the sampling analysis in Section II-D.

PQ−1 ℓ=0

ℓ gi (e xℓi,t ; ξi,t )}ni=1 of

B. Assumptions We impose three standing assumptions: smoothness and lower boundedness of the local objectives (Assumption 1), unbiased stochastic gradients satisfying the ABC condition (Assumption 2), and uniform client sampling without replacement (Assumption 3). The ABC condition [15], [18] covers a strictly larger class of stochastic gradients than the bounded variance and relaxed growth conditions [14]. Unlike existing analyses of FedAvg with partial participation, we impose no additional data heterogeneity assumption such as the BGD condition (3), which may fail under Assumption 1 (Theorem 1). Assumption 1. Each fi is L-smooth and lower bounded, i.e., ∥∇fi (x) − ∇fi (y)∥ ≤ L∥x − y∥, fi (x) ≥ fi⋆ := inf fi (z) > −∞, z∈Rd

∀x, y ∈ Rd .

(7)

Assumptions 2 and 3 are stated with respect to the following filtrations. ℓ Definition 1. Let Ft := σ(x0 , {Ss }0≤s<t , {ξi,s : i ∈ [n], 0 ≤ ℓ < Q, 0 ≤ s < t}) be the information available at the ℓ n beginning of round t. In particular, xt is Ft -measurable. Within round t, define Ft0 := Ft and Ftℓ+1 := σ(Ftℓ , {ξi,t }i=1 ) for Q ℓ = 0, . . . , Q − 1. The sampling set is revealed only after all round-t oracle variables, i.e., Ft+1 = σ(Ft , St ). Thus,

Ft = Ft0 ⊆ Ft1 ⊆ · · · ⊆ FtQ ⊆ Ft+1 . Moreover, we use Et [·] := E[· | Ft ]. Since x e0i,t = xt and the oracle gi is a measurable function of its arguments, every virtual iterate x eℓi,t is Ftℓ -measurable, ℓ+1 ℓ ℓ ℓ and every gi (e xi,t ; ξi,t ) is Ft -measurable. In particular, the round-t virtual trajectories {e xi,t : i ∈ [n], 0 ≤ ℓ ≤ Q} are FtQ -measurable: they are determined by xt and the round-t samples, and do not involve the round-t sampling set St . This

5

is the purpose of the ordering in Definition 1: FtQ contains all round-t samples but not St . The ordering is used only for the analysis and does not contradict Algorithm 1, where St is drawn before the local updates. This is because the virtual trajectories do not involve St and St is independent of the samples (Assumption 3), revealing St after the samples does not change the joint distribution of St and the samples. Assumption 2. Each client i has access to an unbiased stochastic gradient of fi whose variance satisfies the ABC condition along the virtual trajectories. Formally, there exist constants C, D ≥ 0 such that, for every t ≥ 0, i ∈ [n], and ℓ ∈ {0, . . . , Q−1}, ℓ ℓ the stochastic gradient gi (e xℓi,t ; ξi,t ) satisfies E[gi (e xℓi,t ; ξi,t )|Ftℓ ] = ∇fi (e xℓi,t ) and i h   2 ℓ xℓi,t ) − fi⋆ + D E gi (e xℓi,t ; ξi,t ) − ∇fi (e xℓi,t ) Ftℓ ≤ C fi (e (8) ℓ n almost surely (a.s.). Moreover, conditionally on Ftℓ , the noises {ξi,t }i=1 are independent across clients.

Remark 1. At the beginning of each round, all virtual local trajectories start from the same point, x e0i,t = xt . Averaging (8) over clients therefore gives, n i 1X h 2 0 Et gi (xt ; ξi,t ) − ∇fi (xt ) n i=1 ≤ C[f (xt ) − f ⋆ ] + Cσf⋆ + D. This upper bound depends on the global objective gap through C[f (xt ) − f ⋆ ] and on data heterogeneity through Cσf⋆ . The bounded-variance assumption is the special case C = 0 and D = σ 2 , for which the bound contains no explicit heterogeneity term. Assumption 3. Conditionally on FtQ , the server samples St ⊆ [n] uniformly at random without replacement, i.e., P(St = A | FtQ ) = Let Ii,t := 1{i∈St } . By Assumption 3, h i S E Ii,t FtQ = , n

1 n S

,

∀A ⊆ [n],

|A| = S.

h i S(S − 1) E Ii,t · Ij,t FtQ = n(n − 1)

i ̸= j.

Consequently, by the tower property, for any integrable FtQ -measurable random variables Z and {ai }ni=1 , S Et [Z], n S(S − 1) Et [Ii,t · Ij,t Z] = Et [Z] , n(n − 1) " # n 1 X 1X E ai FtQ = ai . S n i=1 Et [Ii,t Z] =

i ̸= j,

(9)

i∈St

Since the round-t virtual trajectories are FtQ -measurable, the randomness of round-t client sampling can be separated from that of the oracles through (9), while the oracle noise is handled through the filtration {Ftℓ }Q ℓ=0 . We also define the sampling factor n−S , S ∈ {1, . . . , n}, n ≥ 2. (10) IS := n−1 C. Heterogeneity Measure and a Counterexample to the BGD Condition Pn Pn Under Assumption 1, the global objective f = n1 i=1 fi is also L-smooth and lower bounded, since f (x) ≥ n1 i=1 fi⋆ for all x ∈ Rd . Let f ⋆ := inf x∈Rd f (x), and define the heterogeneity measure n

σf⋆ := f ⋆ −

1X ⋆ f . n i=1 i

(11)

Pn Equivalently, σf⋆ = inf x∈Rd n1 i=1 [fi (x) − fi⋆ ] is the infimum of the average local objective gap. Hence it is nonnegative and vanishes when the local objectives share a common minimizer. The following lemma, taken from [14, Lemma 1], shows that σf⋆ , together with the functional gap f (x) − f ⋆ , controls the gradient dissimilarity and avoids the need for additional data heterogeneity assumptions.

6

Lemma 1. Let Assumption 1 hold. Then, for every x ∈ Rd n 1X 2 ∥∇fi (x) − ∇f (x)∥ ≤ 2L [f (x) − f ⋆ ] + 2Lσf⋆ . n i=1

(12)

Compared with the BGD condition (3), 2Lσf⋆ plays the role of ζ 2 , and the term 2L[f (x) − f ⋆ ] replaces ψ 2 ∥∇f (x)∥2 . Unlike the constants ζ and ψ, whose existence must be assumed, σf⋆ is always finite under Assumption 1. The following theorem constructs a problem that satisfies Assumption 1 but violates (3) for every pair (ζ, ψ). Hence, Lemma 1 remains applicable where the BGD condition fails. √ Theorem 1. Let n = 2, d = 1, r(x) := 1 + x2 , and p 1 f1 (x) = r(x) + r(x) sin r(x), 2 p 1 f2 (x) = r(x) − r(x) sin r(x). 2 Then f1 and f2 satisfy Assumption 1 with L = 9/4, and σf⋆ ≤ 1/2. However, for any constants ζ, ψ ≥ 0, there exists x ∈ R at which the BGD condition (3) is violated. p Proof. Let u(x) := 12 r(x) sin r(x), so that f1 = r + u, f2 = r − u, and f = 12 (f1 + f2 ) = r. Note that r(x) ≥ 1 for all x ∈ R. We have 1 x ∈ (−1, 1), r′′ (x) = ∈ (0, 1]. r′ (x) = r(x) r(x)3 Lower boundedness. Since |u| ≤ r/2, we have fi ≥ r/2 ≥ 1/2 for i = 1, 2, and hence fi⋆ ≥ 1/2. Moreover, f ⋆ = inf x∈R r(x) = 1, so 1 1 σf⋆ = f ⋆ − (f1⋆ + f2⋆ ) ≤ . 2 2 √ R Smoothness. Let U (R) := 2 sin R for R ≥ 1, so that u = U ◦ r. Direct computation gives √ √ √ 1 R ′ U (R) = sin R + cos R, 2 4 √ √ 1 3 ′′ U (R) = √ cos R − sin R. 8 8 R √ Hence |U ′ (R)| ≤ 1/2 + R/4 and |U ′′ (R)| ≤ 1/2 for R ≥ 1. Since u′ = U ′ (r)r′ , u′′ = U ′′ (r)(r′ )2 + U ′ (r)r′′ , |r′ | < 1, r′′ = r−3 . We obtain  √  1 1 1 r 5 1 1 1 |u′′ (x)| ≤ + 3 + r ≥ 1. ≤ + + = , 2 r 2 4 2 2 4 4 Therefore 1 9 5 |fi′′ (x)| ≤ |r′′ (x)| + |u′′ (x)| ≤ 3 + ≤ , i = 1, 2. r 4 4 Hence, f1 and f2 are L-smooth with L = 9/4. Together with the lower boundedness, Assumption 1 holds. Failure of BGD. Since ∇f1 (x) − ∇f (x) = u′ (x), ∇f2 (x) − ∇f (x) = −u′ (x), ∇f (x) = r′ (x), we have 2

1X 2 2 ∥∇fi (x) − ∇f (x)∥ = |u′ (x)| , 2 i=1 2

ζ 2 + ψ 2 |r′ (x)| ≤ ζ 2 + ψ 2 . We now construct a sequence of points {xk }k≥1 along which the left-hand side of (3) diverges. We define p xk := (2kπ)4 − 1, k ≥ 1. Hence, p

(2kπ)4 − 1 1 ≥√ , (2kπ)2 2 1 kπ kπ U ′ (r(xk )) = sin(2kπ) + cos(2kπ) = . 2 2 2 2

r(xk ) = (2kπ) ,

′

r (xk ) =

Consequently, (kπ)2 . 8 Thus, for any ζ, ψ ≥ 0, (3) is violated at xk whenever k 2 π 2 > 8(ζ 2 + ψ 2 ). 2

2

|u′ (xk )| = [U ′ (r(xk ))r′ (xk )] ≥

7

D. Preliminary Analysis This subsection aims to derive an approximate descent property for Et [f (xt ) − f ⋆ ], from which all convergence results in Section III follow. The main difficulty in deriving such a property is that, within round t, the aggregated direction Gt is affected ℓ by two sources of randomness: the stochastic samples ξi,t , i ∈ St , ℓ = 0, . . . , Q − 1, used in the local updates of the selected clients, which induce stochastic gradient noise, and the random client set St , which induces client-sampling error. These two sources are coupled, since St determines which samples enter Gt . Moreover, neither the noise nor the client-sampling error admits a uniform bound in our setting. Under the ABC condition, the noise variance grows with the local objective gaps fi (xℓi,t ) − fi⋆ . The client-sampling error grows with the dissimilarity of the client gradients at the local iterates, which must be controlled without a BGD-type assumption. We address these difficulties with two key ingredients. First, the virtual trajectories in Section II-A separate these two sources: conditionally on FtQ , Gt is a sample average without replacement from n potential client directions, while the oracle noise ⋆ is handled through {Ftℓ }Q ℓ=0 . Second, Lemma 1 controls the gradient dissimilarity through σf , which removes the need for a BGD-type assumption. The analysis proceeds as follows. Lemma 2 identifies the conditional mean of Gt , and Lemma 3 quantifies the client-sampling PQ−1 error, namely the mean-squared deviation of the sampled average of the accumulated local gradients ℓ=0 ∇fi (e xℓi,t ) from their average over all n clients. Combining them with smoothness, Lemma 4 derives a one-step descent inequality. Its error terms involve three quantities: the local objective gaps, the local drift, and the trajectory gradient dissimilarity. Lemmas 5–7 bound these three quantities, respectively. Lemma 8 then combines these bounds into an approximate descent property for Et [f (xt+1 ) − f ⋆ ], which yields the finite-time and almost sure convergence results in Section III. Lemma 2. Under Assumptions 1, 2 and 3, the conditional mean of Gt satisfies n Q−1

Et [Gt ] =

   1XX  Et ∇fi (e xℓi,t ) = QEt ∇f¯t , n i=1

(13)

ℓ=0

Pn PQ−1 1 where ∇f¯t := nQ xℓi,t ) is the virtual average gradient, i.e., the average of the local gradients along the i=1 ℓ=0 ∇fi (e virtual trajectories over all clients and local steps. Proof. See Appendix A. Thus, client sampling preserves the conditional mean of the full-participation direction. However, Et [Gt ] generally differs from Q∇f (xt ), because the local stochastic gradients are evaluated along the virtual trajectories rather than at xt . This bias stems from local updates rather than client sampling, and it is controlled by the local drift (Lemma 6). Lemma 3 quantifies the sampling error of the accumulated local gradients. Lemma 3. Suppose Assumptions 1, 2 and 3 hold. Define the trajectory gradient dissimilarity, i.e., the gradient dissimilarity accumulated along the virtual trajectories, as   2 Q−1 n 1X  X Ψt := Et ∇fi (e xℓi,t ) − Q∇f¯t  . n i=1 ℓ=0

Then

 Et 

Q−1 1 XX

S

2

∇fi (e xℓi,t ) − Q∇f¯t

i∈St ℓ=0

  = I S Ψt . S

(14)

Proof. See Appendix B. Thus, the client-sampling error is proportional to IS /S and vanishes under full participation (S = n). Combining Lemmas 2 and 3 with smoothness and the ABC condition (8) yields the following one-step descent inequality. Lemma 4. Let Assumptions 1, 2 and 3 hold. Set the stepsize to satisfy αt ≤ 1/(2LQ) for any t ≥ 0. Then, the iterates {xt } generated by Algorithm 1 satisfy: αt Q ∥∇f (xt )∥2 2 Q−1 n  α2 LIS α2 CL X X  + t Et fi (e xℓi,t ) − fi⋆ + t Ψt Sn S i=1

Et [f (xt+1 ) − f ⋆ ] ≤ f (xt ) − f ⋆ −

+ Proof. See Appendix C.

ℓ=0 n Q−1 2 X X

αt L 2n

i=1 ℓ=0

h Et

xt − x eℓi,t

2

i

+

αt2 LQD . S

(15)

8

Lemma 4 reduces the convergence analysis to controlling three error terms: the sum of local objective gaps, the accumulated local drift, and the trajectory gradient dissimilarity Ψt . We bound these quantities in Lemmas 5–7, respectively. Lemma 5. Let Assumptions 1 and 2 hold. We have n Q−1 X X

n Q−1 X X  2 fi (e xℓi,t ) − fi⋆ ≤ 2nQ [f (xt ) − f ⋆ ] + 2nQσf⋆ + L x eℓi,t − xt .

i=1 ℓ=0

(16)

i=1 ℓ=0

Proof. See [14, Lemma 5]. Lemma 6. Let Assumptions 1 and 2 hold. Set the stepsize   1 1 √ αt ≤ min , √ , 2 3QL 2 2QCL We have

Q−1 n XX

h Et

xt − x eℓi,t

2

i

t ≥ 0.

2

≤ 6αt2 Q3 n ∥∇f (xt )∥ + 4αt2 Q3 n(3L + 2C)σf⋆ + 2αt2 Q2 nD

ℓ=0 i=1

(17)

+ 4αt2 Q3 n(2C + 3L) [f (xt ) − f ⋆ ] . Proof. See Appendix D. Lemma 7. Let Ψt be the trajectory gradient dissimilarity defined in Lemma 3. Under Assumptions 1, 2 and 3, Ψt satisfies n Q−1

Ψt ≤

i 2QL2 X X h ℓ 2 Et x ei,t − xt + 4Q2 Lσf∗ + 4Q2 L [f (xt ) − f ⋆ ] . n i=1

(18)

ℓ=0

Proof. See Appendix E. Substituting the estimates from Lemmas 5–7 into the recursion of Lemma 4 yields the following approximate descent property of Et [f (xt+1 ) − f ⋆ ]. Lemma 8. Let Assumptions 1, 2 and 3 hold. Set αt ≤

1 , 8Q(L + C)

t ≥ 0.

Then the iterates generated by Algorithm 1 satisfy   2αt2 QCL 4αt2 Q2 L2 IS αt Q 2 ⋆ 3 3 2 Et [f (xt+1 ) − f ] ≤ 1 + + + 12αt Q L (L + C) [f (xt ) − f ⋆ ] − ∥∇f (xt )∥ S S 4   α2 LQD(1 + 2αt QLS) 2αt2 Q2 Lσf⋆ C + t + 2LIS + + 12αt3 Q3 L2 (L + C)σf⋆ . S S Q

(19)

Proof. See Appendix F. III. M AIN R ESULTS In this section, we establish two complementary stationarity guarantees for FedAvg under partial participation. Theorem 2 provides a finite-time bound on the smallest expected squared gradient norm over a prescribed horizon when a constant stepsize is used, whereas Theorem 3 establishes convergence of the gradient norm along the full sequence, both in expectation and almost surely, under a diminishing stepsize sequence. Theorem 2. Let Assumptions 1, 2 and 3 hold. Set αt = α to satisfy s (  1/3 ) 1 S 1 α ≤ min , , . 8Q(L + C) 4T Q2 L(2LIS + C/Q) 24Q3 L2 (L + C)T Define ∆f := f (x0 ) − f ⋆ . Then the iterates generated by Algorithm 1 satisfy h i 12∆ 4αL(D + 2Cσf⋆ ) f 2 min E ∥∇f (xt )∥ ≤ + t=0,1,...,T −1 αQT S   16αQL2 IS σf⋆ D + + 8α2 Q2 L2 6(L + C)σf⋆ + . S Q

(20)

(21)

9

In particular, if we set ∆f > 0 and s LQT (D + 2Cσf⋆ + 4LQIS σf⋆ ) α= + 3S∆f where

r β = 8Q(L + C) +

Q3 L2 T [6(L + C)σf⋆ + D/Q] 3∆f

!1/3

−1 (22)

+ β

4T Q2 L(2LIS + C/Q) + [24Q3 L2 (L + C)T ]1/3 . S

(23)

Then, s h

min

E ∥∇f (xt )∥



2

t=0,1,...,T −1

+

(L∆f ) ∆f (L + C) T2

2

i

= O

1/3 +

L∆f (D + Cσf⋆ + C∆f ) SQT

(L∆f )2 [(L + C)σf⋆ + D/Q] T2

  q (L + C)∆f + L ∆f + ∆f σf⋆ T  !

+

1/3

r

IS ST (24)

,

where O(·) hides numerical constants. Proof of Theorem 2. See Appendix G. Remark 2. When S = n, we have IS = 0, and all sampling-induced terms in (24) vanish. The leading term then becomes q O( L∆f (D + Cσf⋆ + C∆f )/(nQT )), which exhibits a linear speedup in both the number of clients n and the number of √ local updates Q, and has the same O(1/ nQT ) dependence as the full-participation FedAvg result under the ABC condition in [14]. √ Remark 3. For S < n, both leading terms in (24) scale as 1/ ST , so the bound retains a linear speedup in S. The speedup in persists only when the noise-induced term dominates. q Specifically, the sampling-induced term O(L(∆f + q Q, however, p ⋆ ∆f σf ) IS /(ST )) in (24) dominates the noise-induced term O( L∆f (D + Cσf⋆ + C∆f )/(SQT )) when IS ≥ ν/Q, where   D + C σf⋆ + ∆f , ν := p p 2 L ∆f + σf⋆ or equivalently, 1≤S ≤n−

ν(n − 1) . Q

Here, ν can be viewed as a noise-to-dissimilarity ratio: with f (x) − f ⋆ replaced by ∆f , its numerator is the average variance bound C[f (x) − f ⋆ + σf⋆ ] + D implied by the ABC condition, and its denominator is the dissimilarity bound 2L[f (x) − f ⋆ + σf⋆ ] in Lemma 1, up to a factor of two. This regime is empty when ν > Q. Remark 4. Existing analyses of FedAvg with partial participation for smooth nonconvex objectives [10] assume bounded √ variance and the BGD condition p (3). Besides the stochastic gradient term O(1/ SQT ), their leading-order terms contain a sampling-induced term O(IS ζ 2 Q/(ST )) (Table I). q In contrast, (24) holds under the ABC condition without BGD-type p √ assumptions, and its sampling-induced terms O(L(∆f + ∆f σf⋆ ) IS /(ST )) carry no Q factor. Hence, in our bound, more local updates do not amplify the cost of client sampling. Section IV-C examines this numerically. We now turn from finite-horizon guarantees to the asymptotic behavior of FedAvg under diminishing stepsizes. This complements Theorem 2, which controls only the best iterate over a finite horizon. Theorem 3. Let Assumptions 1, 2 and 3 hold, and ∀t ≥ 0, let the stepsizes satisfy 0 < αt ≤

1 , 8Q(L + C)

∞ X

αt = ∞,

t=0

∞ X

αt2 < ∞.

t=0

Then the iterates generated by Algorithm 1 satisfy lim E [∥∇f (xt )∥] = 0

t→∞

Proof of Theorem 3. See the supplementary material.

and

lim ∥∇f (xt )∥ = 0

t→∞

a.s.

10

IV. N UMERICAL E XPERIMENTS This section illustrates three implications of our analysis. Section IV-A studies how the number of sampled clients S affects convergence under the ABC condition. Section IV-B constructs instances with nearly identical BGD parameters but different values of σf⋆ , and examines how this heterogeneity interacts with partial participation. Section IV-C tests whether the sampling-induced error grows with the number of local updates Q when αQ is fixed. A. Effect of the Participation Level We first examine how the participation level S affects the convergence of FedAvg under the ABC condition. Following [14], we consider n = 16 clients with heterogeneous local objectives ( 2 x , |x| < 1, f1 (x) = 2 1 |x| − 2 , otherwise, (25)
x−i+1 fi (x) = ln 1 + e , i = 2, 3, . . . , 16, where f1 is the Huber function and ln(1 + ex ) is the softplus function [43]. The stochastic gradient oracles are ( p ∇f1 (x) + |x|, ξ = 0, p g1 (x; ξ) = ∇f1 (x) − |x|, ξ = 1, ( p ∇fi (x) + fi (x), ξ = 0, p i = 2, 3, . . . , 16, gi (x; ξ) = ∇fi (x) − fi (x), ξ = 1,

(26)

where ξ ∈ {0, 1} is a Bernoulli random variable with P(ξ = 0) = P(ξ = 1) = 1/2 drawn independently across clients, local steps, and communication rounds. Since |x| ≤ f1 (x) + 1/2 and fi⋆ = 0 for all i, Assumptions 1 and 2 hold with L = 1, C = 1, and D = 1/2. In contrast, the relaxed growth condition fails [14]. We run FedAvg with T = 50000, Q = 5, α = 0.001 and x0 = 10, sampling S ∈ {1, 4, 8, 16} clients uniformly without replacement, where S = 16 corresponds to full participation. Results are averaged over R = 100 independent trials, and f ⋆ is estimated by a fine one-dimensional grid search.Figure 1 shows convergence in terms of f (xt ) − f ⋆ under different participation levels. The full-participation case S = 16 gives the smallest function value gap, while smaller values of S lead to larger objective gaps. This confirms the theoretical prediction of Theorem 2.

Fig. 1. Performance of FedAvg on problem (25) with Q = 5, α = 0.001, and different participation levels S ∈ {1, 4, 8, 16}. The curves are averages over 100 independent trials.

B. Heterogeneity Measure versus BGD Parameters In this part, we examine whether σf⋆ captures changes in optimization behavior that the BGD parameters do not reflect. To this end, we construct a family of problems for which the optimized BGD sum, i.e., the smallest value of ζ 2 + ψ 2 such that (3) holds, remains nearly constant, whereas σf⋆ varies substantially. We then study how this variation interacts with the participation level in FedAvg. We consider n = 40 clients with Huber objectives centered at random offsets di : ( (x−di )2 , |x − di | < 1, 2 fi (x) = i = 1, 2, . . . , n, (27) 1 |x − di | − 2 , otherwise, where d1 = d2 = 0 and d3 , . . . , dn are drawn independently from U [0, Dmax ]. The parameter Dmax ∈ {20, 50, 100, 200} controls the minimizers di of the local objectives. Since fi⋆ = 0 for all i, we have σf⋆ = f ⋆ . For each Dmax , we compute σf⋆ and the optimized BGD sum on the same sampled offsets.

11

All instances share the stochastic gradient oracle gi (x; ξ) = ∇fi (x) + εξ

q

fi (x) − fi⋆ ,

where εξ is a random variable that satisfies P(εξ = 1) = P(εξ = −1) = 1/2. It is drawn independently across clients, local steps, communication rounds, and runs. This oracle is unbiased with variance fi (x) − fi⋆ , so Assumptions 1 and 2 hold with L = 1, C = 1, and D = 0. We run FedAvg with S ∈ {4, 20, 40}, Q = 10, the fixed stepsize α = 0.0001, and T = 50000 communication rounds, where S = 40 corresponds to full participation. All runs start from x0 = x⋆ + 10, where x⋆ is a minimizer of f , so that the initial distance to x⋆ is the same for all Dmax . Each configuration is repeated over 100 independent runs. Table II reports the two heterogeneity measures together with the last-iterate gap f (xT ) − f ⋆ . As Dmax increases from 20 to 200, σf⋆ grows from 4.8 to 52.7, whereas the optimized BGD sum stays almost unchanged between 0.956 and 0.998. Meanwhile, the last-iterate gap increases with Dmax for every S. Hence the change in optimization behavior is reflected by σf⋆ but not by the BGD parameters. Figure 2 plots the corresponding trajectories in Table II. In each subplot, a larger Dmax TABLE II O PTIMIZED BGD PARAMETERS ζ 2 + ψ 2 , HETEROGENEITY MEASURE σf⋆ , AND LAST- ITERATE GAP f (xT ) − f ⋆ ON PROBLEM (27) (n = 40, Q = 10) Dmax

20 50 100 200

ζ 2 + ψ2

0.956 0.998 0.998 0.998

σf⋆

4.838 12.809 26.096 52.675

f (xT ) − f ⋆ S=4

S = 20

S = 40

9.31 × 10−4 1.34 × 10−3 2.38 × 10−3 4.51 × 10−3

1.28 × 10−4 2.34 × 10−4 3.75 × 10−4 7.96 × 10−4

2.76 × 10−5 7.23 × 10−5 1.65 × 10−4 3.12 × 10−4

slows the decrease of the objective gap and leads to a higher residual. Increasing S from 4 to 40 lowers the residual for every Dmax . Both observations are consistent with Theorem 2: σf⋆ enters the error terms, and the sampling-induced terms decrease as S increases.

Fig. 2. Objective gap f (xt ) − f ⋆ on problem (27) for (a) S = 4, (b) S = 20, and (c) S = 40, with Dmax ∈ {20, 50, 100, 200}.

C. Effect of the Number of Local Updates This part examines whether the local updates amplify the sampling-related error in the leading term. Motivated by the Qdependence discussed after Theorem 2, we consider Problem (27) with Dmax = 200 and compare partial participation (S = 4) with full participation (S = 40). For both participation levels, we set Q ∈ {3, 5, 8, 10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200}. For a fair comparison, the stepsize is set as α = γ/Q with a fixed constant γ = 10−2 . Each configuration runs for T = 100000 communication rounds and repeated over 100 independent trials. (S,Q) 2 Figure 3(a) reports the terminal stationarity residual RS (Q) := E[∥∇f (xT )∥ ] for S ∈ {4, 40}, where the expectation is estimated by averaging over the 100 independent trials. It is observed that the residual RS (Q) decreases with increasing Q for both participation levels. Moreover, partial participation (S = 4) consistently yields a larger terminal residual than full participation (S = n = 40), which is consistent with Theorem 2. √ To further test whether the sampling-induced leading term grows as Q or is independent of Q, we plot the scaled residual √
√ √ SRS (Q) − nRn (Q) T q DQ := , (28) √ L(∆f + ∆f σf⋆ ) IS

12

√ √ √ against Q in Figure 3(b). The difference q SRS (Q) − nRn (Q) is designed to cancel the leading term O(1/ SQT ) in (24). p Then, if the sampling term is O(L(∆f + ∆f σf⋆ ) IS /(ST )) as in Theorem 2, DQ should be approximately constant in Q. √ As shown in Figure 3(b), the scaled √ residual DQ does not follow the Q trend. This indicates that partial participation FedAvg does not exhibit an additional Q amplification in the leading-order sampling term, which is consistent with the theoretical prediction of Theorem 2.

Fig. 3. Dependence on the number of local updates Q under αQ = γ on problem (27) with Dmax = 200. (a) Terminal residual RS (Q) = E[∥∇f (xT )∥2 ] for S = 4 and S = n = 40. (b) Normalized residual DQ with the Q0 and Q1/2 reference trends. Error bars denote 95% confidence intervals over 100 independent runs.

V. C ONCLUSION In this work, we study FedAvg with partial participation for smooth nonconvex objective functions under the ABC variance condition. Our analysis accommodates multiple local updates and uniform client sampling without replacement, without imposing additional data heterogeneity conditions, such as the bounded gradient dissimilarity assumption. An example further demonstrates that this assumption is not implied by smoothness and lower boundedness. For a constant stepsize, we establish a finite-time bound on the smallest expected squared gradient norm over a prescribed horizon. This bound shows that partial participation introduces an additional sampling-induced error, which vanishes under full participation and, unlike existing BGDbased bounds, does not grow with the number of local updates. Under a diminishing stepsize sequence, we further establish that the gradient norm converges to zero along the full sequence, both in expectation and almost surely. Numerical simulations illustrate our theoretical findings. ACKNOWLEDGMENTS A PPENDIX P ROOFS ℓ ℓ Throughout the appendix, we write gi,t := gi (e xℓi,t ; ξi,t ) for the stochastic gradient along the virtual trajectory of client i at local step ℓ of round t, where i ∈ [n], t ≥ 0, and ℓ ∈ {0, . . . , Q − 1}. We also define the stochastic gradient noise ℓ ℓ ℓ ℓ 2 δi,t := gi,t − ∇fi (e xℓi,t ). By Assumption 2, E[δi,t |Ftℓ ] = 0 and E[∥δi,t ∥ |Ftℓ ] ≤ C[fi (e xℓi,t ) − fi⋆ ] + D almost surely. In this P P Q−1 ℓ . notation, Gt = S1 i∈St ℓ=0 gi,t

A. Proof of Lemma 2 Pn PQ−1 ℓ . Proof. By the definition of the update rule, Gt can be expressed using the indicator variable Ii,t as Gt = S1 i=1 Ii,t ℓ=0 gi,t Since St is drawn uniformly from all subsets of [n] with cardinality S, we have Et [Ii,t ] = S/n for each client i; see (9). Taking the expectation Et , we obtain: " # " # Q−1 Q−1 n n X X 1X 1X ℓ ℓ (29) Et [Gt ] = Et Ii,t δi,t + Et Ii,t ∇fi (e xi,t ) . S i=1 S i=1 ℓ=0

ℓ=0

13

ℓ is Ftℓ+1 ⊆ FtQ -measurable, so the first identity in (9) removes the sampling The first term vanishes. Indeed, the noise δi,t indicator. The unbiasedness in Assumption 2 then gives " # Q−1 n n Q−1 X 1X 1 SXX  ℓ  ℓ Et Ii,t δi,t = · Et δi,t S i=1 S n i=1

=

ℓ=0 Q−1 n XX

1 n i=1

ℓ=0

  ℓ  Ftℓ = 0. Et E δi,t

ℓ=0

Regarding the second term in (29), each ∇fi (e xℓi,t ) is FtQ -measurable. Applying the first identity in (9), we obtain # " Q−1 n n Q−1 X   1 SXX 1X ℓ Ii,t ∇fi (e xi,t ) = · Et [∇fi (e xℓi,t )] = QEt ∇f¯t . Et S i=1 S n i=1 ℓ=0

ℓ=0

Combining the identities for the two terms in (29), we obtain the desired result. B. Proof of Lemma 3 Proof. For i ∈ [n], define bi,t :=

Q−1 X

∇fi (e xℓi,t ) −

ℓ=0

n Q−1

Q−1

ℓ=0

ℓ=0

X 1XX ∇fj (e xℓj,t ) = ∇fi (e xℓi,t ) − Q∇f¯t , n j=1

h i Pn P 2 E ∥b ∥ . Since i=1 Ii,t = i∈St 1, we have i,t i=1 t

Pn 1

so that Ψt = n

Q−1 n Q−1 n 1XX 1X 1 XX ∇fi (e xℓi,t ) − ∇fi (e xℓi,t ) = Ii,t bi,t . S n i=1 S i=1 i∈St ℓ=0

ℓ=0

Hence, expanding the squared norm gives   2 Q−1 n Q−1 X X X X 1 1 ∇fi (e xℓi,t )  Et  ∇fi (e xℓi,t ) − S n i=1 i∈St ℓ=0 ℓ=0   " n # X X 1 1 2 = 2 Et Ii,t ∥bi,t ∥ + 2 Et  Ii,t Ij,t ⟨bi,t , bj,t ⟩ S S i=1 i̸=j   " n # X X 1 S S(S − 1) 1 2 = 2 Et Et  ⟨bi,t , bj,t ⟩ . ∥bi,t ∥ + 2 S n S n(n − 1) i=1 i̸=j

Here, the second equality uses I2i,t = Ii,t the first two identities in (9), which apply because every bi,t is FtQ -measurable. Pand n For the cross summation, observe that i=1 bi,t = 0. Therefore, 0=

n X i=1

Thus,



2

bi,t

=

n X i=1

2

∥bi,t ∥ +

X

⟨bi,t , bj,t ⟩ .

i̸=j

Q−1 n Q−1 1XX 1 XX ℓ  ∇fi (e xi,t ) − ∇fi (e xℓi,t ) Et S n i=1 i∈St ℓ=0 ℓ=0 #   "X n 1 S S(S − 1) 2 = 2 − Et ∥bi,t ∥ S n n(n − 1) i=1 " n # n−S 1X IS 2 = Et ∥bi,t ∥ = Ψt , S(n − 1) n i=1 S

which completes the proof.

2

 

14

C. Proof of Lemma 4 Proof. By the L-smoothness of f and the update rule xt+1 = xt − αt Gt , we have: Et [f (xt+1 )] ≤ f (xt ) − αt Et [⟨∇f (xt ), Gt ⟩] +

i Lαt2 h 2 Et ∥Gt ∥ . 2

(30)

Applying Lemma 2 to the inner product leads to   − αt Et [⟨∇f (xt ), Gt ⟩] = −αt QEt ∇f (xt ), ∇f¯t i αQ i αt Q h αt Q h 2 2 t 2 Et ∇f (xt ) − ∇f¯t − ∥∇f (xt )∥ − Et ∇f¯t = 2 2 2 n Q−1 i i α Q αt Q h αt L2 X X h 2 2 t 2 Et xt − x eℓi,t − ∥∇f (xt )∥ − Et ∇f¯t , ≤ 2n i=1 2 2

(31)

ℓ=0

where we invoked the L-smoothness of each fi . Regarding the last term in (30), it follows from the same decomposition as in (29) that     2 2 Q−1 n h i X X Q−1 X X 1 1 2 ℓ . Et ∥Gt ∥ ≤ 2Et  ∇fi (e xℓi,t )  + 2Et  Ii,t δi,t S S i=1 i∈St ℓ=0

(32)

ℓ=0

Note that Q∇f¯t is FtQ -measurable. By the last identity in (9), " # Q−1 1 XX Q ℓ E ∇fi (e xi,t ) Ft = Q∇f¯t . S i∈St ℓ=0

Therefore, X Q−1 X

"* Et

1 Q∇f¯t , S

+# ∇fi (e xℓi,t ) − Q∇f¯t

= 0.

i∈St ℓ=0

Then, the first term in (32) can be bounded as follows.     2 2 h i X X X Q−1 X Q−1 1 1 2 2Et  ∇fi (e xℓi,t )  = 2Q2 Et ∇f¯t + 2Et  ∇fi (e xℓi,t ) − Q∇f¯t  S S (33) i∈St ℓ=0 i∈St ℓ=0 h i 2I 2 S = 2Q2 Et ∇f¯t + Ψt , S where the second equality follows from Lemma 3. ℓ As for the second term in (32), each δi,t is Ftℓ+1 ⊆ FtQ -measurable. We first remove the sampling indicators and then show that all cross terms vanish. By the first two identities in (9), for all i, j ∈ [n] and ℓ, r ∈ {0, . . . , Q − 1},    ℓ r  ℓ r Et Ii,t Ij,t δi,t , δj,t = cij Et δi,t , δj,t , ( S i = j, n, cij : = S(S−1) n(n−1) , i ̸= j. ℓ If r > ℓ, then δi,t is Ftr -measurable, and Assumption 2 gives  ℓ r   ℓ  r   Et δi,t , δj,t = Et δi,t , E δj,t Ftr = 0. ℓ ℓ If r = ℓ and i ̸= j, then δi,t and δj,t are conditionally independent given Ftℓ due to Assumption 2. Then,   ℓ   ℓ    ℓ ℓ  Ftℓ = 0. Et δi,t , δj,t = Et E δi,t Ftℓ , E δj,t

Therefore, only the diagonal terms i = j, r = ℓ remain, and the ABC condition (8) yields   2 Q−1 n Q−1 i X X X X h 1 2 ℓ ℓ = 2 ·S 2Et  δi,t Et δi,t 2 S S n i=1 i∈St ℓ=0

=

n Q−1 X X

2 nS i=1

ℓ=0

h h ii 2 ℓ Et E δi,t Ftℓ

ℓ=0

n Q−1    2 XX ≤ CEt fi (e xℓi,t ) − fi⋆ + D . nS i=1 ℓ=0

(34)

15

Substituting (31)–(34) into (30) yields i αt Q αt Q h 2 2 ∥∇f (xt )∥ − Et ∇f¯t 2 2 n Q−1 i h i αt L2 X X h ℓ 2 2 + LQ2 αt2 Et ∇f¯t + Et x ei,t − xt 2n i=1

Et [f (xt+1 )] ≤ f (xt ) −

ℓ=0

+

αt2 LIS S

n Q−1  α2 LQD αt2 LC X X  Ψt + Et fi (e . xℓi,t ) − fi⋆ + t Sn i=1 S ℓ=0

Letting αt ≤ 1/(2LQ) yields the desired result. D. Proof of Lemma 6 Proof. Recall that the virtual local trajectory is initialized at x e0i,t = xt and satisfies ℓ x eℓ+1 eℓi,t − αt gi,t , i,t = x

ℓ = 0, . . . , Q − 1.

Unrolling the recursion gives x eℓi,t − xt = −αt

ℓ−1 h i X j δi,t + ∇fi (e xji,t ) .

(35)

j=0

Hence,

 1 Et 2αt2

h

i 2

x eℓi,t − xt

 ≤ Et 

ℓ−1 X

2 j δi,t





   + Et 

j=0

ℓ−1 X

2

∇fi (e xji,t )

  

j=0



ℓ−1  X j δi,t ≤ Et 

2

(36)

  +ℓ

ℓ−1 X

 Et

∇fi (e xji,t )

2

 .

j=0

j=0

Following similar derivations as in (34), the first term in (36) can be bounded as follows:   2   ℓ−1 ℓ−1 ℓ−1 h i X X 2  X  j j Et  δi,t = E δ ≤ C Et fi (e xji,t ) − fi⋆ + ℓD.  t i,t j=0

j=0

(37)

j=0

Hence,   ℓ−1 ℓ−1 h i h i X X 2 1 2 j j ℓ ⋆ Et x ei,t − xt Et fi (e ≤ C xi,t ) − fi + ℓD + ℓ Et ∇fi (e xi,t ) . 2αt2 j=0 j=0

(38)

Summing (38) over i = 1, . . . , n and ℓ = 0, . . . , Q − 1 yields Q−1 n XX

h Et

2

x eℓi,t − xt

i

≤ αt2 Q2

Q−1 n XX

ℓ=0 i=1

h Et

∇fi (e xℓi,t )

2

i

+ αt2 Q2 nD + 2αt2 QC

ℓ=0 i=1

Q−1 n XX

  Et fi (e xℓi,t ) − fi⋆

ℓ=0 i=1

≤ αt2 Q2 nD + 4αt2 Q2 nCσf⋆ + 4αt2 Q2 nC [f (xt ) − f ⋆ ] + 2αt2 QCL

n Q−1 X X

h Et

x eℓi,t − xt

2

i

(39)

i=1 ℓ=0

+ αt2 Q2

Q−1 n XX

h Et

2

∇fi (e xℓi,t )

i

,

ℓ=0 i=1

where we invoked Lemma 5. We now bound the last term in (39). Noting   ∇fi (e xℓi,t ) = ∇fi (e xℓi,t ) − ∇fi (xt ) + [∇fi (xt ) − ∇f (xt )] + ∇f (xt ),

(40)

it follows from the L-smoothness of fi that Q−1 Q−1 n n n h i h i XX XX X 2 2 2 ℓ 2 ℓ 2 Et ∇fi (e xi,t ) ≤ 3L Et x ei,t − xt + 3Qn∥∇f (xt )∥ + 3Q ∥∇fi (xt ) − ∇f (xt )∥ ℓ=0 i=1

ℓ=0 i=1 2

≤ 3L

Q−1 n XX ℓ=0 i=1

h Et

x eℓi,t − xt

i 2

i=1 2

+ 3Qn∥∇f (xt )∥ + 6QnL [f (xt ) − f

⋆

] + 6QnLσf⋆ ,

(41)

16

where we invoked Lemma 1. Substituting (41) into (39) and rearranging the terms, we obtain n i h XX
Q−1 2 Et x eℓi,t − xt 1 − 3αt2 Q2 L2 − 2αt2 QCL ℓ=0 i=1 2 3 2 2 3 ≤ 3αt Q n∥∇f (xt )∥ + 2αt Q n(2C + 3L) [f (xt ) − f ⋆ ] + 2αt2 Q3 n(3L + 2C)σf⋆ + αt2 Q2 nD.

(42)

Invoking the stepsize condition yields the desired result. E. Proof of Lemma 7 Pn Pn Pn Proof. For any vectors {ai }ni=1 with mean ā = n1 i=1 ai and any c ∈ Rd , we have n1 i=1 ∥ai − ā∥2 ≤ n1 i=1 ∥ai − c∥2 . PQ−1 Applying this with ai = ℓ=0 ∇fi (e xℓi,t ), for which ā = Q∇f¯t , and c = Q∇f (xt ), and then taking Et , gives     2 2 Q−1 Q−1 n n X X 1 1X  X (43) Ψt = ∇fi (e xℓi,t ) − Q∇f¯t  ≤ ∇fi (e xℓi,t ) − Q∇f (xt )  . Et Et  n i=1 n i=1 ℓ=0

ℓ=0

Noting Q−1 X

Q−1 X

ℓ=0

ℓ=0

∇fi (e xℓi,t ) − Q∇f (xt ) =

we obtain

  ∇fi (e xℓi,t ) − ∇fi (xt ) + Q [∇fi (xt ) − ∇f (xt )] ,

  2 Q−1 n n  2X  X 2Q2 X 2 Ψt ≤ Et ∇fi (e xℓi,t ) − ∇fi (xt )  + ∥∇fi (xt ) − ∇f (xt )∥ n i=1 n i=1 ℓ=0

≤

n Q−1 2 X X

2QL n

h Et

x eℓi,t − xt

2

i

+ 4Q2 L [f (xt ) − f ⋆ ] + 4Q2 Lσf⋆ ,

i=1 ℓ=0

where we invoked the Cauchy–Schwarz inequality and the L-smoothness of fi for the first term, and Lemma 1 for the second term. This completes the proof. F. Proof of Lemma 8 Proof. Substituting the estimates from Lemmas 5 and 7 into (15) yields   2α2 QCL 4αt2 Q2 L2 IS Et [f (xt+1 ) − f ⋆ ] ≤ 1 + t + [f (xt ) − f ⋆ ] S S   n Q−1 i 2αt C 4αt LQIS X X h ℓ αt L2 2 Et x ei,t − xt 1+ + + 2n S S i=1 ℓ=0   2 2 ⋆ αt2 LQD 2αt Q Lσf C αt Q 2 + + 2LIS + − ∥∇f (xt )∥ . S S Q 2

(44)

Noting that αt ≤ 1/[8Q(L + C)] and IS ≤ 1, it follows that 1+

2αt C 4αt QLIS + ≤ 2, S S

t ≥ 0.

Invoking (17) leads to   2αt2 QCL 4αt2 Q2 L2 IS α2 LQD(1 + 2αt QLS) 3 3 2 Et [f (xt+1 ) − f ] ≤ 1 + + 12αt Q L (L + C) + [f (xt ) − f ⋆ ] + t S S S  2 2 ⋆ 
2αt Q Lσf C αt Q 2 + 2LIS + + 12αt3 Q3 L2 (L + C)σf⋆ − 1 − 12αt2 Q2 L2 ∥∇f (xt )∥ . S Q 2 √ Letting αt ≤ 1/(2 6QL) yields the desired result. ⋆

(45)

17

G. Proof of Theorem 2 Proof. The proof of Theorem 2 relies on Lemma 8 and the following result from [44]. Lemma 9 (Lemma 6, [44]). Suppose that there exist constants a, b, c ≥ 0 and nonnegative sequences {st }Tt=0 , {qt }Tt=0 such that for any t satisfying 0 ≤ t ≤ T , we have the recursion st+1 ≤ (1 + a)st − bqt + c. Then, the following holds: min

t=0,1,...,T −1

qt ≤

(1 + a)T c s0 + . bT b

To apply Lemma 9, we set h i αQ 2 qt = E ∥∇f (xt )∥ , b = 4   α2 LQD(1 + 2αQLS) 2α2 Q2 Lσf⋆ C c= + 2LIS + + 12α3 Q3 L2 (L + C)σf⋆ , S S Q 2α2 QCL 4α2 Q2 L2 IS + + 12α3 Q3 L2 (L + C). a= S S

st = E[f (xt ) − f ⋆ ],

Letting (s α ≤ min

S , 2 4T Q L(2LIS + C/Q)



1 3 2 24Q L (L + C)T

1/3 )

leads to T

(1 + a) ≤ exp(aT ) ≤ exp(1) ≤ 3. Therefore, from Lemma 9, we have h i 12∆ 4αLD f 2 + E ∥∇f (xt )∥ ≤ t=0,1,...,T −1 αQT S     8αQLσf⋆ C D 2 2 2 ⋆ + 2LIS + + 8α Q L 6(L + C)σf + , S Q Q min

which proves (21). For the choice of α in (22), we have s r L∆f (D + 2Cσf⋆ + 4LQIS σf⋆ ) 4L∆f (2L∆f IS + C∆f /Q) ∆f = + αQT 3SQT ST !1/3  1/3 (L∆f )2 [6(L + C)σf⋆ + D/Q] 24(L∆f )2 ∆f (L + C) 8(L + C)∆f + + , + T2 T 3T 2 !2/3 3L∆f 2 2 2 α Q L ≤ . T [6(L + C)σf⋆ + D/Q]

(46)

(47)

Substituting (47) into (46) yields (24).

H. Proof of Theorem 3 Proof. The proof relies on Lemma 8 and the following result, which we apply with Φ := ∇f , xk := xt , µk := αt , and the filtration {Ft }t≥0 . Lemma 10 ( [45, Theorem 2.1]). Let the mapping Φ : Rd → Rm and the sequences {xk }k≥0 ⊆ Rd and {µk }k≥0 ⊆ R++ be given. Consider the following conditions. (P.1) The function Φ is LΦ -Lipschitz continuous for some LΦ > 0, i.e., ∥Φ(x) − Φ(y)∥ ≤ LΦ ∥x − y∥ for all x, y ∈ Rd . P∞ (P.2) There exists a constant a > 0 such that k=0 µk E[∥Φ(xk )∥a ] < ∞. The following statements are valid. i) Let (P.1)–(P.2) hold and suppose further that (P.3) there exist constants A, B, b ≥ 0 and p1 , p2 , q > 0 such that E[∥xk+1 − xk ∥q ] ≤ Aµpk1 + Bµpk2 E[∥Φ(xk )∥b ];

18

P∞ (P.4) {µk }k≥0 is bounded, k=0 µk = ∞, a, q ≥ 1, a ≥ b, and p1 , p2 ≥ q. Then limk→∞ E[∥Φ(xk )∥] = 0. ii) Let (P.1)–(P.2) hold and assume further that (P.3’) there exist constants A, b ≥ 0, p1 , p2 , q > 0 and random vectors Ak , B k such that xk+1 = xk + µpk1 Ak + µpk2 B k , where, for all k, Ak and B k are Fk+1 -measurable, E [Ak |Fk ] = 0 almost surely, E[∥Ak ∥q ] ≤ A, and q lim supk→∞ ∥Φ(xk )∥b ) < ∞ almost surely; P∞∥B k ∥ /(1 +P ∞ 1 (P.4’) µk → 0, k=0 µk = ∞, k=0 µ2p < ∞, q ≥ 2, qa ≥ b, p1 > 12 , and p2 ≥ 1. k Then limk→∞ ∥Φ(xk )∥ = 0 almost surely. a) Verification of (P.1): Since each fi is L-smooth, so is f . Hence, Φ = ∇f is L-Lipschitz continuous. b) Verification of (P.2): Since αt ≤ 1/[8Q(L + C)], we have 12αt3 Q3 L2 (L + C) ≤ 32 αt2 Q2 L2 and 2αt QLS ≤ S/4. Hence, (19) in Lemma 8 gives
αt Q 2 (48) Et [f (xt+1 ) − f ⋆ ] ≤ 1 + K1 αt2 [f (xt ) − f ⋆ ] − ∥∇f (xt )∥ + K2 αt2 , 4 where 3 2QL (C + 2QLIS ) + Q2 L2 , K1 := S  2  1 1 + + K1 σf⋆ K2 := LQD S 4 P∞ are independent of t. Since t=0 αt2 < ∞, the Robbins–Siegmund theorem [46] implies that f (xt ) converges almost surely to a finite random variable. Taking total expectations in (48) and discarding the gradient term gives E[f (xt+1 ) − f ⋆ ] ≤ (1 + K1 αt2 )E[f (xt ) − f ⋆ ] + K2 αt2 . Iterating this inequality and using 1 + u ≤ exp(u) yields ! ! ∞ ∞ X X ⋆ 2 2 sup E [f (xt ) − f ] ≤ M := exp K1 αt ∆f + K 2 αt < ∞. t≥0

t=0

t=0

Taking total expectations in (48) again, summing over t = 0, . . . , T , and using E[f (xT +1 ) − f ⋆ ] ≥ 0, we obtain T ∞ h i X QX 2 αt E ∥∇f (xt )∥ ≤ ∆f + (K1 M + K2 ) αt2 . 4 t=0 t=0

Letting T → ∞ shows that (P.2) holds with a = 2. By (32), (33) and (34), n Q−1 h i h i 2I  
2 XX 2 S 2 CEt fi (e xℓi,t ) − fi⋆ + D . Et ∥Gt ∥ ≤ 2Q2 Et ∇f¯t Ψt + + S nS i=1 ℓ=0

Adding and subtracting ∇fi (xt ) inside ∇f¯t , and using Jensen’s inequality and the L-smoothness of fi , we have 2Q2 Et

h

∇f¯t

2

i

2

≤ 4Q2 ∥∇f (xt )∥ +

n Q−1 i 4QL2 X X h ℓ 2 Et x ei,t − xt . n i=1 ℓ=0

Substituting these estimates, together with Lemma 7 for Ψt and Lemma 5, we obtain   n Q−1 h i i 2QLIS + C X X h ℓ 2L 2 2 2 2QL + Et x ei,t − xt Et ∥Gt ∥ ≤ 4Q2 ∥∇f (xt )∥ + n S i=1 ℓ=0   2QD 4Q (2QLIS + C) f (xt ) − f ⋆ + σf⋆ + . + S S Since IS ≤ 1 and S ≥ 1, the coefficient of the drift term is at most 2L(4QL + C)/n. Moreover, αt ≤ 1/(8Q(L + C)) implies 2L(4QL + C)αt2 Q2 ≤ Q/8. Hence, by Lemma 6, n Q−1 i 3Q2 2L(4QL + C) X X h ℓ 2 2 Et x ei,t − xt ≤ ∥∇f (xt )∥ n 4 i=1 ℓ=0

 QD Q2 (2C + 3L)  + f (xt ) − f ⋆ + σf⋆ + . 2 4 Combining the two displays with ∥∇f (xt )∥2 ≤ 2L[f (xt ) − f ⋆ ] yields h i 2 Et ∥Gt ∥ ≤ K3 + K4 [f (xt ) − f ⋆ ] ,

(49)

19

where

   4Q Q2 1 2 (2QLIS + C) + (2C + 3L) σf⋆ + QD + , S 2 S 4 19 2 Q2 4Q K4 := Q L+ (2QLIS + C) + (2C + 3L) 2 S 2 are independent of t. Consequently, supt≥0 E[∥Gt ∥2 ] ≤ K3 + K4 M < ∞. c) Verification of (P.3) and (P.4): Since xt+1 − xt = −αt Gt , we have h i h i 2 2 E ∥xt+1 − xt ∥ = αt2 E ∥Gt ∥ ≤ (K3 + K4 M ) αt2 . 

K3 :=

Thus, P∞ (P.3) holds with q = b = p1 = p2 = 2, A = K3 + K4 M , and B = 0. Condition (P.4) holds because {αt } is bounded, t=0 αt = ∞, a = q = 2, a ≥ b, and p1 , p2 ≥ q. Therefore, Lemma 10 i) gives limt→∞ E[∥∇f (xt )∥] = 0. d) Verification of (P.3’) and (P.4’): Write xt+1 = xt + αt At + αt Bt with At := Et [Gt ] − Gt and Bt := −Et [Gt ], so that p1 = p2 = 1. Both At and Bt are Ft+1 -measurable, Et [At ] = 0, and E[∥At ∥2 ] ≤ E[∥Gt ∥2 ] ≤ K3 + K4 M . Moreover, it follows from Jensen’s inequality and (49) that h i 2 2 ∥Bt ∥ ≤ Et ∥Gt ∥ ≤ K3 + K4 [f (xt ) − f ⋆ ] . 2 Since f (xt ) converges almost surely to a finite limit, supt≥0 ∥Bt ∥2 < ∞ almost surely, and hence lim supt→∞ P∞∥Bt ∥ /(1 + 2 ∥∇f with q = b = 2. Finally, (P.4’) holds because αt → 0, t=0 αt = ∞, P∞ (xt 2)∥ ) < ∞ almost surely. Thus, (P.3’) holds 1 t=0 αt < ∞, q = 2, qa = 4 ≥ b, p1 = 1 > 2 , and p2 = 1. Therefore, Lemma 10 ii) yields limt→∞ ∥∇f (xt )∥ = 0 almost surely.

R EFERENCES [1] J.-H. Chen, M.-R. Chen, G.-Q. Zeng, and J.-S. Weng, “Bdfl: A byzantine-fault-tolerance decentralized federated learning method for autonomous vehicle,” IEEE Transactions on Vehicular Technology, vol. 70, no. 9, pp. 8639–8652, 2021. [2] T. Zeng, O. Semiari, M. Chen, W. Saad, and M. Bennis, “Federated learning on the road autonomous controller design for connected and autonomous vehicles,” IEEE Transactions on Wireless Communications, vol. 21, no. 12, pp. 10 407–10 423, 2022. [3] L. Sani, A. Iacob, Z. Cao, R. Lee, B. Marino, Y. Gao, W. Zhao, D. Cai, Z. Li, X. Qiu et al., “Photon: Federated llm pre-training,” Proceedings of Machine Learning and Systems, vol. 7, 2025. [4] T. Yang, G. Andrew, H. Eichner, H. Sun, W. Li, N. Kong, D. Ramage, and F. Beaufays, “Applied federated learning: Improving google keyboard query suggestions,” arXiv preprint arXiv:1812.02903, 2018. [5] Z. Xu, Y. Zhang, G. Andrew, C. Choquette, P. Kairouz, B. Mcmahan, J. Rosenstock, and Y. Zhang, “Federated learning of gboard language models with differential privacy,” in Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), 2023, pp. 629–639. [6] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial intelligence and statistics. PMLR, 2017, pp. 1273–1282. [7] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečnỳ, S. Mazzocchi, B. McMahan et al., “Towards federated learning at scale: System design,” Proceedings of machine learning and systems, vol. 1, pp. 374–388, 2019. [8] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings et al., “Advances and open problems in federated learning,” Foundations and trends® in machine learning, vol. 14, no. 1–2, pp. 1–210, 2021. [9] L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” SIAM review, vol. 60, no. 2, pp. 223–311, 2018. [10] H. Yang, M. Fang, and J. Liu, “Achieving linear speedup with partial worker participation in non-iid federated learning,” in International Conference on Learning Representations (ICLR), 2021. [Online]. Available: https://openreview.net/forum?id=jDdzh5ul-d [11] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for federated learning,” in International conference on machine learning. PMLR, 2020, pp. 5132–5143. [12] B. E. Woodworth, K. K. Patel, and N. Srebro, “Minibatch vs local sgd for heterogeneous distributed learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 6281–6292, 2020. [13] X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu, “FedPD: A federated learning framework with adaptivity to non-IID data,” IEEE Transactions on Signal Processing, vol. 69, pp. 6055–6070, 2021. [14] K. Huang, X. Li, and S. Pu, “Distributed stochastic optimization under a general variance condition,” IEEE Transactions on Automatic Control, vol. 69, no. 9, pp. 6105–6120, 2024. [15] A. Khaled and P. Richtárik, “Better theory for SGD in the nonconvex world,” Transactions on Machine Learning Research, 2023, survey Certification. [Online]. Available: https://openreview.net/forum?id=AU4qHN2VkS [16] X. Huang, P. Li, and X. Li, “Stochastic controlled averaging for federated learning with communication compression,” in International Conference on Learning Representations, vol. 2024, 2024, pp. 27 956–27 994. [17] R. You and S. Pu, “Fedsum family: Efficient federated learning methods under arbitrary client participation,” arXiv preprint arXiv:2512.18275, 2025. [18] Y. Lei, T. Hu, G. Li, and K. Tang, “Stochastic gradient descent for nonconvex learning without bounded gradient assumptions,” IEEE Transactions on Neural Networks and Learning Systems, vol. 31, no. 10, pp. 4394–4400, 2019. [19] H. Yu, R. Jin, and S. Yang, “On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization,” in Proceedings of the 36th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 7184–7193. [Online]. Available: https://proceedings.mlr.press/v97/yu19d.html [20] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” Advances in neural information processing systems, vol. 33, pp. 7611–7623, 2020. [21] T. Qin, S. R. Etesami, and C. A. Uribe, “The role of local steps in local sgd,” Optimization Methods and Software, vol. 40, no. 5, pp. 1017–1043, 2025. [Online]. Available: https://doi.org/10.1080/10556788.2023.2241151 [22] J. Wang, R. Das, G. Joshi, S. Kale, Z. Xu, and T. Zhang, “On the unreasonable effectiveness of federated averaging with heterogeneous data,” arXiv preprint arXiv:2206.04723, 2022. [23] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in International Conference on Learning Representations (ICLR), 2020. [Online]. Available: https://openreview.net/forum?id=HJxNAnVtDS

20

[24] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” Proceedings of Machine Learning and Systems, vol. 2, pp. 429–450, 2020. [25] W. Chen, S. Horváth, and P. Richtárik, “Optimal client sampling for federated learning,” Transactions on Machine Learning Research (TMLR), 2022. [Online]. Available: https://openreview.net/forum?id=8GvRCWKHIL [26] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” Advances in neural information processing systems, vol. 30, 2017. [27] S. Pu, A. Olshevsky, and I. C. Paschalidis, “A sharp estimate on the transient time of distributed stochastic gradient descent,” IEEE Transactions on Automatic Control, vol. 67, no. 11, pp. 5900–5915, 2021. [28] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in 2015 54th IEEE Conference on Decision and Control (CDC). IEEE, 2015, pp. 2055–2060. [29] 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. [30] A. Nedić, 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. [31] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” Mathematical Programming, vol. 187, no. 1, pp. 409–457, 2021. [32] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, “Exact diffusion for distributed optimization and learning—part i: Algorithm development,” IEEE Transactions on Signal Processing, vol. 67, no. 3, pp. 708–723, 2018. [33] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “d2 : Decentralized training over decentralized data,” in International Conference on Machine Learning. PMLR, 2018, pp. 4848–4856. [34] K. Huang and S. Pu, “Improving the transient times for distributed stochastic gradient methods,” IEEE Transactions on Automatic Control, vol. 68, no. 7, pp. 4127–4142, 2022. [35] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” International conference on machine learning, pp. 5381–5393, 2020. [36] Y. Huang and J. Xu, “On the computation-communication trade-off with a flexible gradient tracking approach,” in 2023 62nd IEEE Conference on Decision and Control (CDC). IEEE, 2023, pp. 284–289. [37] Y. Liu, T. Lin, A. Koloskova, and S. U. Stich, “Decentralized gradient tracking with local steps,” Optimization Methods and Software, pp. 1–28, 2024. [38] S. A. Alghunaim, “Local exact-diffusion for decentralized optimization and learning,” IEEE Transactions on Automatic Control, vol. 69, no. 11, pp. 7371–7386, 2024. [39] K. Huang and S. Pu, “Distributed stochastic momentum tracking with local updates: Achieving optimal communication complexities,” arXiv preprint arXiv:2510.24155, 2025. [40] K. Huang, S. Pu, and A. Nedić, “Distributed normal map-based stochastic proximal gradient methods over networks,” arXiv preprint arXiv:2412.13054, 2024. [41] ——, “An accelerated distributed stochastic gradient method with momentum,” Mathematical Programming, vol. 215, pp. 193–236, 2026. [42] B. Luo, W. Xiao, S. Wang, J. Huang, and L. Tassiulas, “Adaptive heterogeneous client sampling for federated learning over wireless networks,” IEEE Transactions on Mobile Computing, vol. 23, no. 10, pp. 9663–9677, 2024. [43] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in Proceedings of the fourteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 2011, pp. 315–323. [44] K. Mishchenko, A. Khaled, and P. Richtárik, “Random reshuffling: Simple analysis with vast improvements,” Advances in Neural Information Processing Systems, vol. 33, pp. 17 309–17 320, 2020. [45] X. Li and A. Milzarek, “A unified convergence theorem for stochastic optimization methods,” Advances in Neural Information Processing Systems, vol. 35, pp. 33 107–33 119, 2022. [46] H. Robbins and D. Siegmund, “A convergence theorem for non negative almost supermartingales and some applications,” in Optimizing methods in statistics. Elsevier, 1971, pp. 233–257.

Related documents

• When Is Shallow Enough? Adaptive Split Federated Learning with Client-Specific Sufficiency Estimation#459621
• Joint Optimization for Federated Learning and Transmission over Unreliable Wireless Networks with Heterogeneous Data#1083703
• Joint Optimization for Federated Learning and Transmission over Unreliable Wireless Networks with Heterogeneous Data#919363
• Does the Trust Boundary Hold over Time? A Long-Horizon Benchmark for Receiver-Directed Federated Learning#1588029
• Asynchronous proximal federated aggregation for heterogeneous healthcare networks.#421053