Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Authors: Paul Mangold
Alain Oliviero Durmus
Aymeric Dieuleveut
Eric Moulines
Venue: ICML 2025 poster (2025)
Keywords: optimization
federated learning
stochastic gradient descent
stochastic optimization
heterogeneity
Primary area: optimization->convex
TL;DR: We propose a new framework for analysis Scaffold with stochastic gradients, showing that it has linear speed-up and giving an expression of its bias.

Abstract: This paper proposes a novel analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic settings—where local control variates mitigate client drift—is well established, the impact of stochastic gradient updates on its performance is less understood. To address this problem, we first show that its global parameters and control variates define a Markov chain that converges to a stationary distribution in the Wasserstein distance. Leveraging this result, we prove that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size. Nevertheless, our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases. This highlights opportunities for developing improved stochastic federated learning algorithms.

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Paul Mangold Alain Durmus'
Aymeric Dieuleveut Eric Moulines
Abstract
communications in certain settings, client heterogeneity can significantly hinder its convergence. When the number of local iterations increases, clients lean towards their local minimums, which differ from the global one due to hetero- geneity. This phenomenon, called client drift, can induce bias in FEDAVG. To control this bias, clients must commu- nicate frequently, requiring at least (2(1/e) communication rounds to reach mean squared error of e² when objective functions are strongly-convex (Karimireddy al., 2020).
This paper proposes a novel analysis for the Seaf- fold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic weer local control variates mitigate client drift-is well established, the impact of stochastic gradient up- dates on its performance is less understood. To address this problem, we first show that its global parameters and control variates define a Markov chain that converges to a stationary distribution the Wasserstein distance. Leveraging this result, we prove that Scaffold achieves linear speed-up in the number of clients up higher-order terms in the step size. Nevertheless, our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg. that does not decrease as the number of clients increases. This highlights opportuni- ties for developing improved stochastic federated learning algorithms.
A key method for mitigating client drift is SCAFFOLD (Karimireddy et al., 2020). In this algorithm, each client updates its local model by performing gradient updates, ad- justed using local control variates. After each aggregation step, clients update their local control variates based on the global model received from the server, effectively removing heterogeneity bias. SCAFFOLD ied by Karimireddy et al. (2020), reducing communications from ((1/e) to (log(L/e)) for strongly-convex objectives, where c > 0 is precision target. Later, Mishchenko et al. (2022); Hu & Huang (2023) proved that (a variant of) SCAF- FOLDD reaches O(log(1 (1/ /c)) communication cost with an improved dependence on the problem's 's condition number. Unfortunately, in all these results, the number of gradients computed by each client does not decrease with the num- ber of clients.' Yet, fundamental promise of federated learning is to reduce training cost through collaboration, a phenomenon called linear speed-up (Y (Yu et al., 2019a).
first theoretically stud-
1. Introduction
This paper focuses on the federated optimization, in which N agents collaborate to solve a problem of the form
N
0* E arg min f(0)
1 N c=1
Σ (0)
(L)
In this paper, we show for the first time, to our knowledge, that SCAFFOLD achieves linear speed-up. To this end, we develop novel point of view SCAFFOLD, showing that its global iterates and control variates jointly form a Markov chain, similarly to SGD (Dieuleveut et al., 2020) and FE- DAVG (Mangold et al., 2025). For strongly-convex and smooth objectives, we show that this Markov chain con- verges geometrically to a unique stationary distribution. careful examination of the pairwise covariances of the global parameters and control variate reveals that, in this stationary distribution, SCAFFOLD's 's global parameters' variance re- duces linearly with the number of clients, up to a maximum number of clients. We then leverage this result to give a new
OgRd
where for each c E NJ. f(=)(0)= E(F 2o (0)
a local risk function of agent for some function (z(e).)) () + F (0) and local observation (()) with dis-
tribution (() over a measurable space 2).
One of the most popular methods for solving (1) is FEDAVG (McMahan et al., 2017). where clients perform multiple local stochastic gradient updates, and send their updated parameters to central server, that aggregates them. Al- though FEDAVG's local training reduces the number of
"Cole Polytechnique, CMAP, UMR 7641, France. Correspon- dence to: Paul Mangold <paul.mangolde @ polytechnique.cde
We note that, although Karimireddy et al. (2020) obtain such speed-up. they do using global step size, which significantly departs from common practice. See discussions in Remark 2.1.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Table 1: Communications and local iterations required for SCAFFOLD to reach Elllo' - 0*1 S e², for e > 0, according to
multiple analyses of SCAFFOLD with stochastic gradients for p-strongly convex and L-smooth functions.
Communication
Local Iterations
Linear Speed-Up
Acceleration (3)
General objective
Det.
Sto.
Karimireddy et al. (2020)(1)
(log(1//c)
0(1/2)
x(1)
x
Mishchenko al. (2022)(2)
O(1/e)
0(1/e)
V
Hu & Huang (2023)(2)
(log(1)/))
0(1/2)
X
/
V
Mangold et al. (2024)
(llo([1/e))
O(1/Ne)
x
X(4)
Ours
(llo((1/e)
O(1/Ne)
x
(1) they obtain linear speed-up by introducing a global step size: in practical implementations, there is no global step size and their analysis loses linear speed-up (see Remark 2.1); (2) based on a stochastic communication scheme; (3) accelcration means that the algorithm benefits from local steps, when gradients are deterministic (Det.), or stochastic (Sto.); (4) only holds for quadratic functions.
non- non-asymptotic convergence rate for SCAFFOLD, highlight- ing the speed-up property. Our analytical framework also allows to derive first-order (in the step size) expansions of this covariances, and unveils that, despite its bias-correction mechanism, SCAFFOLD's 's global iterates still suffer from a small bias. Our contributions are:
i= 2, we define the second-order Wasserstein distance as W p2) infge / || X E dx'), with
I[(1 P2) the set of probability measures X' x X such that E(A x X) pn (A), E(X x A) p2 (A) for A E (()).
2. Federated Learning and SCAFFOLD
SCAFFOLD's iterates converge. The global iterates and control variates of SCAFFOLD form a Markov chain that converges linearly to a stationary distribution in Wasser- stein distance, with a faster rate with more local steps.
The main challenge in federated learning arises from the fact that each client E {1, ,I...., .N only has access to its own local function S(e). rather than the full sum in (I). Since these functions typically differ across clients, this induces heterogeneity, making optimization more complex.
SCAFFOLD has linear speed-up. We give new non- asymptotic convergence rate for SCAFFOLD, showing that the number of gradients computed by each client to reach a given precision decreases linearly with the number of clients (up to limit that we characterize). To our knowl- edge, this is the first result of this kind for SCAFFOLD; see Table for a comparison with existing works.
Throughout this paper, we consider the following assumptions. The first assumptions A A A2 and A3 define the regularity of the local objective functions. A (Strong Convexity). For every c E NN, the function f(e) is twice differentiable and p-strongly-coonvxx In particular, we have (()) > pld for any e Rd. A 2 (Smoothness). For every c E (1...., .N) and E Z, the function 17 is twice differentiable and L-smooth. In particular, we have V (0) & LId for E Rd.
Assumptions.
SCAFFOLD is still biased. We give first-order expan- sions, in the step size, of the covariances of SCAFFOLD's iterates in the stationary distribution. Surprisingly, while SCAFFOLD corrects heterogeneity bias, it still suffers from another bias due to its stochastic updates.
A 3 (Third Derivative). For every E (1...., N), E Z, the function f(e) is thrice differentiable with bounded third derivative, i.c., there exists Q 2 0 such that for any u E Rd and 0 E Rd., || (ce) @2 S Q||u[
Notations. We denote by V f the gradient of differen- tiable function f: _d + R. If f is i-times differentiable for i 2 1, we denote its i-th derivative by V'f. We use (+--) to denote the Euclidean dot product. Vectors are columns, and their Euclidean norm is I1-11. For matrices, |I-I1 is the operator norm, Id is the identity matrix Rd. For two matrices A, B, we define the Stonecker-type lin- car operator @ B A & B- M AM where A, M, and B have compatible dimensions for multiplica- tion. For tensor X, we denote by x its k-th tensor power. For a sequence of matrices MI,..., Mr. we define their ordered product as II M, = M .....,., M, Let B(Rd) be the Borel o-algebra of Rd. For two probabil- ity measures Pl, P2 over X such that J' (xX))(]| < co,
These assumptions are classical in stochastic optimization (Nesterov, 2013; Dieuleveut & Bach, 2016). We discuss the main consequences of AI and A2 in Appendix A.I.
To measure heterogeneity of the problem, we rely on the gradients and Hessians of local functions at the solution.
A4 (Heterogeneity Measure). There exist Çi, So 2 0 such that, with 6* as in (1)
+ Σン | f()) - V f(00) < ? for E [1,2]
Finally, for a parameter 0 E d and 2 E Z, we define the
2

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Algorithm 1 SCAFFOLD
SCAFFOLD. The SCAFFOLD algorithm (Karimireddy et al., 2020) uses control variates to mitigate client drift by replacing the local gradient updates of FEDAVG for h E (O..... H 11-1, by
Input: initial 0 E Rd and ((1).... ((N) E Rd, step size
y 0, number of rounds T > 0, number of clients N > 0,
number of local steps > 0
for = 0 to T 1 do
g.ht1 = 0/ - 7 (VP
Zeett (o) (c)
(0%) + Eia) (4)
2: for c = to N do
3: Initialize (/) = 6t
These parameters are then aggregated by a central server as in FEDAVG: 0++1 N "E= 0'
4: for h = 0 to H 1 do
(e) After aggregation,
5: Receive random state 2 (c)
each client locally updates its control variate
+++
6: Set 001 0/
7: end for
V
(%%) + [
(())
n 10 S(e) + 7H
1
(5)
8: end for
We give the pseudo-code of this algorithm in Algorithm 1. Learning fic) corresponds to estimating a linear correction of the gradient of the local functions so that the corrected gradient is zero at 1** The ideal control variate for client c is thus C(e - V (6*), as this correction ensures that all clients converge toward the same optimum.
9: Update: a1+1 1 Ee cc=1 0zH
10: Update: c/1l f(c) + 7 (c)
( 1
11: end for
12: Return: T
Remark 2. In this paper, we aim to study the SCAFFOLD al- gorithm as it is commonly used. Thus, contrarily to (Karim- ireddy et al., 2020; Yang et al., 2021), we do not consider (2) two-sided step sizes. While this yields the desired línear speed-up by dividing the local step size by vN, and in- creasing the global one, it essentially reduces the algorithm to mini-batch SGD, and does not give much insights on SCAFFOLD itself. Thus, we consider in Table the rate of Karimireddy et al. (2020) without global step size.
stochastic part of the gradient and its covariance
c (0) v (0) (0()
(0) e (0
(3)
We assume in A that (0) has bounded sixth moment. A5 (Gradient's 's Variance). There exist constants o3, ( 2 0 such that for 9 E Rdd E (1, and c E (1....,N).
3. Related Work
E E 111
Zeo (0) S o.2 + 0 - 1/ (c)
Analysis of FEDAVG. Early analyses of FEDAVG were conducted under homogeneity assumptions on the gradi- ents (Stich, 2019; Wang & Joshi, 2018; Haddadpour & Mah- davi, 2019; Patel & Dieuleveut, 2019; Yu et al., 2019b; Li et al., 2019b; Woodworth et al., 2020b). Subsequent studies have shown that FEDAVG exhibits fundamental bias in heterogeneous settings (Li et al., 2019a; Malinovskiy et al., 2020; Charles & Konečný, 2021; Pathak & Wainwright, 2020; Karimireddy et al., 2020): due to client drift, the iter- ates of FEDAVG do not converge to the true solution 0., but to a biased limit point.
where (0) has values in Z and distribution V(()-
FEDAVG. A now very popular algorithm to solve (1) is Fed- erated Averaging (FEDAVG) (McMahan al., 2017). This method leverages local training to reduce communications, by letting each client perform number of local stochastic gradient updates. Each final iterate of these updates are then sent to a central server, which aggregates the model received by all clients. More precisely, FEDAVG defines a sequence of global iterates (Ut)IeN as follows. At a global time step t 2 0, each client e {1, .,, N} performs H > 0 local iterations, starting from 00 0,, where 3, is the current global parameter received from the server. This writes as, for fa E {O..... H- --1
In fact, even in homogeneous settings, FEDAVG remains biased due to its stochastic updates. This appears in the analyses of Khaled et al. (2020); Woodworth et al. (2020a); Glasgow et al. (2022); Wang et al. (2024).
1}.
geht1 (c) (6) VF (0)
(0%)
Heterogeneity mitigation. Karimireddy et al. (2020) pro- posed SCAFFOLD, which reduces client drift with control variates, alike variance reduction methods (Schmidt et al., 2017), and proved its convergence. Subsequently, Mitra et al. (2021); Gorbunov et al. (2021) established similar rates in the smooth and strongly convex case. However,
where { Jh=1 are i.i.d. random variables independent among clients and from the previous iterations, with distri- bution 1/()- After these local updates, the parameters are aggregated by the server +++ N-1 > H.H
(c)
3

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
in all these works, the number of communication rounds required to achieve mean squared error of order 2², scales as OK log()/))), where K is the problem's 's condition number.
to a unique stationary distribution in Wasserstein distance. Next, we analyze the covariance structure of this stationary distribution in Section 4.2. The detailed analysis of this covariance matrix provides important insights into the be- havior of SCAFFOLD in the stationary regime. Finally, based on these results, we derive a non-asymptotic convergence rate in Section 4.3, proving the linear speed-up for a range of step-sizes and horizons.
Mishchenko et al. (2022) then introduced PROXSKIP, which, in deterministic setting, achieves accelerated communica- tion complexity, reducing the average number of communi- cation rounds to O(VK log(e ')) for reaching MSE of order e². However, when gradients are stochastic, their analysis requires (c1/c) rounds. Later on, Hu & Huang (2023) fixed this, reaching OK log(1/e) rounds even in the stochastic setting. Nonetheless, neither of these analyses achieve linear speed-up with respect to the number of clients. Several ex- tensions of these methods have been proposed (Malinovsky et al., 2022; Condat al., 2022; Condat & Richtárik, 2022; Sadiev et al., 2022). However, the sample complexity results established in these works do not exhibit linear speed-up up either. A notable exception is the work of Mangold et al. (2024), who achieves linear speed-up for SCAFFOLD for quadratic objectives; they consider an extended version of SCAFFOLD for linear approximation, named SCAFFLSA, A, requiring On2²² log(1/e) communications with number of local updates scaling in O(L/NE*), effectively achieving linear speed-up. In this work, we present a more general analysis that holds beyond the quadratic setting.
4.1. Convergence of Global Iterates
Iterates of SCAFFOLD. We define the following operators, that generate the iterates of SCAFFOLD. For a value E R define the local update operator on client e as
T(c) ((e)) (()) = 8 - - FVF (c) (0) + {
for (()) E Z. Set TO ((o): =) = 0 and define recursively the local parameter updates
The (c) (0: Etop>
l:bhl) ) (o) (T/)) (0; [(e) ); Step> a(c) (c)
where zte) = [ 2/ogl for c E [N] and E [H]. This allows to define the global update operator
2:H (1:N)) = E T (()) 200)) T(O: ((:)) 2
Similarly, for 0 E Rd, we define the operator that updates the control variates
SGD in Markovian setup. Unlike SGD with dimin- ishing step size, which converges to the true optimum under convexity assumptions, constant step-size SGD does not converge pointwise and instead oscillates around 0, (Chee & Toulis, 2018), introducing an inherent bias. To address this problem, Dieuleveut et al. (2020), following a stream of works by (Pflug, 1986; Fort & Pages, 1999; Bach & Moulines, 2013), analyze SGD with a constant step size as Markov chain, leveraging randomly perturbed dynam- ical systems to characterize its convergence and limiting behavior. Recently, Mangold et al. (2025) proposed to view FEDAVG's iterates as a Markov chain. They establish that FEDAVG's iterates converge towards a unique stationary distribution, and give explicit first-order expansion of the bias in O() This bias decomposes into two components: one due to heterogeneity, and one due to stochasticity of the local gradients. Remarkably, this second bias vanishes when optimizing quadratic functions.
V (io)(E1e35 0, (1=())))) E(e)
+ H (T (0: Stop= *(e)
=1:H1) T(0; E(i:N) =((5)))
Thus, we can define the update of the SCAFFOLD algorithm
S: ((LN)) ((LNN)) - (T (1:N)), 0, 1:H ((:N))))
1:H
(ay( 0, 11H
0, ((i.N)),...,
Note that for all 21:1 (1:NN)
S( 1:H (1:N))
is a mapping from E R(N+1jd
X' =
E = 0}
into itself. We equip X with the norm |I| (X, AX), where A = (Id,
= ld. N
22 Id), or more explicitly,
N
H2 N
N EIX
IX = o1 ++
P2
(6)
4. New Convergence Rate for SCAFFOLD
With these notations, the SCAFFOLD updates of the parame- ters and the control variates see Algorithm 1-wittes
In this section, we present our first main theoretical contri- bution: SCAFFOLD achieves linear speed-up with respect to the number of agents. To establish this result, we introduce a new analytical framework for the study of SCAFFOLD
2111#)) x = S S (1:N)
(7)
where X = x²=10'' 11....).....5 M()) and { (2N))) is an i.i.d.
First, we show in Section 4.1 that the global iterates and con- trol variates of SCAFFOLD define a Markov chain. We then establish that this Markov chain geometrically converges
sequence with 2(0) Ma) for E {l...., NJ and h e (O...., H).
4

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
SCAFFOLD's iterates as Markov chain. SCAFFOLD updates form an iterated random function, specific class of Markov chains that have been extensively studied (see Diaconis& & Freedman (1999) and the references therein). The Markov property is clear: given the present state of the <iN)), the conditional distribution of the
the optimal vector X* (0", (in) f(N) where the optimal control variates are given by ((n) = - (t))
Lemma 4.3. Assume A2, A.. Let Z (1:N) be i.i.d. random variables satisfying A5. Assume the step size and the number of local updates H satisfy (L + j) S
X = =(0", future state does not depend on the past. Hence SCAFFOLD's global iterates define a ume--homgenneuus Markov chain on X' equipped with its Borel o-algebra (()). We denote by ((,,H) the corresponding Markov kernel on X. We define, for / 21 1, the iterates of K (H) as Kt (y. For any probability measure on N' and & E N. the distribution of
S(aj..... -0''</1).....
1. Then, for all 0 E B and (5(0) C IR such that
Σ f(e) = 0,
||((X; Z) - xx1]R]
S -11-2) H |X (x- + +222Hoo,
SCAFFOLD's 's iterates X* started from XD ~ p is pk (x. We show below that the iterates of SCAFFOLD converge to a
with the global iterate vector X = (1) S(n))
unique stationary distribution. This requires a contraction in
We prove this lemma in Appendix B.2. Thus, for any X E X, single iteration of SCAFFOLD brings X closer to neighborhood of the optimal solution X", long as |X - IX is sufficiently large. In Markov chain theory, this implies that |X - X serves as Foster-Lyapunov function for the kernel (r) From this Foster-Lyapune condition, we may retrieve a first rough bound on the fluctu- ation of the estimator around X*.
average (see Diaconis & Freedman (1999), Theorem 1): the next lemma shows that S defines a contractive map over X. Lemma 4.1. Assume A I and A 2. Let Z Z be ii.dd random variables satisfying A Let the step size y > 0 and number of local updates H > O sat- isfy < 1/(2L) and 7H(L= + ()) I
(1-N)
1. Then, for
any 0,00 E Red and (E(o) (1o)- Si E
Tee such that
E S(e) = ExaSle) = 0, it holds that
Theorem 4.4. Assume AI, A2 A5. Lety > be the step size and H > 0 the number of local updates. Assume that Y S 1 1/4L and 7H + μ)) S 1. Then, for any T > 0 and any X E X. the iterates and control variates of SCAFFOLD,
E [[(S((:Z) Z) S(X'; 2XX1 - (1- 7/4 H
IX- IX-X'IR. (8)
with X- (.)......... and X' - (0', Eli (()))
x = 100 -by............... (((.......vv .(rr). ). satisfy the inequality
We prove this lemma in Appendix B.1. A major conse- quence of this lemma is that SCAFFOLD's iterates and con- trol variates converge to a unique stationary distribution.
E |X x²
S (1 (1-
yu 2 HT
1 X
87 +
8707 o
Theorem 4.2. Assume AI, A2, and AS. Let 7 > 0, H > O.
where X is the global optimal vector.
such that 7 < 1/(2)) and 7H + p) S 1. Let {X with X = (0', E E(....... ). be SCAFFOLD'S 's iterates with step size and H local steps and X ~ p. where p is prob- ability measure on X such that [[[XI[% < co. Then, the distribution pKt (1,15) Xf converges to a unique station- ary distribution H)) satisfying J' [XI (7. ()XX) co, and for any t E N.
The proof of this theorem is given in Appendix B.2. This preliminary bound is very similar to the ones established in Karimireddy et al. (2020, Lemma 14) and Mishchenko et al. (2022, Theorem 5.5) (for PROXSKIP). We include it for completeness, to underline that a major limitation is that it does not achieve linear speedup in the number of clients. Nonetheless, this result is crucial to bound the higher-order terms that appear in all our subsequent analysis. Indeed, taking T + 0c. a consequence of Theorem 4.2 and Theorem 4.4 is f'|X"* - X+ π (1.HH) (dx) < 8y02/ p. which gives the following Corollary.
Walkks ( ()) S <(1 7H Ht
W3 (,,)))
We prove this theorem in Appendix B.1. In the following, we indifferently write () (d0, (d),d)) and (y (dX).
Corollary 4.5. Assume AI, A2 and A5. Let Z Z!H i..d. random variables satisfying A5. Let > 0 be the step size and H > O the number of local updates of SCAFFOLD. Assume that 7 S I/L and 7H + 1) S 1. Then, for all h E (0..... H), it holds that
(1:N) be
Theorem 4.2 shows that the Markov kernel K(r,r) is ge- ometrically ergodic in 2-Wasserstein distance. Moreover, the distribution of X converges to the limiting distribution ((y.H) at linear rate (1 7//44), with the exponent given by the number of effective steps H x t. As with the deter- ministic algorithm, for a given step size 7, a larger number of local steps H speeds up the convergence to stationarity. We will show below that it leads to additional bias. Define
f 100 - 0" 10 (T d3) S
8y 0
p
where E = ((n).....(())) E R.d.
5

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
We give a proof and more complete version of this Corol- lary in Appendix B.2, Corollary B.I. We may also obtain similar bound for local updates and control variates.
of noise added by clients during local updates,
s-
N H
/ EIC. (0) (a),,
(d0, dE)|
Lemma 4.6. Assume A I, A2. Let Z Z be i.i.d. random variables satisfying A., Assume the step size y and the number of local updates H satisfy (H + 14) S 1.
N
h=0
where (0) (T (0; S(o) 2) and (o) is the covariance of the local gradient noise as defined in (3), The next lemma relates C C and CS. We present it in a simplified form to highlight the main dependencies.
Under these conditions, for any h E {O...., H} and c E .N, it holds that,
0-] E (0 (0: Sto): 2(01) - ((, (d0, d3) S
?o?
Lemma 4.7. Assume AI, A2, A5. Assume the step size T and the number of local steps H satisfy 7, 7H(I. + n)) S 1, then
P
/ |156] - -(oo (T7 (d0, d=) x
Lo μn
22 +r
PHH - + A
N
The proof is postponed to Appendix B.3. We use S to omit numerical constants, which are provided in the full proof. Notably, for any agent c, the variances of local iterates after h S H local iterations do not scale with 1/N. However, it is crucial to highlight that the fluctuations of the control variate scale inversely with H. We also give derive analog variants of Corollary 4.5 and Lemma 4.6 for moments 2, 4, and 6 in Lemma B.3.
- +
NH 1
C' + +
NH2 + +
where S2 is the heterogeneity coefficient defined in A4, 12, 10,5, and 15 are higher-order terms.
We prove this lemma and give exact expressions in Ap- pendix C.3-Lemma C.8. Using these inequalities, we derive the next theorem, that gives an upper bound on CO.
4.2. Bounding the Variance of the global iterates
We now derive an upper bound on the variance of 0 - 0* under the stationary distribution. In particular, we show that this variance is proportional to 1 I/N, up to a higher order term in the step size. To this end, we track the relations between the covariance matrices of the global parameters and control variates, defined for any c, c' E [N] as
Theorem 4.8. Assume AI, A2, A3, A4, a5d Furthermore, assume that g S 1s, (L + 1) S 1 and yB S p. Then, it holds that
COS 20S Np
1012Q 1 0 +
x²H0²
0
+
1B 0.
- / (0-0r) 82 (d0,))(d,dd)) Σ. A
We prove this theorem in Appendix C.3. Recall that Q is the upper bound on the third derivative, which is defined in A and it vanishes in the quadratic case. We recover in such case the bound on the covariance of the parameter derived in (Mangold al., 2024). A crucial feature of this result, is that the covariance of the parameters' error Σ is proportional to 7/N, up to higher-order terms in the step size. To our knowledge, this is the first time the variance of SCAFFOLD with general objective function is shown to decrease with the number of clients. It in stark contrast with existing analyses of SCAFFOLD (Mishchenko et al., 2022) where variance only scales in
5 A / (E(o) E(o) (ftr)) (ie)) T (n,,r,d0, (c,e))
5o. A / 10- (5 - sta) T (d0,, dE)
(c)
We emphasize that the parameter and control variates are inherently correlated. Local gradient noise introduced in the updates of the local parameters (4) propagates to the control variates via their update (5). We refer to Lemma 5.1 for a detailed discussion on these covariance matrices. There, we provide exact first-order expansions, offering a precise characterization of their structure and interactions.
4.3. A Non-Asymptotic Rate with Linear Speed-Up
Now, we derive an upper bound the global parameter's covariance E" To this end, define
We now state main result, showing that our bounds from Section 4.2 can be used to obtain non-asymptotic rates for SCAFFOLD. This can be achieved by using the conver- gence of SCAFFOLD to its stationary distribution through a synchronous coupling method.
C & CA
1/ EN 2611
= EN Eor= [Ec))
Theorem 4.9. Assume A2, A4, A5d Furthermore, assume that H & p. (T. + μ) $ and 7B $ p
We also define the following quantity, related to the variance
6

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Then, the mean squared error of SCAFFOLD's 's global iterates, initialized with 0 E Rdd and E(1) = {(N) 0 E Rdd
5. Explicit Expression for Bias and Variance
The analysis framework that we put in place in Section 4 is guided by the study of the covariances of the global param- eters and control variates of SCAFFOLD. We now provide novel insights on the behaviour of SCAFFOLD in the station- ary regime. In Section 5.1, we give exact first-order (in the step size) expression for the covariance matrices defined in Section 4.2. Surprisingly, this study uncovers that SCAF- FOLD's global parameters are still biased, and we describe this bias Section 5.2.
is
E -110 -011]]
$ (1- 21) HT
4) )
{ 21100 - 0 +2
of2
Lp
+ 7 0 + 2 Nu
700 101 1
1012 J+ + n² 0+
3
To prove this theorem, we decompose 0" 0+ Oz gr + + -0 0*, where 0T is obtained by running SCAFFOLD with the same realization of noise as 0 but starting from 0 in the stationary distribution. We then obtain a bound on the error by bounding E[||0" - 0-] and E[]] - 0-]]]] separately, using Lemma 4.1 and Theorem 4.8 respectively. We give a detailed proof in Appendix D.
5.1. Variance of the Global Iterates
In SCAFFOLD, the only source of randomness comes from the stochasticity of the gradient updates. These stochastic updates then propagate in the global iterates and control variates of the algorithm. Our analysis framework allows us to give the following expressions of these covariances, as a function of the gradient's 's covariance at the solution 0*.
This theorem converts our asymptotic bound on SCAF- FOLD's error in the stationary regime into non-asymptotic bound, where the variance term scales in 1/N, up to higher- order factors in 0(-3/2 + HH) This gives the following sample and communication complexity for SCAFFOLD.
Lemma 5.1. Assume A AI, A2, A3, A4, A5. Furthermore, assume that the step size y and number of local updates H satisfy THIG₂ S and (H + μ) S 1 and xB S p. Then, it holds that, for o c' E NN)
Corollary 4.10. Let c > O. With Theorem 4.9's assump- tions, we can set Y S min(? Nus² 1//3,/73
o; Qu130? ; Qo?
0 E" Y +C) +03))
and H S o, mmin(I.//aa)) max(?, 2. @2/22 91122). Then,
N
" 11/2
?
AC" f()()))
SCAFFOLD guarantees 1B[10T" [-] S 2 for T Z
(c) N
LL f. max(1,, (2/H)) log(
[100 1100-0'122 -0124431112 ). and the number of
(Co((0) C(())) + 0(22H + +7313)
2 stochastic gradients computed by each client is
N
5
(1
N H Co( + NH C(D') + +0())
2
1
TH S po max 1. N
02/9,213
91 log(
(c,0)
11
5 (c,e')
1
(C(0*) - C,) - (C
(0))))(()))
= NH
where Un = 1100 - 1- + //////2 + (LH).
We prove this corollary in Appendix D. This result combines two crucial features: (i) SCArFOLD has linear Sinearspeed-up speed-up up to given number of clients: the number of gradients computed by each client scales in 1/N; and (ii) SCAFFOLD accelerates stochastic gradients: the number of rounds required for con- vergence depends logarithmically on the desired precision e. In comparison, in heterogeneous settings, FEDAVG's num- ber of communication scales polynomially in 1/c. To our knowledge, this is the first time that SCAFFOLDD is proven to have linear speed-up (without relying on global step sizes), while guaranteeing acceleration with stochastic gradients. Remark 4.11. In our analysis, we show that the number of rounds scales in log(1/c), with a multiplicative factor L/ p.. Additionally, Hu & Huang (2023) proved that this constant can be reduced to VL/u, but without linear speed-up in the number of clients. It is an intriguing open question to determine whether SCAFFOLD can preserve this reduction from T./p s/pto to / IL/ while guaranteeing this linear speed-up.
where A
(Id & V f((') + v2f(0') & Id) Zeo ( and C(0*) NN C. CP
Cx ((E
We prove this lemma in Appendix E.2. This result confirms our finding that, in the stationary regime of SCAFFOLD, the covariances E and $6.5 both scale in 7/N. However, this is not the case for the control variates, which do not even
[c)
scale in the step size y. More remarkably, we show that, for any c, the covariance ((..)) of E(e) does not decrease in 1/N. Fortunately, the covariances of pairs of distinct control variates recovers this 1/N, which is the reason why SCAFFOLD enjoys linear speed-up.
Remark 5.2.
We note that, in the analysis of PROXSKIP (Mishchenko et al., 2022), they use a Lyapunov function sim- ilar to (6), based on the average of the 7 H 1 Lemma 5.1 shows that this Lyapunov function cannot achieve linear speed-up, as its terms only scale in O(₂2
7

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
10
10
10
10
10a
10a
10a
10a
MSE
10P
100
100
100
10-2
10
10
10
10
20
30
40
50
0
10
20
30
40
50
10
20
30
40
50
0
10
20
30
40
50
10
10-1.
10
10
MSE
10
10 3
10-3
10-3
10-5
10-5
10-5
10-5
10
20
40
50
0
20
30
40
50
10
20
40
50
0
20
30
40
Communication rounds (a) N = 10
Communication rounds
Communication rounds
Communication rounds
(b) N = 100
(c) N = 1000
(d) N 10000
Figure I: Mean squared error [0[]]0 [1] as function of the number of communications, with H = 100 and 7 = 0.05, for linear regression (top row) and logistic regression (bottom row) problems. For each curve, we plot the average over 3 runs and the standard deviation.
5.2. Non- Vanishing Bias SCAFFOLD
6. Numerical Results
Quite surprisingly, our analysis highlights that SCAFFOLD still biased. We now give expression of SCAFFOLD's bias, ie., the expected error in the stationary distribution
Experimental setup. We illustrate our theoretical find- ings on E2 regularized linear and logistic regression. For linear regression, we use make-regression function from scikit-learn (Pedregosa al., 2011) generate two different datasets with 100N records and 20 features; to simulate heterogeneity, we use different seeds and n.informatives and n.informative- tively. The first dataset is split evenly among the first N/2 clients, while the second one split evenly across the other half of clients. For logistic regression, we repeat the same procedure with the make-classi fiiiiiiiiii iicaiionn in function with two different seeds. Using this procedure, generate regression and classification task, where each client has 200 records, and where the distribution is hetero- geneous. In both settings, we run SCAFFOLD with y = 0.05 and H = 100, T = 100 and N E (10, 100, 1000, 10000). We estimate the gradients using batches of size 10, and compare the result with FEDAVG with the same parameters.
b [(e -0000000000)) (1) dE)
respec-
We require the fourth derivative of f(c) to be bounded. A6 (Fourth Derivative). For e E (1....,N) the function f(e) is 4 times differentiable and satisfies, for any 0 E Rd and u E Rd, V f(e) (3 < G|lu||
Given this assumption, we obtain the following theorem.
Theorem 5.3, Assume AI, A2, A3, A4, A5, A6. Furthermore, assume that the step size and number of local updates H satisfy 7(H - L1)L S p and yH + S 1 and 73 S p. Then, the bias of SCAFFOLD is
The code is available online at https: /tt://gittt /ttpt/tttub////// com/ pmangold/ hwtooodddcccfaaeeoo sca.folffflllooooooooooooo..offa speldd-spee-upp
7 2 (00)A10))) 2/3)). 2N
SCAFFOLD has linear speed-up. For each value of N, we run both SCAFFOLD and FEDAVG and report the re- sults in Figure 1. As expected, SCAFFOLD consistently outperforms FEDAvG in all settings. In conformity with our theory, SCAFFOLD benefits from the presence of more clients: the number of clients increases, the error in sta- tionary regime decrease, both in linear (top row) and logistic (bottom row) regression.
We refer to Appendix E.3 for a proof of this theorem. Even though SCAFFOLD eliminates heterogeneity bias, its global iterates remain biased. This bias scales with 7/N times the local gradient's variance. solely to the stochasticity of the local updates. In fact, we even recognize the bias of FEDAVG with homogeneous func- tions, as presented in Mangold et al. (2025)'s Theorem 3. We note that this bias scales with the local gradients' covari- ances, suggesting that SCAFFOLD may not be appropriate in problems with very noisy gradients.
due to heterogeneity, but
Linear speed-up with many clients. Remarkably, the lin- ear speed-up remains for number of clients gets large (up to 1, 000), suggesting that the condition on the maximal
8

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
number of clients until which the linear speed-up holds in Corollary 4.10 is not overly restrictive. Nonetheless, there is no more improvement from N = 1, 000 to N = 10, 000 in our logistic regression problem (bottom row): this suggest we have reached saturation, and that in this setting, increas- ing the number of clients does not help beyond this point. As predicted by our theory, this not the case in linear regression (top row). Indeed, in this case, the loss function is quadratic (i.e., Q 0) and the limit the number of clients stated in Corollary 4.10 is thus infinite.
consequences of our work, none which we feel must be specifically highlighted here.
References
Bach, F. and Moulines, E. Non-strongly-conver smooth stochastic approximation with convergence rate (1/n), Advances in neural information processing systems, 26, 2013.
Charles, Z. and Konečný, J. Convergence and accuracy trade-off's in federated learning and meta-learning. In International Conference on Artificial Intelligence and Statistics, pp. 2583. PMLR, 2021.
7. Conclusion
In this paper, we provide a novel analytical framework for the SCAFFOLD algorithm. We show that its global iterates and control variates define a Markov chain, that converges to a stationary distribution. This key property allows to derive the first rate which shows that SCAFFOLD achieves linear speed-up in the number of clients. Our analysis is based on a careful examination of the covariance of SCAF- FOLD's global iterates and covariance, finely tracking the propagation of noise through the algorithm's 's parameters.
Chee, J. and Toulis, Convergence diagnosties for stochas- tic gradient descent with constant learning rate. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1476-1488 1485. PMLR, 2018.
Condat, L. and Richtárik, Randprox: Primal-dual opti- mization algorithms with randomized proximal updates. arXiv preprint arXiv:2207.12899 2022.
Although our work provide novel insights the behavior of SCAFFOLD, many questions remain open. In particular, it is yet to be understood whether SCAFFOLD can enjoy "deterministic" accelerated communication complexity as in Mishchenko et al. (2022); Hu & Huang (2023)'s analyses while preserving the desired linear speed-up. Finally, our analysis highlights that SCAFFOLD's iterates are still biased: designing novel methods that remove this residual bias is promising direction for the development of novel stochastic federated learning methods.
Condat, L., Agarský, I., and Richtárik, P. Provably doubly accelerated federated learning: The first theoretically suc- cessful combination of local training and communication compression. arXiv preprint arXiv:2210. /3277, 2022.
Diaconis, P. and Freedman, D. Iterated random functions. SIAM review, 41(1):45-76, 1999.
Diculeveut, A. and Bach, F. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 1399, 2016. 15-A0S1391.
doi: 10.1214/
Acknowledgements
Dieuleveut, A., Durmus, A., and Bach, F. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 - 1382, 2020. doi: 10. 10.1214/19AAOS1885
The work of P. Mangold has been supported by Technology Innovation Institute (TII), project Fed2Learn. The work of A. Dieuleveut is supported by HilParis FLAG chair, and this work has benefited from French State aid managed by the Agence Nationale de la Recherche (ANR) under France 2030 program with the reference ANR-23-PELA-00S (RE- DEEM project). The work of E. Moulines has been partly funded by the European Union (ERC-2022-SGGOOCE. 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Douc, R., Moulines, E., Priouret, P., and Soulier, P. Markov chains. Springer, 2018
Fort, J.-C. and Pages, G. Asymptotic behavior of a marko- vian stochastic algorithm with constant step. SIAM jour- nal on control and optimization, 37(5):1456- 1456-1482, 1999.
Glasgow, M. R., Yuan, H., and Ma, T. Sharp bounds for fed- erated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Impact Statement
Gorbunov, E., Hanzely, F., and Richtárik, P. Local sgd: Uni- fied theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564. PMLR, 2021.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Haddadpour, F. and Mahdavi, M. On the convergence of lo- cal descent methods in federated learning. arXiv preprint arXiv: 14425, 2019.
Mishchenko, K., Malinovsky, G., Stich, S., and Richtárik, P.
Proxskip: Yes! local gradient steps provably lead munication acceleration! finally! In International Con- ference on Machine Learning, pp. 15750-15769. PMLR, 2022.
Hu, Z. and Huang, H. Tighter analysis for proxskip. In In- ternational Conference on Machine Learning, pp. 13469- 13496. PMLR, 2023.
Mitra, A., Jaafar, R., Pappas, G. J., and Hassani, H. Lin- ear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34: 14114666-1619, 2021.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning, In International conference on machine learning, pp- 5132-5143. PMLR, 2020.
Nesterov, Y. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2013.
Khaled, A., Mishchenko, K., and Richtárik, P. Tighter theory for local sgd on identical and heterogeneous data. In International Conference Artificial Intelligence and Statistics, pp.
Osekowski, A. Sharp martingale and semimartingale in- equalities, volume 72. Springer Science & Business Media, 2012.
PMLR, 2020.
Li, X., Huang, K., Yang, W., Wang, S., and Zhang, Z. On the convergence of fedavg on non-iid data, arXiv preprint 19Xiv:900..22111 2019a.
Patel, K. K. and Dieuleveut, A. Communication trade- ofis for synchronized distributed sgd with large step size. arXiv preprint arXiv: 11325, 2019.
Li, X., Yang, W., Wang, S., and Zhang, Z. Communication- efficient local decentralized sgd methods. arXiv preprint 1910009 126, 2019b.
Pathak, and Wainwright, M. Fedsplit: An algorithmic framework for fast federated optimization. Advances in neural information processing systems, 33:7057-7066, 2020.
Malinovskiy, G., Kovalev, D., Gasanov, E., Condat, L., and Richtarik, P. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692-6701. PMLR, 2020.
Pedregosa, F. Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-learn: Machine learning in python. the Journal of machine Learning rexearch, 12:2825-2830, 2011.
Malinovsky, G., Yi, K., and Richtárik, P. Variance reduced proxskip: Algorithm, theory and application to federated learning. Advances in Neural Information Processing Systems, 35:15176-15189, 2022.
Pflug, G. C. Stochastic minimization with constant step- size: asymptotic laws. SIAM Journal on Control and Optimization, 24(4):655 666)666666666666 1986.
Mangold, P., Samsonov, S., Labbi, S., Levin, I., Alami, R., Naumov, A., and Moulines, E. Scafflsa: Taming hetero- geneity in federated linear stochastic approximation and td learning. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, vol- ume 37, pp. 13927-13981. Curran Associates, Inc., 2024.
Sadiev, A., Kovalev, D.,, and Richtárik, P. Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with inexact prox. Advances in Neural Information Processing Systems, 35:21777~ 21791, 2022.
Mangold, P., Durmus, A. O., Dieuleveut, A., Samsonov, S., and Moulines, E. Refind analysis of constant step size federated averaging and federated richardson-rombeerg extrapolation. In Li, Y., Mandt, S., Agrawal, S., and Khan, E. (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, vol- 258 of Proceedings of Machine Learning Research, pp. 5023-5031 PMLR, 03-05 May 2025.
Schmidt, M., Le Roux, N., and Bach, F. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017.
Stich, S. U. Local sgd converges fast and communicates little. In International Conference on Learning Represen- tations, 2019.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. Communication-effiicee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Wang. J. and Joshi, G. Cooperative sgd: A unified framework for the design and analysis of communication--ffin sgd algorithms. arXiv preprint 4888:: 2018
10

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Wang, J. Das, R., Joshi, G., Kale, S., Xu, Z.,, and Zhang, T. On the unreasonable effectiveness of federated averaging with heterogeneous data. Trans. Mach, Learn. Res., 2024, 2024.
Woodworth, B., Patel, K. K., Stich, S., Dai, Z., Bullins, B., Memahan, B., Shamir, O., and Srebro, N. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-1034-0 PMLR, 2020a.
Woodworth, B. E., Patel, K. K., and Srebro, N. Minibatch local sgd for heterogeneous distributed learning. Ad- vances in Neural Information Processing Systems, 33: 6281-6292 2020b.
Yang. H., Fang, M., and Liu, J. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11200 2021.
Yu, H., Jin, R., and Yang, S. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7184-7193 7193. PMLR, 2019a.
Yu, H., Yang, S., and Zhu, S. Parallel restarted sgd with faster convergence and less communication: Demystify- ing why model averaging works for deep learning. In Proceedings of the AAAI conference artificial intelli- gence, volume 33, pp. 5693-5700, 2019b.

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
A. Preliminaries
A.I. Strong convexity and Smoothness
We list here the incqualities that are consequences of strong convexity (AI) and smoothness (A2) of the functions that we minimize in (1). For E [I....,N) and (e) V(e) A1 and A2 imply that, for any 0, H' E IR,
| Te (0)
(0))1² - L(V ((e) 0¹) VF (0)
(10)
This inequality is generally referred to as co-coercivity of the gradient of f(e), and is proven in Theorem 2.1.5 of Nesterov (2013). Assumptions Al and A2 also imply that, for any 0, 0' E IRd
(V)) - Viee (0),0 0¹) S -u110 1¹
(11)
This second inequality is generally referred to monotonicity of the gradient of f(e)- Finally, smoothness of Fã for (t) E Z (A2), means that the gradient of (()) is Lipschitz, i.e., for any 0, 0' E IRd,
(c)
(c) (0) - Ro (f')l S L to (0) - V t (c) (f')l
(12)
A.2. Iterate Operators.
We recall the operators defined in Section 4.1, that generate the local and global updates of SCAFFOLD. For c E (N....,N..
E IRd, S(O E Rd and ((c) E Z define
((o) = - (
f ( (0) + +
Then, set (0o) = 0 and define recursively for 1::--1
(z (.)) , Att) E Zht1,
[(c)
Thet (0: ((e)= *() = = (T) (T (c) Stop
E(o) 11:h): ); S(o)) (c)
=((t))
This allows define the global update operator, denoting &(I.N) (E()) and 21:H
2(I:N) (2/1
1:H1
1 N N
T(o: ((INN: ((1:N)) =
(0)
(0: E(o) (0: 1:#1
2
Similarly, we define the operator that updates the control variates, for c E f1. fl..... N). as
1 V (S)g 0, =(tht)))) E()) + 7 (T)) I.H) T (0; & (y 1.H =(iik)))
Thus, we can define the update of the SCAFFOLD algorithm with noise
=1:H =(1:N) as
S: E()) S(N) 1-H ((1:N) + (T(8: f(I.Ny. Z), (a)(E 0
21- 2(1:n)) )...) V...,,
B. Proof of Convergence of SCAFFOLD
B.1. Convergence of Scaffold's iterates - Proof of Lemma 4.1 and Theorem 4.2
We now analyze the convergence of SCAFFOLD's 's iterates. Specifically, we aim to demonstrate that, akin to FEDAVG and SGD, the itcrates of SCAFFOLD (i.c., its parameters and control variates) converge to a unique stationary distribution.
To establish this result, we first show that SCAFFOLD's updates exhibit contractive behavior under certain conditions. For this purpose, introduce the following norm, which assigns appropriate weights to each parameter and control variate,
| = | + 2211²
Σ
(13)
N
12

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
where X (0, Eu) :()))) This can be seen norm on ( such that |X]] (X, for X R[ and where
²² H N Ida,....
2² H
A diag
Ida:
N Ida
and Idg is the d d identity matrix. We now show that S is contractive operator under the norm I1-Ila-
Lemma 4.1 (Restated), Assume A and A2. Let Z Z ((ii))
(1:N) be i.i.d. random variables satisfying A5. Let the step size
y > O and number of local updates H > 0 satisfy S (/L) and qH (L + μ) 1. Then, for any 0, 0' E Rd and
(5 Moy l E R2 such that Ee=1 Ex=1 6/e) = 0, it holds that
E B[|s(X; 2) s(X'; 201 511
7/1 H
| IX-X'IX
(8)
4
with X- (0)) ((N))) and X'= ((m)....((()))))
Proof. For readability, we define, for 0 0', Sagy ((o) updates and the control variates E(e) updates as,
RRd, notations for the global parameter 9 update, the local parameters
g+ = T(0; S(1-N): (I:N))
0/s) = T (0: Ste) (,5)))
s = (6)) z(o"))
(14)
and similarly for 0' and S(o)'
8++ T(8': C(:NN) Z(it))
8/h (
Tiog(0 (6': [(o)= Z(o))
% = (6)o ,',
(15)
Recall that 0+ -
N 0g and 0++ N > 1 We can thus use the fact that Emm E(0) = 0 and >, Elc)
0, as well as Lemma F.2 with xe (0) + +H and ye = 8 + HH obtain
(c)
110 - 1
1 N
00 + HH))
1
Σ
(6)
+
N
1 N
10 + + 010 HHE
1
Σ
7111
(Eto) - x
(16)
N
where we used the fact that 7HS = HHH + - (a) and -HC = =7HE( + +
(0) in the second term. We now
define the shifted parameters, for E {1, .., , N1 and h E (0, HO....,.H. H..
0 = ( + (h((
0 = 8/a + yhE(
(17)
The identity (16) can be rewritten using the notations introduced in (17), which gives
5(X)
2)
Σ
10L 121
(18)
remains derive a bound on each term of this sum. We proceed by induction, on {O..... H 1} we have
Thh 12 = 0
> (VF
(e) (0%)
VF to5 (0%) l
(c)
Expanding the square and using (17), we obtain
10/21 1 7 112
(c)
= = [ - / o + Vi
2h+1 (0%)
(0)
-
(0%) 1|2 - 27 (,)) - /
vF
(0)
(0%)
- vF
z
t0
(0%)
(c)
13

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
= h - |/) ||
VF + +
zh+1 to
zhrr (0%)) - VF(0) (o) (0())-
(o) (8%)
(%s) %
2h11 VF(C)
(F 2(0)
(c) (0%) 27 (/
((0) - -(a) VF(()
2h11 (0()) - -VP() 20
(0%)
Now, using Young's inequality to bound 24 = 2(7 1 1/ ha) ) (7/1/2 S La²
Laz + + b -12 we get
-2:2h(5(0) Siop. (4) (c)
(0%) ( VV
200 (0))
s 7 2 [10
| - E/ol f|= 2 V
3:oي ( - VF ((() (0 l2
Plugging this in the previous inequality and using the co-coercivity of the gradient (10), we have
2411 VF (o)
2011 VF (c) (%)
10/ 1 < (1()) ا 11 7 L322 - 12 (7 - ( - (e)
(g)))
Using the fact that 7 S 1/2L to bound -(7 - 7 V -7/2, taking the conditional expectation and using that [(o) is
independent of (0) and monotonicity of the gradient (11), we obtain
E
(6)
/ - 74
0 (0)
- 0% 2
l| + + - E6111
(19)
2
Now, we remark that, for a, b E RRd, we have a² bb) s 2(aaa))2 202 which implies that -aa S - Therefore, we have
gh+11 - 0//
7/ 2
0 >/(E(e) - E(>o\\ 5
7H4 4
0/ 0 +
20h²24
2 (()) - E(e3 l|
2
Using this inequality in (19), we obtain the following inequality
| h+ -1
0 Zioi < (1- 2/4 2)) - || + (7 (799m++912D)) ||Ec]] -Eco|
|
E
(20)
(e)
Taking the expectation in the last inequality, straightforward induction leads
E pt]|" s (1 < e 0 2 +
) "
(H
1)( + 11)
[(0) Etel?
2
Consequently, whenever (L + 1)) S 1. we can sum this inequality for c = 1 to N to obtain
N -
क 2] || < (1-- ) 11
0 0 2
122112
N Σ
((e) - E/A) 1| S (1
21) H
|- x x
E
+
2
N
4
where the second inequality comes from 1 122 S (1 -
H (1 122
Theorem 4.2 (Restated). Assume AI, A2, and A5. Let > 0, H O. such that 7 S 12(( and 7H + 1) S 1. Let {X with X = (0', S.y.....S(yy be SCAFFOLD'S 's iterates with step size Y and H local steps and X p. where p is probability measure on X such that [|[ < co. Then, the distribution pkt (y.H) of converges to a unique stationary distribution HH) satisfying J | T (T. (dX) < oo, for any E N,
(n (G.H) S (1 4) Ht
W2(e,
Proof. We use Douc et al. (2018, Theorem 20.3.4) with the cost function c(x, x) = XX - X11 where the norm || is defined in (13).
Note that the convergence toward the stationary distribution is geometric.
14

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
B.2. Bound on SCAFFOLD's Global Iterates in the Stationary Distribution - -Poof of Lemma 4.3 and Theorem 4.4
Lemma 4.3 (Restated), Assume AI, A2, A5, Let Z (1:N) be i.i.d. random variables satisfying A5, Assume the step size y and the number of local updates H satisfy "H + n) S 1. Then, for all 0 E TBé and (&(o) J C TRd such that
N S(e) = 0,
E E|IS((: 2) - xx1I 1
H IXX +
+2
with the global iterate vector X (0) ((N)))
Proof. As in Lemma 4.1, we define, for 0 Rd, notations for the global parameter update, the local parameter updates and the control variates updates as,
g+= = T(0; S(::N:: (1:N))
Sa = Tic)(0 ((50) </6) = (6e
(21)
H}. for C E {L...., N and h E {0, H Recall that -+ = -N --- D/e
We can thus use the fact that Ee f(c) =
0
and Σ ((0) = 0, as well as Lemma F.2 with = (1))) + (H) and ye 0' THSio to obtain
N
N
1012--11-
(c)
+ +
Σ 0=l
(0 (
l|
N
N
c=1
N Σ
1
Σ
o + +((l(()) - -0" -
2
11 (4to) - -Sio) )1²
(22)
N
N
where we used the fact that (HE 7 (H + +00 -+ in the second term. Define for 0 E Rd, E {1, N) and {O.....H) H}
3 = Ta (0; ((:(t))) + 7h(Er0) - E(a) = oiss + Th(((()) - -(())
(23)
The identity in (22) can be rewritten using this expression, as well as the norm ||.IIa defined in (13),
2) - x 11 N N Eiog 0-112.
(24)
remains derive a bound on each term of this sum, by induction on h {O,... 1 - 1]. We have, for o E NJ.
10
0-1 = [i/))-
1 0 -x (VF
Zh+1 (0%) {io ) 1|
(c)
Expanding the square and using (23) to write
(c) = 0% + TM(E(c - (( : we obtain
loht 1²12== = 10% 0-1
27
0 VF
2441 (0%g + +(6) + V
2h11 (0%) +(o 2
(c)
10% 0-1|
+122 VF (c)
(0%) + |
(pto) 0-, V (0)) + StA - -272h ((c) - Eto Vi v0 (0%) + +tio)
Replacing f//)= ((()(())), we have
5h-1 -0-1( Z = =110%g - -0+1 00-12++77 +
zhtz
(0%) V (ot) /|/ Z
E
(o)
27 08 - 0-, (((()))))))) (00) - 2, (E10) - E6or Vlo -V)))))))))))))))))))))))))))
15

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Using the inequality ||u + v/l2 < 2||u||2 + ||a||
and bounding the two terms using co-coercivity (10) and A5, we can bound
E
(0)) - Vio001)1 [ E (c)
VF to
3 VP (0*) V
ia (0)
vio
Zlo
221
8 (io (((a) +20
Now, using Young's 's inequality to bound 2y2 / (7 (7 1/2 1/26) S s + 7---16 and co-coervicity of the gradient (10), we get
-272n(Eee Eee Vial()))) - V)) S 17018 - -ic) 12 + 1 [ - (()
L
S 5 Eie) 112 700 0', (lo v((o(())
Plugging the last two equations in the inequality that decompose the update above, have
E poj - 0-1?
- 0 0-12 + L 11
(0)
(r 2)00) 0 ((o(()) (()) + +
And using the fact that y S 1/4L to bound- -(7 - 2222.) s -7/2, and the monotonocity of the gradient (11), we obtain
E Th+t1 0+1 12
Zioi
Th (c) S
- 0-0 1² - 2444
b/ 0²1 + + 1 L - Eا + +2220?
(25)
2
Now, we remark that, for a, b E RRd, we have ||a||= = 1|a - + b1l 1 |all2 + |16|2. Therefore, we have
s 211a b112 + 2 2|1 which implies that -Ila - b112 S
7/4 2
O 1 0²12
7/ 2
(e) - 0" -h((E - E(o) E(t) > 7M
1
1
00
3012p
(10) - EGoal" 11
+
4
2
Using this inequality in (25), we obtain the following inequality
5h+1 0-1 Z
s (1 2 p - 0-12² 1
0012² + (5(0) - -5io 12 +2700?
E
(26)
Applying (26) recursively, we obtain
0r |] S (1 7H
110 - 0-12 + HH - 1)( 11)
E (0:
11(0) -(o0 2 Hoo?
(27)
4
2
Consequently, whenever (L + p)) < 1, we can sum this inequality for e 1 to N to obtain
2/ 1-1001+++ 1- 122 N
E 1 ( 0p] < (1-
Els - 2 Ho?
(28)
4
2 N
< 1 7/1 4 |x - X - 22 Ho?
4
and we get the result of the lemma by taking the expectation of (24) and plugging this bound.
Theorem 4.4 (Restated). Assume A I, A2 and A5. Let > 0 be the step size and H > 0 the number of local updates. Assume that 7 S 1/4L, and (T + p) < 1. Then, for any T > O and any x E X, the iterates and control variates of SCAFFOLD, X" = (6", (50) - 5( satisfy the inequality
(5(1)...
E -XIX"-XXRR
- x [3] < (1
(1-1/
7/4
HT
1X
X+1
87
4
where X* is the global optimal vector.
16

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Proof. The proof follows by applying recursively Lemma 4.3 with the natural filtration of the process (X)
The following corollary is a direct consequence of Theorem 4.4, and gives crude bound on the squared error of in the stationary distribution.
Corollary B.1. Assume A 1, A2 and A5. Let 7 7 be i..dd random variahles satisfying A5. Let 0 be the step "(:N)
size and H > O the number of local updates of SCAFFOLD, Assume that y S 1/4L and yH(L + 4) $ 1. Then, for all {0,.-.. H), holds that
87 _|10 0-00 | 1 A(r (d0,d) s
o
(29)
H22²2
N
/ ||50] - -siol I( (d0, d3)
87 o²
v
(30)
N
1
(8: Ecos: ((o)) - 0-12
10:0--011 (6.m) (d0, d3)
87 0²
E
(31)
N
where = (( ((N)) E Rxx
Proof. Inequalities (29) and (30) follow from Theorem 4.4. The third inequality (31) is obtained by unrolling (26) until similarly to (27) and summing over 1 to N.
B.3. Bounds on SCAFFOLD'S Local Iterates and Control Variates in the Stationary Distribution Proof of Lemma 4.6
Lemma B.2. Assume AI, A2, AS. Let Z- Z1:8 be i.i.d. random variables satisfying A5, Assume the step size ? and the (1:N)
number of local updates H satisfy 7H + (1) I 1/12 and 7B I L. Under these conditions, it holds that
E [T Z 8-
T(,, d3)
18y o²-
+ +3²2
(3. /IS(00 1 d3)
(32)
( (15(s) -Gco) li (m. (d8, (d0, d3)
8(L + 1)
4L +
2/3
H-1 Σ h=
μll 0f
E
| (0; E(o) Z(o)) 1-] -
(G.,n) (do, dE) (33)
11
N Proof: Let A E d and (2m C Rdd that satisfy the constraints 2 S(a) O. Based on the proof of Lemma 4.3, we
define a notation for the local parameters and their counterpart with ideal control variates,
b = (io E(o)) ((ab)) i = 0% + -h(E(() E(e))
(34)
(35)
Bound on the local iterates. Then, following the same lines of proof as Lemma 4.3 (see (26)) and using the fact that HHL 1, we obtain, for any h < H, and NJ.
H2²
E
100 0-1[3] < 110 01 +
2 |1E(e) -6,111 22 2 Ho?
Since 0/-= = 0%0 + ( - (. ). this gives the inequality
E 110% 0-[]]] s 2E 110% 0 0-]]]] + 22 1/
< 2| - 0-11² + +3 112111 - Go
47 Ho²
Integrating over the stationary distribution of SCAFFOLD's 's iterates and using (29) from Corollary B.I, obtain (32).
Bound on control variates. For ease of notation, we define
Zh+t
(0h
(36)
(c)
(c)
17

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Let E (I,..., N), the control variate update can be written as
4-1
N H --1
1
(/) = S(e) +
(1)) + ((0) + h+1
-0+
(00)) + ((0) + +5(0))
7H
h=D
h=0
H-1
H-1
E(( H
1
?
Σ
fio (0a) + {(e) + h-1
(0)
7
V Vi (1))
+ E() h+1
N
h=0
==1
Using Di S(3) = 0. -i=1 (0*) 0. {/
V (0t) ) and reorganizing the terms, this gives
N
Ø-1
(/)) - 5(o) = -(() E( NH
((o)((()) + [()) - ((())(())) + ht1 - -E(O))
[c) +e(e)
(37)
h=0
1
Σ Σ
(()( (VS()(0())) - vio)(0)) + sr1 x+11)
[()
(38)
NH
K=D
Taking the squared norm and expectation of (38), obtain
N
H
E [Istto - 1?]
s 2E
NH
Σ
( -(o(0)) - (v(o0)))))-((()))
i=1
h=
N H
+ 2E
h+1
A+1 (c)
NH
h=0
Using Jensen's inequality, as well as E i * and fo..... H 17, we have
h+l (())
(1:N)]
= 0 a.s. and E
[() E() (1:N) = =0 for all c E (1,...,N),
N
H-1
e [isto - -6 S
4
E
II
(o))))))))
(10))1)
NH
i=1
h=0
H-1
2
E
1
(c) |2]
N
By Lipschitzness of the gradient (12) and smoothness of the error noise (A5),
4L2
N
H-1
E [
1/
<
100
- 11 + 110% 0-]]
NH
h=
N H
2
BE
[10%)
0-1 10//) - -011]]] t40?
N
1=1 N=0
<
8
2 +
4L2
2,3
ΣΣ
N H-1
E
110% - 1011 + 110 - 1-11]
H
NH
hm0
Integrating over the stationary distribution of SCAFFOLD's D' iterates and using (31) from Corollary B.1 gives inequality (33).
Lemma 4.6 (Restated). Assume AI, A2. Let 7, = (1:N) be i.i.d. random variables satisfying A5. Assume the step size Y and the number of local updates H satisfy (H + 1) S 1/12. Under these conditions, for any h E (0..... H) and c. E [I....,N, N). it holds that,
|IT (0: E -( 11:t)-00pp 00 1|] (d0 d3) -
28
(9)
f (1Eees - (( 54LO? μH
(10)
18

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Proof. Solving the system of inequations. We now aim find constants Ce) and Ciay for E (I,..,, N), such that for all E [O....,HH, H}
f (0: Ete 2(g) 0 0-1²] (T..))d0,,d S Clo)
and / /lEEc Ete]ll (D) (d0,dd) S C
By the first part of the lemma, we have
187 18 of 3 2 (c)
9L C S μH
(0) S
and
o + 12L (c)
Since yHL S 1/12, this implies that
18y
27-2
217 0,
C/3) S 0 +
0. + 33+
S
+
C
(c)
p
16L
12 18
40T.
C (0)
S
0
0x + 36 2 2H2
0, C
μH
μH
4 (c)
and the result follows.
B.4. Higher-order bounds
We now derive bounds on the moments of the error, up to the sixth moment.
Lemma B.3. Assume AI, A2 and A5. Let 0 E R& and ( C TR that satisfy the constraint Ee S(e) = 0. Define the global iterate vector X (0, Scpp..... ((x))) and the optimal vector X* = =0"", -(ip...... f(x)). Further, let = Z 1:11 be (1:N)
a collection of i...d. random variables such that for any c C {1....,N) N) and h E [l,..., H), Z(o)) =(())
Assume the step size y and the number of local updates 1 satisfy 7 S 1/48, TH + 11) S 1/24. Then,
E [[IS(X; Z) Xx-11 1/3 S (p/) X 1 + 40, Ho?
(39)
Proof. We denote, for 0, Ecyy....,. E IRd, notations for the global parameter update, the local parameter updates and the control variates updates as,
gt T(( E(-N): (1.h))
8/3 = ( (0: E()) 2
<t V (o)) 0, 2(00))
for e E (1...., N} and h E fo..... H}. as well as the shifted local parameters
p = 03/ + Th(E(e) {(6)
We recall the identity from (24),
|S(X: 2) X 0100--0112-
H222
Σ [(Ec) 1²)
1 N
10th 0-113) 3
N
c=1
Thus, using Hölder's inequality, we have
1 N
E -
1/3
1100 - 80 1/3
(40)
N
We proceed by induction. Expanding the second power, for {o..... .. 1), using Eie = (()))(()*
10 0-112= = [0] 0+ -7( (VF ( (0%2) (io( 1|2
(c)
= =10% 8+| 0-12² 2n 0% 0*,
VF
2 (ot
V((an(0))
+ 2011 (0%) (
(c)
19

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Now, we compute the third power of this equality. We write it as (a² (a2-27b- )², with
a² = 10()) (e)
11112.
zh+1
2yb = 27 8 - 0¹, VF
(c)
(0%) - vioo(())
(r)
x2 = 72 / V
2
(c)
(0)) - Vi00100)
We remark that [b| S ac, which gives
10 - 16 = (a² - 2xb+
= a -
-6 + 666
S a - +3 + + 127 + + + 7
a. - 6,a00+ 20, + 157' + 0 4
(41)
Remark that a o( measurable. m Since B% 0% + 7 -(()) we can split the dot product b similarly to
Lemma 4.3's proof, using Young's inequality to bound (u, s ul + 6||l|| for any two vectors u, v E IRd
E
6rabb|
[ = Gyaa (0%) 0", (0)) V (0a)
= a² (-67(0%)) - -0", v(ie((()) - v(a)(())) 6)ph(56)) - Elo v(a - v(o)((1))
< at (-6- - 0², ((o - ((())(0)) + 1 - 5/ + 2 L (Q(( - ((00(1))1))
Which gives, by co-coercivity of the gradient (10),
E
- [ ك - 5-a - 0*, Vi (0())) - ((a)) + La (aa - E(,
Furthermore, we have, by Lipschitzness of the gradient (12), and smoothness of the error noise (A5), and using the definition
B 0 ?h(EE)) - E(o) as well as the fact that (xr + y 2)* < (x* y* + =*) for 2 < k S 6.
Aht (0%) - (0o 1 VF
E 0 [
= =naaa ca
Z
(e)
$ 2
E
h+1 (c)
(0%g) - VF (c)
2h11
(0))
+ +
< 2
6-
12L
k-
10% 0-, v(o - v(a)((0)) + +o,
(42)
b!- (e)
where we used (12) to bound A2 and the conditional expectation of (41) and plugging (42), we have
| F
(c)
VF
(())
(0)) < 4 - 00 = La in the last inequality. Taking
E 100- 1-
Z
E aa
Gra't +
+ 207"0''²" 15 + ac + Z
S a - -57a Sraa(0// (0%) - 00, (o)) Vi(o((0)) +36, |
(10) &
20a 4 Σ ((2))* 1 (0% 0+, v.( (0) + 20 Σ (2700))a00
+20
Letting 7I. $ 1/40 to bound the second term, we get
E | 11 [
S 8 ya² (a0(0/)) - -0,, Vio ((()((0))
+ 36y 1/2 La 1 [10) - -sto 12 20 E(270, (a &aa-
k=2
20

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
As in the second-order bound, we use the monotonicity of the gradient (11) to bound -7a"
-ra" (0%s 0*, f(c
((e) I -mpa"100 I1? which implies, using the fact that - -|lull2 < - 2112 + v112 + ||el1 for any pair of vectors
u,U Rd.
ya (0% - 8", (()) Vi(((()) & 2yuaa - 00112 + n² plallll - 5tal?
Finally, we obtain
6
E 110tt-- - 0-11 [(0) < - (2/2)a + 16
+ D)a E sio)
|/ + 20
k=2
(1-74/2)10 + +.3,, 1, (u+ + 1) - {/o
1|2 Σ
+ +00
(2 )
2
2-22k
2h
(43)
k=1
using for is odd, (uo)* S wh+ 1 k /22 + /2. Using Hölder inequality, we have
Elll 1 1- (1- 24a2))(aa11 L
Etg) 191// + 30 Σ (2yo.) (2
Therefore, we get
B11@ht1 11] S (1 -11-7u/13 (11111((1))1111) (000)//))/=////1>>> + + 12 L)B S%c) 1011// + +0772?
(44)
Using (1 - 1 < 1 - 7///66 and straightforward induction shows that
11100" 0r 19)1//3 - - 7//66]10 - 1- + 12- + L))lE()) -T) 40H/20?
Using (1-1u/6) 21 1/2 and y ( + L) < 1/24 completes the proof.
Corollary B.4. Assume AI, A2 and A5. Let > 0 be the step size and H > 0 the number of local updates of SCAFFOLD.
Assume that L S 1/48 and y H + μ.) S 1/24. Then, for all h E (O,..., H), and E (1,2,3), it holds that
8 8r
2p * ()) (d0, dE)
1/v I 0
2407
(45)
20
1/p
240y
N
Σ
E
The (0: E(o) Z(05) -
T
T(. (d0, dE)
S
(46)
H2 N
Σ /|s0
(100 - -too 22
(d00 (d0,))
1/2
<
2407
0
(47)
N
p
where = = (E(1) (E( E Nxd
((N))
Proof. By Lemma B.3, we can bound the A-norm of the T--th element of the process (X ) as
T-1 Σ
E [[IXT x-11 1/3 <1 7//6) HT xx
x
(1
71/6) Hi 40,² 20,
0
Taking the limit as T + 0o, we obtain
lim E [|IX" - T-0
11]
1/3 <
2407H
o²
The result follows from derivations similar to the proof of Corollary B.1 to bound the third moment of ||X- -x11 (i.e., the case p = 3). The result for p = and p = 2 follows by Hölder's inequality.
21

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Lemma B.5. Assume AI, A2 and A5. Let > 0 be the step size and H > 0 the number of local updates of SCAFFOLD.
Assume that x S 1/48, 7 (T. p) S 1/24, 7H4221122 v 1/12 and BB s L//12. Then, for all h (o,..., H),
1/3
600Y
(0: Mo0))) 0* 1 (T. (d0,d3)
0
2
(48)
p
(/1Eico (( (dl, d3)
1/3
3000L
0-
2
(49)
Hu
Proof. The proof follows the same lines Lemma 4.6.
Bound on local iterates. Let 0 E Rd and {5(o) l C Id that satisfy the constraints Ee= S(c) = 0. To bound the local iterates, we proceed as in (34), we define 0%) (c) (eo) Ziott) and 0io) 0f6s + yh(S(e) f(e)). Similarly to Lemma B.2, we use Jensen's 's inequality to bound
E
[10% - 11
s 1/3
110% - 0¹110] + + - - Eto]11
(50)
Then, unrolling (44) for h steps and using the fact that 7H( + 11) S 1/24, we obtain, for any h S H, and E (I....,N),
H22
/ |10 - 0-11-] s 11-- 1-
[5()) Etal1 2 +407 2072HO,²
(51)
2
Plugging (51) in (50), we obtain
3²²
E1/3
[10% - -011
s |10 1+
(15(e)
E/ + 40,² Ho?
(52)
2
Taking the third power of this inequality, integrating over the stationary distribution of SCAFFOLDD's iterates and using Corollary B.4, and using Jensen's inequality, we obtain
E 110% or [1] Tn (d0,d3) d3) < / (3 [10-0011 -16 - + 40 .7 7 0.. (1, (d0, dE)
s 8 / [166] - fio) (l (do, d3)
3a. (2403 + 1) 73
5
(53)
43
where we used y < 1/48 and 1/L < 1/M to bound 40 < 1/1². Bound on control variates. To derive the second inequality, we start from (38),
H-1
to - NH i=1 A=0
Σ
((T1) - viil(0)) - (V)))(0))) -V)o(0))))) +o/tt - =(()
Using Jensen's 's inequality, we obtain
N
R1/3 [1st)
11
1/
(l vi(s(0))) - (Vi())
V 11)
NH
h=0
|IN
N
H-1
1+l ||
6
H-1
+ 1/3
Σ
4E//3
/3
h+1
+
H
(c)
h=0
To control the last two terms, we note that they are reverse martingale differences w.r.t. the filtration F ((Z(iNN)) By Burkholder's inequality (see, e.g., Osekowski (2012), Theorem 8.6) which holds due to A5, we have
E1/3
N
カ-1 &
32 N2 H2
B1/3
Σ
カ-1
Σ
I 1
(())))))))))
3)
32
1//
|1 1
NH
N2 H
K=
22

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Using the smoothness of the error noise's moments (A5), we thus obtain
/1/3
II
N H
h+1
32
H-1
BE 100
0-10 1/3
+o?
N2
i=1
i=1 hm
Using Jensen's 's inequality again, and proceeding as in Lemma 4.6's proof using Lipschitzness of the gradient (12), we have
11/3 [1sT]
-E(2]1 $
412
H-1
Σ
EV3
[1e9
- 0-110]
R1/3 [100 - 81110)
NH
h=0
4 3
N H-1
Σ
/3R2/3 [10% - -001
+ +o?] + 4.3 3 H-1
Σ
/ 1/ [100% - 0011]
+ +o?}
+ N 2
H²2
1=1 h=0
h=
8 82
o +
4L. + 4. 3
N ΣΣ<
E2/3 [100) 80110]
+ E1/3
[100% 09188}
(54)
H
2
k=
Plugging (52) in (54), we obtain
72
8L. + 723
22
E1/3
(1Et() f(e) [1 $ H o
(100 0 11+
[15(o) E(e) + 407
2
72 0. + (40- 8L2 + 404 7
8122 + 723
10-
0012
+ (3.4L² + (63)) H(((() - Eic)
H
H
72
1 1+5
0.- 81.² - 72, H
1
3
< 0
10-011
+
(1(())
E(e) 12
(55)
H
96
16
where we used 7 S 1/48, 7( + p)H s 1/24 and /1///331/2 1/12. Remark that 1/96+3/4 + third power of (55) and using Jensen's 's inequality, obtain
1/5. Taking the
[ 11 S
783
H3 0. +2 (
8T. (812 72/
) 110 1- +
32
|15(0) E6
H
53
Integrating over H), remarking that f [1ISt) - =00 T((,,)) (dB, d3) = (1 Stg ( (d00, (d), using the fact that 32/ 3²/5² s 1/10, and multiplying the resulting inequality by 10/9. we obtain
/ (15()) -Eoll ( ()(8,) (dH,dE)
10 783
8L + 728
+
10
10 0
(n dE)
H3
H
10 783
(8L2 + 723)3
2
10 783
L6 + -3
240
3000 L
o. + 10
6
6 <
0 + 90
6
o <
1 113 0, (56)
113
113
n
H3
113
43
where the last inequality follows from y S 1/48, // 1/2 < 1/12 and xB < L/12.
Final bound on the local itrerates. From (53) and (56), we have
f IF (10%)-10 - 0-110 -0
T(. (d0, H HD / /15 - (T) (d,00 d3)
3 12402 1) .33
113
8 30003701313 of 32. (2403 + 1) 33
3
and the result follows from THL S 1/24, which ensures that 8 3000 33113 + 32 (240" + 1) - 600
C. Bounding the Variance of SCAFFOLD
We now study the bias of the SCAFFOLD algorithm. Let X E. E(N)) where the global parameter and control variates are E... E(N)) is vector in R(N+1)d drawn from the stationary distribution ((y,H)- To study its expected value, we use the fact that, by definition, the 5(X;Z) has the same distribution as X.
23

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Notations. For 0 E Rd and = (G()::...... IR-xd, define the variances and covariances of parameters and control variates in the stationary distribution "(y.H) as
Σ
T (d0, (0 (0-08 07) 07)
02
A
/ (Sia) s(a) (5ie) -(o)) (6, dz)
(00e)
105 A
/ (o 07) (Eco) - -((S) T (0-08
(d.H) d3)
/ (5()) ((e) (o - (0-0r) ((.,t) (d0, d3)
A
(0)
In the following, we use the following matrices and tensor, that appear in the integral remainders of our expansions
(0) / fir(00 +t (0: (c)) 4 0*) -0)))dt
(57)
D8 (0) = ! (1 (1-6) (1-1)V² ha + (Th (0: [(ah)) - -00))d
(58)
For conciseness, we will often use the abbreviated notations
D1 = Dio (0%) and D Di
= D (0(x))
(59)
Following an update step of the SCAFFOLDD algorithm, we obtain their updated counterparts, which reflect the adjustments made during this iteration.
g+ E(IN) ((:N))
p = T (0: S(o 2,o1
(60)
for h E (O....,II HI and {I,...,A] NJ. We define the noise accumulated in one round, with s()) defined in (36).
H
I.H
(c)
(c) (c)
Matrix notations. We define the contraction matrix l(e) = ld - 7 (0*) well as its powers, for h E (O....,
average, and scaled difference between the local matrices and their average,
L (Id - ( r
Σ
A
(Fio) -T)
(61)
Finally, we define
C1-H
(c)
H
H
Σ
(6)
5 =
:.: [c)
Id
H
#-1
H-
(c)
RI:H- (c)
11
Σ
H H-hh h- 1 (g)
(c)
(0%) - 8²) 02
gr)00a (62)
h=0
h=0
h=0
C.1. Expansions of local updates and control variates
First, we give explicit expansions of the local and global parameter updates. Lemma C.1. Let E Idd and E = (E( E Rxd, After one global update of SCAFFOLD, we obtain a global parameter 8+, N control variates E/a and N local iterates fccy as defined (60). These updates parameters can be expressed as
0 0 - 0- = r. (c)
(0 8*) + 7
HH H
(Eio)
{io) - 1:H - -R
-Y((e)
1.H
(63)
0+ 0- = i (0- 0*) + 711
Σ
N
(Eie)
- Sie)
N
R
1:H
7
1:
(64)
N
N
N
(e)
c=l
24

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Proof. Let {I,..., N3 and h (0...., H 1 1]. Expanding the gradient at step / gives
ghtt (6) (0) ? Vir + ((o) + +=(o))
(0))) ? (f)) + v2 (0)) (0l)) 0) + D (0%)- -0t) 002 5(() + =lott)
(65)
Since (()) - - (0*) we obtain
0ht11 0r -f(e) - 0- - 7V2 f(0) (0%s - 0r) - ? (f1o) - {(c) DD (0%s - -0¹) 62
= ld - > ((o) (0+) (9is 0*) (51) -f(a) -70000 3. (0%s 0*) @2 A+1
(c()
Pio)
We obtain the following expression for the local updates
H
H
H 1
0%/ - = r(t (0- 0*) Σ
(
(5/0) - -(() Σ
D00 (e)
(0/:
-0')
(
(n)
(a)
h=0
h=0
h=0
(c) (0 0*) + +
(Sie) Sto) - [(
1:11
1:I (e)
which gives the first identity (63) The second identity (64) follows from averaging the first one over all clients and using the fact that
N Cl:ll (5() - -G() = N
N
1
Σ
(fi) - Sta))
(66)
N
c=1
which follows from Eee S(c)
5(c) = 0.
Based on Lemma C.1, we can give an expression for the control variate updates.
Lemma C.2. Let 0 Fd and = = (S()))...((N)) E BN After one global update of Scaffold, we obtain global parameter 0+, N control variates c/c) and N H local iterates Oc: as defined in (60). The updated control variates can be expressed as
N
(() - S/e) = (0) (0- - 0-) + G1.
+ (5()
- -
-Eio)
1
H (6)
(5())
EGa)
N
1=1
(67)
1
R R1:H
1
R
1
1H
Σ
1:H
H
NH
H
(c)
NH
(0)
1=1
where CL-H G1.H. (0) (0) Ro) and el:ff are defined in (62).
Proof. Letce E fl..... N}. E(o) is updated as 5To = E(e) + 78 ((()
1 (0
- -8+). whicc gives
N
%0 S(o) + 7H (6)
1
- r) (0 0+) + Clal (S(e) {(c)
+
1
1::1
(5()) S70
N
1=1
N
1 I:H
1
R 1:ff
R I:
1:H
H NH
(1)
H
(c)
NH
(i)
N
= E// + E() - E(e) + T (c)
(0 - 0²) + ClEH (Eio)
{tA)
+
Cl:l (i)
(() - 6(8)
N
N
H
Ree)
I:H
+
NH
R 1:
H
1.8 (c)
NH
(1)
1
i=1
1=1
Then, remark that (6) - =(/
(6)
(E())
{ (()
(5() {(0
since G..
(c)
Id + C1:H
(o)
25

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
C.2. Covariance of the Parameters and Control Variates
C.2.1. RECURSION ON COVARIANCE MATRICES
Lemma C.3. Assume AI, A2 and A5. Assume the step size ry and the number of local updates H satisfy H + p)) S.. Then, it holds that
H
N
H² N
N
ČL.H 22 (e) (ad) (c')
Σ
1
G (c) (c)
+ + (0) +
S
+ E' + R
N
N2
N
where E' = N
1
Σ
(Elo)))002
and R = R + R + R2 + R2 + Rg. with
= R9
7²
N
E
(c)
1:11
(R(:))
x T(T (d0,d dd)
N
c=1
N
R2-
IF
Riee)
1:
(0- 0²)² Pr
N
2 H
N
[ (Sie) - -tte)) T Guff (n (d0,
E
N2
R
N
IE
(R(
(R((t) ] Ti. (d0, d3).
N
Proof. Using the results from Lemma C.I, we have
v0--8-) = [(0
( - 0*) +
H N
اIl (c)
(5()) {(0)
- 7 N
R
1-11
62
72
Σ
N
1:11 (c)
62
N
N
N2
N
N
N
T
1:11 (c)
[(0 - (() +
H
H. (c')
(م/d) - -Ste1)
7
N
N
N
(c')
e=1
d==1
N
7(0-0)+
+
H
N
N
H1:
9e')
(Ste)
- S(c1))
N
N
R
1:
62
5
(
T
2==1
Taking the expectation, and using the fact that the Zio) are independent from one client another, obtain
[ [((0-
E B((0 110+-09) -11)
=E
-
0²)
H
((()
E(O)
2
R
I:H (()
N
N
72
827
T
T (c(e)
N2
E
1:f1
N2
E
(c)
1:I1
(R(:)))
R!:-H
1:11
The first term can be expressed using the identity
N
62
[ - (+) + 7
E
1: (5ie) {(A)
R(ce)
I:H
N
N c=1
c=1
[ 0-) + H
Σ
N
H1: (5() - -sio))
82
+
22
E
N
R
02
N
c=1
2 N
N Σ
T
[(0- - 8*) + 7
> E
R l:H
[(0
(e)
(Std) - -E(er)
N
N d'=l
26

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
N
H [0 0++ +
<(c))) E [ 71
CLu (e)
(Sie)
N
N e'=
The first term can be expanded as
7H1 N
@2
[ 1(0-00 0-) +
Σ
H [c]
((()
s(o)
N
c=1
= -r 77000-)82 r
2 212
N
HLH (5ie) s(e) (Sio) - Eie)
Ge)
N2
H N
Σ (i(00 (G)) -
((a)
T
GlUH + cluf (Ete) - -0
and the lemma follows by integrating over the stationary distribution of SCAFFOLD
Lemma C.A. Assume AI, A2 and A5. Assume the step size r and the number of local updates H satisfy 7H + p)) S 1. Then, it holds that
N 7
(o)
N
1
Σ
T
B.E
N
Σ
(1)
(0)
y==1
i=1
H
N
S (1,c)
G1:1
H
N
2I:
+ 7
(5( - -E') + +Ro5
N
(c)
N2 ==
(
(1,19)
(e')
NH
1=1
where E- = 1
N Ee
E
(c(of)
#2
and
R 0. = (oj,1
(c)
+ R R +
+R
(c),3
8.
+ R&
+
R R
(0),5)
with
R (0),1
N 7 / Σ
E
1.H
1
R1:H (e)
Σ
N
R
H
T
+ RI.H H:
1
1:H
1
Σ
1:8 (t))
T (d. (d0, d3).
(3)
H
NH
(
H
(c)
NH
2=1
R 9.6
7 N
Σ1
N
/
E
[
(Alos (0- -0))
T( (d.,)) (d0,dd) ,
(0),2
1=1
R 9.
(0),3
N
2
Σ1
N
E
R
(6)
G1:1
- -E(s) (
N
1 N
Σ
G1:
(p))
(5(o) - Stor)
T
(d,, dE)
i=1
P=1
2.5 (
/ E
[
0*)
H
Σ
N
T.. (1)
(51) -E() (
1
Rioe
+
1
Σ RiHh)
T6.1) (d0, dE)
N
H
NH
N
N
R
?
E
R
1:H
1:H
Ri:l
(d00 dz)
(c),
NEL
NH
F==1
Proof. Using Lemma C.I and Lemma C.2, we have
(0+- (4t) - 5i0) = [(00- - 0*) + 7H
(((0-00
N Σ
H1.H (i)
(5()
Eis)
- N
RIH
2 INW
Σ
N
N
.N
1=1
1=1
1 N
4 (0- - -8*) + اار (56) -f(e)
H.H (f)
(5()) - -E(e))
x
N
Y=1
H
1 R 1:
NH
1
R l:
R
H
1
(c)
I:H
NH
Σ
(()
l:H
Y=1
27

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Taking the expectation, we have
( (+ 8+) (5t)) )
E
(T(0- 0*) +
7
N
H.:
(5e)) - {(s) )
(oo (0 0¹) + |// (5t0 - -((o)
1
N
H
(5(0) - -5(rr)
N
(3)
N
(i')
N
N
T
N
Y
Σ E
(8)
I:H
X
H
(c)
1:H1
+
NH #=1
1:11 (i')
N
N E
N
Y
Σ
E
(i)
I:H
H
1
R
I:
NH
Σ
R 1:11
7 N
R
1:H1
(-
H (c)
1
I:f1
+
NH P=1
1
Σ
1=1
p=1
i=1
+
E
(T(O-
8*)
+
H
N
H:
(())
6(0)
7
N
RIHH
1
R1:H (c)
+
N
R
R1
N
N
NH
p=1
N
N
7
R (i)
Als (0 0*) + cاa""
- Sia)
1
Cl:l
(G()) - siirs (t))
N
p=1
The result follows by expanding the first term of the right hand side and integrating the resulting identity over SCAFFOLD's s stationary distribution.
Lemma C.5. Assume AI, A2 and A5. Assume the step size y and the number of local updates H satisfy HHL + p)) S
Then, for c, c' E {I....... ] such that e f d, it holds that
S (0.0
P 5 A
1
2
D
1
E
H²
(
2
N
N
N
+
A 1i
(c)
(c) (c)
Σ
(c)
0.
(c)
S
C.0
S
E.0 (1)
AT (c)
Ø=1
1 N
N
N
N
5f T.
S (1.2)) (1)
C.. (0)
5
+ +R(
+ (c) (1.0) (c)
N
N
(
N2
(1,)
F=1
i=1
_
T E' A
NH ()) N E
(c,c) (6) (c)
NH
(c)
1 N
1 N
(0) (2) (e)
N
Σ
AT
0 G1:l
(0)
r
N
Σ
90) (1)
(/))
P=1
1=1
1 N
N
5.. + (e) (c,e)) (07)
N
Σ
(d)
(c,5))
Qit)
N
Σ
%i)
GLI E
(1,0)
(c)
N2
1
ΣΣ
(i)
(1.0)
31:
R
i=1/=1
where R ((cse))
R$
(c,e"),1 + +BC (e(,))
T + R (odd)
+
R (c),))2
T
R
(1,')) + ((())))
T +
T
R
+ +R
(d
T+
R
Reees with
R$ (crr),1
1
/
Ar (0)
(0- 8*)E E
RliH
Σ
R.H
(dHH)
H
N
/=1
R$ = 1
H /
cu: (Eco - -(iO) E
Σ
R1H
T(HHH (d0,
(c,c'),
(c)
N
P=1
R (+,e'), = 1
NH /
N
(5c) - E(A)
1
Σ
N
E
T
(1)
H
(c')
NH
1=1
#=1
R$ (c.e') = H²| / E
1
1-
1 N
Σ
R
(ctiet)
N
1:H ((T)
TG. (dd, dE).
N
N im
2=1
28

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
R (,,c)), =
/ H²
1 E
R
1:H
+
1 N N
I: (i)
R
N Σ
Ril R(p))
(d0,)(
N 2=1
1=1
Proof. Recall the expression of {(c) from Lemma C.2, we have
N
- = (o) (0 0*) + G1:H
+ (f(e) - -(c) -Eis)
1
Hl:H
(510)
- ETa)
N 1=1
(i)
N
N
- R
1 1- 1
R 1:M
1
1:11
1
1:11
11
NH
H
(e)
NH
(1)
Taking the expectation and expanding the product, we obtain, for any c, c' N},
(/) s(e) (Ste) - s(c)))
T (ay (0 )=202 Te + (oo (0 (8-00) (0-0") (Ere) - -E(o))
(e))
1 Σ
A (c) (0- 8*) (5c0) - -((m) T "Qui"""
1 A [o) (0- -0*) R(oo)
1
1 N
Σ R
H
N
Cl:ll (c)
((() ((a) ) (0- on) TTe)> + [o)
(5c) Sia) (fie) - -5(c1)
Σ
الا! (5c) ) (Ere) - -E(r)
%0
T
H
1
2
(c)
(4e) - -sta) E
Rliff
N
1
R (8))
N
N
ビ (
(5m) - -in) (e- - 8T) A (d)
1
G (
(()) Eis) (S(o) - -S(o))
N
N
N2
N
N
H.: (
(()) - Sis) (500) - -Eiv)) )
T
(t")
G1:H
+
NH
N
H (1)
(5()) -GO)) E
R1
N P=1
N
R
f=
1=1
1 N
E
R
1:H
1
(10-09) T TTor + (Eir) -((og
(<o) - -Eir) )
H
N 1=1
N
Y=1
N Σ
H²
1
E
RRI 1
N
1
RIlH
( (RiH
Σ N
R + 1:H
(())
1
T
x=1
N
N
N
1
1
+
H²
E
((())
1:f1
N
1:H (2)
(
1:
N
R
1:f
+
(c)
1:1
N
(i')
1:11
1=1
Integrating over the stationary distribution, this yields
ES (cdd) = T6 E"A
A
(er)
N AF
+ (0) (c) (0T)
0. Fil
1
C
1
GIH $.0 AF (1)
N
N
N
N
N
+
CI:
(c) (c,ee)
:1: (c')
N Y=1
(c)
S
(c)1)
C.l
(P)
N
(1.0
HHl (c)
+
N2
(
:=1
Y=1
N
1 N
H²
1
E
(n)
I:H
N
1
Σ
(i)
((())
1:H1
N
Σ
(
(dB, d3)
x=1
29

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
N
N
E
A r (c)
(0
8*)
1-H
R
1:H1 (+))
11H
R0
R1: (0-00)
10-) slc)) (/))
(d0m) dE)
H
N
N
i=1
N
E3
C1:H
(c)
((())((e) f(c)
(R(
N
1
(1))
1:11
T+
(fee) ) R()
1:11
9e')
((,,5) dE)
1
E
N
HL:H (i)
(1)) - fi()
RROOf
1
N
R1H
T
NH
N P=1
N
N
1
E
R
H-H
(3)
1-H
([(p)
f(e)
G2. (r9)
(d.n/d0,d3 dz)
NH
N
im1
8=11
1
E
RIH
R
I:H
l:ff
1 Σ
1:H (())
T TG.
H²
(
N i=1
(c')
N
NN Σ
N Σ
1 NV.
E
H-H (0)
1:H
(d0,) dE)
H2
N
(i)
i=1
==1
N
N
1
B
R
H
R11
1:H
R
1:H
1
R
1:H (1))
T(H,H) (d0, dd).
H²
(0)
N
N
P=1
To study the noise term, we expand
N
N
1:f1
1:
1:H
1:#1
(1))
N
(i)
(ce)
N
(())
1=1
1=1
N
N
N
I:H 1:HT (()
((d)
N
1
1:
1: (cf)
1
1:#1 (e)
I:H1
N2
Σ
(0)
I:H 1:HT
i=1
Now we distinguish two cases. First, if c + d, we have
E
1:H
1:
1:H (c')
1
Σ
1:81 (1)
((r, (d0, (d0,))
d3)
1
E (c)
1
i + 1 Σ
H2|
N
N
N
N
N22
Otherwise, we have d' and
N
N N
H²
E
H-H
N
Σ
1:#1
1:H (c)
Σ
(e)
1:
K(r (d0, d3)
2
1
N ( + 1 Σ
2
NH²
and plugging these identities in the above equality gives the lemma.
C.2.2. BOUND ON REMAINDER TERMS
Lemma C.6. Assume AI, A2 and A5. Assume the step size 7 and the number of local updates H satisfy (H + p)) S $1/48,
3/ 1/2 < 1/112, and 7/3 S L/12. Then, it holds that
1080-
2
11202
tr R <
+
13/2
N₂²
6000,3/20
2 HH
tr R
3
3///2
12
8000>
4
200
tr R$
+
Hp3/2
22
where Rd, R and R are defined in Lemma C.3, Lemma C.4 and Lemma C.5 respectively.
30

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Proof. Bound on R We bound each of the terms from Ir R$| = 1r + +2 R2 + +1rrg)) s [2 + 12 Eir + 12 [2rr We have, using Cauchy-Schward and Hölder inequalities,
2 N tr
|tr
E
1:11 ((e)
T( TH.
llstef 1:H1 [P]]
1/2 (00
(ʃ |irRttt
[2]
(d,,)
1/2
By Lemma C.13 and Lemma C.14,
7² N (H/20, + G 6//12 11/2
600,HQ 0. 6007 10073H2//2Q
Q
6 7/307/23//222 12/21111222222
tr Rr
0 +
0+
1
N₁
N N113/2
Then, by Corollary B.I, Lemma C.14, and Lemma 4.6
N
tr Rg
S
7
trE
[
(0- - 00) (d0,
N
H
N
Σ
IrE
R1HH (Sie) (
-i())
Gej C (d.0)(d dE)
N2
e=1
c'==1
28 HQ
1/2
28,
81
S9.
07
/
0+ + -2
1
/2 H 0.
which gives, using 7HL < 1/48 in the second inequality,
8/Q 43/2
224Q,
H3/2 2 1/2
90Q25/2
tr R
+
0, S
13/2
13/2
Finally, by Lemma C.14, we obtain
N N
=1=02>"1²Q22
Ir [ <
E
Ir (R(oHt
(H, (d0, (d0)
N2
112
Summing these inequalities, we obtain
|tr < 1200g>( 1/2 + 2/2 2
3//2Q
1/2Q
2
10002/===022
0 +
0, +
0,
N N
43/2
112
and the result follows from //3/2 < 1/12 and 71/2211/22111 < 1/6.
Bound on R()) We bound each term of tr R 1/51 = [0),1
0
+ tr (0),2 + tr R 0.0
0.5
(c).3 (0),
+ tr R
+ tr (0),s
S (R +
tr R.
(0)22 +| tr R + +It (6 + tr
0,
By Lemma C.13, and Lemma C.14,
(0),5
N
N NH
T + UR!
N
|r 0. (0),11
1
N
E
tre 1:H1
H
R
1:H1
R
I (P))
1:
H
(c)
1:H
NH
Σ 1:17
((r)
Th, (d0, dE)
1=1
8=1
==1
29
H 11
6y 2/12
/1/2
0+
2
2-6001Q o?)
P
27
n²/2
H2/²
0++
6007Q o?)
/
which implies tr R.
"100 1/2 46y
H
Then, using Corollary B.1, Lemma C. and Lemma C.14,
(o).1
(0),2
N
Σ
/ tr
[
|
(Alo (0- (0-00)) (d, (d0, 5.
600g
1
0f
3/2 C2
1112""
o.
31

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
which gives tr &
1800, 8/2 QC2 o. Furthermore, we have, from Lemma 4.6, Lemma C.11, and Lemma C.14,
(c).21
n172
tr (c).31
Σ
/
EE
R
C (Aio) G f(e)
1
(5(v) 5(r)) (2)
((., ((, d3)
N
6007Q
7(H - -1)L 8/
22
2
112 H
therefore, we have tr (0),31 Lemma C.14,
4800y 1/33 n 1
3.
We also bound, using Lemma 4.6, Lemma C.10, Lemma C. I, and
(c),1 - f B (T(O-0)) 0+)
H
Σ
11H (
(5))
(7) ())
Σ
(d. (d0, d
N
H (c)
NH
(1))
1'=1
33/1/2
7HL
8/2/22
1200>Q
<
11/22 Ox + +
/1 H1/2 0+
0,
2
1
and we obtain Lemma C.14,
(c) S 1/1//200+
Hy2 o.
1200~Q 0² 1
3600 70600/
1 2a/2 og. Finally, we have, by
(
2 N
Σ
N
E
R1:l
R1:H
1
Σ
R
(d.,H) d3) S
2 2-00032HHQ
122 0
NH
P=1
summing these four inequalities gives
244072Q(u + 6 1/2
H 1/2
180075/2QQ3
4800 13/2 1/2
tr R <
0
13//2
13/2
13/2
3600Q73/2 + 9600Q.'
1//2
2 >- H1²²
0.
11322
112
and the result follows from 7/3//1112/2 < 1/12 and 7H1 + 1n) S 1/48.
Bound on R
(c,et) We bound each term of tr R (oo
= |t R (c.e),, +tr R
(c.00)1 T Tttr (0 ttr (0),))2 T R (
tr R
(r)) + t (c.e'),
+ R (ccss)
+ tr tr (c,e"),s
E |tr
+ tr R (et,), T tr |r (2c)) + tr R (c,))) +
trr R$
(1) + Rs (+,0),3
T RR
+ RR
(c(o) + tr R$
(90))5/- First, by Lemma C.12, and Lemma C.14,
S 1 / tr Tr (0- E
1 3/1/2 1200yHQ w a.
R
R R(d
R R Σ
H) (d0,
S -S2
0
N
H
which gives tr R
3600/3/2Q u3/2
σ. Then, using Lemma 4.6, Lemma C.11, and Lemma C.14, we have that
N 1
|tR
(ce))22
5
1
/
ir
Ti: (5ce)
((s)
E
Reee)
1:H
1:H R(y))
(T. (d0, dz)
H
N
P=1
1 >H 1)L
81/1/2
1200; 0
<
H
2
1/
H1/2 a.
and thus Rs
( <
9600- 2000,-22//0 /2/2 1 3/2
Q
The next term can be bounded using Lemma 4.6, Lemma C.11, and
3/2
Lemma C.14,
N TH.H (51)
N Σ
tr S
NH Σ
tr I
E(s)
E
R I-H (c))
1
R R(p))
T( (dB, d3)
H
NH
2=1
32

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
1
7H
1)L
8L
1200yHQ
H
2
1//211220
9600- 9 2
which implies [tr (+,c)),3)
S
Moreover, we have, by Lemma C.13 and Lemma C.14,
]
N
N
Ir Rt
1 1T2
IrE
R1o
1
Σ
R
1
Σ
1:ff (e')
(1n, d3)
(c.e),
N
N
1=1
t=1
1200yHQ
12
<
2H 00,0 +
H²
1
1/
4800 (1 133
and thus tr R
Finally, Lemma C.14 gives
1:/2
N Σ
tr R
(c,'),5
112
EE
R
Σ Rij
N
1:f (m)
F(r d3)
===1
4
Q222
<
0
2
12
Combining these bounds, we obtain
7200/
12
tr R
0.¹
0. +
(c,e')
43/2
13/2
13/2
9600yQ (n2/2 + 16/1/23122
2 222 o+
4
113/211/2
42
and we conclude using 7/31/211/22 < 1/12 and (L + 1) S 1/48.
Corollary C.7. Assume A 1, A2 and A5. Assume the step size oy and the number of local updates H satisfy (T++p) S $1/12. Then, it holds that
R
(H 1)
Σ
N
DIRS +
-12
Σ
N
|RS
S
15080~5/2HQ
0 +
8
0
N
N
163/2
112
0,0²=1
Proof. We have, using the results from Lemma C.6,
|RR|| + 7( -
1)
N
|
|R
0 (c)
+
22(H - 1)²
N Σ
|
N
N2
c,'==
7(H 1)
N
72( 1)2
N
$ Rtr
N
tr
8
N2
tr R
(c,ee)
C,6²
2/2
6002
< (1000 5/2 H + 6000-3/2 3/2
7H +
7 2 H22)
o.t + -22 + 22 7H + 472 x2112)
113/2
112
and the result follows.
C.3. Upper bound covariance matrices - Proof of Lemma 4.7 Theorem 4.8
In this section, we derive an upper bound on SCAFFOLD's global iterates' error covariance
|| To this end, we define
1 N
N
N
c = =1'1 C
C²= =
C
1
E
(c.)))
N
(
N
N(N
1=1
c=1
c/c
33

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
We also define the following quantity, relating the average norm of the noise injected each step
N
s' N
Σ
E ا
We now derive a system of inequations that relate all the quantities we just defined. This Lemma is a complete version of Lemma 4.7.
Lemma C.8. Assume AI, A2 and A5, Assume the step size 7y and the number of local updates H satisyyyH -H(I+ then
S
11/12
CO s1 (1- H - 1 + (H
-
1 +
+0+11111
1
C$5
+
72
5
+
| ||
(68)
4
N
N
N
C < 22²20 + +47*
- 1)813 11 C5=
+ (
(1-
1
(5+A)
+
47
5
+
2
> 6:51
(69)
N
N
NH
N
1 005++ N
(1- (1-++1111
c S 22 + NH + - 1 N
9
N
|
(c,e))
(70)
N2
Proof. Parameter Covariance. Taking the operator norm of Lemma C.3 and using triangle inequality and sub- multiplicativity of the matrix operator norm, we have
E S [T'TI
TH N
N
+ G IC
+
[c) (o)
H2
N
+ Σ + |R|
N
cl==
<
||||||
H
N
+ CP
5.0 |
122
N
N
ا + N EΣ || + |R
N2
(c)
(.
This gives, using Lemma C.10, Lemma C.11,
~ s (1 - (1-71)#C
72 +
+ |
HH1
Σ
Hl1 - 1)L
7(1 - 1)L coss
N
N
2
22112 N +
7(1 1)L
7(1
1)L
H2
N
N
7H
1)L
-CE# 2(H - 1)L
-CS==
N2
2
2
N2
2
2
c=1
cc=1
22
H cD + < (1 - (1
1111 + |
N
11 - 1)2 C+== + HH - 1)2L2
(1- 1
+ + HHHH-1)LC
(1-
C$
4N
4
N
Parameter-Control Variate Covariance. By Lemma C.4, we have
|5 11 s |
| || || + | S 8
H II
1
+ H N
Σ
N
DIG
$.0 5.0
N ==1
(3)
7 H N Σ
N
11
(1.c)
III| 1:
(0)
+
H
N
N Σ
N
C
(1,)
II
|IGHT
1+
NH
Y
|E -
E'
+
| 9
34

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Averaging this inequality for c N and using Lemma C.10, Lemma C.1I, and Lemma C.12 gives
C Σ (1 -1)* H 62 || |E'| I| + (1 -1) -7(H - 1)L C + +yH (H - 1)L C2 C
NN - + 1 (1+ -
1
+ 7H : 7(11 1)L
H N
N
Σ
HH - 1)L. (+ +
) (R.t) (,( - +
1
NH (()) E' 1- - |R[51
N
N
i= P=1
which gives
C S2 C + (H 1) + H - 1) C H2H (
NN (N0==+ + +11- 1/
N ((.))
N
+ NH (0) + N
E
and the second inequality follows from HHL + 7 H - L) 1/2
Control variate covariance. By Lemma C.5, we have
|| s
|1|
|c +
1
(c)ll
Σ
NH2
NH²
NH
N
N
+ || |4
+
+
CL#
5.0
| ||
N
+ |
c
|1
Gl:
|
1
I E
||||
| I|
(ce))
(d))
(o)
(c
N
(1,e7)
E (a))))
1:H
+ R
N2
(7)
Averaging over all pairs c, d E [I,...,,N; N3 with c + d', we have
1
1
1
-005. 7(H - -1)L
C$ S S2 CO C2 +
NH²
NH²² +
NH2
+
2
+ +22 C ,(H - 1)L
71111 L2
1211-1122
1
C8= + ++11- 1 cG5t)
C +2.
4
4
N
72(H - 1)2L2
CB= + (1-
1
(ES))=
N(N 11 Σ IIR (
+
4
N
agte
3
I <2E00=
5t + 3C2 - 1
NH²
721
L)2
CS + 37 17((1-1)22 1)
1 c5.= + (1 c5==+
1 11 c55))
4
N
N(N - 1) cxc'
Bounding 1HH-11)22 C + 2. AHH-1)222 C + (HH-1)222 CC.t < $1/20%it, we obtain the third inequality of the 4 lemma. With similar derivations, we bound the control variates' covariances
4
4
1
2
1
+ -22-00 COS. 7( 1 1)L
OC C2 CO C2 H22 +
NH?S
+
SHS
5
2
+ 2C2 CO 7711 1)
+ (H 2)2
C + 22
1)2
- + (1-
1
4
4
N
7²( - L)
1
0+:=
+ (1-
1
N
R
4
N
N
N
35

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
s G + H²2 S + 3 1)L0
+ - 11)32 Ck + 37 - 11)
1 N
N +
+
R
4
4
N
Summing these two inequalities, we obtain
1 0E=
+ (1- 1 N
8
c s <2200
NHH² 5 + - 1)LC
N
+ (1 OC=
1
(1-
N
1
(BiT)
+
N
||R
(a.e7)
Since -H S 11/12?, we obtain
N Of= + (1- N
+
9 1 csi 22G00 + NH2 + ( +
2
Σ
|
(c,r))
N2
0,0²==
which is the third inequality of the lemma.
Lemma C.9. Assume AI, A2, A3, A4, and A5. Furthermore, assume that 5 - - S p1/ and HH pd) S 1/12 and _ J S 1/19. Then, it holds that
10y No
2 YAH
|R + 7( 1)
N
2
1)²
N Σ c,'==1
C < 0. +
| +
|
N
N2
Proof. Plugging (70) in (69), we obtain
- ~ 2G=C0 + HHH 2G,0* I5*
NH² (H42)(H-1))CCC
2
Σ
| (oa))]
+
4y
5"+
2
Σ
R
N2
NH
0,0==1
I 33600 +
57 5 1Hy + HH - 2
N
| (c,et)
+
2 N
Σ
R
NH
N2
0,0²=
where we used HHL S 1/12 to bound 3 HHH - 12 S C2 and 4, H( - 1)
NH - NH Using this
9
inequality again, we have 16 (H - 1)3 1,36 $ 11/122 This allows to simplify the previous inequality, obtaining
CO < CC + 67 5 + 2 H(H 1)
N Σ
N EIRGS
|
(e,
+
(4)
(71)
NH
N2
N c=1
ce'=1
Plugging this bound in (70), we obtain
-5== + (1- 1)) Csi < 1400 + NH 5" +
10
3
Σ
N
R
12G27 - -1)L
Σ
N
R
8.5
(72)
N
N2
N
c,c==1
where we used 4(27(HH (H 1)I 4G2 < 2C3, 462 - 1)L We now plug (71) and (72) in (68), which gives
NH
By
v NH
and 4627(H - 1)L
94 HHHHH-1122
N²
N..
_O < (1 - 71) 0 + (>² 1)L+ -121
4
6r H 1)L + 10 - 2
72
5
NH
4
N
36

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
7 ( - 3 1)
1
|
(cery)
N2
0,0'=1
312 (H
N
126
Σ
| (6)
+ ||R^||
4
which can be simplified using 7HL - 1/12 to obtain
c² s (1- 4 + 2;2
7H - 1) N
N
( -12
N
N + |
Σ
+
Σ c,0'=1
| (oe))
N2
Now, using 1 S 1, we have (1 n 2
/2 Consequently, we have (1 - 1-) + + - S
1 7H (H 1). Since we assumed 5 - 1) S 4/2, we obtain
2² N + |R
7H 1)
- -12
N
C (1 (1-~2HH) (1-2111)2 +
Σ
R 1
Σ
|
N
N²
c,c'=1
We then bound the variance term using Lemma C.13, which implies that
28y
Ho
Plugging this bound in the previous inequality, we obtain
H HhH C & of + N₂ o + | + (( 1)
3
N
22 1)2
0.6 (c)
Σ
+
(c,e))
N2
c,c==1
which gives the first inequality of the theorem.
Theorem 4.8 (Restated). Assume AI, A2, A3, A4, and A5. Furthermore, assume that 7/ S m/10, 711 p1) 1/48 and BB $ 19. Then, it holds that
107 Nμ
6
15080-3/22
48 - 6002,,$H00
C <
0 +
o
n//2
Proof. The result follows from Lemma C.9 and Corollary C.7.
C.4. Bounds on intermediate quantities
C.4.1. BOUND ON MATRICES
Lemma C.10. Bound on [(e) 's powers Let > 0, 2 0, recall [(o) = - -VV3 Assume AI, A2, and that
7 S I/T, then it holds that
[ l| $ (1 - 7/4)
Proof. Follows from A1 and A2 with 7 1/L.
Lemma C.11. Let h > 0, 7 2 0, recall ((o) Id 7 2 (0*). Assume A A2, and that S 1/L, then it holds that
T < 7H 1)L
2
Proof. Recall that ČI:H Id 1 B-1 HH--- Since for any (square) matrix anyy > 0 and any le E N we get that
(c)
k-1
Id - (I-7A)* = A
Σ [Id
(Id-7A)'
37

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
obtain
1 H-1
H-1 v
Σ [Id (Id - ~V2 (io)))
Σ
(1-
- s(o
(73)
H
h=0
h=0
Using the triangle inequality, A2 and Lemma 1.10, obtain
L
Σ
H - h - 1)(1 - -74)
11
h=
and the lemma follows from H-1 E h H(H-1)
Lemma C.12. Let h > 0, 7 2 0, recall ((0) = Id VV (0*). Assume AI, A2, A4, and that S I/T, then it holds that
| S C2
Proof. We have, using Lemma F.I,
1
TH - r) PHN (Id (Id=>VS(((0")) 1id-~90 ((o (V1)))0)) ")
7H
H
(Id (1)
((() (Id - (Vd->V((s(0*)) H-h-1
HN
The result follows from taking the norm, using triangle inequality, Lemma C.10, and A4.
C.4.2. BOUND ON THE NOISE TERMS
Lemma C.13. Assume A1, A2 and A5. Let y > H > 0, such that (H p1) S 1/12, then
28
E
|l [1
(d (d0, dE) & Ho² +
0
Proof. Since e/o is a martingale difference sequence, we have
#-1
#-1 Σ
11 = Σ
Bir
|
|1
(74)
(4)
h=U
By Lemma C.10, and A5, have
E
H
Σ
(1->p)* >1)^ (o? BIIT (0: (())))))
(75)
h=0
Integrating over the stationary distribution ((),H), and using Lemma 4.6 gives the result.
C.4.3. BOUND ON THE REMAINDERS
Lemma C.14. Assume AI, A2, A3, and A5. Let > 0, H > 0, such that (L++ < 1/12, then
28
E 1
TT..H) (d0,
1
If 1/48, 7H( μ) $ 1/24, 1/2 < 1/12 and 78 < L/12, then it also holds that
/
E
[IRR 1R [13]
((..H) (do, dE)
6002>2 22 o
38

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Proof. Taking the norm of Ri and using the triangle inequality, A3, and Lemma C.10, we have
(e)
H-1 1 S
82
#-1
| O
DD (Th) (0: ((o) 2(5)) 0*)
(0: 2(5 - 0²12
h=
A=o
Integrating over the stationary distribution and taking the expectation, and using Lemma 4.6, we obtain the first inequality. The second inequality follows from similar computations, using Jensen's inequality to bound
H- H
2 |
H
| 12
S 12
Σ h=0
T (() (0: A(0) -0))
0+)
S H
Σ
(P 200 0-11*
h=0
and the result follows from taking the expectation and integrating over SCAFFOLD's stationary distribution, then using Lemma B.5 to bound each term of the sum.
D. Asy-tsympto Rates for SCAFFOLD Proof of Theorem 4.9
Theorem 4.9 (Restated), Assume AI, A2, A3, A4, and A5. Furthermore, assume that ry H LL2 S 1/10, -HO,,,H(L + pd) S 1/48 and 7/3 S p/19. Then, the mean squared error of SCaFFOLd's global iterates, initialized with 6 E Rd and (()) = {(N) 0 E Rd is
Yu HT
64o Lp
E [110T - 0-113] s
22100 27
20dy
12. 15080d33/2Q
96
6
600 d 4
HQ²
+
Nu o² +
0
1212
Proof. Let 80 ERd and 20 "1p.... ((N)) E Rdd be sampled from SCAFFOLD's stationary distribution
20 x = (P.
S(v) (Ty,H)
For an i.dd sequence (1i))) hEN determining the randomness of the algorithm, where [(() Me) force [I....,NN
and h E H., we define two sequences, starting respectively from x (00, (01):- -0( ((() and 80
(00, 20 "app (.vr) and following the recursion for t 2 0,
x -(0
(oc+1 ct+1 ((1)
5(x: 24111 (1:N)
S(N)
x++1 (a+1)
2+1 ((t))
=5(x';
(1)
(1:N)
The first sequence are the actual iterates of SCAFFOLD, while the second one is its counterpart with the same realization of noise, but initialized in the stationary distribution. By definition of the stationary distribution, all iterations of this second sequence also follow the stationary distribution, i.e., for all 2
X ((..H)
We can thus decompose the error in two parts
E [|ITT 0T1]]] < 23|110" - - [12]
2 0-139
(76)
where we recall X = (0-, Sty Si)) is the optimal vector. The first term is an optimization term, which determines the distance from current iterate to an iterate drawn in the stationary distribution. The second term is the variance in the stationary distribution. We now bound each of these two terms.
39

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Bounding the optimization term. Using Lemma 4.1 recursively with the natural filtration of the process {X) 1200 bound the first term
can
2 0 [[2] - 2B[[|x" - -1
$2(1 7H0 HT
||X 12
4
$ <4(1-
7p
HT
|| - 1012 + 4 (1 74
HT
1 - 1x11
(77)
4
4
Integrating (77) over the stationary distribution and using Corollary B.I, we have
2B||I0" 0-1131 S 4
HT
X - x + (1
7/0
HT
647 2
(78)
4
4
Bounding the variance term. For the second term, we Theorem 4.8 to bound
2 0- 0/11])=3 = f100 -10-0011= T (d0,
(d0,, d3) S 2d E
20d o² +
12. 15580dd33/20
96
6002 HQQ
Nu
15/2
0+
N₂
0
(79)
Final rate. Plugging (78) and (79) in (76), we obtain
E -110 - 111 -
70
HT
[10 00-00122
2²H2 N N
E1e - Etgl1 + 644
4
c=1
20dy
16 1508003/20
96
1000dd>>112
Np 0
0
15/2
Nu3
and the result follows by taking E(e) = 0 for all c E (1....,N} and using the fact that E7,) = -V f(e)((0))
Corollary 4.10 (Restated). Let E 0. With Theorem 4.9's assumptions, we can set 7 S min( Nuc² 10 1 max W: 2//3,2/3 Q1,/22 Liee"
oe Qu/907 Qo?
and S of mimi((1,4/aa)
Then, SCAFFOLD guarantees Elll0" 0'1131 S 6 for 2
p
L max(11 62/H) 1100 100-011+1111 and the number of stochastic gradients computed by each client is
TH S - m 1 N: 21/2
2/33,33
Q1
log(
where v/n -1800 -- G7/L² + /Z?
Proof. By Theorem 4.9, have
E [110T 001 [2] $
7/4
1100- 1- -01
2
7o?
11
+
Nu
7 o²
+
1512
o3
1
For the last three terms to be smaller than e², we require
1 NuE² 1/// T. o² Q2100?
12/2
min
Qo?
where the first two conditions follow from the terms in y and 3/2 and the last one follows from the term in 3 H, using the property 7H L/L. To choose H. remark that, in Theorem 4.9, we require 7HL S and 7H S p. Thus, choosing the largest step size possible, we have
22/3,2/3 QT/2/2 of min((,, max ( P
H S 7L
min(1, p/(2) S
(80)
Lue?
11/
40

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
This gives
E [110" - 0-11 < (1- 2/ "T
("( 1000 1100-0010 0-11 + T
20 +
Now, we choose y and H as big as possible, which gives
L
G7/T. 1 o2/((()) [160- 11 (
T 2 max (1x log
(81)
e²
such that IE [110T 1-1 S e. Since each client computes TH gradients, the result follows from (80) and (81).
E. Bias of SCAFFOLD
We now give first-order expression of the bias of SCAFFOLDD For 0 E TRd and E = (5(1))-... ((ii)-...-00 ((N))) E Rxd we define the bias in the stationary distribution of the parameters and control variates as
- (0 6*) (). (dd,dE) /
b a
(fi) (d0 (d0,
Alike the tensors defined (57) and (58), we define the following tensor that will be used expand the gradients to third order,
Dit (0) = (0((0)//()
- (1 (1- (1-t) (i) +t (0: 2 f*) )a))ttt
(82)
As in Appendix C, we will often denote D4h = Dioh (0%,) for conciseness.
(c)
satisfy- Lemma E.1. Assume the step size and the number of local updates H y H S 1/12. Under these conditions, it holds that
h = Id y/V (t00 (c)
Î = Id ((V)
H 7 - v2 (0') +06)))
Proof. The first equality follows from expanding [ie) (Id - > (0-) using the Binomial theorem and the fact that Id and V (0*) commute. Then, terms of higher order can be bounded by bounding the remainder terms using the exponential series and the fact that V (8r) = L with HHL 1. The second equality follows from the first with
h = H and 2 f(0()) = N N (0))). The last identity follows from (73) and Lemma C.10.
E.1. Bias on the Control Variates
Lemma E.2 (Bias of Control Variates). Assume AI, A2 and A5. Letc [I,...,,N,, Z = Z be i..dd random variables. Assume the step size y and the number of local updates H satisfy (H (1) S 1/12. Under these conditions, control variates' bias satisfies
= -V) +0(7)
(83)
Proof. Let 0 E Rdd and E.p...... Rd. For [L,...,N} and h {0.... H}. define
h-1 h ((: =0 -
Σ
(1: + cl (z((²) + E(6)
(84)
p=
t (Eo)) (, E(o) + 7
(TH (0; {(o)= z(/ T(0: E(I:N)+ 2(1th)))
(85)

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
First, we derive first-order expansion of the local updates error. Using Corollary B.1 to bound the remainder term, we have
0- - 0- = 0"
(0))
((())) + (() + 0(71/3))
(86)
(c)
0 - 0 rh(E(c) {ie)
(+] (255 + 0773/11))
(87)
t=0
Then, we recall the expression of the control variates updates
1
5/0 = (c) +
(0t)
E1o) Z(o0) - T(0; ((. 2(1th)))
(88)
7/1
H
N H
= (6) H
(0)) + ((())) + E(o) - N Σ
ΣΣ
(0)
(Z)) + +5(0)
(89)
1=
h=
Taking the conditional expectation, and expanding the gradients we have
H
N
H
E
++ (c)
=
T - 00]
1
V2 (0) (0 100-0% 001 + +1]+0(7)
H
N
1=0
K=
A=0
H
1
Σ
S + v2 (O)) 0: 0r)
V (1o 10+- 0- + +0(+))
= - H
N
1=
Since E |0th - -0* = 0 - 0 + O( we have
E St Eio = (V -200)0)))000000000000--------0--
(90)
and the result of the lemma follows.
E.2. Expression of the Parameter's Variance Proof of Lemma 5.1
Lemma 5.1 (Restated), Assume AI, A2, A3, A4, A5. Furthermore, assume that the step size ? and number of local updates H satisfy THT.22 S p/10 and 7 (H μ4) s 1/48 and 7B S p/19. Then, it holds that, for e. + d' (!,....,N) N).
Σ" 7 +0000))(()31))))))))) +
N
8.6 0.6
Y
AC(1') ((² V2 f²0))))) + 7 (C(0))
N
E (c,e)
(1
N H Co + 1
2 1
NN C(0') + +0())
E (c,e) NH (C(8") (0") - (o)) +0
where A (Id f + (f*) & Id) -1 (.*) El(e(2) Zio (**) and C(P + Ee (o*)
Proof. Lemma C.9 gives E" = 0()). Then, by Lemma 4.7-(69) and Lemma 4.6, it holds that Finally, Lemma 4.6 ensures that
N EN 5 = 0()).
_ (c,c') O(1HH) for all c, E NN.
We recall the expression from Lemma C.3,
-
N T N
Σ
C + Gif ( +
22
N
N
H1. (c)
+ 2 Σ' + R
N2
(c.)) (c)
By Lemma E.I, to expand the matrices and Öين for c E (l,...,, N}. and using 7/1 = O(),, we thus have
x2 E H²) 0(
-"
+
(91)
N
42

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
where we also used Lemma C.6 obtain R² -)) Finally, we expand Σ` uuing A5 and Corollary B.I, which gives
' = HC((") + 0
Plugging this equation in (91) and reorganizing the terms gives the result.
Covariance of 0 and Stey From Lemma C.4, recall
S 0.5 = -
A +1
GII (c) (e)
Σ
IH1
Σ
F.e 55.
(c)
N
N
(1)
8==1
i=1
N
N
N
7 H
H.H
(8)
(i,c]
H
(c)
H
N
Σ
CLE (1)
(1,1) (P)
HI:
(P)
+
NH
7
(E(a) - - + +R
i= P=1
which gives
-ー Σ A (c)
7 NH
[ - -50) + +(())))
and the result follows.
Covariance of control variates. Similarly, we obtain
AT (ae) ( Σ Al
E (c,,) ( E
1
(0)
2
(c)
+ 1
E' +0( +03/))
H2
NH
NH
1
1
1
(ey + NH?
E' +0(721 +
NH
NH
and the last two identities follow.
E.3. Bias on the Parameters - Proof of Theorem 5.3
Lemma E.3. Assume AI, A2 and A5, Let Z = (I:N) be i..dd random variables. Assume the step size and the number of local updates H satisfy (L pd) $ 1/12. Under these conditions, it holds that
(b) - 0τ) 02
H) = / (0- (0-0r) (d0, + U%
@2
E
where U/:) = O))
Proof. To this end, we expand the gradient in 0%) - 0- = - = (()))(()) + +5
0
+et1] 0+, which gives
h-1
(0/s-00 -r))
82 = (0 (0-8) 0- - (h(((e) - E(o) - roto
1th -
Σ
52.6
(ot,) - ) 02
t=
Expanding the square, we get the result with U given by
U/G = - / (0-or) (E(e) - -ft +
Σ
[p3
E
D2s (ots - =1)) (d0, d3)
E=
+ 2/2 / (5io) E(e) + h
h-1
Das (0%,) - -D+) 82
(E) (d, (d0, dE) + +2² f E (c(o)
f
1:h) 027
(d. d3)
E=
2 h-1
EE
D2. (%i)) 0r)
(ste)) T
+
1sh (at))
D2g
(%/)-- -0r) rr) ] (d0,) dE)
which satisfies U% = 0(721) by Corollary B.1, Lemma 4.6, Corollary B.4, Lemma B.5 and ,HT S 1.
43

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Lemma E.A. Assume AI, A2 and A5. Let Z Zi- be i...d random variables. Assume the step size & and the number of local updates H satisfy y (L + /1) _ 1/12. Under these conditions, holds that
b" b 2N V (200)) + 0 +
Proof. By definition of the local updates, we have, for h E {o..... H 1}. assuming glitl
(c) is F measurable,
E 0
8r F (c)
0r fial 75(0)
Like in (65), we expand the gradient, but for one more order, and use f(c) = - (0)))
E g+tl
0r
F
8%)) H" -io (0% 0*)
7 v f(o)(0") (0%s 80) 82
2
7 Dantt (%%s - 00) (5())
{(e)
2
Taking the expectation, unrolling this equality and averaging the result over 1 to N, we obtain
E
0-] =
(6
0*)
H
Σ
1:: [c]
(5()) (io)
7
N H
Σ
(
(0:s) - 00-
82
N H
rH-
D4.h (or (0)- 037 ((()
2N
2N
h=0
Integrating over the stationary distribution of SCAFFOLD and using Lemma E.3, we obtain
N CH
N
#-1
50 = rb
H
h V (0) (E*
Σ" + +U/) + W
N
(c)
N
4=
where W
2N
Σ cc
h-
H
(c)
4.
(c)
(0)
0*)
83 satisfies W = =0 by A6 and Lemma B.5. Plugging
in the expansions from Lemma E.I, we obtain
N H
6" = (ld [4==))=)3(0)+++0 6"
Σ
(H - 1)
V2 ((((00) b
N
2
c=1
N
(Id O v ((o))))))))))))))))))))))))))))) (5 +(/ss) + W
2N
h=0
which gives
THO 2H -))
v2 fee (0 (
7
Σ
N #-1
Σ
V (OS
+ 2/2 )/)
2NV
2N
The result follows by multiplying by 2 f(a)(0))) (0)) on both sides, and using Lemma E.2 to bound b
Theorem 5.3 (Restated), Assume AI, A3, A4, A5, A6. Furthermore, assume that the step size and number of local updates H satisfy>(FF - T)LG2 - 1/10 and 7H + μ4) < 1/12 and 7/3 S 1/19. Then, the bias of SCAFFOLD is
8" - 2N 2 / (0*) + ((7"H 207 -/22).
Proof. The result follows by plugging the expression of E from Lemma 5.1 in Lemma E.4.
44

---

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
F. Useful Lemmas
Lemma (Matrix Product Coupling). For any matrix-valued sequences (MR)SEN, (MA) and for any K E N, it holds that
K
K
K
E-1
M II
II k=1
M
M
Σ
Me
(Mx - MM)
Mp
k=1
k=1
t=1
E=++1
Lemma F.2 (Projection). Let N > 0, , .N) and y 1.1 yNN with Tee Uc R.d for E N). We
define &= (I....,.B B) and y (y..... 7) with N Em=1 Fy and -N-1 Ee= ya It holds that
N
x y| = ||x y112 |1(x x) (g - y))
where ||-|] is the Ez-norm over I Nd, Since 1x - - = N T we also have
1 N
51
Σ f| vell [ xe) (ū -yy)ll
Proof. Expanding the norm, we have
ド| = x + x x- y-1
X y|| + x,,---xx-x-----
yl
= x y|1 + 2(x
- - x
Then, we notice that
{3) 2(x x y) = - - = 2( - 7, N - 9) + (8 -z))
And we have 2(x - 3, N(# - 9) Dm {y: x31) = since No- = Σソ x; and Ny E y/:
45


Reviews:
[{"review_id": "IyUxGZGTgj", "reviewer": "Reviewer_muGE", "summary": "This paper studies the convergence of the SCAFFOLD algorithm under the assumptions of (a) strong convexity, (b) smoothness, (c) first-order similarity (i.e. the average norm of the difference between the gradients on each client and the avg function is bounded), (d) second-order similarity (like the former, but for Hessians), and (e) second-order smoothness (so the Hessian is Lipschitz). The original analysis of SCAFFOLD does exhibit a linear speedup, but only when using a global stepsize (i.e. not straightforward aggregation). This paper gives convergence guarantees showing that SCAFFOLD does exhibit a linear speedup in its main terms, albeit at the cost of the additional assumptions (d) and (e). The paper also derives approximate expressions for the covariates of SCAFFOLD at convergence.\n\nAfter reviewing the authors' response clarifying their focus on studying SCAFFOLD with global stepsize η=1 (which aligns with standard usage in implementations), I maintain my accept recommendation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of our paper! We appreciate that you found the Markov chain point of view \"very useful and insightful\", and \"helpful to the community going forward\", and that you found our theory based on algorithmic stability \"very creatively applied here\" and \"rare to see in the literature.\"\n\n\nWe address your concerns below.\n\n**\" “in practical implementations, there is no global step size” This does not seem to be true. Looking at GitHub repos implementing SCAFFOLD, many use a global learning rate [e.g. 2, 3]\"**\nThank you for allowing us to clarify this point. Our statement refers to the experimental section in the original SCAFFOLD paper, which states: \"We always use global step-size $\\eta_g = 1$\".\n\nWhile it is true that implementations of this algorithm allow for a global step size different from one, the default setting in all experiments we found is $\\eta_g = 1$.\nFrom the references you cite, [2] consistently uses a global step size $\\eta_g = 1$ in its experiments, and [3] only provides an implementation of the algorithm without using it in specific tasks. \nAs an additional example, the FLamby dataset's benchmarks [FLamby] also sets the global step size to one across various optimization tasks.\nWe will add these references to the statement in the paper to make this as clear as possible.\n\n[2] https://github.com/KarhouTam/SCAFFOLD-PyTorch/blob/master/src/server/scaffold.py\n\n[3] https://github.com/BalajiAI/Federated-Learning/blob/main/src/algorithms/SCAFFOLD/server.py \n\n[FLamby] https://github.com/owkin/FLamby/tree/main/flamby\n\n\n**\"One of the key flexibilities of using two stepsizes is to be able to interpolate between minibatch SGD and local SGD, as argued in [1]-- I don’t see why removing this is any good idea.\"**\n**\"Moreover, [4] argued that server stepsizes play a crucial role in federated learning algorithms. Nevertheless, I think understanding the algorithm with global stepsize $1$ is still useful.\"**\nWe acknowledge this point and agree that server step sizes can play an important role. \nHowever, as stated above, using a server step size departs from standard usage of Scaffold, motivating our choice of studying the algorithm with the global step size set to one.\nPrecisely studying the impact of the choice of global/local step sizes on Scaffold (in terms of convergence rate, bias, and linear speed-up) could be an interesting extension of the analysis framework we propose here, that goes beyond the scope of the current paper.\n\n**\"Virtually all of the results require using local stepsizes that scale with $1/H$, this is a tiny stepsize and does not reflect practice. It also means we can not recover results in the i.i.d. regime, which require large local stepsizes.\"**\nThank you for raising this point.\nNote that the condition was already present in the original Scaffold paper.\nRemoving the condition $\\gamma H L \\lesssim{} 1$ in the convergence of Scaffold to a stationary distribution this question is highly non-trivial.\nIn fact, it is not clear that Scaffold converges to a stationary distribution for larger H: this is a very interesting open problem to solve in future work.\n\n**\"1. I am not 100% sure if any of the papers on the second-order similarity assumption show a linear speedup; Do you think it’s possible to get a rate like $\\zeta_2^2 / \\mu^2$ here?\"\"**\nTo our knowledge, our result is the first to show that a method that corrects heterogeneity (at least without global step size) has linear speed-up. Reducing $L \\zeta_2 / \\mu^2$ to $\\zeta_2^2 / \\mu^2$ would require to remove the conditions $\\gamma H L \\lesssim{} 1$ which, as stated above, is a difficult problem.\n\n**\"2. Can the Performance Estimation Problem [6] be used to derive an algorithm-specific lower bound for SCAFFOLD that can shed light on what the tightest rate we can expect to be?\"\"**\nPerformance estimation ideas are completely orthogonal to our work.\nTo perform this kind of analyses, profound investigation is required. In particular, PEP relies on \"interpolation conditions\", which, to extend to the federated case, would require to choose an heterogeneity measure and adapt interpolation conditions accordingly.\nNonetheless, they constitute an interesting perspective for future work, with the goal of achieving the best possible rate for Scaffold.", "claims_and_evidence": "The paper presents novel theory that provably shows SCAFFOLD does enjoy linear speedup in the number of nodes, albeit at the cost of added assumptions (in particular, the Lipschitz Hessian assumption and the second-order similarity ones). There are additional higher-order terms that do not enjoy a linear speedup, but this is common to all other analysis of both SCAFFOLD and FedAvg.\n\n1. \"In this paper, we aim to study the SCAFFOLD algorithm as it is commonly used. Thus, contrarily to (Karimireddy et al., 2020; Yang et al., 2021), we do not consider two-sided step sizes. While this yields the desired linear speed-up by dividing the local step size by √N , and increasing the global one, it essentially reduces the algorithm to mini-batch SGD, and does not give much insights on SCAFFOLD itself. Thus, we consider in Table 1 the rate of SCAFFOLD without global step size\" One of the key flexibilities of using two stepsizes is to be able to interpolate between minibatch SGD and local SGD, as argued in [1]-- I don't see why removing this is any good idea. I also find it a bit strange to say \"does not give much insights on SCAFFOLD itself\" when the SCAFFOLD paper uses a global stepsize as an integral part of the algorithm! \"in practical implementations, there is no global step size\" This does not seem to be true. Looking at GitHub repos implementing SCAFFOLD, many use a global learning rate [e.g. 2, 3]; Moreover, [4] argued that server stepsizes play a crucial role in federated learning algorithms. Nevertheless, I think understanding the algorithm with global stepsize $1$ is still useful.\n2. The fact that SCAFFOLD still suffers from bias due to stochastic updates is not very surprising. After all, there is no correction term applied on the basis of which stochastic gradient we are using-- the correction terms are indexed by the clients.\n\n[1] Woodworth, Patel & Srebro (2020) Minibatch vs Local SGD for Heterogeneous Distributed Learning.\n[2] https://github.com/KarhouTam/SCAFFOLD-PyTorch/blob/master/src/server/scaffold.py\n[3] https://github.com/BalajiAI/Federated-Learning/blob/main/src/algorithms/SCAFFOLD/server.py\n[4] Charles & Konečný (2020) On the Outsized Importance of Learning Rates in Local Update Methods.", "methods_and_evaluation_criteria": "This is a theoretical paper, and the included examples are toy to demonstrate the theory. However, I think the paper would benefit significantly from including some experiments on neural networks to see if we can expect the same linear speedup to hold in the nonconvex setting.", "theoretical_claims": "I have checked some proofs in section B, particularly the proofs of Lemma B.1. to Theorem B.4. I did not check the other proofs.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "There is plenty of literature on variance-reduced methods like SCAFFOLD for reducing the heterogeneity bias in federated learning; This paper advances the analysis of SCAFFOLD and the methods here can potentially be used for other algorithms as well. The analysis in the present paper borrows a lot from [5], but I think it's sufficiently different that it is still a significant contribution.\n\n[5] Mangold, Paul, et al. \"Refined Analysis of Federated Averaging's Bias and Federated Richardson-Romberg Extrapolation.\" arXiv preprint arXiv:2412.01389 (2024).", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "1. (Strength) The Markov chain point-of-view is not very common in the federated learning literature, and using it here turns out to be very useful and insightful. I think this connection can be helpful to the community going forward. \n2. (Strength) The two-tiered approach of first relying on a convergence guarantee with no linear speedup, then one with linear speedup, is also quite nice.\n3. (Strength) The approach of studying the convergence of the algorithm by essentially studying its algorithmic stability (Lemma B.1) is also very creatively applied here. It's rare to see this in the literature.\n4. (Weakness) Virtually all of the results require using local stepsizes that scale with $1/H$, this is a tiny stepsize and does not reflect practice. It also means we can not recover results in the i.i.d. regime, which require large local stepsizes.", "other_comments_or_suggestions": "Line 1094: \"Bouding\" should be Bounding.", "questions_for_authors": "1. Given that you do assume second-order similarity, the rate you obtain for SCAFFOLD is $\\frac{L}{\\mu} \\frac{\\zeta_2}{\\mu}$ when $\\zeta_2 > \\mu$-- given that $\\zeta_2 \\leq L$ necessarily, this rate is always larger than $\\frac{\\zeta_2^2}{\\mu^2}$, which is the rate obtained by several algorithms in the second-order similarity setting (e.g. [5]). This adds yet another dimension to the comparison: sometimes, $\\zeta_2^2/\\mu^2$ can be even smaller than $\\sqrt{L/\\mu}$. I am not 100% sure if any of the papers on the second-order similarity assumption show a linear speedup; Do you think it's possible to get a rate like $\\frac{\\zeta_2^2}{\\mu^2}$ here?\n2. Can the Performance Estimation Problem [6] be used to derive an algorithm-specific lower bound for SCAFFOLD that can shed light on what the tightest rate we can expect to be?\n\n[5] Khaled & Jin (2022) Faster Federated Optimization Under Second-Order Similarity.\n[6] https://francisbach.com/computer-aided-analyses/", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0ocodvGbWO", "reviewer": "Reviewer_QhCL", "summary": "This paper investigates the convergence properties of Scaffold, a federated learning method designed to reduce variance among clients. By analyzing the global iterates and control variates from the perspective of a Markov chain, the study establishes a novel non-asymptotic convergence rate for Scaffold with respect to the total number of clients.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review of our paper and for your insightful comments.\nWe are happy that you found our paper \"well written, and the theoretical part is mostly clear to follow.\"\n\n**\"I believe the theoretical results in this paper rely on some strong assumptions, such as the bounded third and fourth derivatives. [...] If these assumptions are also commonly applied in other convergence analysis works related to Markov chains or other perspectives, I would suggest the authors highlight their necessity and reference existing related studies to make it clear.\"**\nThank you for allowing us to clarify.\nThese assumptions are not required to establish the *convergence* results (namely Theorem 4.2 and 4.4), which hold under standard assumptions ($\\mu$ strong convexity and $L$-smoothness).\nThey are necessary to bound higher-order terms in subsequent results (e.g., Theorems 4.7 and 4.8): this is needed to derive our refined results.\nHigher-order derivative assumptions are standard in the literature, they are employed in the analysis of SGD in [1,2,3], using similar ideas of viewing SGD as a Markov chain.\n\n\n[1] Dieuleveut et al. (2020). Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains.\n\n[2] Allmeier et al. (2024). Computing the bias of constant-step stochastic approximation with markovian noise. \n\n[3] Sheshukova et al. (2024). Nonasymptotic analysis of stochastic gradient descent with the richardson-romberg extrapolation.\n\n**\"The improved convergence rate with linear speedup in terms of the number of clients seems to rely on specific conditions, as highlighted in Corollary 4.9 ($\\gamma \\lesssim ...$, $H \\lesssim ...$, and $N \\lesssim ...$).  [...] I think such conditions about and appear to be less prevalent in related works, such as Mangold et al. (2024b) and Hu & Huang (2023).\"**\nCorollary 4.9 provides the sample and communication complexity of SCAFFOLD. The bound on \\\\(H\\\\) arises from the necessity to simultaneously control errors in both the parameters and the control variates, explaining the discrepancy between our analysis and that of Mangold et al. (2024b). The bound on \\\\(\\\\gamma\\\\) is standard in the stochastic optimization literature, typically required for bounding the error of the final iterate. Finally, the bound on \\\\(N\\\\) emerges from the need to manage higher-order terms: convergence still holds for values of \\\\(N\\\\) exceeding this bound, albeit without linear speed-up. If the reviewer believes it would clarify our main message, we can provide an alternative formulation of this lemma without imposing this condition.\n\n\n**\"Moreover, one of the key motivation behind Scaffold is to address ...]. However, in this paper, the condition [..] contradicts this motivation.\"**\nA similar condition appears in the main theorem (Theorem VII) of Karimireddy et al. (2020), which requires \\\\(\\eta_g \\\\gamma H L \\le 1\\\\), with \\\\(\\\\eta_g\\\\) denoting the global step size. Since Karimireddy et al. mandate the global step size to satisfy \\\\(\\\\eta_g \\\\ge 1\\\\), their result implicitly enforces the condition \\\\(\\\\gamma H L \\\\le 1\\\\), matching the assumption in our paper. To our knowledge, no existing analysis of SCAFFOLD (with a deterministic communication scheme) avoids this assumption. If the reviewer is aware of any such analysis, we would gladly include it in our discussion.\n\n**\"1. The authors discuss the non-vanishing bias of Scaffold in Section 5 and claim that Scaffold can eliminate heterogeneity bias....\"**\nOur analysis of SCAFFOLD's bias facilitates a direct comparison with that of FedAvg, as characterized, for instance, by Mangold et al. (2024b). Specifically, we demonstrate that the bias can be decomposed into heterogeneity and stochasticity components. Regarding the empirical validation of this finding, we note that related experimental evidence has already been provided, for example, by Karimireddy et al. (2020). Consequently, our own experiments primarily focus on investigating the linear speed-up phenomenon.\n\n **\"2. The authors claim that Scaffold achieves linear speedup based on the results in Figure 1. [...].\"**\nWe respectfully maintain that our result does represent a notable advancement: demonstrating that SCAFFOLD achieves linear speed-up has been an open problem in the literature for several years. Although linear speed-up is well-established for FedAvg, extending this result to SCAFFOLD is considerably more challenging due to noise propagation through the control variates into all parameters. To establish linear speed-up in this context, one must carefully track covariances among all pairs of control variates and demonstrate that these covariances scale as \\\\(1/N\\\\), a task that is technically intricate and previously unresolved.", "claims_and_evidence": "I think the claims in the submission are mostly clear. The paper well illustrates the key contributions as stated in the introduction with sufficient evidence.\n\nHowever, regarding Remark 2.1, I find the claim that \"While this yields the desired linear speed-up by... and increasing the global one, it essentially reduces the algorithm to mini-batch SGD\" somewhat confusing. To my understanding, this is not entirely accurate because federated algorithms involve locally iterative training. Reducing the local learning rate and performing multiple steps of local training does not equate to simply increasing the batch size in mini-batch SGD. The iterative nature of local updates in federated learning introduces additional dynamics and are not equal to standard mini-batch SGD.", "methods_and_evaluation_criteria": "The main focus of this paper is on studying the convergence properties of existing methods. Consequently, it does not introduce any significant new methods or define evaluation criteria for comparative analysis.", "theoretical_claims": "I have reviewed all the theoretical results in the main paper and briefly examined the theoretical results in the appendix. I have several questions regarding this:\n1. I believe the theoretical results in this paper rely on some strong assumptions, such as the bounded third and fourth derivatives. While I do not think these assumptions necessarily make the paper less convincing, it is true that achieving better convergence results heavily depends on them. If these assumptions are also commonly applied in other convergence analysis works related to Markov chains or other perspectives, I would suggest the authors highlight their necessity and reference existing related studies to make it clear.\n2. The improved convergence rate with linear speedup in terms of the number of clients $N$ seems to rely on specific conditions, as highlighted in Corollary 4.9. These conditions include $\\gamma \\lesssim ...$, $H  \\lesssim ...$ and $N \\lesssim...$, this implies that the better rate seems achievable only when the number of local steps $H$ and the number of total clients $N$ are constrained within certain bounds. I think such conditions about $H$ and $N$ appear to be less prevalent in related works, such as Mangold et al. (2024b) and Hu & Huang (2023) referenced in your paper. \n3. Moreover, one of the key motivation behind Scaffold is to address the issue of client drift, which occurs when a large number of local training steps cause clients with heterogeneous data distributions to converge toward their local optima rather than the global optimum. However, in this paper, the condition $H  \\lesssim ...$ (which, to my understanding, is not required in the original Scaffold paper),  somewhat contradicts this motivation.", "experimental_designs_or_analyses": "1. The authors discuss the non-vanishing bias of Scaffold in Section 5 and claim that Scaffold can eliminate heterogeneity bias. However, they do not provide further analysis or discussion on heterogeneity bias in the experimental section. It would be beneficial to include empirical results or insights that demonstrate how Scaffold addresses heterogeneity bias in practice.\n2. The authors claim that Scaffold achieves linear speedup based on the results in Figure 1. However, this claim is not particularly convincing to me, as linear speedup with respect to the number of clients is not unique to Scaffold—FedAvg also exhibits this property. Therefore, the linear speedup of Scaffold does not stand out as a novel or exciting result.", "relation_to_broader_scientific_literature": "This paper may contribute to the privacy-preserving related machine learning applications.", "essential_references_not_discussed": "There is a (recent) paper that also explores FL using a Markov chain framework:\n\nSun, Z., Zhang, Z., Xu, Z., Joshi, G., Sharma, P., & Wei, E. (2024). Debiasing Federated Learning with Correlated Client Participation.", "other_strengths_and_weaknesses": "Strengths: The paper is well written, and the theoretical part is mostly clear to follow.\n \nMost Weaknesses have been discussed in previous sections, particularly about the theoretical claims, the claims of the paper and the empirical analysis.", "other_comments_or_suggestions": "The legends in Figure 1 are missing.", "questions_for_authors": "Please refer to previous sections. Addressing the issues in previous part would help me better understand and potentially change my evaluation of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OGWHVl8qP3", "reviewer": "Reviewer_LPDP", "summary": "The paper proposes an analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning.  The authors first show that the global parameters and control variates define a Markov chain that converges to a stationary distribution in the Wasserstein distance.  Leveraging this result, they prove that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size.  The analysis also reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and constructive feedback. We greatly appreciate your recognition of our paper’s contribution and the innovative perspective provided by viewing Scaffold using Markov chain formalism. Below, we carefully address each of your remarks:\n\n**Claims and Evidence:**  \nWe appreciate your positive acknowledgment of our contributions and claims, particularly regarding the theoretical framing of Scaffold using Markov chain analysis.\n\n**Methods and Evaluation Criteria:**  \nThank you for your insightful comment on the experimental section. Our computational experiments primarily validate our theoretical findings rather than establish novel empirical superiority over existing methods like FedAvg, whose empirical performance is already well-documented in the literature. However, we respectfully suggest retaining Section 6, at least in a condensed form. Indeed, numerical validations, even when theoretically expected, offer essential practical insights into the assumptions and conditions underpinning our theoretical results. We will explicitly clarify the purpose of these experiments in the revised manuscript to underscore their complementary role.\n\nConsidering your feedback, we will condense the experimental section, and stress its role as an illustration of our theoretical results. This adjustment aligns with the theoretical focus of our paper while providing an experimental component for practical reference.", "claims_and_evidence": "I think this is a great paper. I agree with the contributions and claims. Viewing scaffold through the lenses of MC is a great idea.", "methods_and_evaluation_criteria": "In my opinion the computation part is superfluous. It essentially confirms the theoretical results. It better should or otherwise there are flaws in the math. \nThey also make a claim that it's better than FedAvg. This has already been established numerically in many other papers. \n\nThe value of this paper is in theory and thus Section 6 should be removed since it doesn't add anything interesting.", "theoretical_claims": "No, I did not. I checked the math in the main body, including all of the statements.", "experimental_designs_or_analyses": "This section is not needed (see my previous comments).", "relation_to_broader_scientific_literature": "See my comments above (MC and scaffold).", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "1. What is the purpose of Section 6?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bBhymWh4Dw", "reviewer": "Reviewer_cy3M", "summary": "This paper presents a novel analysis of the SCAFFOLD algorithm, a popular method in federated learning designed to address client heterogeneity. The authors show that the global parameters and control variates of SCAFFOLD form a Markov chain that converges to a stationary distribution, which allows them to establish that SCAFFOLD achieves linear speed-up with respect to the number of clients, up to higher-order terms in the step size. The analysis reveals that SCAFFOLD retains a small higher-order bias due to stochastic updates. The paper derives new non-asymptotic convergence rates and highlights that SCAFFOLD’s global parameters’ variance decreases inversely with the number of clients, enabling scalable and efficient federated learning. Additionally, the authors provide precise characterizations of the algorithm’s variance and bias in the stationary regime.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of our paper!\nWe are happy that you found that the Markov chain-based analysis of Scaffold is original, and that \"this originality strengthens the theoretical understanding of federated learning in stochastic settings,\" that proving that Scaffold has linear speed-up without global step-size is a \"significant theoretical contribution,\" and that our analysis \"extends the understanding of bias correction mechanisms in federated learning\".\n\nWe address your concerns below.\n\n**\"A key significance of the original SCAFFOLD by Karimireddy et al. (2020) is its independence from the heterogeneity of data distributions. However, the convergence rate of the one-learning-rate SCAFFOLD in this paper depends on the level of data heterogeneity   (Assumption 4 and Theorem 4.8).\"**\nThank you for allowing us to clarify this point. This is also the case in the original Scaffold analysis (see Remark 10 in [1]), and in analyses of related algorithms like Scaffnew [2].\nSimilarly to [1, 2], heterogeneity appears in our results with a multiplicative factor $(1 - \\gamma \\mu/4)^{HT}$, and thus does not prevent convergence. It only has a small impact on the convergence rate, as it only affects logarithmic terms in the algorithm's complexity (as in [1, 2]).\nWe insist that this measure of heterogeneity is not an additional assumption, as Assumption 4 always holds as long as a unique global optimum exists. We will replace this assumption and state it as a consequence of strong convexity, which implies that a unique global minimum exists.\n\n[1] Karimireddy et al. (2020). Scaffold: Stochastic controlled averaging for federated learning.\n\n[2] Mishchenko et al. (2022). Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!.\n\n**\"The analytical framework is somewhat restricted, as it only applies to strongly convex objectives.\"**\nAnalyzing strongly convex and smooth objective functions is a common approach in federated learning, as it allows for rigorous theoretical guarantees.\nWhile our focus is on this setting, we believe our methodology could serve as a foundation for extending convergence analysis to weaker assumptions, making this a promising direction for future research.\n\n**\"While it is understandable that this paper is primarily theoretical, the experiments appear relatively simple. Moreover, certain aspects of the experimental setup, such as step size tuning, are not well conducted (see comments in Experimental Designs Or Analyses).\"**\nAs noted by the reviewer, our experiments primarily serve an illustrative purpose. We selected a representative step size and number of local iterations to demonstrate the key theoretical insights in practical settings. \nIf the reviewer thinks this limitation is crucial for acceptance of our paper, we are happy to provide more results with more thorough hyperparameter tuning in the final version of the paper.\n\nWe now answer your questions:\n\n**\"1. Can SCAFFOLD, without a global learning rate, handle partial client participation effectively?\"**\nThank you for this insightful question. We believe that results similar to ours would still hold with partial participation and that the analytical framework we propose can be extended to this setting.\nNonetheless, we refrained from including it in the paper, as we believe that it would divert attention from the core of this paper's study, which is the linear speed-up phenomenon.\n\n\"**2.  Do the theoretical results in this paper imply linear speedup for FedAvg when using only a local learning rate?\"**\nYes, indirectly. The results on the stationary distribution $\\pi^{(\\gamma, H)}$ (that is, Lemma 4.6, Theorem 4.7, and the variance part of Theorem 4.8) would still hold when setting $\\xi_c = 0$ throughout the analysis. \nThis substitution would directly imply that FedAvg exhibits linear speed-up whenever SCAFFOLD does.\n\n\n**\"3.  Does the algorithmic framework strongly rely on convexity assumptions? Can it be extended to non-convex settings?\"**\nThis is an exciting direction for future research. While we expect that viewing SCAFFOLD as a Markov chain and establishing convergence to a stationary distribution could be established without strong convexity, doing so would require fundamentally different analytical tools.\nAssuming that, without strong convexity, a stationary distribution would still exist, our current analysis would not allow to study it as is.\nBuilding an analysis in this setting (e.g., following ideas from [1]) is thus a promising direction for future research.\n\n[1] Yu et al. (2021). An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias.", "claims_and_evidence": "The claims made in this submission are generally supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria generally make sense.", "theoretical_claims": "I do not carefully check the correctness of any proofs.", "experimental_designs_or_analyses": "In the experimental setup, using the same step size $\\gamma$ for both SCAFFOLD and FedAvg without tuning them individually does not seem very reasonable.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n1. The paper provides a novel Markov chain-based analysis of SCAFFOLD under stochastic gradient updates, which has not been explored in prior work. This originality strengthens the theoretical understanding of federated learning in stochastic settings. \n2. The result showing linear speed-up for SCAFFOLD in stochastic settings without relying on restrictive assumptions (e.g., global step sizes or quadratic objectives) is a significant theoretical contribution. \n3. The identification and quantification of higher-order bias caused by stochastic updates in SCAFFOLD is a new insight that extends the understanding of bias correction mechanisms in federated learning.\n\nWeaknesses: \n1. A key significance of the original SCAFFOLD by Karimireddy et al. (2020) is its independence from the heterogeneity of data distributions. However, the convergence rate of the one-learning-rate SCAFFOLD in this paper depends on the level of data heterogeneity $\\zeta_1$ (Assumption 4 and Theorem 4.8).\n2. The analytical framework is somewhat restricted, as it only applies to strongly convex objectives and assumes full client participation.\n3. While it is understandable that this paper is primarily theoretical, the experiments appear relatively simple. Moreover, certain aspects of the experimental setup, such as step size tuning, are not well conducted (see comments in Experimental Designs Or Analyses).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can SCAFFOLD, without a global learning rate, handle partial client participation effectively?\n2. Do the theoretical results in this paper imply linear speedup for FedAvg when using only a local learning rate?\n3. Does the algorithmic framework strongly rely on convexity assumptions? Can it be extended to non-convex settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a new convergence analysis for SCAFFOLD, a popular method in federated learning. The primary focus is studying SCAFFOLD with a single stepsize ("without global step size"). This corresponds to the variant of SCAFFOLD primarily used in practice and improves over the original paper, which introduced an additional stepsize for technical reasons.

The reviewers commended the approach from a Markov point of view, which might be interesting for some readers (although this approach is not novel, it is less common in the FL literature). 

The discussion between authors and reviewers clarified some aspects of the paper. In particular, the key differences (and similarities) between the convergence results presented in this work vs. the original SCAFFOLD paper and the justification for the particular assumptions used in this work (discussion with Reviewer QhCL) were discussed. We ask the authors to incorporate these aspects in the final version of the paper.
Decision: Accept (poster)