Revisiting Consensus Error: A Fine-grained Analysis of Local SGD under Second-order Data Heterogeneity
Authors: Kumar Kshitij Patel
Ali Zindari
Sebastian U Stich
Lingxiao Wang
Venue: NeurIPS 2025 poster ()
Keywords: Federated Averaging
Local SGD
Convergence Analysis
Communication Complexity
Data Heterogeneity
Primary area: optimization
TL;DR: Local SGD converges faster under low second-order heterogeneity, and we prove it with tight bounds and supporting experiments.

Abstract: Local SGD, or Federated Averaging, is one of the most widely used algorithms for distributed optimization. Although it often outperforms alternatives such as mini-batch SGD, existing theory has not fully explained this advantage under realistic assumptions about data heterogeneity. Recent work has suggested that a second-order heterogeneity assumption may suffice to justify the empirical gains of local SGD. We confirm this conjecture by establishing new upper and lower bounds on the convergence of local SGD. These bounds demonstrate how a low second-order heterogeneity, combined with third-order smoothness, enables local SGD to interpolate between heterogeneous and homogeneous regimes while maintaining communication efficiency. Our main technical contribution is a refined analysis of the consensus error, a central quantity in such results. We validate our theory with experiments on a distributed linear regression task.

Revisiting Consensus Error: A Fine-grained Analysis of Local SGD under Second-order Data Heterogeneity
Kumar Kshitij Patel"
Ali Zindari CISPA Helmholtz Center for Information Security Saarbrücken, DE 66123 a a zindariiiiee spa de
Institute for Foundations of Data Science
Yale University
New Haven, CT 06511
Sebastian U. Stich
Lingxia Wang
CISPA Helmholtz Center for Information Security Saarbrüccen, DE 66123 srichecispaa de
Department of Data Science
New Jersey Institute of Technology Newark, NJ 07102 1 1w324@njit.com
Abstract
Local SGD, or Federated Averaging, one of the most widely used algorithms for distributed optimization. Although it often outperforms alternatives such as mini-batch SGD, existing theory has not fully explained this advantage under realistic assumptions about data heterogeneity. Recent work has suggested that a second-order heterogeneity assumption may suffice to justify the empirical gains local SGD. We confirm this conjecture by establishing on the convergence local SGD. These bounds demonstrate how a low second- order heterogeneity, combined with third-order smoothness, enables local SGD interpolate between heterogeneous and homogencous regimes while maintaining communication efficiency. Our main technical contribution is refined analysis of the consensus error, a central quantity in such results. We validate our theory with experiments distributed linear regression task.
upper and lower bounds
The Unreasonable Effectiveness of Local SGD
We study the following distributed optimization problem over M machines:
min ZER
F(z) M
1
Σ Fm
(1)
ME(M]
where F., :=,,, [x;; 2m.)] is the stochastic optimization objective on machine m, defined using a loss function f(;= 2) and data distribution D,, E A(2). Problem (I) appears widely in machine on millions of edge devices 2 Perhaps the simplest, most basic, and most important distributed setting for solving Problem (I) is that of intermiltent communication (IC) 4. In this model, illustrated in Figure T. machines optimize the objective across rounds of communication, and in each round, each machine performs K sequential stochastic gradient updates before communicating.
raaning from multi-GPU training in data centers [1] to decentralized training
Several variants stochastic gradient descent (SGD) have been proposed for the IC setting 6 most of which build on Local SGD or Federated Averaging. In Local SGD, each machine performs
Part of the work was done when author was student Toyota Technological Institute, Chicago (TTIC).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

K local stochastic updates starting from the last synchronized model and then at the communication round the machines average their models. Specifically, denoting the overall time by T KR, at time step & [0, 1 machine m E [M] samples 2t" ~ 'Dn. and performs the update:
I T Lt
n/ [<'"" ;
if t mod K o 0
Σ (x) (V((())))) if t+1 mod K = 0
(2)
= M
DE|M
with initialization 20 for all E [M]. Despite its simplicity, Local SGD consistently
outperforms other first-order methods in practice 7 g). including mini-batch SGD g TO M.
This strong empirical performance has motivated more than decade of theoretical work aimed 18
understanding its advantages [12 13 14 15 16
17
II
19 20
21
22
23
8
24
25 26].
In the homogeneous setting where D,,, m for all m E M a sequence of results 16,
D
M macchnns
21 23 27 25 28 has shown that explain the benefit of Local SGD, one must impose higher-order smoothness assumptions-à la quadraticity in linear regression or quasi-self- concordance in logistic regression. However, in the more general and interesting heteroge- neous case, most existing works either fail to demonstrate an advantage of Local SGD over mini-batch SGD [7 19 18], or require highly restrictive conditions that prevent any meaningful data variation across machines (c.f. Assumption
K. local updates
K local updates
2K
Figure I: Illustration of the intermittent communica- tion setting.
Wang et g described this discrepancy between theory and practice as the unreasonable effectiveness of Local SGD.
Recently, Patel et al. 25 conjectured that combining second-order heterogeneity condition (c.f. Assumption 6) with standard first-order conditions (c.f. A (nd can account for the success Local SGD without requiring overly restrictive assumptions. Concurrently, other works have shown that these second-org order conditions sharply characterize the communication complexity of various other distributed optimization algorithms 22] 30
31 32 34 35). Motivated by these
observations, we aim to validate the conjecture of Patel et al. (25) and show that low second-orde
heterogeneity indeed improves the convergence and communication complexity of Local SGD.
Towards this goal, our main contributions are as follows:
I. New Lower Bound Characterizing Second-order Heterogeneity. In Theorem we refine the lower bound of Patel et (25) accommodate second-order heterogeneity. Specifically, we show that low second-order heterogeneity reduces the hardness of their lower bound instance. This refinement suggests that the communication complexity of Local SGD depends primarily on the second-order heterogeneity constant, rather than the more conservative second-order smoothness constant (c.f., 7 vs. H in Assumptions and 6
II. New Upper Bounds without Restrictive Assumptions. In Theorems 2 and we establish upper bounds that align with the qualitative predictions of our lower bound: Local SGD converges faster as second-order heterogeneity decreases. These bounds also incorporate the effects of first-order heterogeneity (Assumptions and allowing us to interpolate smoothly between heterogeneous and homogeneous regimes. Our key technical contribution is new, sharper analysis of the consensus error-a central quantity in distributed optimization which enables us to avoid the restrictive heterogeneity ussumptions used in prior work 25).
III. Refined Analysis under Third-order Smoothness. We improve our upper bound for quadratic objectives in Theorems 4 and [S] We then extend the analysis to third-order smooth functions in Theorem 6. requiring control of the fourth moment of the consensus error and careful handling of four coupled recursions without losing the benefits of local updates.
IV. A Controlled Regression Experiment. We validate our theory on a synthetic linear regression task in Figure by independently varying first- and second-order heterogeneity and highlighting the role of second-order heterogeneity in dictating Local SGD's communication complexity.
Throughout the paper. for integers i < j E Ezo. we will use the notation [i,]] = (i, i I,...,j- 1 + and when we denote it by b).

---

Thus, our paper significantly shrinks several gaps in the convergence theory for Local SGD. We summarize some of our results Table contextualizing them in existing literature. Our techniques may also be useful for other areas of distributed optimization where consensus error-like quantities
arise, including communication compression 36 37 M quantization [39 40) asynchronous
updates 41 42
differential privacy 43 44
and Byzantine robustness
45
46
2 Setting and Preliminaries
In this section, we introduce our notation and assumptions while discussing several related works.
Local SGD Iterates. For analytical purposes, we will define the average Local SGD iterate at time t T) by 22 == Eme[ar] "7"". which may not be computed in practice (when t mod K * 0).
Regularity Assumptions. We assume that the local objectives are convex and smooth.
Assumption (Convexity and Smoothness). For all m E J. the function Fm twice differen- tiable and satisfies p. La 3 Fm)) 3 H for some 0 S μ S H. When 0, we say Fm is H Furthermore, there exists Q 2 0 such
strongly convex and denote its condition number by that for all x. y E R. we have || V (v)ll2 S Q || y
#
Recall that a strongly convex function admits a unique minimizer. Also, Q = 0 implies that Fm is quadratic. We further discuss the role of third-order smoothness in Section 5
We also assume the stochastic gradients have bounded fourth moments. Assumption 2 (Bounded Fourth Moment of Stochastic Gradients). For all m [M] and Rd. we have Ez (V [V; 2)] = Vm (I), and
Ez-D,,. [I[ [ F. x|]
Using Jensen's inequality, the above assumption implies the second moment of the stochastic gradients are also bounded, i.e., EgwD... [=;; (x))l2 x) S o². We only require the fourth moment bound for Theorem 6 which involves a higher-order moment control of iterates. For all other results (Theorems 5) the second moment bound suffices.
Finally, we assume that each local function's optima and the global objective are bounded.
Assumption (Bounded Optima). For all m [M]. define the set of optima as St arg mRn Fm (x). Then 3 Im E S such that || < B. Similarly, define the set of op- tima for the average objective as S* := arg min F(x). Then 3x" S* such that ||=*1| S B.
These standard regularity assumptions alone are insufficient to establish the utility of a large number of local update steps for optimizing Problem (1) [20 18 25). To address this, now introduce heterogeneity assumptions that control how the data distributions across machines are related.
Heterogeneity Assumptions. The most natural assumption linking the optimization problems across different machines is that their optima are close. particular, we assume that at least one pair of optima from two machines is close relative to their norms.
Assumption (Distance between Clients' Optima). There exists C. S 2B such that,
sup m.ne [M] *t, ESS. at ES: | - x < SC
inf
When all machines share common minimizer, we have Ç. 0. and solving Problem I recovers this global optimum. However, when machines do not share an optimizer, we must additionally assume that at least minimizer of the average objective is approximately optimal for each machine. Without this condition, some clients may not benefit from collaboration.
Assumption 5 (Distance between Clients' and the Average Objective's Optima). There exists d. < 2B such that
sup inf mE[M] st, EST, E* || x 22112 5.
*We use a single assumption for convexity and smoothness, but in our results we will denote μ to emphasize when we are considering general convex (as opposed to strongly convex) functions and when we do not want to capture third-order smoothness upper bounds, will interpret the assumption with
3

---

Reference
Function Sub-optimality Bound
Restrictions
Strongly Convex Setting (μ 0)
Kolosokova et al. 18] (Upper bound)
o²
+
Hº n²
Ho² D²KR
R = P
Woodworth et al. [20] (Upper Bound)
HKR
HB²
+
a² μMKR
H
Ho² H
Patel et al. 25 (Upper Bound)
HKR HB + μMKR
PKR
H2
R
+
0' n1 R
क. + Qº H'c
R
Theorem 3 (Upper
"KR
pB²
d RMKR
HH
2=202
R á (²1//
Tv/K
p K'
Bound)
Ha² a K'
Convex Setting (μ = 0)
Kolosokova et al. 18] (Upper bound)
HBa RI
+ oB
H43/5g4/3
11/2,2//8///
VMKR
R
K473
Woodworth et al. [20] (Upper Bound)
HB² KR
+ oB
2/3
VMKR
R2/3
R
Patel et al. 25
HBa + oB
112
VMKR R477
R172
(Upper Bound)
18/3 K1/31213 + 1QH g
RE7S
Theorem (Lower Bound)
rB² +
HB² aB
+ min
T T02/334/8
KR VMKA
12733
oB 1 g4/3
min
VKR' K1/3
Table 1: Summary of existing and (a subset of) our convergence guarantees for function-value suboptimality for convex and strongly convex settings (ignoring poly-logarithmic factors). The red terms are the ones that determine the communication complexity, as these terms can not be made arbitrarily small even with a very large K. Notably, there is no relevant lower bound in the strongly convex setting under the assumptions of our upper bounds, and there gaps between the upper and lower bounds in the general convex setting.
Most existing first-order heterogeneity conditions are variants of Assumption 5 The quantity captures the notion of approximate simultaneous realizability across clients and has also appeared in the literature on collaborative PAC learning and incentives for Federated Learning 447 48 49 50
immplees Remark (G, Φ.). With μ 0, Assumption implies Assumption 4 with Ç. 2 However,
the reverse is not true general: there exist problems that satisfy Assumption with Ç. << B, yet only satisfy Assumption 5 when o. z B. For this reason, distinguish between these two assumptions. See the discussion in Appendix A for more context on heterogeneity assumptions.
We also impose the following recond-orde heterogeneity assumption, which bounds how different the Hessians can be across machines.
Assumption (Bounded Recond-order Heterogeneity). There exists S 2H such that,
sup sup | F (x) ST. m,ne(M) ZER*
Note that the above assumption can always be satisfied by using = 2H and Assumption corresponds to the second-order smoothness of the function F.,(.) F.(-) for any pair of machines m, [M]. This observation will enable to replace H with 7 in several places.

---

Several recent works have established that Assumption 6 plays a central role in determining the communication complexity of distributed optimization. A prominent line of research has focused on distributed proximal-point methods. Early results in the quadratic setting showed that when 7 = 0. these methods can achieve extreme communication efficiency; requiring only a constant number of communication rounds [51]. More recent works extended these guarantees to the general case with 32 33 34 35]. In the context of Local SGD, Patel et al. [31] showed that a variance-reduced
т >>> variant achieves similar communication efficiency in the non-convex setting when
0, and that the optimal communication complexity scales linearly with T when the number of local updates K is large. Later, Patel et al. [25] studied Local SGD in the convex setting and showed that it can also be extremely However, their analysis relied the restrictive heterogeneity Assumption 7 They also conjectured that Assumptions 4 to 6 together are both necessary and sufficient to establish the communication efficiency and dominance of Local SGD over baselines like mini-batch SGD for convex problems. However, convergence guarantees under broader conditions as non-quadratic objectives as well as lower bounds that decay gracefully with т, have remained open.
providing convergence guarantees in terms of т.
Remark 2 (G. and vs. o+). In some settings, the parameter & in Assumption can can be bounded using S. and from Assumptions I and 6
For example, each F.. a strongly convex quadratic function with Hessian An and unique minimizer rmm then the global optimum satisfies
1 M
A-
Am
MM(M)
where == Emelan] Am. Using this, we can derive
25
(see proof in Appendix A):
Th+
|| x² x2112 S || - -1'll +1* x'112 S C, +
Vm E [M]
where x²
Σm -in Hence, can set o. (1 + 7/p). For general non-quadratic problems, however, it may not be possible to eliminate the dependence on Φ..
1
M
3 New General Convex Lower Bound with Second-order Heterogeneity
Our first result is the following convergence lower bound for general convex functions, explicitly capturing second-order heterogeneity t along with first-order heterogeneity é..
Theorem 1. There exists a quadratic problem instance satisfying Assumptions 7
1oo (with μ = 0)
such that for any choice of step-size T, Local SGD initialized at = O outputs model EKN with:
T
HB²
aB
aB /
E [F F(x*)
min
KR
VMKR
VKR K2/3
2/ B4/3
2/3
min
TO?
R2/3
We prove this theorem in Appendix C When Φ. is small and K is large, the lower bound is dominated by the term R. which suggests that the communication complexity of Local SGD should scale as TB² a rate that mirrors known results in the non-convex setting 30
z82
Comparison to Existing Lower Bounds. The strongest existing lower bound for Local SGD under the first-order heterogeneity assumption d, is due to Patel et al. [25). However, their result does not incorporate second-order heterogeneity as in Assumption 6 As the authors note, their hard instance degenerates when r = 0 because the smoothness constant H also vanishes, making the instance trivial. To address this, we extend the construction of Patel et al. (25 by introducing an additional dimension, which decouples the effects of and H on the convergence behavior of Local SGD. This modification ensures that our lower bound reduces the bound of Glasgow et al. 23 when
T 0-a bound that is known to be tight in the homogeneous setting.
'Patel et al. (25) also showed that Local SGD converges rapidly to its fixed point and exhibits no fixed- fixed-point discrepancy for quadratics when yielding extreme communication efficiency (see Appendix B).
5

---

Potential Future Improvements. We note that our lower bound does not depend on Ç., and o. alone captures the hardness of first-order heterogeneity. This is because for our hard instance Ç. o+. which is why we choose to state the result in terms of d+. which is usually bigger than Ç. (see Remarks T and 2). Deriving a lower bound that can decouple the dependence on S+ and Φe. i.e., decouple the proximity of machines' optima and "fixed-poin discrepancy", remains an open question. Also, we suspect that the last term of the lower bound, т can be replaced by H. Finally, all quadratic lower bounds for Local SGD 120 23 25 do not use unbounded fourth moments. Thus, we do not know if under weaker eccoddmomen variant Assumption 2 the lower bound can be improved by using higher moments of the noise to "confuse" the local updates.
In the following section, we will prove new upper bounds that exhibit qualitatively similar behavior to Theorem in regimes with low data heterogeneity and large K, reinforcing the role of т, Su, and de in governing the performance of Local SGD.
Breaking Down the Consensus Error and New Upper Bounds
In this section, we first present result on convergence in iterates in the strongly convex setting in Theorem 2 and then on convergence in function values in Theorem 3 Both our results will hold even when Q in Assumption I and as such the goal of this section is to highlight the effect of low second-order heterogeneity. We will focus here on the key ideas used to derive Theorem 2 the proof of Theorem is morally similar, and deferred to Appendix I.2
Our analysis proceeds in three stages. We begin by introducing a standard one-step progress result in Lemma [] which quantifies the improvement of Local SGD in terms of the consensus error quantity that measures the deviation between local and global íterates and plays a central role in the analysis of many distributed optimization algorithms. We then identify the main issues in the existing consensus error bounds: (i) they rely on restrictive assumptions 20 25]; and (ii) they do characterize the effect of second-order heterogeneity. To address both these issues we establish a new upper bound on the consensus error in Lemma 2 that only depends on Assumptions 4 to Finally, we substitute this bound into the progress lemma and unroll the resulting recursion obtain convergence guarantees for both strongly convex and general convex objectives. These results reveal how the convergence of Local SGD depends on the data heterogeneity parameters т, Su, and d., and highlight the algorithm's 's communication efficiency in regimes of low data heterogeneity and large K.
Lemma (Canonical One-step Lemma). Assume that the problem instance satisfies Assumptions 7 Then, for step-size rj म and all i E [0, T 1}, Local-SGD's iterates satisfy:
2 Band 6
E - x²12] s (1 - mn) E ||2 - x
+ nH²
1
Σ ME[M]
E
2
12
112
+
P
M
M
The above lemma is standard in the analysis of Local SGD [6
20
21 23 25]; we include a
proof in Appendix [F] for completeness. The blue term is the consensus error, which vanishes when all clients communicate at every time step (i.e., in fully synchronous SGD). Early analyses of Local SGD, such as (20), often controlled this term using the following restrictive assumption:
Assumption 7 (Uniform Bounded First-order Heterogeneity). There exists >> 0 such that
sup sup F| - VF H H-S.
m,ne[M] #ER"
Under Assumption
7 Woodworth et al. (20 showed that the consensus error can be bounded as:
< 22 + o² In(())
M
ME[M]
We include a proof of the above statement in Appendix G for completeness. Substituting into Lemma 1 and unrolling the recursion yields a convergence rate However, Assumption is very restrictive it requires the gradient functions across clients be pointwise similar, allowing only
'In Appendix G we also state some iterate convergence results under Assumption 7 that we could not find in clean form in the existing literature.

---

limited heterogeneity- y in the linear terms. Such mild variation can typically be resolved with constant mitial communication rounds (see Appendix A]. Notably, Wang al. [8] criticized the uniform consensus error bound in 3 arguing that contrary to practice it implies an overly conservative step-size 1j = ( to prevent consensus error from diverging as K - oc.
The following result relaxes the need for Assumption 7 by providing a new upper bound on the consensus error that depends on Ç.. 7, and the expected iterate error at the most recent communication round-a quantity that decreases over time.
Lemma (A Coupled Recursion for Consensus Error), Assume that the problem instance satisfies Assumptions ! 6
6 Then, for step-size < и and all t E [0, Local-SGD's 's iterates satisfy:
21 2 + 21 K² + 221 K + In(K))
Σ mE[M]
E Fe "n"l
M
+
0 -t
- ( (1))((=1~6())
E
Za(K) - x [12] + +
2
where 8(1):= : -- (t mod K) is the most recent communication round prior to or at time L.
We prove this result in Appendix H Unlike the earlier bound in (3). our upper bound improves
with lower second-orde heterogeneity. In the limit + 0, it effectively replaces with C. in (3). and can therefore be significantly smaller. While our bound does require setting 1 = (1/K) to
prevent ul as K - 30, we provide an alternative bound in Appendix H.3 that avoids this and
addresses the concerns raised by Wang et al. g That said, as we explain in Appendix [H.3] the
regime 1) O(1/K) is ultimately the most relevant for our analysis, making Lemma 2 more useful. Finally, we note that similar fine-grained upper bounds on consensus error have also appeared in the
literature on decentralized optimization [52 53, 54]
Combining the coupled recursions in Lemmas] I and leads to the following convergence guarantee:
Theorem 2 (Informal, Iterate Error). Assume a problem instance satisfies Assumptions 1 (with
Q = 20) and R==3 á
H1r n²² "H B2
Then, for a suitable 1, and To = 0 Local SGD oulputs x JKR s.l.:
o²
T2 T2 R²
H R²
H²7202
H² KAK
[KR x² Ö
μ2MKR
K
For the complete theorem statement, the precise step-size choice, and the derivation of the bound, see Appendix [.I As a baseline, we can compare the above rate to the convergence rate of mini-batch SGD in the intermittent communication setting (see e.g.. (20).
RR ~ MB-SGD - 111 = 28 B2
MMKR
It is well known that the convergence rate for mini-bateh SGD above is tight and can not improve with lower data heterogeneity [20] 225 Patel al. (25 proved that local SGD can not beat mini-
batch SGD under just Assumptions and 5 leaving open the question of what happens when we
additionally have Assumption 6 Theorem 2 answers this question, showing that with a small т, Local SGD can converge much faster than mini-batch SGD. Notably, when K - co, the communication complexity of Local SGD for target accuracy e and large K satisfies:
( (HT + THo. H2G.) 122 12VE
(c) - RL-SGD R
Ō
+
u2ve)
The above communication complexity decreases with data heterogeneity, suggesting that Local SGD becomes increasingly communication efficcient when tasks are more aligned. In particular, the convergence rate smoothly interpolates to the behavior on homogeneous problems, for which our bound implies that a constant number of communication rounds suffice. On the other hand, with similar K, the communication complexity of mini-batch SGD is ②(x)), and does not improve with a lower data heterogeneity. We note that this is the first ever result prove the domination of Local SGD over mini-batch SGD in settings of reasonable heterogeneity, i.e., these rates only depend on 7, S., Φ.. and not on while also showing a provable benefit of local update steps.
Using a different progress lemma (Appendix F33), we also derive a corresponding function-value convergence result based on the same consensus error bound in Lemma 2
7

---

Theorem 3 (Informal, Function Error with Strong Convexity). Assume problem instance satisfies Assumptions to (with Q = 20), R = Q
IVR ). and KR S2().. Then, for a suitable TJ, Local SGD initialized 2o 0 outputs &, a weighted combination of its iterates, satisfying,
F(x") - δ (
0²
H² P
H²
HTG
Ho²
E [F(()
aKR 2H BB²
+
+ K2KR
μMKR
HARS
The proof of the above theorem can be found in Appendix 1 The above convergence rate also has a desirable dependence on the data heterogeneity constants and improves over mini-batch SGD.
General Convex Functions. One might ask, what is the corresponding rate to Theorem for general convex functions (with possibly zero)? A natural approach to get that rate is using a convex to strongly convex reduction, using an appropriate amount of regularization in Theorem 3 This strategy, unfortunately, leads to very stringent constraints on the heterogeneity constants and the number of communication rounds. This is why we omit stating the result here. We suspect that extending the ideas in this section to general convex functions might require more technical innovations. We leave this for future work, and note that this is an important gap as the upper bounds presented in this section are not directly comparable to Theorem
Finally, it is worth noting that the hard instance in Theorem T quadratic function, and thus has Q = 0 while in this section we only present results for general strongly convex objectives. This raises the possibility that, by restricting attention to quadratics, we may be able to improve upon the upper bound in Theorems 2 and 3 In the next section, we explore this direction by deriving tighter upper bounds in regimes where the third-order smoothness constant Q from Assumption small.
5 Incorporating Third-order Smoothness
In the homogeneous setting, Woodworth et al. 22 showed a surprising result: for smooth and convex objectives, Local SGD can outperform mini-batch SGD only when SGD on a single machine also outperforms it. This contradicts empirical findings, where Local SGD consistently outperforms both mini-batch and single machine SGD [55] 77. However, for certain objective classes with higher-order smoothness as quadratics [6 and logistic regression 28 Local SGD can be provably superior to these two baselines and even min-max optimal some scenarios. To alleviate this gap, Yuan and Ma [21] analyzed Local SGD under third-order smoothness assumption (i.e., bounded Q in Assumption
[ providing convergence guarantees that could interpolate between convex functions and guadratics. Patel et al. [25] extended this to the heterogeneous setting but relied on the restrictive Assumption 7 In this section, equipped with the new consensus error and a modified one-step lemma, relax that assumption and refine our upper bounds from the previous section to make their dependence on third-order smoothness explicit.
We will begin by stating modified one-step progress result in Lemma 3 that explicitly captures second-order heterogeneity and third-order smoothness. This directly recovers improved bounds for quadratic objectives by setting Q 0 in Theorems 4 and 5 To handle general third-order smooth functions, we combine this with new bounds on the fourth moment of the consensus error (Appendix H.2) and corresponding fourth-moment progress lemma (Appendix F.2),, resulting in Theorem 6 These results show that when Q and T are small, Local SGD can achieve significantly faster convergence, even under substantial first-order heterogeneity.
Lemma 3 (Modified One-step Lemma). Assume the problem instance satisfies Assumptions 7 and 6 Then, for step-size 1) < and all E [0,T T 1), the iterates of Local SGD satisfy:
7200
E
1aa1-xx00 -x-=x=113 x11]] S (1 mnt1) E [|:0 |1:41-
2
M
2n 1
2n7
|x0 x
+
Σ mE[M]
E
Iz - 2
M
M
mE(M]
We prove Lemma 3 in Appendix Compared to Lemma [ this recursion introduces an additional
fourth-moment of the consensus error, weighted by the third-order smoothness constant Q. While this
'In the regime >>>>>> 1 Theorem is much better than just applying second-order smoothness Theorem 2
8

---

fourth- morentt term can dominate the second-moment term, the decomposition reveals how smoother problems (with small Q and 7) reduce the impact of delayed communication. In particular, when Q = O Q- when each Fm. is quadratic- we obtain significantly sharper bounds than in Theorem 2 Assumption (Quadraticity). For all m E [M], the objective function Fm (-) is quadratic. Theorem 4 (Informal, Iterate Error for Quadratics). Assume the problem instance satisfies Assump- tions
( and KR = (11).. Then, for a suitable choice of step-size T, Local SGD iitiillizdd To 0 outputs J.K. R such that:
to 6 and R ②
||IRR - x E
(
e.R B²
a²
+
TO P +
J²02 Jea KRRR
NRMKR
n
K
We prove this theorem in Appendix I.I To understand the improvement over Theorem consider the implied communication complexity in the large K regime:
The THG, (
T 12
R(() Ô
(5)
1PVe
p²ve)
which becomes constant when T O. In contrast, the bound in (4) still depends on Ç. even when = O. This highlights how low third-order smoothness (Q) and low second-order heterogeneity (T) improve Local SGD's cefoomannce-spcciaalll in settings where first-order heterogeneity is still large. It is also worth noting that the convergence rates for mini- SGD do not improve with a lower third-order smoothness, as the hard instances for
SGD are all quadratic [56].
Using a different modified progress lemma (see Appendix gence rate in terms of function values.
F.3) we also derive the following conver-
Theorem 5 (Informal, Function Error for Quadratics). Assume a problem instance satisfies Assump-
to 6 and 8 R 2 (م² and KR 22(:). Then, for suitable choice of step-size 1), Local SGD initialized wo = 0 outputs L, weighted combination of its iterates, satisfying,
tions
BB² 0²
A022
2 22
T²
7202
E [F(+)] - F(x*) δ
PMKR
1 R2
R
K
The proof for the above theorem can be found in Appendix Compared to Theorem 2 we again see an improvement, as all but the first two terms in the convergence rate go to zero when 7 = O.
Finally, we prove the following result for general third-order smooth functions.
Theorem 6 (Informal, Iterate Error with Q). Assume a problem instance satisfies Assumptions to T Then, for suitable choice of size 1), Local SGD initialized at zo 0 outputs E&R satisfying:
E
|0KR- ==1[]]
+
E
|IKR-
x x2166] =
(
nRnKR B²
0²
A M
B
pa
M2MRR
7200
T-02
0272
H²
T202
n''
112
Ro Ba
K B
1A
K
(0lln(K)
HAC
Aaa
H2
720
0² d'nK(K)
(1PK
B²
R5
B
K
where we assume R ==
IVK
and define K²' = 2 40
6H
We can see that the above convergence rate improves with smaller 7 and Q. via the constant k', and the effect of a low third-order smoothness is most pronounced when B/p² p.² is large relative to x To prove the above theorem, we first derive new fourth-moment bounds on the consensus error and one-step progress in Appendices F and H Solving the resulting four coupled recursions directly challenging, so we stack the iterate and consensus recursions into two vectors and apply matrix algebra, leading to cleaner proof in Appendix [.3] A limitation of our analysis is that the final bound is expressed in terms of the norm of stacked vector that includes both second and fourth- fourth-moment errors. Since bounding the fourth moment of the iterate error is not strictly necessary, this may have introduced extraneous terms in the upper bound. We therefore believe that Theorem [couudd be further improved through a more refined analysis of the underlying matrix incqualities.

---

6 Case Study: Distributed Linear Regression
We consider a linear regression task, where for each client m [M], the data consists of covariate- label pairs 2m (8m, Fm Dm with Gaussian covariates 3m NN Ig) E R and labels ym (2 3m) + NV o maise) generated using ground truth model Fin R Each client minimizes the mean squared error, [2; (Bm: Vmm) = 1 (1m (z,,mm) leading to an expected loss:
(x) = 22(2 -x--220 -mm) (MmH + 1a)(2 mm + 2 noise
Under suitable bounds on Mons Em, and moise, this problem satisfies Assumptions I for bounded Furthermore, we have Fm (x) F2 (1))2)12 I (llmmll22 + [| 122 I1 M 1 for any
m,n n [M]. So Assumption @luantifies oqquatiis the covariate shift across clients. Meanwhile, Assumption reflects the concept shift via the bound ||=, - - S C..
In Figure 2 we examine the convergence behavior of Local SGD on the synthetic linear regression task. In Figure 2aj we decouple first- and second-order heterogeneity by independently varying the means am and the ground truths 2,, We observe that Local SGD performs well only when both types of heterogeneity are small. This highlights why carlier works that did not account for second-order heterogeneity (Assumption ( were unable explain Local SGD's effectiveness fully. In Figure 2b we fix the first-order heterogeneity and plot the communication complexity required to reach a target accuracy a function of 7. As expected, find monotonic relationship, further reinforcing the connection between second-order heterogeneity and the communication efficiency of Local SGD.
Importantly, when varying the heterogeneity, we ensure we do not inadvertently make the individual optimization problems harder, for example, by increasing the condition number & or the radius B. In Appendix describe how we control for this and include additional experiments.
Local SGD Aug Best Error
Comm.comppeedty
Comm. complexity vs. 2nd-order heterogenelty
5.00
136
Avg commmnttiio Rumit 10ch o70
1.50
332
330
0.75
40
100
10c
Cousride
Coveriste anif:
(a) Heatmap of the average best-final &a error of Local SGD after communication rounds as function of covariate shift r (horizontal axis) and concept shift S. (vertical axis).
(b) Communication complexity of Local SGD versus covariate shift т. for fixed concept shift Ç. = 1.0 to reach an &a error < 0.04. We allow up to Rmaax 100 rounds, and plot the mean rounds-to-target.
Figure 2: Impact First- and Second-Order Heterogeneity on Local SGD. In both figures, we use d 5, MM 20 clients, K = 10 local steps, and noise level of noise 0.1. The step-size is tuned over a logarithmic grid in [10 10 10011 3I. and the error is averaged over multiple trials. For (a), report the mean eгror over 7luus 20 trials for each (T, (.) pair, tuning the step-size separately in each trial. Similarly, in (b), we average over Nyuns = 20 trials for each T, again tuning the step-size independently per trial. We discuss in Appendix P hoow to interpret the G. in our plots' axes.
Practical Implications for Federated Learning, Our results highlight that the performance of Local SGD depends critically on the structure of data heterogeneity. In practice, this suggests distinguishing between heterogeneity in optimal predictors (firttorderr, measured by Ç. and Φ.) and curvature or feature distributions (second-order, measured by 7). For example, Ç. may be small for learning in overparameterized settings while remains significant. Large local steps (K) can still yield good performance and communication savings in such cases. But when T is very large, aggressive local updates with fixed step-size can cause instability. We recommend tuning 1 function of K and using diagnostic signals-aan -uch as consensus error growth or curvature estimates- too adjust training parameters. Estimating from local and running statistics could help guide such choices in practice.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers NeurIPS, who helped significantly improve the paper. KKP was supported through the NSF TRIPOD Institute on Data, Economics, Algorithms and Learning (IDEAL) and other awards from DARPA and NSF.
References
[1] Alex Krizhevsky, Ily Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
[2] Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint arXiv: 160.00629, 2016.
[3] H Brendan McMahan, Eider Moore, Daniel Ramage, S Hampson, and B Agüera Arcas. Communication--ffficienn learning deep networks from decentralized data (2016). arXiv preprint arXiv: 1602.00562, 2016.
[4] Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in neural information processing systems, 31, 2018.
[5] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. corr. arXiv preprint arXiv: 2019.
[6] Jianyu Wang. Zachary Charles, Zheng Xu. Gauri Joshi, Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide federated optimization. arXiv preprint 107.v:2107.069// 2021.
[7] Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large-cohor training for federated learning. Advances in neural information processing systems, 34:20461-20475, 2021.
[8] Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint arXiv:2206.04723, 2022.
[9] Ofer Dekel, Ran prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Ohad Shamir, and Lin Xiao. Optimal distributed online
[10] Tao Lin, Sebastian Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, local sgd. arXiv preprint 100.002177 2018.
[11] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[12] Ryan Medonald, Mehryar Mohri, Nathan Silberman, Dan Walker, and Gideon Mann. Efficient large-scale distributed training of conditional maximum entropy models. Advances in neural information processing systems, 22, 2009.
[13] Martin Zinkevich, Markus Weimer, Lihong Li. and Alex Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
[14] Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré. Parallel sgd: When does averaging help? arXiv preprint arXiv:1606.07365. 2016.
[15] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767. 2018.
[16] Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32, 2019.
11

---

[17] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
[18] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[20] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-653 1-622,, 2020.
[21] Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344 2020.
[22] Blake E. Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. Conference on Learning Theorr, pages 4386 1.86-4437. PMLR, 2021.
[23] Margalit Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pages 0050-90900 PMLR, 2022.
[24] Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, and Nathan Srebro. Federated online and bandit convex optimization. In International Conference on Machine Learning, pages 27439 27460. PMLR, 2023.
[25] Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian Stich, Zi- heng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication. In The Thirty Seventh Annual Conference Learning Theory, pages 4115-4157. PMLR, 2024.
[26] Paul Mangold, Alain Oliviero Durmus, Aymeric Dieuleveut, Sergey Samsonov, and Eric Moulines. Refined analysis of constant step size federated averaging and federated richardson- romberg extrapolation. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258, pages 5023-5031, 2025.
[27] Brian Bullins, Kumar Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake Woodworth. stochastic newton algorithm for distributed convex optimization. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[28] Michael Crawshaw, Blake Woodworth, and Mingrui Liu. Local steps speed up local gd for heterogeneous distributed logistic regression. arXiv preprint arXiv:2501.13790 2025.
[29] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint mtxxxiv:000.066000 2020.
[30] Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning. arXiv preprint arXiv:2102.031198 2021.
[31] Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nathan Srebro. To- wards optimal communication complexity in distributed non-convex optimization. In Advances Neural Information Processing Systems, 2022.
[32] Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. In SIAM Journal on Optimization, 2022.
12

---

[33] Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Dmitrievna Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. In Advances in Neural Information Processing Systems, 2022.
[34] Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Federated optimization with doubly regularized drift correction. In Proceedings of the 41st International Conference on Machine Learming, volume 235 of Proceedings of Machine Learning Research, pages PMLR, 21-27 Jul 2024.
[35] Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Stabilized proximal-poin methods for federated optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[36] Sebastian U Stich, Jean- -aptittt Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Proceedings of Advances in Neural Information Processing Systems, 2018.
[37] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Muchine Learning (ICML 2019). 2019.
[38] Yuan Gao, Rustem Islamov, and Sebastian Stich. EControl: Fast distributed optimization with compression and error control. In The Twelfth International Conference on Learning Representations, 2024.
[39] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Proceedings of Advances in Neural Information Processing Systems, 2018.
[40] Sindri Magnússon, Hossein Shokri-Ghadikole Ghadikolaei, and Na Li. On maintaining linear convergence of distributed learning and optimization under limited communication. In 2019 53rd Asilomar Conference Signals, Systems, and Computers, pages 432 022-436.77 2019.
[41] Min Ye and Emmanuel Abbe. Communication-compuaatii Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 5610-5619. PMLR, 10-15 Jul 2018.
efficient gradient coding. In
[42] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedbcc framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 2020.
[43] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang. Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454-3469, 2020.
[44] Yongqiang Wang and Angelia Nedié. Robust constrained consensus and -esuualltycoonstaaneed distributed optimization with guaranteed differential privacy and accurate convergence. IEEE Transactions on Automatic Control, 69(1 1):7463-7478, 2024.
[45] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in neural information processing systems, 31, 2018.
[46] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. International conference on machine learning, pages 5311-5319. PMLR, 2021.
[47] Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. Advances in Neural Information Processing Systems, 30, 2017.
[48] Huy Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative pac learning. Advances in Neural Information Processing Systems, 31, 2018.
[49] Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances in Nearal Information Processing Systems, 35:406-419,
2022.
13

---

[50] Minbiao Han, Kumar Kshitij Patel, Han Shao, and Lingxiao Wang. On the effect of defections federated learning and how to prevent them. arXiv preprint arXiv:2311.16459 2023.
[51] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication--effiienn distributed optimization using approximate newton-type method. In International conference machine learning, pages 1000-1008. PMLR, 2014.
[52] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34: 14:13975-13987, 2021.
[53] Edward Duc Hien Nguyen, Xin Jiang, Bicheng Ying, and César A Uribe. On graphs with finite-time consensus and their use in gradient tracking. SIAM Journal on Optimization, 35(2):872-89) -98, 2025.
[54] Sulaiman A Alghunaim. Local exact-diffusion for decentralized optimization and learning. IEEE Transactions on Automatic Control, (9(11):77717738 2024.
[55] Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learning without centralized training data, Apr 2017.
[56] Yurii Nesterov al. Lectures on convex optimization, volume 137. Springer, 2018.
[57] Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pages 6692 6701. PMLR, 2020.
[58] Zachary Charles and Jakub Konecny. On the outsized importance of learning rates in local update methods. arXiv preprint arXiv:2007.00878, 2020.
[59] Xinran Gu, Kaifeng Lyu, Longbo Huang, and Sanjeev Arora. Why (and when) does local sgd generalize better than sgd? arXiv preprint arXiv:2303.01225. 2023.
[60] Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 10X1v:190.004232, 2019.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes. All the claims in this paper reflects the scope and contribution of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes. We discuss some limitations of our lower bound in Section 2 and our third-order smoothness upper bound in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Yes. We provide detailed proof for all the theoretical claims with all the assumptions needed for the proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Yes. We provide all information and details needed to reproduce our results in Section 6 and the Appendix (submitted part of the supplementary material).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes. We include the code for reproducing all results the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
pub / gu des / CodeSuuom ss isiionn onPol cy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
httpsscccppppcccccc...co.cccccc Swweiideeee/oeeeeubeeeee Sttme as owooooooiiii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes. All the details regarding the hyperparameters are mentioned in Section and the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes. We repeat the experiment for several times and report the average
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes. We include the information about the computer resource in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, this research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical and raises no immediate concerns on socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No assets used in this work.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assests are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: No core method development in this paper used LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ht //t::///neuipppeeeee /tt.arrrippecccooooooeenneeee//e 2025/ LLM) for what should or should not be described.
21

---

Table of Contents
The Unreasonable Effectiveness of Local SGD
2 Setting and Preliminaries
3 A New General Convex Lower Bound with Second-order Heterogeneity
Breaking Down the Consensus Error and New Upper Bounds
5 Incorporating Third-order Smoothness
6
Case Study: Distributed Linear Regression
10
A More Discussion on Heterogeneity Assumptions
23
A.1
Construction for Remark
23
2 Proof of Remark[2
24
More Discussion on the Fixed Point Perspective
24
B.1
Fast Convergence to Fixed fixed-point in the Quadratic Setting
25
B.2
Improved Fixed-point Discrepancy Upper Bound for Quadratics
................................
28
B.3
On the Nature of Local SGD's s Fixed Point for Quadratics
31
B.4
Implicit Regularization due to Local SGD
34
B.5
Extension Non-quadraties?
36
Proof of the Lower Bound in Theorem
36
Notation and Outline of the Upper Bounds' Proofs
40
Useful Technical Lemmas
40
Useful Facts about Stochastic Noise
40
Other Analytical Lemmas
43
F Deriving Round-wise Recursions for Errors
45
F.1
Second Moment of the Error in Iterates
45
Fourth Moment of the Error in (erates
48
Function Value Error
54
Uniform Control over the Consensus Error and Analysis using Assumption 7
54
G.1
Upper Bound on Second Moment of Consensus Error
54
G.2 Upper Bound Fourth Moment of Consensus Error
55
G.3
Convergence in Iterates
58
22

---

G.4
Tuning the Step
59
Double Recursions for Consensus Error
60
H.
Second Moment of the Consensus Error
60
H22 Fourth Moment of the Consensus Error
H.3 Should Consensus Error Explode for Large Step-size?
69
Putting it All Together
70
I.1
Convergence Iterates without Third-order Smoothness
70
I.2 Convergence in Function Value without Third-order Smoothness
74
Convergence Iterates with Third-order Smoothness
J
More Details the Experiments
82
U.1
Data generation for each client
82
J.2
Controlling first-order (concept) heterogeneity
83
J.3
Controlling second-order (covariate) heterogeneity
83
J.4
Hyper-panee parerearreeter tuning and metrics
84
J.5
Ensuring fixed problem difficulty.
84
J.6
Experiments with More Machines and Communication Rounds
84
A
More Discussion on Heterogeneity Assumptions
A.1
Construction for Remark 1
This sub-section will show a problem with G. << and é. As B. As a preliminary remark, note that we must consider high-dimensional examples for this: in a single dimension, x² must be in the convex hull of {zf.... E5 } (which is just a mee-seemmnt). The instance we will consider will make of the following two functions, which take woo-dimensional inputs (z., v) R.?
2 + x + y 5t
5. 2
Se
f(x v) =
x
and g(x,1)
+
x
+ y
Note that both these functions are strictly convex with optimizers at tively. However, the optimizer of the average of these functions is given by S which is notably not on the convex hull of the optimizers of the constituent functions.
(=) 0)
and (2.0) respec-
Now define M different objectives d dimensions (assuming M, d are for simplicity) as follows:
(x) = [(=[1),
F2(x) = g(*[1], x|2)) + 2 (00,0, (.,...
Fs(x) [=]33 x(4) [(2,1),,=22)00,,.x,, [MM
Fa(x) [1=33, +
[(<=1),==2200000004 (M)
1 2
FM-1(x) = f(x[M =1,) (0 0. ..... 2(M 1], =],=(MM)11
(x) = 9(x[M - I],+ + (1 0, x/M - 1}.=(M))
23

---

Due to the properties of f. that we discussed above, note that for any two machines m + n, | 1ill2 S.. Furthermore, note the optimizer of the obejctive given by x² This implies that,
x x. 6 $6....... g 5
S+
(M 1)
(M + +
| x=1
m is odd
2
36
36
C+
(M
1)(2
(M + 15)ç2
1 x=1
+
m is even
2
6
36
36
15 (assume it is even number), then can guarantee that s. must be at least B. This proves the claim we made in the remark.
In partieular, if we pick M
36 12a c.
A.2 Proof of Remark
This is easy to see let us just write 8* more explicitly,
| x² 112 I
|1 - 12112 + | - x²
ll2
1
1
(x - xnn
+
(x - A -Annt
M
M
M
ME
2z lll2 +
1
Σ
A- (A - An) (27 - -x²)
M
M
[E[M]
nE[M]]
Assumption
Σ
||-- (A - An) (x
E²)112 (x))=
M
ME(M]
1
S S. +
Σ ||
1l 1A - Anll2 (I -²)
M
RE(M]
S + TG
which proves the claim of Remark
2
B More Discussion on the Fixed Point Perspective
Several papers have pointed out with varying levels of explicitness [57 58 25 that the hardness of analysing Local SGD's convergence comes from fixed-point discrepancy. i.e., Local SGD in the limit of large R converges to point different from x² whenever K > 1. This is an alternative viewpoint to data heterogeneity, and can be useful provide analyses of Local SGD. For the simple case of strongly convex quadratic functions Patel et al. 25 showed that in the absence of noise, Local GD converges very quickly-with extreme communication efficiency-to its fixed point and they also gave a bound for the fixed point discrepancy in terms of Assumptions to
In this section, we will revisit their analysis, showing that it extends to the stochastic case and also provide a more finennrained upper bound on the fixed-point discrepancy for the quadratic case. Both these advancements allow us provide convergence for strongly convex quadratics in Theorem 7 Then we will make a few comments about the convex quadratic setting, i.c., when μ 0, commenting on the potential regularization effects of Local-SGD.
Throughout this section, we will consider Local SGD with both an inner step-size v and an outer step-size B. In the main paper, we only analysed and discussed Local SGD with single step-size,
24

---

Le., we set B = 1. To make the notation easier to accommodate two step-sizes, we use the following.
F..0 Tr-1-
vm E [M]
r,++
m m2
1/
2r m ~ Dm
Vm e [M]. k (0, --1]
(6)
T, E 1r-1+ +
Σ
(r, - 1,-1)
M
ME[M]
B.1 Fast Convergence to Fixed-point in the Quadratic Setting
The following Lemma extends the analysis of Patel et al. the stochastic setting.
25 for convergence to the fixed point to
Lemma 4. For quadratic problems satisfying Assumptions and with machine m ''s hessian denoted by Am. with < T.' and B S T-(1-111 the Local-SGD iterate RR (with initialization
To = 0) satisfies,
E | 100 112]
o² μ.
s (1 B (1- (1) | 112 + n/3 (1 1 (1-B(p B(1 (1 ))
where we define Ixo == 1. EmE(M C Cm for Cm == (I nm ) k and Emelan Om. In particular, when 3 = we have,
1
M
- (1-7 2k 1 12 + 17 (1- m1) kR) o²
E
|| -1 Ioo 112]
MM
Proof. We consider quadratic problems of the form,
1 ( =mm"
(x: 2
Am (x T xmm)
where Am > 0 is positive definite Hessian matrix. We denote the fixed-point of Local SGD by (for a simple intuition see (25)).
Σ ME[M]
C-
where C'm := I (1 nAm)
M
We now note the following about the local-SGD updates between two communication rounds on machine E [M.]
2T K
1. K- 1 2m 7Am(=
xmm
+ 17 (A (-,,K-11 xtm)
(1 Am
(z/7) -xnn)
K
+ Σ
(T Am 111 (mm(17 Imm) (. 2x
k=
K-1
= (I 1mm) K (Ir~1 - xxi)) +
Σ
(I - 1--Amm) k K-
k=
This implies the following
K-1
Kr 2r-1 I'm -r-- + (I nAn) K (xr-1 - (#1-1-2ū1)
xxm) +1
(I nAm)
K-1-k
Sm
k=0
K
=- (--nAm))) (I -0m)1 +
Am
K-1-k
Sm
k=0
25

---

K-1
(1 Am 1-Am))--1 --
-C (Ix-1 I'n) + "
5r,k
k=0
K-1
- + Cm +
Σ
(T Am
1111 Sr.
k=
This implies for the r-th synchronized model,
K-1 1
Tr 1
8
Σ
Cm + Cm +
Σ (I nA
K-1-k
K
Sri
M ME[M]
k=0
K-1
= =(1 -T (1-3C) 3C) -- +
3
Σ
Cm + n1.3
Σ
(T - mm K-1- )
1
Σ Sri
M
M
mE[M]
k=0
mE(M)
= (I 3C) (z )00) + 2000
Σ Cm
M
mE|M
K-1
+ 13 Σ k=U
(I - -mAm)) )km K-1-- Er.k
Cma + 1
(I BC) (xr-1 D00) + 1:000
Σ
Cmmin
Cm
M
M
MEIM|
ME(M]
K-1
+ n3
Σ k=0
(I - nm))
K
Er.k
Simplifying and rearranging this, we get for R,
K-1
FR - Jx00 = (1- - (IR-1 x20) + n1
Σ
(T
Am)
K-1 En,
h=0
R-1
K-1
= (I - BC) (xo- xx ) +
Σ
(I- BC) R-
113
Σ
(I - 1--)mm))
K-1
Eri
r=0
k=
Take the norm, squaring, and taking expectation, we get, x 2
||ar
2R $ -
[ =10)
2
+ 82 R-1
R-1
|T - BC
Σ
(I Am
) 11-) E |15 113]
2(K
S ||| - BC1| 2R
T 2
R-1
K-1
(1 (1-n K -1 --
+ 7
1| - 301 2(R-1-1)
Σ
M
k=0
< (1 AAmin (C)) |
R-1
(1 (1-(--m)) mm)
σ²
+ n 82
Σ
(1 - 3Amin (C))
(
M
r=
We now need upper and lower bounds on the minimum eigenvalue of C. For this, note that,
Xmin (C) Ammin
Σ
M
ME(M]
min
1
Σ T
(T - mmm
M
M
ME[M]
26

---

Σ 8² nmm! )
1 - max
|| || M
mc[M1]
E 1 ((1 m1/)** " (1 ,)H )
(1 - (1 .//)** x 1 (1 n,H )
Plugging these bounds in the above inequality leads to,
E ||,r - x0 [12]
S (1 - 3 (1 (1 - (1-r)/) )) 212 ||:00011 1
+ n13 - (1 - 3 (1 (1 - m/) )
1 (1 - mu) K
x²
1 (1 m/)iKK
1
M
$ (1- - B (1 - (1 - ))))x) 212 || 1
o²
m (1 3 (1 - (1 - mu) (1-1 ))
PM
Note that the range of Amnn (C) is what suggests the upper bound on of
1- nH
Next we will establish an upper bound on | which would allow us to provide the upper bound in terms of B from Assumption
Lemma S. In the setting of the previous lemma,
| S min (NTKEG. + BBKB)
Proof. Recall the definition of &os.
| 1|2 = C-1
Σ Cm
M
MEI
C-1
Σ
(Cm - CC+ - F + +T*)
M
MEIM
C-1
1
Σ (Cm -))(() (zt - x²)
+ x²
M
MEM
Σ
||C
C0-1(C (Cm - Cn)ll2 + M
Σ || ll2
M
[,nE[M]
mE(M]
Σ
||c [[n,-,,))* - -I - AmAm - )k| 112 || - -x7ll2 + M
Σ
|
M
[M
mc(M]
6 MTK (1 (1 -
Lemma and Assumptions
(1 - (1- C.
1 1-11n S KTK
I- - nn)* So +
1-(1- can be upper bounded by к g(1) for any choice of step-size 77. To do this we show that g is non-increasing function and thus can be upper bounded by g1). To see this note for & E Ez1. while denoting 0 < a = 1 - 7i s 1 - 1-np =: < 1,
Now we will show that the factor g(K) 1-(1-1H)*
k
g(k)
bk
1 -aa
1 a + + o
1-b b 1+b+ b--1
27

---

1- Sa(a)
Sa(b)
where we defined the geometric sum Ss(.) for ease notation. Using this we get that,
b = (x(a) Sx+1(a)
(g(h) - g(k + 1)) 1 a
Sb) Sk+1(b)
Sa(a) Sa(a) +
Sx( (x(6) +
(A( + 11) (Sx(a) + +
(5x (4)
a²b²
(sa(a)
Sc(b)
(L(b)( + b*)
a
6
a²b²
a b'
(S& + b4)
a
bk
a²b²
(a - bi-b)
(bb ba)
(acb) 0
Thus 9() is non-increasing function proving our earlier claim. Plugging this above gives us,
|| S KTC, B
Note that in the very first step of the proof could also upper bound || by g (())B, thus can also get the trivial upper bound xB, following the result of the proof. This proves the lemma. O
Combining the previous two lemmas and simplifying we get the following convergence rate to the fixed point.
Proposition 1 (Fast Convergence Fixed Point). For quadratic problems satisfying Assumptions 7 to and 8 with machine m hessian denoted by Am, with < H. and 3 = 1 the Local-SGD iterate FR (with intiialization To 0) satisfies,
yo² pM
B R - x 200
s e 2naKR min {NTKKG. B, BB
Note that while Assumption 3
we assume that ||x* < B, but in general if we only assume norms of the individual machines optimizers are bounded by B, then the most natural upper bound
on xx is IC. B.
B.2 Improved Fixed-point Diserepancy Upper Bound for Quadratics
We will need the following lemma about the Lipschitzness of specific matrix polynomial. Lemma 6. Let Am, An E Raxd be symmetric positive-definite matrices whose spectra lie inside the interval [u, H] C (0, 1/n), with 0 < μ S H and 0 < 1 < 1/H. Fix an integer K 2 1 and define the polynomial
R(A) = 1- 1- (1- nKA,
EER. IR
Extend to symmetric matrices by functional calculus, R(X) = - (1 - -x)) K -nKX. Then
[((Am) R(An)ll s L||Am - -Aull2: L= n [1 -(1 -11-nH K-1]
Proof. Step 1: A scalar Lipschitz constant. Direct differentiation gives
R' (A( =nk [(1 [ --1 1].
28

---

which is non non-positive and increasing on [p, H]. Hence
L = sup A
[R' = nk - - (1-))))))-
Step 2: Fréchet derivative. Write X U diag( (1,,...................... Ad) and set F U EU for any
symmetric perturbation E. The Daleckii Krein formula yields
R(A:) R(Aj)
(R U(MO))U)
My
X X,
Because R is operator-monotoon on (,, HJ, the matrix M is positive-semidefinie and its entries satisfy |M₂l S L..
Step 3: Schur-multiplier estimate. a PSD matrix M has entries bounded by L. then for every
G' E gdxd
||M 3 G & (max Ma) |G]|2 & L |||||2
Applying this with G= gives
[R[X](E)]22 I 2
Step 4: Integration along line segment. Set A = Am - An and A(I) :- A, + +1 for / E [0,
Define (t)) := H( ((((t)). Step 3 implies [| - L|lA|1 for all t, so
||((Am)) R(A,))l [L) (0))l - / || (1)l222 S ||
This is precisely the claimed bound.
Now are ready to prove the following lemma which improves upon the result of Patel et al. 22
Lemma 7 (Fixed Point Discrepancy for Quadratics). For functions satisfying Assumptions anddn 6 we can guarantee the following for n 1/H,
S-T (1- (1- nH) 1 + nHK quk (1 (1 (1-n1H) nH)K-1)
| S
/b
Remark 3. Note that the above bound goes to zero when Ç. is zero, which matches the behavior of the bound due to Patel et al. (25). However, the bound also goes to zero when = 1 or 7 - 0, behavior their bound did not capture.
Proof. Note the following.
1|0" 20o112
1
Σ
(A-1 Am - (4 - xtri
M
m.nE[M]
S
Σ
AA-
- 112 |z -2
M
M.nE[M]
Am-1Am
-m
M
ME(M]
Let us denote the following,
Cm = I- (T-mAAmmm =: 17K An + Rm and R:
Σ Rm
M mE[M]
In particular, note that when K = 1, then Pnm O. which implies that R = 0. Using this notation, we have the following,
||A- Am -- c--Cmllly -||0-1 (CA- Am Cm2)l2
29

---

||c (MKK+ A - -nKAm - -Rm)ll2
||c (RA-1A,, Am Rm)
||C-! (RA-LAm - - - -2--P- R Rm) 112
||c- 112 (11 |1A-AAm - -1112 + || |R-mmll
1 1
Σ
[11/11l22 + |l Rulla)
1 (1 npi M
ME[M]
Now it suffices upper bound the two terms |m lly and || Rallz- As sanity check, note that when K = 1 and r = 0, the upper bounds are still zero. For the first term, note the following using the diagonalization of the matrix Am = Vn Em Vm+
R ll2
|| AKAn mnn)) ll2
= || - mkKin - - -112mn)) 1x] 1
< sup || 1yK (1 -n))*(
xE(u.H)
(1 H)) - + nHK
where we use the fact that 7) <
17 which implies that n, < the above function, which in turn
implies that |1 y (1 m))* | is an increasing function in the range À E [e, H. Now we need
to bound the second term Rm 12- Note that ideally we would like the upper bound to also vanish with K = and r = O. We cannot use the strategy from above because we do not know if the matrices A, and A,, commute. Instead we will use the following property (see Lemma 6 that follows),
[[(Am)) RR(A)ll 3 sup [R) ||Am
An ll2
xE(a,1]
where we define R(A) = 1- (1 -11 -)))) KKA. Note the following.
[R() |nK[11 m7 *-1 n9
=1-nk nK (1 -11 (1-12)*
= =nk |1 (1 - -1
Plugging this in the above bound gives us
Rm Rull22 = [|((Am) - R(An)) l1
S sup n Am An 112 11- (1 -
A
< nkK r (1 (1 m/11
For sanity check, note that when K 1 or O, this bound is zero. Plugging the blue and cyan upper bounds back into the original bound on fixed-point discrepancy, we get,
||=- -Kooll 122
So
1
Σ m.ne(M]
(H 11m + || Rull2
1 (1 k K
ME
So
1 (1 mu)K
M Σ ((1111))* -100) 1+ + +TKT (1 m)H) (1-()1)))(11))
M.NE[M]
4T (1 1HH KK
qHH K- + qukK (1 - (1 - -HH)
1 (1 nu)
This proves the lemma.
While the general behavior of the fixed-point discrepancy upper bound can quite complex, we can study its effect for specific step-size, which leads to the following convergence guarantee.
30

---

Theorem 7. Assume we are optimizing problem instance satisfying Assumptions 7 to 6 and g
R 2 2ln
B² > and KR Z 2x
for some target accuracy c. Then using
In #kR
B² and? 3 = 1, Local SGD initialized at 20 = O outpus T, such that,
2² B
22
B
d²
2 H²R²
B
E
| x* 211 S
In?
+ 2
+
In?
12
MRM
Remark 4. As we will see in Appendix functions, we derive a slightly worse convergence rate which contains all the terms in the above upper bound upto constant factors.
L33
while analysing Local SGD for third-order smooth
Proof. We will first simplify the upper bound by noting that 1-(1-9H)* x 1-(1-nu) is non-increasing in K, as
was proved in Lemma 5
HHH K + 9HK
quk (1 (1 -11
(1 qu)k
1HKK
1 1 (1 H1H
$ (1 m/) tuk
1 (1 m/)KK
1HK
1 - (1 7)H)
$ (1 mu) K + nuk-
1- (1 m//1)
n
= (1 mnn + nHK
Now, assume that 2x In
B² < K R for target accuracy so that we can pick 1) uKn
In
B²
2H < 3. For this choice of 1) the above upper bound reduces to,
B I/(K)) In
1100 - Tool12 S
R
K In
B²
1- (1
B
R
TT
B²
1
In
1+
uR
E
x lu n2
6
Now further assuming
In
B²
we can upper
In
n1
by 1 which implies,
2
36Tk
B2
xx"
Jo 112
In
μR
Let us also upper bound the rate of convergence to the fixed point for this choice of step-size and under these assumptions,
min (NTKKG. + BRKB + - (1- Kn) o²
E a - xoo [2]]
S (1 n1) n4)2k
2K
HM
2
22T2k2 In2
B2
o2
$ B
min
+ 2B2
RRB, ,12B²)
R2R22
HrMKR
12 In?
B²
o²
Se.
min
+ 2, x2
B2
R2
μ2MKR
The above term is under standard conditions of the order c, so ignore it. Cobining this with the fixed point discrepancy upper bound above proves the statement of the lemma.
B.3
On the Nature of Local SGD's Fixed Point for Quadratics
While in the general convex setting we can not write an explicit formula for the fixed point Toor we can characterize it as the mini-mum norm solution of certain leas-squares problem, where the geometry for each machine is defined by the matrices Cy-
31

---

Proposition 2 (Fixed Point for Convex Quadratics), Assume we have problem instance satisfying
Assumptions I to and with
ŋ H/H. Further define C. := -- (I ndm) C' = M m C. and c M EmElMn Cm for some F'm. E Snn for each m E (M]. If e + 0 and e im(C) = ker(C)+, then Local GD converges to the following solution in the limit of R 00,
Jo arg min
||=|| s.t. x
min WERd
1
ΣE
|
Fim C....
M
mEIM]
on the other hand # 0 and & im(C),, the the iterates do not converge, but if we define the sequence yR = C. then
lim yR R-000
Σ iE(l)
Enaue e lim (1 -1- x=)
R-00
where C Eiely Aaaeey is the eigen-value decomposition of C for orthonormal vectors (UI...., v1.. 0, the iterates of Local-GD do not move from Tog = 0.
Remark 5. When the objectives on each machine are strongly convex, then we always have im(C)= = Rd. In general when im(C) = Rd we can guarantee convergence to fixed point. An {0}. which guarantees that ker(C)) = {0} and hence im(C'= = Rdd We prove this last condition in Lemma 8 The condition Om (m)) {0} is equivalent to the average Hessian A being positive definite, i.e., A > O, or the global objective being strongly convex. This condition ensures that local curvature from different clients collectively constrains all directions and the machines are no simultaneously blind to some direction.
even weaker sufficient condition is assume that ( ker(kn))
Proof. We recall that even in the convex setting (i.e., with μ 0) we can write the following for the Local SGD iterate FR the noise-less setting with 3 = 1 and initialization Zo O,
1 M
Σ
(u (u-nAm) K (ØR-1 Imm) +mm)
IR
mE[M]
Σ (I- Am)) IR-I+
1
Σ (I- (I-(I-nAm)* x
M
M mE(M)
mE(M)
(I C)- +
Σ Cm
M
ME[M]
R-1 (z)=0)
Cu-Crye
j=0
Now let assume an orthonormal basis for the span of given by {e1...., mn where S This allows us to write,
C
Σ Naaeyy
where A 11- as our step-size is 17 1/H. . Let us extend this an orthonormal basis for the entire vector space IRd as {v1...., 1411..... ma that U1415 Va E ker(C)) This also implies for j E Z>o.
(1 (1-CY= =
Σ (1 --)o) +
Σ
KE(9
Σ (1-A))
SEll
1e[++1.d
Now will inspect how FR evolves in each direction, i [d].
32

---

First let us consider i E [1]
T 0 2
1/ (1 cyc,
T
1=0
R-1
Σ
(1 - Mu
1=0
Ao)
it
us
A
No matter how we pick 7,, K, this would converge as + oo, some quantity proportional to of"e Now let us consider E 1,,1
n
0.
RR
Σ
of
-
cye.
1=0
n-1
Σ
1s c
j=0
Roy
Notably, this does converge unless v/ O.
In particular, the iterates of local GD converge iff c! c 0 for all E [1+ 1, d.. Or in other words, E im( C*) = ker( L First let us assume, this is true, then we can conclude that the local GD iterates only evolve in the sub-space iC(C). Where do they converge? Solving the fixed-point
equation in the limit of large R gives us,
Too = (1-C)ay Too +c,
+ Cxx =c
Summarizing the two key findings so far we get that assuming e E im(C), Crx = e and toe & ker(C). This is equivalent saying that Joo is the minimum norm solution of the linear system Cr c. In other words,
Joo arg
min |||||
x s.L Ca=e
Further, note that using the least square formulation we can write the solutions of the linear system Cr C as,
min
M
mE[M]
This implies that Too (when it exists) is the solution of the following optimization problem,
min ||1|2
s.t. x min ZERd M
Σ |x- x" 112
mE[M
In the case, that e & im(A), there exists i E + 1, d] such that v/ c * The iterates will explode in this direction, but still notably, the sequence Că does converge, because
lim Cān = lim R
Amaey IR
R
(E(T]
lim R-+00
Σ
Vaue c (1 - (1 ->i)
[E(1]
No matter how we pick K this limit exists.
33

---

Lemma 8. Let Ai..... Am E Bdxd be symmetric positive semidefinite matrices, and let 1/H > ? > 0 and K N. Define
In==I-[[-AAn) C
1 M
Σ Cm
Suppose the kernel intersection is trivial:
ker((A (Am) (0}
m=1
Assume further that 1) < 1/Amax(Am) for all m (where Amm) S H denotes the largest eigenvalue of Am-
Then:
1. For each m, ker(Cm) = (.m))
2. The matrix C is full rank: im(C) = Rd i.., ker(C) [0]}.
Proof. Part (1): Since Am 2 its eigenvalues lie in [0, Amax (Am)). Then n.mm has eigenvalues
in [ mmaxx (Am), 1] C (0, 1], so:
K
Cm = I -m
( (-nAm)
==1
matrix polynomial in Am. Due to the polynomial structure it is easy to see that,
ker(Cm) 2 ker(Am)
To see the other side note, we will prove the contrapositive. Suppose that v & ker(Am), but E ker(C.)), then
Unu= (1 7m K
+ ||l||2 = [|(1 - 1m "0ll2 < |101|2
which is contradition. Thus ker(Am) implies that, & ker(Cm)) or in other words, ker(Cm) S kee((A Am))
This proves the first part of the statement that kcr(Anm) kcr(Cm)
Part (2): Now suppose for contradiction that Cv = for some v + O. Then:
M
1 M
C=v=0
(Cv.u) =
Σ
() =0
M
m=11
m=1
Since each On 2 0, it must be that (Cm v) Cm v 0 + ker(Cm) ker(Am) for all
m. So:
ker ker (Am) {0}
m=1
contradicting v # Hence ker (C) {0), and since C is symmetric, im(C) R.d
B.4 Implicit Regularization due to Local SGD
Several works have tried to understand the effectiveness Local-SGD from a different perspective, ie., by arguing that the solution obtained by Local-SGD is somehow better. In other words, these works have tried to characterize the implicit regularization of using local update steps. On such notable work is due to Gu et al. (59).
For convex quadratic problems, fixed-point perspective can also be used to understand the implicit regularization of Local SGD. Specifically, recall that under the assumption we discussed in
34

---

Curvature and Fixed Points: Local SGD vs Synchronized SGD
1.0
0.5
-0.5
well-conditinned
outlier
-1.0
K=
K=
K=10
K= 50
K=100
X1
Figure 3: The effect of having an outlier with sharp curvature on Local SGD's fixed point with progressively higher local update steps.
the previous sub-section, i.e., OME[M] ker(Am) = {0} we can also characterize the fixed-point of synchronized SGD as follows,
SGD 2 oc
arg min ||0||
s.t. I E
min
Σ
||
x 122......
ZER
M
mE[Md]
Thus the main difference with respect to Local SGD with K machine defined by Am as opposed to Om of Local-SGD,
different geometry on each
I. ICS arg min 00
||ا|||
min #ER
Σ mE(MM
||x
x. Ile...
M
One natural question is: under what conditions is the geometry endowed by Local-SGD better?
When 17 is "large enough," then for larger K, the matrix polynomial C.. I (I nA K increasingly flattens the influence of high-curvature (i.e., high-eigenvalue) directions in Am In other words, Local SGD implicitly applies spectral filter that downweights directions where the local objective is sharply curved. This has a regularization effect: machines with highly ill-conditioned losses extremely sharp eurvature (possibly due overfitting, poor conditioning, adversarial data) contribute less those sensitive directions. Instead, Local SGD emphasizes agreement in directions where curvature more moderate or shared across machines.
As result, the fixed point x L.SDD avoids overreacting to any single client's 's extreme curvature and instead biases the solution toward directions of consensus and smoothness. In this sense, Local SGD can be interpreted as interpolating between machine-specifi. optimization (via A..) and more uniform averaging of preferences (via Cm), particularly in settings with heterogeneous curvature. This implicit regularization may lead to better generalization in practice, especially when the global objective inherits pathological structure from just few problematic machines.
In Figure 3 we simulate the effect of having an outlier with sharp curvature, showing how progres- sively more local update steps regularize the geometry.
35

---

B.5 Extension to Non-quadraties?
The biggest issue with extending the above analysis to non-quadratic, is that it becomes hard even write the expression for the fixed point in closed form. As we will see in Appendix | it is much easier to use the usual consensus error based analysis in these settings.
C Proof of the Lower Bound in Theorem I
To prove Theorem I the main result need is Lemma 10 which we then combine with the lower bound due to Glasgow et al. (23]. Notably, Lemma i0 is an improvement of the lower bound due to Patel et al. and like them we also borrow the folklore Lemma 9 about gradient descent.
We first state the following standard Lemma which the context of Local-SGD was previously also used by Patel et al. 225
Lemma 9. There exists F(x) a convex quadratic function for x E IR² satisfying which is H H-smooth, u-sttonnly convex with k = 12R, and a bounded optima x² with ||=" 12 S B such that & the R
gradient descent iterate initialized at zero and for any step size 1 > 0, F( F(xx)* N HB²
SR
Proof. Let be the Hessian of F. Observe that we have F(x) F(x*) {x - )²)² A(x - x*).
Let 2n and U2 be the cigenvectors of norm 1 of A with the greatest and least cigenvalues, respectively,
Assume x² == B 2 which ensures ||=* ll2 = B. Then, solving for the GD iterates in closed form, we have
ER- x² = IR-1 - x² - 11 (zn-1 -x)
(T A) (0R-1 (8")1-x"))
=() (aial + 12 nauno (omnnn T) R (Io (x)-
((1 n)H)uu + (1 muu) (00 =x))
= ((1 - -n " uuu + - m/) "V222 (-x*)
V2 B (1 - (1-) R v1
B (1 1) k
12
V2
where in (a) we ue the eigenvalue decomposition of A = Hanns + poaea and the fact that for
orthonormal vectors U1, U2 we have l = Vn + vzul. Observe that n 2 H. then the iterates explode and we have F( 2 F(xa) 2 Ω (HB*).
1 S 3 then using the fact that ω: 2 6, we have H
B
3
R
T
B
F(ZR) - F(x*) (a)
1
02
02
2
V2
K
V2
B²
2R
1/2
Av2
K
B2
3
H
4
HB2
6R
(6)
4R
K
where in (a) we lower bound by the function sub-optimality only in the second component corre- sponding to Dy; and in (b) we assume k > 3 and Bernoulli's incquality. Finally using λ = 12R we get the lower bound HB²
S.R. The result follows.
Note that the following proof actually works for Local SGD with both an inner step-size n) and an outer step-size 3. In the main paper only analysed and discussed Local SGD with a single
36

---

step-size, i.e,, we set =. This makes the lower bound below stronger and not weaker, as it works for more general algorithm. To make the notation easier to accomodate two step-sizes, we use the following.
700 FT-1
mm [M] Vm [M]. k (0, -
rx++ Tr.k
(Fr,ki 27,k):
2r, Dm
B M
Ty 1 +
Σ (.,,,
2r-1)
ME[M]
Lemma 10. There exists convex quadratic function for R satisfying Assumptions 7 and
such the Local SGD iterate nn when initialized at zero and for any choice of step-sizes 7),
must have F(TR) F(x*) Ω
TB
Proof. We consider the quadratic functions defined by the following two Hessians for S H,
A
0
AA
0
A1
and
A2
H
H
where we for some a E (0, 1),
Å 1
0 and
a²
avI- a
Å. vo (a, - a
aav
a²
Note about the spectrum of A,
Spec -AI) 10,
Similarly for A2 we note that,
det [A A12 =0,
+ (A a--a3) a² - 1+ a² a - a2))
+ x² - +1 (d²+1-o²)>>- 0=
A E (0. 1}
which implies that also for,
Spec (A2) = {0, T, H
Thus objectives defined by both these Hessians A₁ and Ag are H H-soooth. Further, we can notice the following about the difference between these Hessians,
Spec (A1 A2) = T Spee
(A - Ag) Ut0}
41-Ay
([ -avI-a ạ -(1 a²)
1- -av1 a²
r Spec
U10}
{ (-rVi - -0,11 a² U{0)
which implies that,
- 12ll2= ST.
Now we shall split the objectives on each machine follows, For even m, let
(x) = A1 x²)
For odd m, let
F. (z) = ] (x- - x A' x²)
37

---

Note that the iterates after K local updates leading up to communication round on machine m gives,
K = (I - -)A 1y-1
where we denote 37 = 7.d x² for all l: E [0, K] and C., = Jr x² for all r E [0, R. For odd machines it is straightforward that,
(1 77T) 0
(--0)-11*)) -AI
12
(I - (1)
0 1
0
0 0
(1
nH)
K
0
(1 nH
For even machines, the above can also be noted using vu. as the unit vector orthogonal to o,
(I - n222
1/2 1
A2
0
[12 nroo")
"
0
1 nH
0
(1 ml1)*
(v0 FuLu N)TU??)
0
0
(1 (1-bH) k
(1 m7)
ovT
+ Faueh
0
(a)
0
(1 n
12 vv
+ (1
TTT vv
0
(1 - nH)
12 (1-1---)*
A
0
(1 - n1
where in (a) we note that ((1 - uu) + + 2 = (1 - vo + V. This implies for the
1- for all m E [M].
local updates with 7j =
12 ūjt Am
(12- (12 -r 8 [1 2]
0
(1-
(1 (1-1H))= K Σイ- [3]
Now, using the calculations so far, we can write the updates between two communication rounds as,
B
8, = xr
Σ
5r-1)
M
ME(M]
3
TiT (( mod mod())
2,-1
Σ
M
(1
nH ) )
[M]
(12 Ai 2; 2 1
(1 - 3 (1 - (1 - (-HHH)) 1
The above calculation implies that the third coordinate evolves as synchronized gradient descent with K iterations, while the first two coordinates evolve with step size 3ij and a hessian matrix of A[1 2; 2] (i.e., the top-left 2 x block of A the average Hessian) for R iterations Now note that A(1 : 2; 2] = 7(1 A) + taAz and
{
1/2 (M 1)/2M
M is even, otherwise.
Now, all we need to do is apply Lemma to the first two dimensions. To be able to do need to be able to choose a condition number A Q(R) for A[1 2; 2). in particular 2(x:). Let us first consider the case with even machines, i.c., when 1/2. Then note that,
A + A 2 avi1 a²
o+
avI a
Al1 2;1 : 2]
1 a
We don't need to restrict the step-sizes because Lemma
9 works for any step-size.
38

---

which implies for the spectrum of the matrix,
Spec(A[1 2, 2|)
T
{1 a, 1
2
which in turn guarantees that,
1 +
(A[1 :
which can indeed be made S2(R) by picking an close enough to 1. Now let us look at the case when M is odd and
M+1
2M
M - + (M (M + 1)ayT-a² a² A : :1::::121 2M (M + 1)avi-
(M + (1-a²)
which using simple calculations as before implies for the spectrum of the matrix,
Spec (A(1 :2) 2M which implies that,
{ M v1 a² M2d M V1 +2+ M2a
(A[1: ::11: M
M
V-VI-aa M
which can which can indeed made Q2 (R) by picking an close enough to Finally this allows us to use Lemma which implies that the progress on the first two coordinates is lower bounded by It for any choice of hyperparameters. To make this more explicit, note the following for any model 2,
rB²
F(6) F(x*)
x Ax (Ax*)²x
x" Az (x*)²AAx
x|1 2 A(1 22 2/0(1 2] (x1[1: 2)) A(1 2; :]1[1]
H -33] Hx 13|13]
+ 2
x11 ATTA A[1: 2|-[1 2] (11 2)) A(1 2;1: :]=[]] :2]
F12 F1.2(=*)
where we define a different quadratic objective Fi.2 : R² + R2 using the top left two-dimensional
block of the Hessian A. This implies that we can lower bound the sub-optimality F(xR) F(x*) by
rB² which finishes the proof of the lemma.
L
R
Now conclude the proof, first note the following tight lower bound for the homogeneous setting due to Glasgow et al. [23] for the local SGD iterate FR. which we recall also uses a quadratic hard instance satisfying Assumptions too
HB
aB
OB VKR''
})
F(RR) - F(x*)
+ min
KR
VMKR
K1/3R2/3
also recall the heterogeneous lower bound due to Glasgow et instance satisfying Assumptions [o and apply it on 7-smooth problems (instead of H -smooohh in their construction, as they do not decouple T and H in their construction).
23 using quadratic hard
2/3 B4/3
F(TR) - F(x*) = Ω min TO?
R2/3
To translate their bound to our setting we also set Ç. (in their lower bound, not to be confused with our Assumption 4) as Th to account the different definitions first-order heterogeneity in their paper and ours (c.f., Assumption 5). Combining Lemma 10 with the above two lower bounds from Glasgow al. (3 by placing different hard instances on disjoint co-ordinates and noting the independent evolution in the gradient descent iterates completes the proof of Theorem
39

---

D Notation and Outline of the Upper Bounds' Proofs
Recall that the algorithm we would like to analyze is local SGD in the intermittent communication setting. In particular, assume the algorithm runs over R E N communication rounds, with K E N local update steps between each communication round and total T = K time steps. We also assume we have M N machiness/Clientssaggnns with each agent m [M] sampling from their data distribution Dm E (Z)). These samples from the data distribution are used to calculate the stochastic gradients for each machine for each time step. In particular, time [0, I' agent m calculated 9:" := V fz""; 2(") where 2!"h ~ Dm- We recall the local SGD updates that use these stochastic gradients for all [0, and E [M].
m
"99 T2
++1 1 mod K + 0
#+1
1
Σ REIM
(x
if ++1 mod K = 0
M
We will also define the "ghost iterate" for all times E [0, which may or may not be physically computed depending the time
Σ M
34
M
Considering these iterations, we will define several quantities in the analyses throughout the appendix. We include this notation in Table 2 for ease of reference. With the above notation in mind, our analysis aims provide upper bounds for A(K R) and E(KR) R) as a function of problem-dependent parameters that appear in all our assumptions. To do this:
We will first state some technical lemmas in Appendix E
Then in Appendix F state recursions
communication rounds for the sequences
A(-). B()). and E in terms the consensus error sequences C(-) and D(-). These recursions highlight the need to control the consensus eπro sequences C(-) and D(-).
Appendix G we we first control the consensus error by relying on the strongest Assumption In the following sections, we relax this need for the ( asssmption and do more fine-grained analysis the consensus error.
In Appendix H we provide more fine-grained recursions for C(-) and D(-), which depend on A(-) and B-)), i.e., they leads to coupled recursions. The main technical contribution of this paper is providing these coupled recursions and using them to provide new upper bounds.
Appendix [ Ihen brings together the results from Appendix F and Appendix H and provides convergence guarantees in terms of the step size n)- Then we tune the step-size and obtain all the upper bounds from the main body of the paper.
E
Useful Technical Lemmas
E.1 Useful Facts about Stochastic Noise
Throughout this sub-section, we will assume Assumption 2 Recall the following standard lemmas about the stochastic gradient noise,
Lemma 11 (Averaged Stochastic Noise Second Moment), For t e [0, 1] we have,
o² M
|k:
*We note that we are less explicit about randomness the proof these recursions and following results. In particular, we often omit repetitive steps using the tower rule and conditional expectations to shorten the already complex proofs. We urge the reader to familiarize themselves with applying these techniques by first reading the proof of Lemma 20
40

---

Symbol
Definition
A(O)
|| - x²1
Vl [0,T]
B())
E
|1 x² 112]
Al [0.T]
C(I)
M Em.e((n) B ||:77 x; [
VI [0,
((t)
M Emme(M B ||= x 1b
Vte [0,
E(I)
E [[F(a,)] - mRn F(x*), V1 [0,
6(L)
1-7 mod (K), V (0.
ge
= 2ith Dm AIE [0, m E (M]
<i
Vmm(T?")
2ोth Dm, ALE [0,T], E [M]
MI Emeran Ii, A4 E [0,7]
gt
gt
&
&. = M EmEiM Em V E [0,7]
H ((=8) Jm
1 M
V E [1, 7]
Table 2: Summary of the notation used in the appendix. In the definition of the filtration He, abuse the notation (c.f., Assumption 2 and use oXX) to denote the sigma algebra defined by the set of random variables X.
Proof. Recall that at any time step E |0, T 1).
1
E
E
E
M
ME(M]
(Tower rule)
E
E
1
Σ mE(M]
(9."
Vf(="'
mh m 22
174
M
E
Σ
E
Vf 11 H4
M
mE[M]
d2
(Assumption B
02
M
M
M
41

---

where (a) uses the fact that for all m * n, 2t 1 27 H,,, i.e., ,t....,, on the history H4.
E, are independent conditioned
We can also give the following stronger bound on the fourth moment of the stochastic noise. Lemma 12 (Averaged Stochastic Noise Fourth Moment). For t E [0, T' 1] we have,
30
E
[15:111]] S
M
Proof. Recall that at any time step E [0, T - 1).
E
=
E
Σ
St"
M
me
2
27
E
mm
E
1
Σ
(St -
M
mE(M)
m.ne(M]
Σ
E
[(5b (tr) (
M
Lm,,no0[MM [M]
(Tower Rule)
Σ
E E [CE) (nr) (2) [74]]
M4
[m
Recall that for all m + n,, 25" z7 (H,, i.e., ,i...., eM are independent conditioned the history H4. In the above sum, the only non-zero terms are the ones where either = m the set {l. m, n, o) has two distinct values, each repeated twice. There are M terms of the first kind, and 3M (M - 1) terms of the second kind (first choose two colours out of M, then choose two indices of {1, m, n, of which divides into two groups, i.e., total M(M-1)
o, or where
4!
Using this we get,
| l2
Σ
|1st
[e]
+3
Σ L
E [
|I
M
ME(M]
1
(Mo' + 3M - (1)*)
4
3
M
which proves the lemma
Lemma 13 (Averaged Stochastic Noise Third Moment). Fort E [0, we have,
3
[1
M3/2
Proof. This result follows from simply noting the previous lemmas, and the fact that,
E
|1
E
[
Cauchy Shwartz
[1EE
3
Lemmass Li
M
M2
3
<
33/2
which proves the lemma.
42

---

We can also note the following about the difference of the stochastic noise in two machines.
T - 1] and m + n E [M] we have, Lemma 14 (Second Moment of Difference). For E [0,T
E [IKT
[| 20²
Proof.
Note the following for m # [M], and for t [0, - 1]
E [1sT - 1: = E ||ST
||: 2 2 ( -5")
(a). (Tower Ruks) E
|| | + E
||5T 2
2B [E ks?" [H4], , [e? HH))
(AAssumpttion (2. (h) 20²²
where (a) we used that 5!"h 1. HH: and in (b) we used that TE [cT = [E = 0. This proves the lemma.
Lemma 15 (Fourth Moment of Difference). For 1 E [0,T 1] and for m + n E [M]] we have,
E [IST - -- s 80a
Proof. Note the following for m + [M]. and for / E [0, - 1]
E
||c!"
= E
[|<T" 1 + l|< 12
2 ".5"".77)
(6)
E
[1<T" [1
+ EE
[|<77|] 2
+ 4E
[1ET" -
2E
[1177
[2]
E
|| [2]
2E
|ist" 2 em
T ElerT
21
[|s7
4T
E
|1s""
+ E
+ 6E
[15?"
12
E
|1 12
(Assumption
g
Sa
where in (a) we used that &!"h 1 57" [He along with tower rule several times like in previous lemmas. This finishes the proof.
E.2 Other Analytical Lemmas
We will also use the following inequality several times, essentially a variant of the A.M.-G.M. inequality.
Lemma 16. For any a, b E R and 7 > O we have,
(a (++b 6)² < 1 + 7
a= - (1+
3
(a (a+b)) $
1+ 7)
at + (1 + 7))
Proof. Note the following.
(a b)2 = 0² + 12 + 2ab
(1²) (v7b)
0² 12 +2
< (.MM....M. Incquality) a² + 12 + a² + +
?
< 1 1
11 a² +
a (1+ 62
43

---

which proves the first statement of the lemma. To get the second statement we will just apply the first statement twice as follows,
| 1 ) a² + (1+
(a 1a+ v
1 + _
1 + ) d²) +1++)
3
a (1 + 7)
which proves the second statement of the lemma. Lemma 17. For any a, b, c R we have,
(a ba+b+ c)) S 3a² + 3b² 3c²
(a + b c)* c)* 27a 276 276
Proof. We note the following.
(a+b+c)² = a² + b² + 2² + 2ab + 2bc + 2ca
< <.A.M.GG.MM. incquality) a² b² e² + (a2 bb) -
3(a² + 62 + c²)
which proves the first statement. For the second statement using the first statement note the following.
(a+b+ b)+++c** < (3a² + 36² + 3c²)²²
(3a² 2 + (3b²) 2 + (3c²)²
27a + 276* + 27c
which proves the lemma.
Lemma 18. Let x E (0, and K then we have
K
K
Σ
x
1
- x)²
i=1
Proof. Note the following.
K-1
K-1
Σ
<
K
ir
i=1
K-1
KV 7
Σ
1 K
KV
1-
Kk
Kr K- + (K
+(K-- -1)x
K
+ Kx
(1 x1-
1 σkK
x x K+1
K x - -ok + +(K - 1)x
K
(1 x))2
(1-x)-
1 (K + 1)x + Kv
K
x²
K
< (1 2
where in the last inequality we just note that (K + 1)ak KrK+1 S This proves the lemma
D
44

---

Lemma 19. Let A and B be two positive-sems definite matrices. We have:
k A B
A B)B
==
Proof. we prove by induction. For h = we have:
B = Σ
(A (A- = A
1=0
for &- + we have:
A - B++l AA BB* = AA* AB + AB*
BB* A(A* B*) (A BYB
for the first term the above equality we have:
k- (A--)BB B)B
A(A*
B* =
A (A-BB- Σ
j=0
==
By adding the second term we have:
k-1
k Σ
A k++ Bk+1 Σ
(A- B)BB + (A B*
A (A B)B
j=0
which completes the proof.
Deriving Round-wise Recursions for Errors
In this section, we derive several recursions that prove usefuu later in the analysis and form the core of our proof. An informed reader would note that the ideas and some cases the entire recursions occur in previous works 25
20 18 15].
F1 Second Moment of the Error in Iterates
The main result of this sub-section is the following result, which relates A(-) to C(-) and D(-). Lemma 20. Assume have a problem instance satisfying Assumptions 7 and 6
Then assuming
7) < H we have for all t E [0, 1].
120²
A(t) + ? A(t +
min
+ M
This also implies that for all E [R]]
A(Kr) (1 mn)* A(K(r - (1 (1- (1_1/)**) 1102
H.M
Kr-1
Σ (1 (1-mu)Kr-1-) min ()) ( 20)
j=K(r-1)
Note that the above lemma implies that if Q and T are both zero -io--ee. we have quadratic problem with no sedond-order heterogeneity- thenn will achieve extreme communication efficiency, matching the convergence rate of mini-batch SGD, with KR communication rounds. As such, the trade-off between the red and blue upper bounds is that the former allows exploit higher-order assumptions, but we need to be able to bound the fourth moment of the consensus error. In contrast, the latter only requires bound the second moment of the consensus error.
Remark 6.
Proof. We note the following about the progress made in single iteration for / E [0,T - 1].
A(l + 1) = E | - x 211
45

---

Towwer rule)
E
It x
Σ mE(M]
Dt
He
22
(a)
E
It
17
(x."
+ n²²E
M
M
ME(M]
[M]]
7700
Lemmm
11
E
It f)(F(x)) - x²' +1VF(())
Σ VF
+
M
M
Lermmn 16.00 (b)
1 +
op
(1 m/n EE' ||00 - x x=1
1 m/
+
1
m/
1
1
FV (2:4) V Fm (x
+ 12a2
M
M
Tra ME [[M]
27
=11 11-1pp mp/t) E |1:02 x= 112
+
1 Σ (V
V (x
+
1202
M
mE(M]
<0 (1 mp2)
|1
2²
211
+ 7
E
1
Σ ME(M]
FFF" - x²")
n²a0
1
M
M
where in (a) we used the fact that ......, Et E mfH i.e., they are measurable""nnn--rddom under H4 and zero-mean, which allows to ignore the cross-terms while squaring; in (b) we use the fact that 7) < 1/H which implies that A I- F()) = (1 - nH)) Ia and also that (1 (1- (1-7/4 > O; and in (c) note that due to the mean-value theorem there exists some 27th which is convex combination of wtth and dt- From this point, we can proceed in two different ways. First, to get the blue upper
bound we just smoothness follows,
A(t +1 1)
(1 mH/ E ||0, x² x'1]]]
E
1
Σ
V
(1
(z+
x
+
1202
1
M
M
mE[M]
(Jensen's 's Inequality)
(1 - n/41
|1:0e
+
Σ
V2 Fm (2
(x) - xx²" ||2
M
mE(M]
17202
+ M
< (1 mT(c) E |100-- -x=111 + nH2
17002
Σ E
Iz
rell
M
M
mE[M]
+ nHH
17 1700 +
(Jensen's is Incquality) (1 - m714 IE |1:c0 fate-xx"ll ==1
M
Σ
E
x
a
1
M
M
= -1- A(1) + 7/12 C(1)+ +
12202 M
which proves one part the lemma. To get the red upper bound, we will use second-order hetero- geneity and third-order smoothness as follows,
A(t + 1)
46

---

S (1 (ali E ||:0e x=13 x0]]]] + _
E
1
Σ
Fm (xz )²
1f00
M
M
mc(M]
(1
my1i EE
[|are x=1 [
1 Σ (V2Fm - Fm)s)) + FmF(( F²F(2)) (xr x²""
E
p
M
mE[M]
T²²0
M
(ensen's 's Incquality). (Lemma 16 (1 (1-npp mp) E ||0| x=' 113]
2m E
Fm (8TT)) V² Fm
(2 (2iz)) (xtx - x=2" 112]
μM
[M]
2n
E (1( 42 Fm (2ta) (xxa - xr." >|2]
1P02
+ M
μ.M
ME|M [
2n12
Assumption 1 and
- (1-n E |1108-
- x² [1]]]
+
Σ
E
22112 11a0a - 22"113
WM
[M]
+ 2mp 2
E 100 xx" 11] [2] + 11202
MM me[ad]
M
+ 2n12
2n7²2
<(1)
(1
nu)
E
||0 -.- x= ==1]]]
Σ
E
||0
- 24 211 12
+
E 11 - 22'1
MM
PM mE(M]
mEIM]
17²02
M
20/Q2
(Jnsse''s 's Incquality)
(1-) E |1:ra x² 11]]
+
Σ
E
- xx" 11
uM
m
2
n702
Σ E
[1aT - =x7" 112]
2M
M
m.nE(M]
211 D(t)
C())
n7²02
= (1- A(t) +
+
1
11
M
where in (a) we use that ||-; mell2 S ||--7 za llz for all m E [M]. This proves the second part of the upper bound, thus finishing the proof for the first statement of the lemma. Note that for E [R] we can re-write this result as follows,
A(Kr) < (1 - mp) A(Kr-1K) 1) 1)
1702
+ " min D(Kr - -)) 11) + M
μ
< (1 nu)* K A(K(r-11)
+ 7 Kr-1
1702
Σ (1- mu) kr- min (22" +
nM
())
where in the second inequality we just unrolled the recursion till the time-step of the previous communication. This finishes the proof of the lemma.
would also be helpful to state the following lemma, which talks about the convergence on individual machines between two communication rounds.
47

---

Lemma 21 (Single Machine SGD Second Moment). For any machine m E [M],fort E T) and for k 2 0 we have the following for 1s H
800+K x²' [ (1 2 ||000))
110²
E
=ml12]
1
The above lemma follows the usual strongly convex analysis of SGD (see, for instance, [60]), since we can rely on that between two communication rounds.
F.2 Fourth Moment of the Error in Iterates
Lemma 22. Assume have a problem instance satisfying Assumptions 7 and 6
Then assuming
1) < H we have for all t E [0, 1).
n
16
0n mp)
B(t +(++1) B(t)
D(t)+
+
A(t)
43
uM
M
167
9n
C(1)
μM
M
We can also get the following simpler upper bound,
+ nH
μ³ D(t) on mp)
A(t) + 22
91
Bit + 1)
C(t) + M
M
nM
This also implies that for r E [R] we have.
nH + 16 0²Q²
Kr-1
B(Kr) S (1 - m11 B(K(r - 1))
(1 (1-
j=K(r-1)
8n
Kr-1
(1 mm) Kr A(j) 16120272
Kr-1
(1 (p))k(l--iC())
+ M
HMM
j=
j=K(r-1)
91
p.2
Proof. Fort [0, T 1] we note the following.
[141 - x²
E
E1
7
Σ
(=m(x)))++
n
Σ
St
M
M
mE[M]]
mE[M]
E
Ft
Σ (IM(
+
Σ
St
M
M
M
M
2
1)1
+ 2m
04 x²
Σ
V
(a
Σ
M
M
mE[M]
ME(M]
E
xx
Σ (Tm
+
Σ ET MEIM]
M
M
mE[ad]
27
((0 xx-
+ E
"
Σ (I
Σ ET
M
M
mc[M]
ME[M]
48

---

2n
It
Σ
(
Σ
M
mE [
m mE(M]
+ 4n
Et x²
7 Σ (x
It xx
7 Σ
(m
M
M
mE[M]
MEIM
E
cm
M
mE
mE(M)
It
7
Σ
(a
1
cm
M
M
MEIM]
ME(M]
(Cauchy Shwartz)
E
2t.
x¹
7
Σ
V (x.)
+
Tn²BB
1
M
M mc(ar]
mE(M]
2
Σ
V (xi"))
1
St
M
M
mE[M]
ME(M]
+ +2n
Ft. xx
V (x
Σ
5T
M
M
M
ME[M]
+ 4r7
It x²
77
Σ
M
M
mE(M] [M]]
mE [A]]
Tower Rule)
E
F4
7
Σ
(x
1) AE
St
M
M
mEIM]
mE
[d]]
61) 2
E
24
7
Σ
V (a
1
cm
He
M
M
mE[M]
me [M]]
+ 2
E
x²
71 M
Σ
V Fm
1
H+
M
mE(M]
mc(M]
(a)
F1 xxa
77
Σ
V
F (xTT)
+ +1/
Σ cm ME(M]
M
M
mE(M)
+ 2
F1 x
1 M
Σ
Fx
1
m
Hl
M
ME(M]
mE(M]]
2
3
+ 4m) 2E
Ft x=
Σ
VF
(2
1
Σ
14
M
M
MEIM
mE(ad]
49

---

3n ot M
Lemmas
E
Ft
Σ
(xt"
M
MEIM
617 2 0²
E
Σ (=m()
M
M
ME(M]
4/331"00
E
F4
x
7
Σ
V
(3:
M3/2
M
mc[M]
E
T1
Σ VFm(
+
M
M
mE(M]]
617 2 0²
17
Σ
T1 x
M
ME(M]
27
311404
1/022 M
+ 4
E
84 x
7
Σ mE(M)
V
Vm (2
M2
M
9ry 91 M
(A. M.-.M.. Inoquality) E.
Ft
V
M
mE(M]
81/² 0²
E
x²
Σ
VFm(xT))
M
M
m
9r o
E
E1 x²
+
Σ MEIM
V (x
+
M
M2
23220 0
Et - x² NVF(()) n Σ Vm
M
M
mE(M]
(9)
(I 2 =( (oF())) 7
Σ mEIM
V (x
M
M
02
E
(T (2- (x+ 1=4-x") ( 17
Σ (=
M
M
ME(M]
11 emmmall (o)(
+
7/14
(1 - -1=)E) |1:0 - x111"]
1 - 7//4
+
A/AE
Σ (1+)) - V V (x
7//4
M
M
me M
50

---

811²0²
+ M
+ 1 - 17p1 1nn1
(1
2 11:0 - x= 12
27
01
(1 1+ 1 - m/
1 E (VFm( - V (n
M
m7
M
mE[M]
(Jensen's Incquality)
(I -1-Lrp n1)e ||00 - =11
9
[I( - (=m(aa)))
+ M
1 M
M
S17² 0² (1 nm)
+ O1 uM
|1:7 - x²11]] 1072=x112
E
Σ (VFm(r))) V (xt"")
M
M
mE(M]
nlf
81720² nu)
9njo
(Assumption]
(1 (1-11 B(I
D(1) +
A(I)
n1
M
M
S1y² 0² p.M
E
1
Σ
Fm
V2 (xxe) + (m 42 )((()) (xt xx{)
M
mEiM
+ n11a
811²0² mu))
911400
(Assumptions Tand (e) (1-nu)B()
D(1) +
A(1) +
n3
M
M
81y²02
2Q
27²
+
Σ
||0t
x. l12
+
Σ
E
| - x; 2;-11
J.
M
M
mE(N(]
m ME[M]
(1 - Bp) + nH
8n7 o1 1711))
A(1) + 9r7 04
(Jensen's Inequality)
D(1)=
133
M
M
01p²02
(2Q2D(1) + (2Q=D(()+2+2(1))
+ PM
= (1 14--m B(t) + (nET²
1679 o
D(t) + 811202 (1- mu1)
A(t) + 16np0272
+
C(t)
PM
M
μM
0n7t04
M
where in (a) we used the fact that vz x² 37 EmEM FFm(IT) E mfH in (b) we used the V E [[v]l]] in (c) we use mean value theorem to conclude that
Jensen's incquality IE []lvila] s
there exists some á. which is convex combination of xe and x* such that Fx(x,) = VF(**) + ) (It (²F(;t)
:::;; in (d) we apply mean value theorem to find a 27" which is convex combination
of xr and xtth such that V Fm (v.)) = (z,(""") (a7") + V² (2Tr) (5. -x""); : and in (e) we used the fact that | xellg- I | 2z l| This finishes the proof of the first statement of the lemma. By
letting t + Kr for some r E [R]. and unrolling till the previous communication round we get,
B(Kr)
$ (1 - Bu)) 1)+ nH 16020²222
D(Kr-11
43
HM
81720 (1 - -14) A(Kr - 1) + 1677 7
C(Kr- - 1)+ On
+
M
μM
M²
$ (11 BB(K)) 1)) + nH
1602
Kr-1
Σ
(1 - (1-11) (r
+
113
UM
j= (()-
51

---

02 Kr-1
Ky-1
91y'a*
Σ (1- j= j=((r-1)
(-rn))rrAAA + nM Σ (1-m))kr-1-22
+ M
j=K(r-1)
where in the last inequality for the last term we used that EKr1 -)jK(r-1)({ - m1)
S
1-(1-m0)* 1. This proves the second statement of the lemma.
would also be helpful to state the following lemma, which talks about the convergence on individual machines between two communication rounds.
Lemma 23 (Single Machine SGD Fourth Moment). For any machine m E [M] E TT, and for k 2 0 we have the following for n < #.
m ((t)+ x² =1]
S (1 --/ B 10v600=2iul1 =mull]] + 08)20²k(1 - =1 =|00) - x 12
111120a
112
We can also get the following simpler bound,
==11]]
16no
E
++
s (1-n)))
" || -2 2tn1l]] +
Proof.
For any machine m E [M] note the following for t 2 8(t),
E
1 c+1
- vim [
=
E
|:07 xmm VV (3: + n 12]
|0:T0 xn V (x 1| + 17 ||mm 12 + 2n (x] - zin - (x?"), cT²) ) 21
= E
< E
7/ Fm (z="") ||
+ 1) "B
||STT 12
+ 41
||00"
2/7 1/ Fm (x 11
E
|
+ 2,7"E
E
||
+ 4T
[|
=m 17 v Fm (3.""'
EE
||e." [1
+ 47E
||a2""
xm V/ mm (3x²7)
12 (x:"
1/ Fm Fm (r?"))² [ 0
(a)
E
||0:""
I'm Fm |1/2
+ +1700*
on || 2xn - V Fm (17" 112]
+ 4n7 00
"E [|x:"" - -x V/ Fm (- [12]]
(Jesse''s Inequulity)
E..
|>> - ttth v Fm
||aا - -m - VV Fm [ + +
(z/ )12
+ 4n 3 3
xm V m (x.²7 112
+ +1
-A..M.G.. Inequality) (AneuuiM.n
EF
||000"
+61 ||-70 xm - 1/ (x:"" )12
110d
+ 447
E |
2t, 1V (1 (12)))
+ +17001
2m
E
||a.711
17 V m (x.4)) ||
+ +3 + 8nj²0²E |1,77" - x; V
5th)
(1
||اا
x 11
+ 31/ 4 + 81 - nn)²1 ||02"" 2
00
52

---

Lemma
(1 nuy'D ||l77 =milll 3n
+ 887 0² 02 - mui? (1 mulr 20 E [| - 2/ [ + no2
[2]
= (1- - "1 |102"" - [1/] + 347² 0²
-1-n
811" - mm)
+ 2 211 - (hll) ( (()) [|00(1) - mml12
1
50 (1 - =mnaa11 ||:ي"² - x [b + 00)²02 - -114) ( [110300 - - [2 +
11 0a
||00000 - xin| =mn1 [=]
11
= (1 - (7l1 a(e++1 4(c+1-660)1B
+
122
+ 817202 0² Σ (1 - (t)))(1-)) - m))) 1010++1-600pp)
[10000) - xm [12]
j=o(1)
$ (1 - (ull 1((+1-6(0)1B
||=000]] - x =m [ا
11
+ 8 ||10000 - =im1?3] Σ (1 - n))))(+11111))))))))
+ 1²
5=)(1)
S - (1-1j) 4(2+1 -(t+)- ||0000) - xmm [t
11nja
+ +812002 (t + 1 - -(t)) (1 (1))(4+1-6(00))
x
=m|12
[12]
+
1.2
where in (a) we used the fact that E
[15T7 2
S E
||e
2
E
||E?"
2 and Assumption 2 in (b)
we used that ||سا"" - Fm - 2 ll
I (1
mu) -|= - x ll2 for < } in (c) we use that
" < #े S 1/2 which implies that 30 & 3n
We gave the above analysis for + > 5(1), thus
can be translated for > 0 as follows.
E
m M
-
Fm
S (1 - m/) t |10600 - [
111804 22
+ 8n/² 0² 0²k(1 - m/1) 2 [|0300) -
- 11
+
Since when k = 0, this is still valid upper bound, we have proven the first lemma statement. To get the simpler upper bound, we will complete the square, proceeding from the red term in the above analysis as follows,
E
m
- xmm 12]
+++
< (1 - -nn)=E ||0770 - smn [12
+ +37 337 oz + + - =1122 ||077" xmmll [12] ,
<Jensen's 's Inequulity
(1- 11-111 = ||a27" 2ttll
-16)' 0z + 81p2 =)11)² / B [107
2
< (1 nuu)
E
|للل - x [6]
+ 272002
Taking the square root of both sides, we get.
E |1077
(1 m/n
V E
||o - 27 11 + 4n)²0²
4no2
< (1 nn. (1))((+1--(01)
E 22(1)
+
53

---

Finally whole squaring and using Lemma 16 we get,
E ||
m/ +
(1
7714)
4(1+1-6(0))
(5())
Fmm
1- - 7711
+ 1+ 1 m7p1
16
tp
12²
4
16
$ (1 ()/))((+110))))))) (
|
Fmm
+
2
We proved this for 1 1+1 > 8(1), but clearly also holds when + 1 - 8(1), which implies that for
all k 2 0,
=01]]]
16n
E
2 +
x*
s (1 m/n " [|=000) - - =ml11
thus finishing the proof of the lemma.
F.3 Function Value Error
The main result of this sub-section comes from the work 25], which relates E(-) to C(+) and ( Lemma 24 (Section D.4, (251), Assume we have problem instance satisfying Assumptions 7 and Then assuming 1 1 we have for all t [0, 20, 1).
20 D(1) + M 87² C(1)
no²
F(t) S
11 2
E
2041 - x 111 +
Remark 7. The above result is known from the paper (25). and we do not claim any novelty here. Our contribution improving the bound on the second and fourth moment consensus error (C(L) and D()).. Later, we will put our improved bound in this lemma and provide tighter convergence guarantee for local SGD under the Ç assumption.
We will also recall the more straightforward recursion, which does not explicitly depend on Q. used several existing results, including the following due to Woodworth et al. 20
Lemma 25 (Lemma 7, (20). Assume have a problem instance satisfying Assumptions 7 and
Then assuming vi S 1OH we have for all E [0, T -111
E(I)= < 1
E [1041 - x" ==] + +2HC(() + 3no²
E
|10
xx
M
G Uniform Control over the Consensus Error and Analysis using Assumption 7
G.1 Upper Bound on Second Moment of Consensus Error
In this subsection, we re-state the upper bound on the second moment of consensus error from the work (20). We do not claim any novelty and include this lemma for completeness.
Lemma 26 (Lemma 8 from 20 ) For all 1 E [0, T] under Assumptions and with stepsize 1 we have, 2H
n S
C(t) s HK3 + 6Kopn²
(8)
Proof. Note the following about the second moment of the difference between the iterates on two machines m, E [M] when f > 5(t),
E
|
E
||://01
xz-1 - n9.h1 + ng 11
<
20 - VV (x + V F + 22 |
54

---

EE 1
+ 21/ 0²
( E - 2
+ 2110²
= E |1 -
V - (1
+ +n)20²
<
1 K 1
E [1( 17 Fm (c)) (x 2112
+ EK
V (x - V (x [/] + +21100²
1
(1 2 |1005-1
- - 1
112
+ +K H + 2n200²
K
K-1 1
1
E
|0 1 -
1 +
+
K
where in (a) we use the mean value theorem find between . and -;- such that V (x/"1)
Pmn (x
(x==1 x(-1). Unrolling the recursion for K steps givse us, FC)
E ||2T - z; 2f11]] s <6K2 + 6n2 Ko²
G.2 Upper Bound on Fourth Moment of Consensus Error
In this sub-section, we re-state the fourth moment upper bound on consensus error from the work 25 Here we do not claim any novelty and we include it for completeness.
Lemma 27 (Lemma 12 from 25)). For all t E [0, T) under Assumptions 2 and with stepsize 1 S 2H we have,
D(t) < 3840n K = 5
5920m -220
Proof. Note the following about the fourth moment of the difference between the iterates on two machines m. [M],
E
1
m
2zt [12]
E
b x²[11 105-1100 n19h + 1
1 -m + 27
E
|||071 - +|
E
2n (1 +
EE
|| - x 1) VV
T [|6T 1
2
- - 1
VF
211²E
| - - -
VV (1
-
+ 2
2 - (1 - ||<T| - 1-
55

---

4n
(x
x - 7fV (x + 77 1))
E
cm
51-11
(CSS. Incquality, Assumption
E || - 2
V
Fr (x
800'11" 17¹
61j |----11
- 1/
E
2
+ 4n E 1==-111 x/-1 - 1/ (r
E
6-
(a)
In order to bound the term E
[|5- - -2 ||ا]
we use Cauchy-Schward Inequality:
E 6 - 12-1112
=
||sm
- 1- ||=m== 1- [|]
E
||
- [2]
2
E
57th 1
Assumption
4V
Also the term 4n
E
-|
x 1/
Fn (x
112] (1r
can be bounded
E
17
Jensen's 's Inequality
- (x W NV
Putting everything back into (a) gives us:
E || - x
l1
(Assumption in
D
S
E
1z-1 - 7/ Fm (2 + 1 (x 11]
+ +817004
+ 12n
2
| - -x/-1 - 1) V [2
+ 16n'
Vo
- - - Vi + V
To bound the third term in the above inequality, we use the A.M. G.M. Inequality vab S + c
27 &
for y O. Let y 17, a 0² "
b = 04. We
have:
16n² / To
- +,
-
= =16n² V (a
- - -11))
< 16n
10t
o²
|| - -,
E
||
2
21
So we have:
E
| xx x11
|,-hh1 - -2t-1-17 - ) 7
E
12
1 - -
VV (-:²
V 112]
10"0
+ +177 3
E
m - - V. + V
2
2m
56

---

E |---- x2-1 -
20022²² ||=2-1 - + + 16n
=E |1--1 - - 1) - - - -VF((?-))))
+ +220n
-,- - - +
- - -VF
+ +161'0*
Now by using Lemma 16 we have:
E || - -= 2x112]
$ 1+ 1 _ )
3
E
|0 24 - 77 (VFm(= Vmn (zf- 1)
70-1
+ (1 + 71-1) '
|| (xi_1) VF (x ||{]]
+ 201220²
(1 1 7-11
E
-- - -ー - 17 (x - (x
+ 200 22
+ 1- -
V (-:- 1 + -667/a0
From the mean-value theorem we know that VF(x) V (c)(c) y) for some c A + (1 A)y. By applying this theorem to the first and third term of the above inequality we have:
1
1 +
E
F1-1
xh-1 Fm (FFm(())))))
76-1 1
3
1
+
E
| - - - -
- -
3
[|(( F (e)) 2لاا)
+
7
1
3
(1
m
Vo-1
With the same approach for the third term we have:
20ni²0²
I+
1
E
||=Th
2²11 -1
n/ Fm (=m()=))))1
71-1
< 220m20²
1
1 (++)+)
(1
2
[|021 1 x 2
Putting all together gives us:
E
12 - x²"113 [1
3
(1 - (1 |10011 - 22 [1 [
x 1 K - 1
+ 16n² kx3
E
V - VF (x [|
+ +E VFF(22)) -V
+ 20n202
+ K-1
(1 - )1=)))) ||ام511
- x. 1-
111
+ =40nt02K
- VFn ||VF((=))))
( - -
+
+ 01
1 K K-1 )
3
<
(1 - nE 'E ||اا1 - +2 11 + +32m K3
57

---

1+ K- (1+x-1)(r (1
1
+ 20
7 | - =2-1112 + 00 +
E
-
2 [12]
K
+ 40 (3Ko2n²
+ +6K
30 16
+
E
2 x1111
+ 32m " + 1361) Koo + 320 320
K-1
3(K-1)
+ K20 320
+
K
20 (32m"
1361 4
+ 160 2 (
< 20 (1927² (296n
s 3840n/ L K
where in (a) we used that (1 1/x)" 20 for all 2 0. Finally averaging this over m, n E [M] implies,
1
E
1
x:
Σ
E
||
m2 l1
M
M
ME(M]
m.nE
[M]
s 3840n'
K 55990m 1220
which proves the lemma.
G.3 Convergence in Iterates
In this sub-section, we provide a convergence guarantee for the iterates of local SGD under Assump- tions 16 and 7 We do so by using the red upper bound from Lemma 20
Lemma 28 (Convergence with Ç, T and Q). We can prove the following convergence guarantee
assuming 1) 1/H:
A(T) S (1 - mn1) KR B² + 15360Q9/ARRH444 2 >
24
+
112
4
12
12 Ko²
no²
+ 42
PM
Proof. Use the red upper bound for one-step progress from Lemma 20 lemma using the red upper bound,
We first restate the one-step
A(KR)
2012²
211T² C(KR -1)+ 1702
$ (1 mHI A(KR 1) +
D(KR 11)+
1
M
21
KR-1
< (1 m/)* A(K(R 1)) +
Σ
(1- (Q))))
+ +((
j=
+ (1 - (1 ) 702
HM
< (1 - T/)** A(K(R-1) - 1))
2Qt KR-1
Σ
(1- m111 KR-1-1 (30-111)380000*****|303 + 5590m -
1 j=K(R-1)
27'n
KR-1
Σ
(1 - (R-1-
((
58

---

+ (1 - nn) no²
HMM
< (1 - -m) A(K(R-) - 1))
(76800 1 11
KR-1
Σ (1-1))
1
1
((R-))
12T 12
Ko
KR-1
(1 mu)Kk-l13
1
1
(=K(R-1)
n
+ (1 - n1)
(a)
μM
Note that we can simplify the summation as follows,
KR-1
K
1 (1 mu) K
Σ (1- KR-1-j- = Σ (1 nu)²
(1-mu)RR-1-3
m/
(R-(1-1)
1=0
Plugging the above result back into (a) gives us,
7f
A(KR) & (1 - mH) K A(K(R - 1)) + (1- (1 (1-11(11))00 )))*
122
+ (1- 11840QP11*K30
12 6
no²
122
12
112
μM
Now we unroll the above inequality over R rounds and we have,
"6 11840Q2
18400"17AK''"
K?
1272122HH''
A(KR) S (1- mp) KR
= B²
+
+
122
112
112
Gr2
+
112
μMM
which finishes the proof.
G.4 Tuning the Step-size
In the previous subsection, we provided the following bound on the iterates of local SGD,
7680Q21)* K K* 11840Q? 2204 12 K2 2
A(KR) S e R
4²
42
42
6r²
no²
42
uM
To achieve the final bound, we need to tune the step-size to have the following Theorem,
Lemma 29. For all E [] under Assumptions 7 and Jasummig 1) S 1
2H we have,
(7680Q2 KAÇt
11840Q 0
12
6r2g²
A(KR) R) S e
u.B. 2H
+
+
R
K2
R²
H*K2 p2MKR
Proof. We pick the step-size follows:
if 211 2 μKR (1(Tmo)).11BBBT/o))) we choose
1
1
uKR (m p²
1
if 27
S WRn (2, we choose 277
Which gives the following result,
7680Q2 KAst
11840Q R2
127252 + R
6r202
d² μ
A(KR) S 2H + +Ō
R
PKR
where the notation Ō hides the logarithmic terms. This proves the lemma.
59

---

H Double Recursions for Consensus Error
In this section, we will relate the consensus error to the iterate errors of the previous communication round. This would allow us to get more fine-gres tnee-griied upper bounds on consensus error, which would decay with time and more communication.
H.1 Second Moment of the Consensus Error
We can prove the following bound on the second moment of the consensus error using Assumptions and
6
Lemma 30. For all E [0,T] assuming 1i < π we have,
C(I) S 22 O 221 K (1 In(K))
1
+ 71 (1 8(1))² (1 qu) qu)) (1))(((1-6(()) (A(5(1)) + +
< H2 + 2
+ 21 O
K (1 + In(K)) + = (A(5(t) + +.)
P
This also implies that for r E [R].
Kr-1
Σ (1- -1))k~1---(()
j=K(r-1)
1 (1 nu)K
21pr22200 22 (1 (1+ In(K)))
20 H2
mp
H
1 (1 mu)k
112 1 (A(K(r 1)) o.)
Proof. Note the following about the difference of iterates on two machines m, n E [M] for some time > 8(t) (for t 6(t) the lh..s is zero).
E
|
m
x
112
|
x
- -99 + +ngg-1l1
(Asssumption
(a) ||xm-11 2--1 - Fm (m -V + 02
(b) 1
x - (x V En (x(x)_))) - (x (=
+ 2n200
where in (a) we exploited the fact that 5Th 1 et HH and ,, E mn as well as used tower rule introduce conditional expectation; and in (b) we added and subtracted the term Vf (z 1). By mean value theorem we know that there exists c ri-1 + 0(x71, xf_,) for some 0 E [0. 1] such that:
Fm (x Vmm((=))) 2 (=) x7-1)
Using this in the above inequality, we get:
E
|| - 2211
||-TT1 - 2. 2) - (VPm (F, 1|1] + 2n220
E
E
[|(1 1 - - 1) (x"_) (= + 22
[1++1 1
w
E [I - 112 Fm (c) (xth - 2
60

---

+ +(1 + +(1+7-11) E -V 11(]]
+ +21f022
1+ 1 (1 ) || - -
+ (1 + +--1 E
-
+ +211²02
+ 1
(1 E ||:211 - ] + 021/0²
+ (1 + 7- 2
V Fm (2)-1) Vfm(),)) +
(
++
(1 - 1714) E 1 - =
7--1
+ + + 17
V (x VF - (2,(( + (2;))1
+ +1 + 1-11
|| Fm (2,1) - VF [|]] + +21120²
Assumptions m
1 %/-1
1
(1 - - [|| 1 - -2,11
+2(1+70-1) 17 E ||| V (1 VFr(2"))) (V (z V. (2 |1
+ +2(1+7 1² 11 + 217²0²
where in (a) and (c) we used Lemma 16 and in (b) we used Assumption | and the fact that 17 < 1/H. We will again use the mean value theorem for the blue term in the above inequality. For v == x4-1 -5 we have:
Fm (2
(Fr(a (VE - (z,))
L. (V2 + tv) F., + tri) vdt
|| Fm (1 - VF, (x (VFm (x+)) - VF
$ Fm (2, + tu) - V2 (2, + tu) || dt
Vm (= (= (VF (zx) - VVxx 11 ST sT|1oo11 -2%71y
Plugging this in the inequality above gives the following,
E
| m xx [1:]
$ 1 + 1
7 ) (1 - 1 |
x²"1 22]
+ 2 (1 + (1-1)) 11)1)²² 7
[[| || - -x2ll3 =il12] +2 227
$ 1 + 9-11
(1 - 11)
||-221 -2, 12] + 72 + 2n2202
+2 + 7t-1) 1??
no² (1 (1 (1)
x (1 20
|10(0)
11
where in the last inequality above we just used upper bound for the convergence of SGD single machine n E [M]. As a sanity check note that if t 1 = 5(t) then the red term becomes
||= - ==1]]] Continuing further and choosing 73 = j - 5(j) (note that the term with 1/7--1 8(t), making this choice well defined), this leads to,
becomes when
||07 x
61

---

S II 1=6(1)
1+
11 (1 m)))2B ||00000 =0c0112
73
1-1
) (1 - m/0) (m-) (11 + ()) + 0²)
+ 2212 (=b(t)
II
1=/+1
+ +2
Σ
(1+ 7/
2) (1 - mjus (1-)
(1 (1+ (1 - ((1))(5-6(6))) E [10000) - 2x1l:
s=j+1
2n 200
Σ
1-1
[+ 11++) (1 monu (1-m
+ 73) (1 (1 - (111)))(--((011)
(=
i=j+1
++ 1 (1=)))((1)1)) (11 (1+ + 02)
221
(=)(()
(1+ #)) (1-1)))((-13)) (1+7 (1 - m1))((-60))) [| - -ah
+ +212²²
(=
1=/+1
21pp00
Σ
[-1
1+ (.) 2)) (1 - (1))((1111))) (1+73) (1 (1 - m2))(6-5(0))
i=j+1
i i+1- 8(t)
= 202
(6++1550))AP (1 (1--))++---0116-1)))--- + x²)
i 5(t)
)=5(()
+ +2127²
Σ
1-1
5(())
(5+1))(t)) (1-)))11111) (1-))))((11 [|0300] - -=il:]]
8())
(=j+1 (=
212²²00 1-1
Σ
i+1-8(t) 8(t)
()+1-6(1) (1--11)800111)) (1 -)))(((-1-((())
i i 8(1) 8(1)
1 )=((()
imj+1
2-1
8-5(t)
= =nn² Σ
j - 8(1) (1 - (1))((1111)) 5) ((+1 ((++1- (6)
(=6(()
1-1
+ 222
Σ
(1 (1-)(1)) (1 -1-111 ())) | - =
(=)(()
217² 002
1-1
- (1 Σ (t- ((1) (11 (1--1))((-1-))
()1))((-1--((1)
/
(=1(1)
a²
=2nj(t - -8(1)
Σ (1- - (1))((1-1))) ( + j+ 1 8(t)
(=0(()
+ 72 (t- 5(t))² (1- nnu 21) E ||006e)
020 t-1
Σ (1 (1-8(1) (a (1- - (1 - mnlu (()))((---)(1))
/ ((t(
<2)((18(1)) + 20 6()) 2 Σ
1
j 1+1- ((1)
j j=)(1)
62

---

+ +21 (t- -(t))² (1 1000 1 [10,00] =2112
210 (t- -
I (t ( (t-)(tt)) 2n 210
+
(1 + In(t 5(t)))
1
+ + (t- -5())) (1- -11))(t-11
[
(|10800) - =1] + -|1e²* - 2 111)
((t-6(0) (2) H 21p522K² +21 (1 + (++((KK)
1
+ +41/7² (1- 8(1))² (1 - -nnn 2((-111(11) (A(6(1)) + 0.)
<2 + 2n1 O²
+ 217² 0- K (1 + In(K))
+ +47 (t- 5(t))² (1 (1- 22)) (A()(t) + +
where in (a) we combined the red terms into one, used the fact that
1 (1 nu) (tt))())
1
(1 mH²)²
mHl(2 TH1)
TH
As sanity check, note that the above bound has the property that when = 8(1), it automatically becomes zero (we adopt the notation that O- (-oc) in the second term becomes 0). Thus, we can safely drop the assumption that t > 8(t), making the above bound valid for all values of t. Finally, averaging the upper bound over m, n E [M] proves the lemma's main upper bound. To get the other result, we will simply use this upper bound. In particular noting that 8()) = K(r - 1) we get,
because 77 < 1/H and used Lemma 16
Kr-1
Σ
(1- 11) --)))~----(()
1=
Kr-1
(1- (1-n HP 222 +20 K (1 + In(K)))
Σ
(= 1)
Kr-1
Σ
(1 11-nui (1-n))kr-->) (4n27²() (j - K(r - 1))² (1 - 2 (A(K(r- - 1)) + +o))
j=k(r-1)
1 1- (1 (1- =
22 222
+ 222 (1 + +l((K)))
Kr-1
+ +4n2+2(1 mu1) =/
(A(K(r 11) + +%))
Σ
(1 - 11) (o- (j K(r- 1))²
j=
1 (1 - =
2K202
2n²"12 +
+ 21² K (1 + lm(K))
qp
1
1- (1 (1- ) 212
(A(K(r- 1)) o?)
This finishes the proof.
H.2 Fourth Moment of the Consensus Error
Lemma 31. For all E [T, assuming 17 < 1/H we have,
12811"7'0" (t - 5(t) + 320m (t (0t(((()(1111))))))))))))))) - (10 (A(5(t)) + +
D(t) <
#
+ +647 7 6(t))((1 mn)=-1-611 (B()(t) + ot)
63

---

881)
160n
+ 1600
+ +122 (1 + In())) (1 8(1)), (1)(
+
1
1281 k²
+ +3300' 220)))? (A(0(t)) + + + 644 (B(0(t)) + +
11 Soy² K
881) 18 + 1
160n
112 K (1+In(K))
113
1
This also implies that for r E [R]]
Σ
(1- (--n)) m))))r-13--()
j= 1)
128n' K'7-02
320m" (1 mp)) (A(K(r- -1)) + 11) o.)
(1 (1 )
112
1
K4
+ -1- - (1 - -mp)*)
11-m))) (B(K(r - -1)) + +
(1 (1 )m
811 812 H²
160 k2 160 88n 8 K3
112,"K 0² (1 (1+ (+(n(()))
4
Proof. Note the following about the fourth moment of the difference between the iterates on two machines m, [M] for 8(t (for 5(t) the lh..s is zero).
E
| 2x 22112 l1
||اا -z-1 n9 no 112
E
(10711 xx=1 17
E
VV ( -
||احا x -
E
+ 2n (1 - x (x,")
_00 E || xx- 1/
[||T_ 112
+ 2
[<x7-1 x/-1 7/
---))))
10 - - -|
+ 2
Eh_ 2
+ 1
(nrT - 1
- -
|
5--
(Lemma 15). (b) ||>;" - -
+ 80
+ E
| - x.-1 11
[||s - 47-1 1
+ 417 E [1 - -p11 - V/ +
V
F..
5t [1
where in (a) we use the fact that LE stochastic noise i.e., { 1 {- x } Hi-1 allowing us to ignore one of the terms while expanding the square; and (b) we again used this fact along with an application of
58 ft-1
- -ー
H2 = 0 and the conditional indepence of
Cauchy Shwartz inequality. In order bound the term E [| 1- Inequality:
11
| we use Cauchy-Schwar
E
c - 11
[| - 5--1l, ||5TT
- -r_
64

---

-- [2 E |1 - 47 12111
4v 40
Also the term E
=||--11 - 27-1 V
V (o7 [
can be bounded as:
E 2 xp-1
V (xx--)
+ V
(Jensen's Incquality)
E 1r
1/ (00 +V
Putting everything back together gives us:
E |2""
- x7
(Assumptioo
S
E
||
27 - + (z }11]] + +8n20 00
+ 12n)²0
||
- 11 )
+ 16n VOTE
- 11
[1
-
To bound the third term in the above inequality, we use the A.M G.M. Inequality vab S a. + 7b
27
for y > O. Let y = 17, a = O²E
- x; +
= 04. We
have:
16n/ VouR | x/-1 - (x7) (,7
=16
V
(04)
2B
||حا V
112)
n1=
S 1673
E
107-11
2n
Plugging this upper bound and following similar strategy as in Lemma 30 get
E
|
x." [1
E
|,-=1
V/ + + VPP + Sn -6-1-111 -2-1-1/V1
12nj0"
||-""11
2- - FF ( V
+ +67 3
110
0²
E
m - x +1
2
211
E |-m-1
n
41-1
1
Fm (x
+ 20m22 02E
||0.011 -
- 77 VV 16
= E |--01 - xh-1 - Fm fm
-
+ 16
+ +2n0 2 d²E [x1=1 V -V
3
Lemma
+
(1- - nhu
- - - 2 [1
7t-1
+ (1 + --11)² " || | (x
Fa - Vl + V (2
++ + (1 nw) ||اا0 - x 1
+ 20?2 o²
65

---

+ 200 (1 + yt-1) ||
| (x (2 (zm(xt)) + VF + 161
Lemmal Todand Assumptions
Bnd 0
I+ 1
3
(1 1 ||=2]1 - =2-111
8 + 1011²² 1017² (T'B ||02111
2till]]
+ HH 522
+ 20020² 0²
1+
1
(1 -n)) $ |||-7- - x 112]
7-11
+ 400 100)/22(1 (1 + 7)
T ||تا
2in [2] + +112(2)
+ =16
Averaging this over m, 12 E
[M] we have for all t > 8(1).
1 3
D(t)= = 1+ 7--1
(1 - (1-n m(t) ((t-
+ +8(1 + n2-1" 0,)8)8)) 171">" M
Σ
E
1 =xllb]] +
H
nE[Ad]
+ 20120² (1 +
1
(1
- [1)) 11
7--1
+ 10 + 1(-)
1
E
||
- 2n [
M
nE
+ 400 0² (1 + x- H1 C + 1617004
Now we will use a couple of upper bounds that we already have for E ||0]_ 2x l from
Lemma
23
E
|12-1 - [ from Lemma 21 and C(t- 1) for 1 2 (1) from (9) in the proof
of Lemma 30
This gives us the following with Ny = 5() = j- -5()) for j 2 5(t).
((t)
< ( + 7-1
(1 (1-
1 121++1++00 +1)+
3 8817 8878 00
112
3 7 1
Σ ((1 (1--1))(--1-5000) E ||ax(e) - -25113)
+ +8 + 71-1)
M nE[M]
+8 11 n+t 7 M
Σ (8)20(( (t 1 1---1--6))0 ( -(t))(1-m))(( ())(((11-(00)) E |,:000 =5.11]]
nE(M]
+ 20122
1+
1
1
(1 - ( 1)
9--1
+ 400n000 0272 + 70-1)
1
Σ (1 (1- 60) |10000 - -x 12
n0²
+
M
nE(ad]
+ 40 + 7 S2 + 16 04
(Lemma andand A (1 1 (1+11 (
3
(1 (1-7)4)
7/1)² DD 1) +8 8 + 1) 17² A
7/-1/
+ +64 (1 + 76-1) )²² 7'177 (11 - (1-1 1(c-1 ((0) (B(6(t) + o))) + (1 + (1+7+-)) 11)) 7
112
+ 128 (1 + 2)-1) )²3 7 07 - 8(1) - 2p))2(c---000 (A(b(t) + +ot))
+ 22
1+ 7
(1 mpaa (4nj2 (t- 1 -8()))((L
(1 (1- -10)))(1-1))) (A(8(t) + +)) ( 2(t-1-88) 8()) (12KHP22+ p2-KO²
+ 22
1+
1
(1 nwna
+ 72 (1 (1+ (L+n(K))))
7o-1
P
66

---

+ 400 + 71 1) 2(1 - 1/1)2((11-600)) (A(8(1)) + 5.) + no²
14
+ +40n'o 02 + +-11)112 + 1617'o"
1-1
1+ 1 3
$
II
73 ) (1 11-7111 1 |122009 T6(1)) 2
j=6(1)
*(3 (1) H + 88187904
Σ
II
1+ ) 3
(1 - m/)) (1-mna²) (1 + 75)0
112
j=o(t)
p=j+1
+ =4 (B(O(t) + +
1) 3 (1 - m/)* (1-n)))) (1 (5 - -10)4(0-000)
x Σ
II
(1 76
8-1(
(=j+1
+ 1287 7 0² (A(6(t) + o.)
x Σ
[-1
(++
3 7s
(1 - m/0u* (1-n)0²*
5(0)(1 -00)))-0-000022----0000 (2))00-0110))
(=6(1)
i=j+1
+ +80 02 (A(o(t)) + +
Σ
[-1
(1 1+ 7/
)))² (1 (1-ma)') mu)") (1+
1 3
(t7g)/ 11) ( - 8()))( -(0))(11n2266-000 22))
x
(=1(1)
i=j+1
+ n²²
+ 400/20
+ +n1021 (1 + In(K)))
Σ
1+ 1 3
) (1 (1- mpss (1-mas))
(1 11-mpy mp)2 (1+1) 738) 1)) 6 8(t))
x
j=0(1)
i=++1
+ 00 (A(8(1) + x
x Σ
II
[-1
(1
1
3
(1 - m/is* (1-m
(1 + 75) (1))((1-800)
+
7//
j=8(1)
(=++1
nT'O²
Σ
1+ 1) 3
7 (1 (1- mps*) (a-nsy))
+ 000
+ HH(C2)
|I
(1 (1 75)
1
j=((()
)
3
+ +161 00
Σ
1
1
(1 m/my
:
imj+1 (-1(1)
88107'004
1-1
8 H +
Σ
(t (L-)())) -())((111>))
412
(=1(1)
+ 644n"> (B(((t))
+ Φ
Σ (t- (--(())((1 mu))(t-116(())
(=
r-1
+ +12877740² 2 (A(5(t)) + ))
Σ (t (t-5(()) ((-5(1))3g - 5(1))(1 -21021)-1--2--2861
(=8(1)
+ +800)00272 (A(6())) +
Σ
(t- 8(t)3
(1 41)-
(j+1 1-11-600 -8())2
(=(())
67

---

+ +40rfo2 ( + n2p +1p002 (1+
+ +In(K)))
Σ
1-1
(i+1- (1 mp))4(1-)
(t - 6(t))
j=8(t)
1-1
(t-8
+ +800/0077 (A(5(t)) + x
Σ
(1))- (1 - (1-1))) (1)))))(---222222260
(=)(()
nT222
(t- 8(1)3
+ 02
+ H
Σ
(1+1 8())2 (1 mp)d(e-111)
1
(=8(1)
[-1
(t- 6(t))
+ +167 0
Σ
(1 m)))((-1-3))
(i+1- b(t)3
(0)
8np C
881
(1)
(t (t-)(t)3
1
+ 64 1 (B(8(1) + 65) (1 (0--611 (1 - 111))0----0100)
128
(A(5()) + +0)) (1- ((0))((1 (1-0000)) (1)2((11-5(00)
P
+ 160m' 7272
(A(8()) +
mu) (10))((1))) (1-)01---5(0)
I2IPK + N²==K²² +100² (1 + +1 (n(K))))) (1-
+ 801)²02
1
+ 160m/ 0²7²
(A(6(t)) + +o2)(t (t-(()())) - (100)((1100)0--11-1011 ())(((11-0(0)
TT'O²
+ +80n'02 02
+ +1P??)
(t- (t- +
11
<1h)
811 HA
740
+ +160 Ko² 2 + 160m"
+ +112,/ o (1 (n(KK) ) (1- 8(1)) (1-8(1))
+
11
113
1
+ 64n"" (t-((((())))( (10)) (1))((1--5(()) (B(6(t)) + +
12811 7
(t - -1)) + 320m (1 - (1)) - (1)) (A(5())) +
+
where in (a) we used that Σj=8(h U+1-00
E)) -ーーー S - < 2: in (b) we used that
< H < 1/2 to get the red and blue terms. This finishes the proof of the lemma, once we note that when t = 6(t), the upper bound is zero, which means we can extend the proof to & 2 8(t), which essentially means all t.
We can now use this bound give the following bound for r E [/t].
Kr-1
Σ
(1-11)KK-I-DD)
j= 11)
< 1
Kr-1
(A(K(r- - 1)) + +3)
Σ (1- m11) k1- - ((r-1)) (1)=())(11 - 21006661---6111
/
j=K(r-1)
Kr-1
+ +320n' '07? (A(K(r- - -1)) + +
Σ (1-1ju) - -K(r- - 11))(11)1111111) - 21-
j=
[=K(r-1)
Kr-1
+ + (B(K(r- - (1)) + 04))
Σ
(1 - (1-
Kr-1 - K(r - 11)) - -1-
(r
80p H
2
43 + Ko
Ko²
+ 1120"'0 (1 (1+ (I+)n()))
/
68

---

Kr-1
(1 (1- - (()
x
((--1)
128n " A02
Kr-1
(1 11-7i1 (T-T - (A(K(r - 1)) 1)) +
Σ
(1- )- -K(r-1)
P
j=k(r-1) 1)
Kr-1 Σ
+
02
( 1)) + +
(1-n))(-((r-) -X(r-1)
j= =k(r-1)
Kr-1
*64/** m11) K5 ()(){~>(((((FF) - 1)) + xt)
Σ
(1 (1- (1-111133 3(jj,(jjrrr- 1(r-)))
+
j=R(r-1)
81) 81
S
160n 0
+ n3
+
+ 1 (1 +In(K)))
P
Kイ-1
Σ
(1 (1-nn)krot))
x
j- 1(r-1)
1281)
K 102
(1 (1 - )/)**
(1 - n1) K- (A(K(rr 1)) + +
1²2
320m 3 K 7²7
(1 )m
(1 m1) (A(K(r 1)) + +
64
- (1 - -m))
(1 - mu)K- -5 (B(K(r - 1)) + x
P
(1- - nu)*
88n K 070 87 K
160n K k 2222
160n 2
112 o (1 + +nnn())))))
x
122
1
4
which proves the claim.
H.3
Should Consensus Error Explode for a Large Step-size?
Note that the results in Lemmas 30 and 31 suggest that when K 0o we must pick 1 = so that the consensus error does not explode. This small step-size was criticized by Wang et al. through experiments showing that even without such small step-size, consensus error did not blow up in the regime of large K. In the following lemma we show that even with eтror does not blow up, and actually saturates to a value that depends on the data heterogeneity The lemma relies on just the evolution of iterates on a single machine, and the fact that is decoupled between communication rounds.
g
A ( consensus
Assumptions 4 to 6
Lemma 32 (Alternative Bounds on the Consensus Error ). We have the following for any 1 2 5(1) for q < 1/H when optimizing a problem that satisfies Assumptions
aadd
6n0
C(t) I 12(1 (11))((-6600)))) (A(5(t)) + +
+ +3²
864n0*
D(t)= < 432(1 m1u a(t ((t) (B()(t)) + Φt)
+ +27Ç7
In particular, when - 5(t) + oc the upper bounds converge to respectively.
Gnd²
3x2 and 864n0"
+ 27ç
4s
Proof. We note that for any and m, [M]
E
xx 21'12]]
E
|
+
xx
x
69

---

Lemme and Assumption
311 || xin =mll
+ +3B || - + +3
|100000 - -x =mmll2/ + n1o²
Lemma 3 (1- (1-1 2 E
+ (1 m1))(( TE |1:0003 - 25 [alla] + no²
1e ) + +c,22
Averaging this over m, [M],
6i70²
C(t) S 6(1 mh) ((1 ((1))
Σ me(Md]
E
||=SCC) - =mnll22
+ 36
M
1
6no²
< 12(1 - 1114) )(())(()(()))
[ [1(0) xx =111
+ <b?)
+ 35,
11
Gnjo²
12(1 - ()/)2((-((()) (A()(()) + +
+ 3
which proves the first statement. For the second result we similarly note that for any and m, n E [M] and E [0.
| 2. [11
E
|| zm x²? + xn + xm 22l12]
(Lemmal 17 and Assumption
27B ||-7
=m
+ 27E
|10| xillā]]
+ +27
(emmmn 23 27 (1 (1- (1-n m)/r)sc (yp))sce-8(00 6( ||=30ce) - -zt =2,11:]]] + 16no*
27 (1-nn))(t- [| 2iilba]
1610
+ +2774
Averaging this over n2 [M].
864n0
D(t) s 55(1 mnr ((L))(0))
Σ E ME(MM]
[
11
+ +27
M
1
Lmmma and Assumption
432(1 mlla 3(4 ((t))
E
x x=112]
+ +0²
864no
+ 27ç2 +
3
864n0
432 mul1 m 3(1- (A(6(t) + o.) + 27Ç1
3
which proves the second statement of the lemma.
The reason we do not use the above lemma over Lemmas 30 and 31 Appendix dictates that we anyways need to use 77 = nKR
is that our step-size tuning in to get our convergence guarantees which puts the issue of exploding consensus error to rest. Having said that the above lemma offers reconciliation with the observations by Wang et al. X in the regime when = (+)
I Putting it All Together
I.1 Convergence in Iterates without Third-order Smoothness
This subsection will essentially combine the weaker blue upper bound from Lemma 20 with the consensus error upper bound from Lemma 30 This would lead to an inequality that we can unroll across communication rounds.
70

---

Lemma 33. Under Assumptions I using 1 < 1/ H and such that
== - nu)} k + (1 (1 - nu)** 4nj 22
- (2
<1
1²2
we can get the following convergence guarantee with initialization =
R B² + 1 - (1 11--100 np))
K
n1o²2
1 11
4n7² 1=² (1 nu) 200
A(KR) S p
1 P1
J.M
1
1-P1 P1
n²
+ 1 (1 - ) 21 H
21j"
12
2nj H222K (1 + In(K])
(1+(k(())))
+
1- P1
n
n
112
Proof. First recall the round-wise recursion from Lemma 20 for R.
nH² KR-1
A(KR) S (1 muou** A(K(R 1))
Σ (1
(1-m))-R---00)))
"
j=K(R-1)
nu) n1²
+ (1 1
(1 (1-
WMM
mp)* SK A(K(R - 1)) + (1 (1 11-111100 -1n))) no?
(Lemma 30
HM
1- (1 -1 nm)*
2n 2r2 + 27 22222222 2220
+ +27 11 K (1 + (m(K))
122
1
+ 1 (1 mK) K
2 22² (1 mT1)** K- (A(K(r 1)) + 02)
42
(1 mu)) "K + (1 (1-(1-11)) )1)**) 4n 72
K² m)))k=) A(K(R- 1))
112
1102
+ 1 1- 1-(1 mp)K K
+ 11 - (1 - x)/***
Anj 2n12 11221122211 x20²
WM
122
(1- -m)))
27 H2 K22
2n12 K2 S? +
27 212 2 (1+
+
112
pi R B² + 1 - (1 - -
k
no²
1- (1 -
T2 1)))) K
(1
1 PI
μM
P1
112
1- (1 = H2
H2?
21 K (1 + +l[(k))
+
1 P1
122
n22
where we defined P1 (1 -m)B + (1-(1-1ph) lemma.
4n 7" K2 (p) k This proves the
122
We can tune the step-size in the above guarantee, using standard techniques while making sure that is small enough and K is large enough. This gives the following result,
Lemma 34 (Strongly Convex Functions Iterate Convergence with T, Se: 0.). Assuming
3HT 122
B²
2HT
B²
R max
In
In
3/2
112
we can get the following convergence guarantee for local SGD, initializing at Io = 0 and optimizing functions satisfying Assumptions 1o
A(KR)= = (
KRR B2
H²
22702
H²02 (1+ (1+(((K)))
+
+
+
R2
Re
KR
w' K KR
where we pick the step-size,
B
min
2H' pK R
71

---

for the choice of e,
20² M2MMKR'
872 1²
AH RAR
202 4H2 (1 + +In(K))
c:= max
Starget
1 KRR
K²KR²
where Etarget is a larget, which is greater than or equal to the machine precision.
Proof. We will pick our step-size as follows, where we will specify some e bigger than machine- precision in the end:
B²
7 min
In
2H
pKR
1- (1-nn)* K
We will now derive conditions that are enough to bound
by 2. Note the following,
1-p1
(1 mp)* K
1 P1 2
3 PI 1 1+ (1 - -m
2
(1n))( ) 4np
5 1- - (1 mu) k
4 1 1-
(1 -
K² nu)
112
2
412² H272
1
k² -1111 K-2 =11))=22
S
12
2
2 In²
B²
1
2
3
B²
+ R
In
n2
Hence it is sufficient to assume that R2 3/4 rate from the previous lemma as follows, x²
In
n²
This allows us to simplify the convergence
21p0²
817 2 22
K-
A(KR) S B
pM 4n² K22 G
42
4n H2 K222
4n
(1+
K
122
122
210²
817² r K2K 0
2
H22222
S p B2 +
PM
11
2
11
2 02 K (1 + (n(n()))
122
Now, let us upper bound the exponential term more carefully. Recall that due to the choice of our step-size, as we used this before,
H2
P1 (1 mp) K.
(1-(111p))
k² n2)K-2
112
4n72 H2?
5th (1 >n))** + muk
K2 -11)==
112
< (1 - mnu)* K + AH222
B22)
In3
(1 -nu)k>
1rt R3
S (1 m/) K-2 2
B22
In
(1 mnu -1n K-
R²
+ 22
B²
1
(1 mn11 K-2
1 R² R3
Se nn(( 2)+ 2H22
ln3
8²)
n
72

---

where in (a) we use Bernoulli's inequality, and the choice of the step-size which implies that my < 1.
Assuming K 2 and raising the power of both sides to R gives us,
R
naKR
<
2Hr where in (a) we assumed that 2
In 3/2 (5²) Finally, we will pick the as follows,
20² H
4H
4H2 4H (1 + In(K))
max
D2MKR' RA
RA
K
K
Etarget
where Starget a target, which is greater than or equal to the machine precision (say, floating point precision), thus implying that In choice of this step-size,
.3a c
a numerical constant. We note two things that justify that
The largest will lead to the step size end up using, in particular determine govern which term dominates the convergence rate. For instance, let us assume that p² P
20
Furthermore, let
2H Z u In
B²
which implies that --2
211
S
W MKR
2x²
With f)
In
B2
this makes the convergence rate,
PKR
20 PR μRMKR
20
B² 2 μ ARMR
RKR
T²
A(KR) S
=
On the other hand if 2H S nkR In makes the convergence rate,
then it implies that,
PRR
21
2r M' which
2 =
KKR 2H
KKR
A(KR) S
2H
μH
μ²MKR
Using the above logic for all possible choices of e (ant thus 17) allows us to give the following convergence rate,
A(KR) = Ō ( RRR B²
T²
22 R²
H
H7202
Ho (1 (1+In(K))
+
+
μRMKR
KRR
HRR
Furthermore, assuming the functions are quadratic we can replace some of the smoothness constants with r, by relying on the better red upper bound of Lemma 20 as with Q = 0 we do not need to bound the fourth moment of consensus error. The proof more or less follows the above lemma, and results in the following rate for quadratics.
Lemma 35. Under Assumptions
1 to 6 and using 1 < 1/H H and such that P2 = -11 - mH4
=(1
(1-(1- 4n²2* 2² mp)
K < 1 we can get the following convergence guarantee with
4²
initialization x0
0,
1- (1 qp)
K
no²
+ 1
(1-1
AnpT"K2(1 mH1) -22 202
A(KR) S p B2 +
1 1- P
PM
1- P2
1²2
k1)K K
(272 H2,2 k2C?
22 K (1 + In(K)) K20²
P2
1²2
One notable thing that for quadratics, when 7 we can get the fast convergence guarantee for dense mini-bated SGD, i.e., with K communication rounds. We do not get this for non- non--uadratics, which highlights the need to understand the effect of third-order smoothness. This not surprising because third-order smoothness is known to play vital role in the convergence of local SGD even in a homogeneous setting. Just like the strongly convex case we can tune the step-size to get the following convergence rate for quadratics.
73

---

Lemma 36 (Quadratics
Iterate
Convergence with O.). Assuming R N
max
we can get the following convergence guarantee for local SGD, initializing zo 0 and optimizing functions satisfying Assumptions and
3r² 12
In
2
s/2
B²
A(KR) = Ô (e
TO²
F²0²
+ T²O² (1 In(n))
PRR
B²
+ KR
μRMKR
R²
k*KR"
where we pick the step-size,
== min (1
B )
In
1H pK R
for the choice of e.
2a
&r 4f
4
4 (1 + In(K))
:: max
12MKR' RA
R²
'OKR3'
1 RR R2
Etarget
where Ctarget is target, which is greater than equal to the machine precision.
can be noted the above convergence rate than when r 0 we recover the fast convergence rate of dense mini-batch SGD.
1.2
Convergence in Function Value without Third-order Smoothness
Lemma 37 (Strongly Convex Function Convergence with T, S+ Φ.). Assuming
4TVK H
nB² c
[BB2
R2
max
In
. 22n2 V
KR 2 4k can get the following convergence guarantee for local SGD, initializing zo 0 and optimizing functions satisfying Assumptions 1o
E =
*KR
LB²
3
HT20²
HO² (1+In(K))
+
2
d²
12
KARS
12KR2
n²
RMKR)
where define a = Et= wait for the choice of weights
R-1-5(t)/K
(1 11))(t)+K-11-
P1
W
for W 1-p. 1-(1 and P4 = (1 - -11))* + (1 (1-1 807 30² R²
(1-1 k-))-2 And
nu we pick the step-size as,
I-P4
In uB²
11 = min
2H pKR
for the choice of e, c= --min max
{ ( 4HT222 4Ho² (1 In(K)
8H+262
30² Starget
uB2
R2 p*K
K2R
R2
"MMKR'
where Etarget a target, which greater than or equal to the machine precision.
Proof. The main task in this subsection is to combine Lemmas 25 for all E [0, 1).
30
Recall Lemmal 25 implies
3n"0²
A(t + 1 mp) A(t) - E)(()) + HnH +
M
Also recall the upper bound on the consensus error from Lemma 30 for all E [0,7],
C(t) < 1 + 2 + 2n (1+In((]
74

---

+ 4 (t 5(t))² (1- n1)2((11-((0) (A(o(t)) + +
Plugging this upper bound into (+) gives us,
A(t + 1) = (1 - mn) A(t) - TE((t + 41 4n' +4 HO² K (1 + In()))
37
+ (
(A()(t)) + + +
M
Unrolling the above recursion for over an arbitrary round E [0, - 1] gives us (c.f., the calculations in Lemma 30).
Kr+K-1
A(K(r + 1)) (11 m/)* A(Kr) - (1
Σ
(1-n)))rrkR-1-1)))
t=Kr
+ +11 (1- 811 H22
1- (1- mu) K
(1- (1-mu))-2A(EE)
Th C1
μ
Where C₁ is the sum of constant terms in the upper bound which do not depend on and defined as,
G = 41 22"
3nf0²
Hop (1 + In())) + 8r + M
1
We also define the following constant,
8112 812 (1 (1-1)) mu) (1-nu)K-2 K-2
P4 == (1 (1-n + (1-
These notations allows us to re-write the above recursion as follows for r E 10, R - 1),
Kr+K-1
1 1 (1 - np) K
A(K(r P4A(())
Σ (1 (1-m (1-n)))+tk---1((0)) +
C1
1/
t=Kr
Now unrolling the recursion over rounds gives us,
R-1
Kr+K-1 K-
A(KR) S A(0 - Σ
R-1-1
Σ
(1 (1-n))Krt--I--pp
P4
t=Kr
+ 1 (1 - M1)
K
R-1 R-1--Ch
P4
7/41
1=0
R-1
Kr+K-1
A(0)))
Σ
R-1-r
Σ
(1 (1-mu) (--m))Kr-----111
P4
r=0
t=
(1 mp)
K
1- pf.
C1
n/ 1-ps
We will now define the following sum of weights,
R-1
Kr+K-1
Σ
Σ
(1 - Kr
=
P1
0
K=
R-1
1- (1 - (1-nu)
R-1-r
04
1/11
0=0
1
P1
1- (1 - =
A4
7/11
Dividing by 17W in the above recursion and re-arranging gives us the following,
R
Kr+K-1
Σ
(1 - KrtK------)))
P1
k=
75

---

P
A(KR)
(1
nu)
1 P1
A(O)
C1
nW
nW
nW
P
1 (1 na)R WB2 + C1
1-P1 P1
P
P
8np2 H K2
4Tp
(1 - nu) nu)
HB² +
4
P
3no
+ 4nj Ho & K (1 In(K)) + H K2
M
Now similar the proof in the previous section we will pick the step-size follows,
1 In
IBB²
n = min
2H μKR
where we will define c later in the proof. Our goal now is to bound the term P T-
(1- Sn "²² " (1 m)))K-? that it looks more like the exponential decay in usual con- vergence analyses. We first note the following.
8H+2
1B2
1
In2
1 R
2
by assuming R ViaIn In
MB²
This allows us to upper bound (1- 8ny H, (1 m1)(K
by 1. Now we will upper bound
To do this we first note the following.
1-p
817 2 R
pf = (1-11)) -m) KR
1 (1 (1- (1-(1--mmp)))) nu)k)
1u(1 7111
(w) nHKK
(I+
8112 2 K22
R
M1 2
HB²
8H 2
R
S RkR
1+
In
R3
(1
μ1 22
Se Mu 2 ln2 uB²
<in <k2 1) MKKRt n2
In
12Mー2
<(h n
where (a) we use the Bernoulli's inequality after noting that zp < for our choice of step-size; and in (b) we used
I 1
In
nB²
32k. Now using this upper bound we get,
R
MKKR+1
P4
p
1
((1) 2e MKRR+1 < 6e GaKR
where in (a) we assume that e R+ < 1/z which can be verified to be true for both choices of step-sizes as follows,
PKR 28
+1
<
1
-
2e
S
RKR 2H
4 S KR
2
(ii)
In In(=B
/c)
1
1
5 BB²
2 nB2
We are almost done, but we still need to choose e. We do this the same way as in the previous section: we pick as the maximum of the target accuracy Etarget and the value of the convergence rate terms which are an increasing function of 17. at T/ "KKR In particular we pick as,
4H R2
20 4Ho² (1 (1+ In(K))
8H7202
30²
BB
= min max
K
4²RR² R2
μM K R Starget
6
76

---

Finally, note that the we have essentially used the weights on the models fzo..... :5: 1 defined by the blue term. Rigorously for time step t [0, 1] we use the following weight.
( K (1 ny (02
W2
W
Wedt by using Jensen's inequality as and we bound the function sub-optimality of the point Ei= = follows,
-F
E
F
Σ 1=n
S
Σ we
F(xx))
t=0
Thus, our choice e, 7, and averaging weights proves the lemma statement, assuming the highlighted required conditions.
L
the following lemma, we state the result for strongly convex quadratics, by noting that in the proof
of the above lemma, we simply replace the usage of Lemma 25 by Lemma[24aa note that Q 0 for quadratics, which allows us to replace several smoothness constants H in the convergence rate by т.
Lemma 38 (Strongly Convex Function Convergence with T, Se. &, for Quadratics). Assuming 4x
R Z 4r² max In NB² < 2
)=
uBa
get the following convergence O and optimizing functions satisfying Assumptions 7
KR 2
guarantee for local SGD, initializing at xo to
E
oKR AN
BB²
TOO2
+
Po? P2 (1+(11(((
T 0
R²
KKRS
KRR
R²
HMKR
where we define at = =TT w for the choice of weights
R- 8(t)K (1 n1))(0)+KK111
P4
W
for W 1-ph" n1) and P1 (1 m/)* (1 (1-(1- k)
8n2r*k2 k2
(1 mu) K-2 And
n/s we pick the step-size as,
T-ps
1²
min {
In IB22
1 m
(H pKR
for the choice e
H2 R² KRR
4
4r In()))
Ar
30²
nB2
c= min max
KR
pMKR'
Starget
f
where Starget is target, which is greater than equal to the machine precision.
1.3
Convergence in Iterates with Third-order Smoothness
The main technical challenge in incorporating third-order smoothness (c.f., Assumption T in our upper bounds lies in bounding the sequence D(-) while working with the upper bound in Lemma 20 One natural approach is mirror the analysis in the previous section: unroll the consensus error recursion back to the previous communication round, substitute that into the upper bound for A(-). and then iterate across rounds. However, this strategy quickly encounters difficulties. We need to control the fourth moment of the iterate error, B--), and we lack uniform upper bound for it.
To overcome this, adopt a different strategy. As the following lemma shows, analyze the pair (A(-), B(-)) together in terms of the pair (C(.), D(-)), treating them as components a two- dimensional recursion. Once do this, we can more or less use ideas similar to those before.
Lemma 39. Under Assumptions 7 using
1/ H and defining
Ps = (1 - na)* + (11-(1- m))*) k1)))
77

---

(T
BQ
167
H²
16
(412** +
112 +
4²
1BM
12M
12
320m
64n/T/'11
v=
4==4
HB²
B
B²
27p
8 Ct
887 K3
H²
+2120 K (1 + ln(K))
H
BB²
1
160n/ 22
16
112n 04 (1 + In(k))
B²
BB²
B²
we can get the following convergence guarantee with initialization To = 0.
max A(KR), B(KR)
B² + 1- (1 mp)*
no²
917 0d
S 2ppBB²
B
1 P3
μM
3M 16n20²²²
1 (1 mp)*
22T
BQ²
1617
H
+
1 P3
112
1²
M2M
1+
2²M
Proof. We will denote the following vectors for all t E [O,T].
A(L)
C(I) D(t)/B²
A(t) =
and C(t)
B²
B
where note that B comes from Assumption 3 and we divide the sequences B(),, C(t) by B to make them "dimensionally consistent" or similarly vcrle-variant as the sequences A(), C(t). Based on we get the following vector recursion.
the recursions we have developed in Lemmas 20 and 22
1
0
201²
2nQ2 B
A(t + 1) mpp)
8n"0a"
1
A(t)) +
16r
3 HM
9H* R3
161"
C(t+ +
9n
MBT
aM
M
PA(t) + QC(() +N
S p141-600 ((+10)(0((((0))
Σ pt- (ECU(QQC++)))) j-8(1)
where we define P,Q E 2222 and N E R simplify the calculations. Let us also recall the recursion we get for the consensus error terms based on Lemmas 30 and 31
4 K2
O
C(t) <
128 24 R" NB
320g 2 Ba
A(((t))
2 K2 02
+
320g 2 R3
64n '
aB
13
B²
2n H2 k22K22 2
27 3 020
2n 0²
2 K (1 + In())
+
8n K2
88n K²
1607
K
22
112n x 20
nB*
B
12
HB²
= +
where we define U E xx and V E R?. Now we can plug in this upper bound in the inequality above, which gives us
A(t ( (t+11)5Pp pt 800 A(((t) + Σ p' (QUA((())))) + QV +N)
(=8(1)
Now, let us denote / = KR - 1 and unroll across communication rounds to get the following.
KR-1
A(KR) & PKA(((RR- - 1)) +
Σ
P 1)) + QV + N)
(=
78

---

=:
1)) QV + NN) =PK PQU) A(K())K((())))))) 1)) (QV +
where we define P= 2jjK( PKR-1-j E 22 Taking norm on both sides and using the triangle inequality, we get,
||A R) ||(k + PQU) lla ||A(K 1))1 + PQ |V ||P||| |1
< ([| 1| + Pll, 1Ql1 (12) | - 1)) + ||||| 1Q IV + Ill|, 2
We will not individually upper bound these spectral norms. First note that due to P being lower triangular matrix,
9
pk = (1-7
2 MB
Since pk is lower triangular matrix, its eigenvalues can be read off its diagonal. In particular,
note that pk 112 = (1 auui. We can use a similar idea to upper bound |||| as follows,
Σ K-1 (1 np)*
p=
1=
Bn MB
i= i(1 mu)
Σ Ee (1 nu)*
This implies |||||
1-(1- We also note the following about Q, noting that the spectral norm aM upper-bounded by the Frobenius norm,
2nT²
20
16 0²72
nH14
161"0002²
1Q12
1
/
nMB
3
nM
Finally, noting that U is also lower diagonal, note that,
||U|| max { 222 64n
6
S 7n 64n"'~'''
Combining the upper bounds for pk P, Q, U we get.
||p*|] 112 1|1++|11 -||P112 |1Q112 ||0||22
$ (1 - -mp))
(2r² (u22 +
BQ2
16120222
+ Ha # +
167202²²
+ (1 (1-
(1 - )))
12
PBMB²
22M
=: P3
Note that when 0, then P3 (1- (1-mpp = which will lead the fast exponential decay we do get in the homogencous setting. Using the above calculation, we can also conclude that,
|ll| [Q12 |Vl|2 S (1 (1- (1-mu)*)
27
2Q²
1612
+ Ha
16 o²Q
+
122
n22
BBM
4
1²M
1102
|P|| < (1 (1 - mm)*
WM
μM²
Plugging this back into the red inequality and then unrolling the recursion, we get,
[A((K)]l22 - p (A(K(R 1))112
+ - (1 11) K
27
2Q2
167"0272
H² 16n 0²Q
+
+ at +
|
P3
112
12
12MB²
12M M
+ - (1 - m1)* K
(102 9npor
1 P3
PM
μM2B²
which proves convergence rate upon applying the triangle inequality note that,
1287 3 k
320r/
-2 K3
64n
- K
||V||2 s 2
0²
+
4B2
B
B2
79

---

222
22 (1 [n(+)((K)))))))))))) + 811 8T"
88n K""
21
P
1B²
1B.2 B2
160n 160m "00n
160
112 of (n+kn())
1
uB²
B
This proves the lemma.
We will now tune the step-size following a similar idea to the previous section to achieve the following convergence rate.
Lemma 40. Assuming sufficiently many communication rounds.
R 2 8T P
max
In?
B
4QB
5H2 112
.In3/2
(150)
B2
(
1+
QB P
+
H 1
In(B2 /e)
II([n(B3/ee)
B² > et, and KR 2
max {} we can get the following convergence guarantee
/²MM
for local SGD, initializing at zo
and optimizing functions satisfying Assumptions 1
0²
0 +
T00
|| (A(KR)] =
P2MKR P
12R2
n JOKR
0272
H&G
7002
0² (1 In( In(K))
Rk
W*KR=B
K*KR3
1²KR²
H
Tot
Pot
o (1+ (1++b(()))
+
B2
BA
K2
KAKBRR
where we define K² 2 +
B² n²
6H re
and we pick the step-size,
{
B (E))
n
min
2H
pKR
In
with the choice of is given by
2²
PoRn' AoRR OPPRO AND p2R "PKKS WKRA JABRR
max
MRMKR'
HR
(1+))(()) HAN AAt CH2 FO2
12R2
KAR
12KR
R J BM
PoRK (L+
BABBR
Etarget
where Starget is the target accuracy, greater than or equal to the machine precision.
Proof. We will pick the following step-size,
B
= min 2H pKR
In
where the choice of > will be made explicit later. We will first identify the requirements on problem parameters to guarantee that,
- (1 - n/)**
2
1 P3
(1 - mu)k
< (1- p3)
12T2
B2
227
H² 16n²
16272k2+66n)44''' -647"''K'
< 1
+
4²¹ +
2
12
JPMB B
μ²M
80

---

2T2
BQ
16n
11a
06
(4n) + 64n S
+
112
112
M2M
122
1Q2BB B
160072
B2
+
3H
+
16
In?
(ē)
B2
122
1
N2 M
B
2²K2
47
B²
6474
B2
x
R2 In2
+
R
2Q Ba
3H +
47
B
64-1 1
B²
- (1)
ln2
+
In
$
and
12
12 R
R²R
4
160272
B2
160
Q²
B²
(i)
ln²
ln
NA De M2
2²
R
4T
B2
6474 In
B²
In²
12R2
RA
16Q2 B2
24H
2T
B2
- (1)
+
In
S
R
;
112
16Q2 B
24H
V64T
B
(11)
In
R ;
12
SOT
B2
(111
In
S
KR ;
8
B2
(iv)
In
KKR;
and
4T
B
(0)
In
S
R
So
B
T
5.03 ;
KR
In
maxx
and
112
M
B
3r
B²
[QQB
5H2
(i)
R2
ln
H
p
122
where in (a) we used that 7²/1²² < H² 1//p,
Now we will upper bound 2s as follows.
Ps
(1)
(1
nu)**
1
B2
12QB B2
16a2
72
B2
3H*
In
Ba +1
ln?
R
112
H²
K2
c
472
B²
6474
B2
X
ln²
Ina
R
c
<bh)
.UK
1
In
B
2Q
B²
11
3H
472
B2
+
647
I
(
(B²
R
142
R2
c
1
Rx
eaIkk
B²
(2Q² B2
3Ha
Se
+
In
+ +1+
R
112
14
472
132
6474
(32
ln?
# n+ In
x
12R2
enuK
B²
(2Q² B²
3H
(
(Ar²
472
[2
647
B²
< < -upk exp
In
+1 1 +
In?
Ind
R
42
12222
e
c1/RIn(B2/e)
Ba
(2Q²B² B²
3Hd
(
472
B²
6471
I RNK exp
In
+ 1 1
ln²
+
ln
R
1²2
R2
4 4 R
81

---

1 R
B
1/R
B2
BQ
B2
3H 1²
4-2
B2
647
B
$ Se-ouK exp
In
+1+
In?
In
n
n1222
E a R
where in (a) we use Bernoulli's Inequality and the choice step-size, which implies nn < 1 as well as the fact that /2/2² S. HH/H""/p// /p"; and in (b) we assumed that the conditions derived above to ensure
1- (1 (1-1)) < 1 P3 are true, which allows us to conclude
16a²
-
In?
I 1.
KK M
B
Raising both sides to the power R gives us
p
B
1/R
B
BQ
3/1)
47
B
647
B
S e RRKK exp
In
+1+
In2
+
In
112
122 R2
1r
Rd
B²
(2Q²B²
B
3H
47²
B²
64
B
<(a) -ukk
exp
In
1²2
+ 1+
n4
12
In
+
R
In
< (b)
e -npKR+1
where
in
(a)
we
assume that R In B
and
in
we
assume
8z ln observations, along with the conditions derived so far allow us to simplify the convergence rate as follows,
R2
B2 (1
11+2
# as well as R Sz
3/2
B2
1+
QB
These
|[
2no²
18
4Q2
6H
S e SURRRR V2B²
+
2
+
[V
2M2 B2
n22
1²
20
B
1804
B
B²
S 4e T
In
+
In?
H.MKR
M
12R2
12
B
2
B2
647
B
+k¹
In
+
0. In
+
8- In'
KRKS B
JAKR*
B2
B2R
2H
B
27
B
20t
(1
In(K))
B
+
ln R2
+
In
(
+
In?
KRR
R2KR2
122
B²
160g2
H2
B2
+
In B2
In
ln
1 18R2R5B' B²
B2
c
16
B²
112o (1 (n(K)
B²
+
In
Ind
NOKR"B' B
K2R
where we define n²' = (2 4Q
We are almost done, but we need to define e. Our choice of e simply the maximum of all the terms (after removing the logarithmic factors) in the above convergence bound, except for the first exponential term and the target accuracy étarget, which an input to the algorithm. Like the previous lemmas' proofs, we recall that the term dominating in c also dominates the final convergence rate. This choice of and 17. proves the lemma statement. L
6H
J More Details on the Experiments
In this appendix we describe in full detail how we generated the synthetic data for each client and how we controlled first- and second-orde heterogeneity without altering the inherent difficulty of the individual optimization problems (e.g. their condition numbers or solution norms) for the experiments in Section 6
J.1 Data generation for each client
We consider linear regression problem with parameter dimension d. There are M clients, indexed .....,M. M. For each client m, we generate i.i.d. data (.mm 3m) ~ Dm with
by m I,...,
Bm
(pm, Ia).
ym (2 Bm) + EE, E N0 o
82

---

The corresponding per-sample squared loss is
f(z; (8ms Um)) = (pm (0, pmm)
and the population objective on client m
Pm (a) = (( [f (3, v))] = (x - m (ummpm + Ta) (xr - -mmm + noise
Under suitable bounds on |m noise, and || these objectives satisfy Assumptions | to for all a bounded region.
Controlling first-order (concept) heterogeneity
We fix the norm of each true optimizer to ||=; ll R.. To vary the maximum pairwise distance maxm,n|12 2, Sa, we sample each
R, Um
with
Um E R ||ml 1,
where um is drawn uniformly from the spherical cap of half-angle
((C.) aresin C 2R.
around a fixed "central" random unit vector tp- This ensures ||~ maXm.n | xt S.. so that larger S. increases concept heterogeneity purely by angular dispersion, without changing the optimizer norms. This process is illustrated in Figure 4 In our experiments we fix R. =
R. for all m, and
Vedge
Figure 4: Illustration of sampling unit vectors from spherical cap. We draw cross-section of the unit sphere (circle), mark the central axis uo. and show the cap of half-angle dcC.) (shaded blue).
J.3 Controlling second-order (covariate) heterogeneity
Likewise, we fix each covariance matrix to la and fix the norm of the feature mean to ||/6m||| = 4oo To vary the maximum pairwise mean distance maxm,n I| Pn || = т, sample
E IRdd ||um || = 1,
Pm =
Um
with uh drawn uniformly from the spherical cap of half-angle
((T) arcsin(7/(2
around the same central direction uy. Again, this rotates the means without altering ||/4m||| or the eigenvalues the Hessians 2 Fm pmlli + Ia, whose condition number remains 2g In our
experiments we fix gg 5.
83

---

(for the Local SGD Avg Best Error
2.00
0.16
1.75
0.14
1.50
0.12
Concept shift
1.25
Avg Best Error
0.10
1.00
0.08
0.75
0.06
0.50
0.04
0.25
0.02
0
Covariate shift
Figure 5: Same experiment as in Figure 2a but with R 10, i.e. more communication rounds. Note that the heatmap colors scale changes.
J.4 Hyper-parameter tuning and metrics
For every experimental setting (T, Sx) (or every т in the communication complexxii study) we first sample uh and sample {=t)), then perform 20 independent trials with fresh draws of (um). In each trial we search over a logarithmic grid of step-sizes
[10-3, 10-1) and record either:
The final & error ||="" =²|l after R rounds (for the heatmap in Figure 2ap. or
The minimum number of rounds s Rmaax needed to reach ||"" x+ I communication plot in Figure 2b).
We then average these quantities over the n, uns trials obtain the plotted heatmaps and curves.
J.5 Ensuring fixed problem difficulty
By sampling {*th} and } on fixed-radius spheres and using identity covariances, we keep every client's Hessian condition number and solution norm constant, that any change in convergence communication cost is attributable purely to the angular dispersion (i.e. heterogeneity) parameters т and Ç, not changes in problem conditioning scale.
J.6 Experiments with More Machines and Communication Rounds
include additional experiments in Figures 5 to illustrating the effect of having more machines and communication rounds in the experiments of Figure 2 We note that as suspected increasing the number communication rounds, makes the effect of data heterogeneity less drastic as we can see higher data heterogeneity, hand, we see that increasing the number machines while keeping the communication rounds has a be
able to attain better final error in Figure 5] On the other
mixed effect as perhaps this level of parallelization the SGD noise is still dominating seen in Figure 66 Having said that we again see the benefit of increasing communication rounds at increased parallelization going from Figure 6 to Figure 7 We also run the analogue of Figure 2b with M = 50 Figure
84

---

Local SGD Avg Best Error
2.00
0.10
1.75
-0.08
1.25
Concept shift
0.06
Avg
0.75
0.04
0.50
0.25
0.02
0.00
0
8
10
Covariate shift
Figure 6: Same experiment as in Figure Za but with M 50, i.e., more number of machines. Note that the heatmap colors scale changes.
Local SGD Avg Best Error
2.00
1.75
0.10
1.50
0.08
1.25
Concept shift
1.00
0.06
0.75
0.04
0.50
0.02
0.25
0.00
Covariate shift
Figure 7: Same experiment as Figure 2a but with M 50 and
10. i.e., with more number of machines well communication Note that the heatmap colors scale changes.
85

---

Comm. complexity vs. 2nd-order heterogeneity
Avg. communication rounds to reach error 0.04
100
80
60
40
8 10
Covariate shift
Figure 8: Same experiment as Figure 2b but with M 50.
86


Reviews:
[{"review_id": "MhYUGsp6e3", "reviewer": "Reviewer_un1E", "summary": "This paper explores the advantages of Local SGD over mini-batch SGD in heterogeneous settings. The authors derive new upper and lower bounds on the convergence of Local SGD and demonstrate its superior communication complexity, particularly in settings with low second-order heterogeneity.", "questions": "One of the paper's key contributions is presented as removing the assumption of uniformly bounded first-order heterogeneity. However, prior work in similar convex settings, such as Koloskova et al. (2020), also avoids this assumption, instead using bounded first-order heterogeneity at the optimum.\nGiven that this paper also appears to rely on a similar condition (Assumptions 4 and 5), could you clarify how your contribution differs from what could be derived from these existing results?\n\nI would be happy to reconsider my score after clarification in this regard.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis paper makes a valuable theoretical contribution by clarifying why Local SGD can outperform mini-batch SGD—a phenomenon widely observed in practice but not well-established in theory. The work is also clearly written.\n\nWeaknesses:\nsome assumptions are quite restrictive, such as requiring the objective function to be strongly convex (μ>0).", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time and effort to provide feedback on our work. We are glad that the reviewer found our paper to be clear and appreciated the key technical contribution: identifying conditions under which Local SGD can beat mini-batch SGD.\n\nWe would like to answer the two concerns that the reviewer has raised.\n\n### **Regarding Kolsokova et al. [18]**\n\nTo summarize our argument, **the results in Koloskova et al. [18] analysis can not differentiate between functions with a high v/s a low second-order heterogeneity, while our more fine-grained analysis shows that Local SGD converges faster under low second-order heterogeneity.** We elaborate in more detail below:\n\nWe agree with the reviewer that Kolsokova et al. [18] considered a similar assumption that bounds the gradient heterogeneity at the optimal point. Specifically, the assumption they considered in their paper is a bound on $\\frac{1}{M}\\sum_{m\\in[M]}\\|\\|\\nabla F_m(x^\\star)\\|\\|_2^2$ where $x^\\star$ is an optimizer of the average objective $F$. Their assumption is weaker than ours, but overall, given second-order smoothness and Assumption 5 in our paper, it is straightforward to derive the condition needed for their assumption, so our assumptions are comparable. The main reason we used Assumptions 5 and 6 is to highlight the pathology mentioned in Remark 1 (see Appendix B). \n\nKolsokova et al. [18] consider both the convex and strongly convex settings, but they **cannot show an improvement over mini-batch SGD**. Patel et al. [25] demonstrated that the general convex bounds in Kolsokova et al. are tight, indicating that additional assumptions are needed beyond their setting to demonstrate the benefit of local updates. Patel et al. [25] also conjectured (see their Conjecture 1) that second-order heterogeneity (Assumption 6) might be the needed assumption, providing preliminary evidence to support this. \n\nWe have cited these works (and many more), and we provide guarantees that are strictly better than all of them. Specifically, we prove **the conjecture of Patel et al.**, showing that assumptions about optima (akin to first-order assumptions), along with the second-order heterogeneity assumption (Assumptions 4-6), enable Local SGD to improve over mini-batch SGD. This is something Kolsokova et al. (and all the previous papers) were unable to accomplish. \n\nLet us be more precise. We will use the notation from our paper, except that we will use $\\phi$ and $\\zeta$ instead of $\\phi_\\star$ and $\\zeta_\\star$, as the latter do not compile correctly with exponents in open review. In the strongly convex setting, translating our assumptions to the setting of Kolsokova et al. [18] gives the following convergence guarantee (ignoring polylogarithmic factors in problem-dependent parameters):\n\n$$\\mathbb{E}[\\|\\|x_{KR} - x^\\star\\|\\|_2^2] \\leq \\textcolor{red}{\\frac{\\sigma^2}{\\mu^2 MKR}} +  \\textcolor{blue}{\\frac{H^3\\phi^2}{\\mu^3R^2}} +  \\textcolor{red}{\\frac{H\\sigma^2}{\\mu^3KR^2}}\\enspace,  \\text{for}\\enspace \\textcolor{green}{R= \\tilde\\Omega\\left(\\frac{H}{\\mu}\\right)}\\enspace.$$\n\nTranslating their guarantee requires some work (cf. Table 2 in Woodworth et al. [20]). Note that the requirement for communication rounds in the above rate stems from the exponential term and, in particular, matches the requirement for mini-batch SGD. Furthermore, the first term in the above rate is identical to the \"noise term\" for mini-batch SGD. Both of these together mean that **local updates do not provide a provable improvement over mini-batch SGD based on the result of Kolsokova et al. [18]**. Even when $\\phi_\\star=0$ and $K\\to\\infty$, their result implies that Local SGD needs at least $\\Omega(\\kappa)$ communications rounds, as opposed to constant communication rounds, which is what Local SGD needs in the homogeneous setting (see Theorem 2 due to Woodworth et al. [11] and let $K\\to\\infty$).  \n\nOn the other hand, the rate implied by our Theorem 2 in the same setting is:  \n\n$$\\mathbb{E}[\\|\\|\\hat x - x^\\star\\|\\|_2^2] \\leq e^{-\\frac{\\mu KR}{2H}}B^2 +  \\textcolor{red}{\\frac{\\sigma^2}{\\mu^2 MKR}} + \\textcolor{blue}{\\frac{\\tau^2H^2\\phi^2}{\\mu^4R^2}} + \\textcolor{blue}{\\frac{H^4\\zeta^2}{\\mu^4R^2}} + \\textcolor{blue}{\\frac{H^2\\tau^2\\sigma^2}{\\mu^6KR^3}} +  \\textcolor{red}{\\frac{H^2\\sigma^2}{\\mu^4KR^2}}\\enspace, \\quad \\text{for}\\enspace \\textcolor{green}{R = \\tilde\\Omega\\left(\\frac{H\\tau}{\\mu^2} \\right)}\\enspace.$$\n\nAs opposed to Kolsokova et al. [18], our rate's requirement on communication rounds reduces to a constant when $\\tau\\to 0$. This is because Kolsokova et al. [18]'s analysis **cannot benefit from $\\tau \\ll H$**. Furthermore, note that when heterogeneity is low ($\\zeta, \\tau, \\phi\\to 0$) and $K\\to\\infty$, then our convergence rate may become arbitrarily small, meaning that we can also prove the benefit of local update steps over mini-batch SGD in regimes of low data heterogeneity. This matches the expectation in the homogeneous setting. The results of Woodworth et al. [20] and Patel et al. [25] also predict that this should occur in regimes of low data heterogeneity; however, they require the restrictive assumption of uniformly bounded gradient heterogeneity. \n\nFurthermore, since we make more fine-grained assumptions, note that in the regime where $\\tau=0$ and $\\zeta\\ll\\phi$, our rate is significantly better than theirs, even if we ignore our improved communication complexity. This is why we demarcate between $\\tau, \\zeta, \\phi$, to delineate all relevant sources of data heterogeneity. We also want to underline how our paper fills the quadratic v/s non-quadratic gap by studying rates under third-order smoothness. \n\nWe hope this addresses the reviewer's concern. We assure the reviewer that we are **very familiar** with Kolsokova et al. [18]'s paper as well as all the follow-up work. If our paper is accepted, we will ensure that it includes a table summarizing the convergence rates from the seminal papers in this area. Currently, we have some discussion after Theorem 2, but we will make it more explicit by converting it to a remark. \n\n\n### **Why We Need Strong Convexity**\n\nFirstly, we would like to point out that our lower bound is intended and stated for general convex functions, so not all our results assume strong convexity.\n\nOur upper bounds do assume strong convexity, but we believe that understanding the role of data heterogeneity for strongly convex functions is worthwhile, and many existing works (including Kolsokova et al. [18]) also consider strongly convex functions for that reason. From a practical point of view, convex optimization problems often exhibit strong convexity due to regularization (for instance, consider logistic regression with an L2 penalty). \n\nFurthermore, we believe understanding the precise rates for strongly convex functions is an essential step towards extending our analyses to general convex functions. As the reviewer can note about our analyses, they are extremely non-trivial and require considerable care in writing the correct recursions, tuning the step size, and adjusting other hyperparameters. We attempted to use our strongly convex analysis as a stepping stone, hoping to perform a convex-to-strongly-convex reduction —a common approach in the optimization literature. Unfortunately, the parameter dependence we obtained was not ideal, which is why we did not report those results (see lines 244-254). \n\nWe believe that removing the strong convexity assumption is a non-trivial task. For instance, we cannot state a version of Lemma 2 when we do not have strong convexity, as the machines may converge to solutions that are far apart from each other between communication rounds. Strong convexity and some control on first-order heterogeneity precisely avoid this problem. There is also no existing work that provides similar guarantees in the convex setting. For instance, the rate due to Patel et al. [25] (see their Theorem 3) requires the more stringent uniform bounded first-order heterogeneity. In the non-convex setting, Patel et al. [30] provide a rate that improves with a small $\\tau$, but for a more complicated **variance-reduced version of Local SGD**. It is unclear what led to improved rates in their paper: local updates or the particular variance reduction. \n\nThat said, we have a few ideas to extend our work to the convex setting. This would involve deriving a version of Lemma 2 in terms of the gradient norms on each machine. However, so far, we have not been able to make this coupled recursion work. **It is possible that, without strong convexity, the kinds of improvements shown in our paper may not be achievable for Local SGD**.  We are also unsure about how to prove such a hardness result, as incorporating strong convexity into our construction for Theorem 1 does not imply this. Another clue as to why this may be challenging comes from the quadratic setting. As discussed in Appendix C.3 in Proposition 2, for convex quadratic functions, the fixed point of Local SGD is the minimum norm interpolator for the problem under a different geometry. It is unclear whether controlling just second- and first-order heterogeneity will reduce the fixed-point discrepancy in the directions \"not shared\" or \"mis-aligned\" (due to non-commutativity of Hessians) between the machines.     \n\nHopefully, this discussion highlights that our strong convexity assumption is not a careless oversight, and the general convex setting is a significant technical extension. It remains an open problem whether such rates can even be obtained, and as such, our paper only partly answers the conjecture of Patel et al. [25]. We are actively investigating how to close this critical gap in the literature. \n\n### **Summary**\n\nWe hope that we have addressed the reviewer's concern. Since, besides these issues, the reviewer had a positive impression, we sincerely hope they will consider raising their score and vouch for accepting our paper."}, {"review_id": "L1O5gnLrfV", "reviewer": "Reviewer_ag4U", "summary": "This manuscript studies distributed optimization using Local SGD with full node participation. The authors present a refined analysis for convex objective functions with high-order smoothness by introducing the second-order data heterogeneity / similarity, providing both upper and lower bounds on convergence complexity. The results emphasize that Local SGD performs well in homogeneous data scenarios.", "questions": "- Comparing Figures 1a and 5, it seems that as R increases, the average best-final error gap narrows. If R grows further, will the convergence errors of Local SGD continue to converge?\n\n- The algorithm assumes full node participation, which limits scalability. What challenges would arise if node sampling were incorporated?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "__Strengths__\n\n- The paper presents a new theoretical lower bound for Local SGD under second-order similarity conditions and includes sufficient technical details.\n\n__Weaknesses__\n\n- The significance of the contribution is unclear. The main conclusion—that Local SGD performs well in homogeneous data settings—is intuitive, as model divergence across nodes is minimal in such scenarios, reducing the need for frequent communication. While the analysis is refined, it does not yield fundamentally new insights compared to prior work.\n\n- There are several overstatements. For instance, in line 25, the claim that Local SGD “consistently outperforms other first-order methods” is inaccurate. In heterogeneous settings, methods like SCAFFOLD [19] have been shown to outperform Local SGD. Similarly, in line 33, SCAFFOLD is proven to have advantages over SGD.\n\n- The comparison between Assumption 6 (second-order similarity) and Assumption 7 (first-order similarity) is not entirely fair, as Assumption 6 additionally requires twice differentiability, making it more restrictive in a different sense.\n\n- This work only analyzes the case when the second-order similarity is small, but does not discuss what happens when it is large. For example, in the comparison between Equation (3) and Lemma 2, when \\tau is large, the consistency error bound given by Lemma 2 may not be tighter than that of Equation (3), due to its dependence on critical parameters such as 1/\\mu and K. Similar issues also appear in the discussion of the main results. This one-sided analysis further limits the significance of the work—especially given that data heterogeneity is common in federated learning scenarios.\n\n- Theorem 2 (and other theorems) does not clearly display the dependency on \\tau. Upon closer inspection, the term R (related to \\tau) appears in the denominators of multiple terms, implying that when data heterogeneity is small, the steady-state error actually increases. However, the authors only highlight the positive effect on convergence speed.\n\n- The experiments only show the communication efficiency of Local SGD, without evaluating its impact on sampling or iteration complexity—particularly relevant since it may increase the steady-state error.\n\n- The experiments are conducted only on synthetic settings, lacking real-world datasets to adequately support the theoretical claims.", "was_revised": true, "final_justification": "Most of my technical concerns have been addressed. I raise my score to 4.", "rebuttal": "We thank the reviewer for their feedback. However, we believe there are some major misunderstandings about our setting and results, and we urge the reviewer to reconsider their score after reading our response.\n\n## Allowed Values of $\\tau$\n\n> This work only analyzes the case when the second-order similarity is small........ This one-sided analysis.......\n\n**This is not true**. Note in Assumption 6, we say that $\\tau\\leq 2H$, to highlight that $\\tau$ is trivially upper bounded by smoothness. Thus, in the worst case, $\\tau$ will just become $2H$ in our results. With this in mind, the reviewer's objection that the bound in Lemma 2 might not be useful is incorrect. Even if $\\tau=2H$, the bounds in Lemma 2 and equation (3) are **not comparable**, because (3) requires the much stronger and opaque Assumption 7 where it is unclear how $\\zeta$ in the assumption will even depend on $\\mu, K, \\eta$, something Lemma 2 makes very explicit.\n\nWith this in mind, **we disagree with the assessment that our analysis is \"one-sided\"**, because even if $\\tau=2H$, our results are not worse than existing results in the relevant regime when $K$ is large. We have discussed this issue extensively in our response to Reviewer un1E, comparing our results with those of Kolosokova et al. [18]. To summarize our main point in that response, it is well known what to expect when second-order heterogeneity is high, as existing analyses do not differentiate between functions with high or low second-order heterogeneity (at least not without assuming restrictive gradient similarity). The interesting case is indeed what happens when it is small, and to our knowledge, ours is the only analysis that can highlight the benefit of local updates when $\\tau \\ll H$ without any restrictive assumptions.\n\n## $R$ in Theorem 2\n\n> Theorem 2 (and other theorems) does not clearly display the dependency on \\tau.......\n\n**Note that the smallest value for $R$, the number of communication rounds, is $1$; it is a positive integer, and does not approach $0$ even if $\\tau=0$!** We discuss this explicitly in the first paragraph of our introduction, and Figure 2 illustrates the intermittent communication setting. With this in mind, the issue the reviewer raised is completely unfounded: our results do not deteriorate when data heterogeneity is small. While Theorem 2 provides a lower bound for $R$, as soon as this lower bound is smaller than $1$, it becomes vacuous. We wonder if the reviewer confused the asymptotic notation $\\Omega$ with $\\theta$? If so, **we hope they will change their review upon realizing this**. \n\nEssentially, as detailed in response to Reviewer un1E, our constraint on $R$ (in Theorem 2) improves when $\\tau\\to 0$, as opposed to mini-batch SGD, which must always communicate $\\tilde\\theta(\\kappa)$ times, no matter how small $\\tau$ is. Along with Theorem 1, this highlights the positive role of a low second-order heterogeneity on the required number of communication rounds. In fact, as we show in Theorem 4, when $\\tau=0$, by choosing a $K$ large enough, we can indeed get away with a single communication round, something well known for the case of homogeneous quadratics, but not for Local SGD in the heterogeneous setting. This characterization is our main contribution. \n\n## SCAFFOLD\n\n> There are several overstatements. For instance, in line 25........\n\nWe assure the reviewer that we are **very familiar** with the SCAFFOLD paper. Having said that, none of the existing analyses show that SCAFFOLD can theoretically improve over mini-batch SGD even when there is no second-order heterogeneity (see Table 2 in Woodworth et al. [20]). Furthermore, as pointed out by the experiments in the paper titled \"Adaptive Federated Optimization\" by Reddi et al., and further underlined by Wang et al. [8], **SCAFFOLD and FEDAVG have roughly identical performance** on many realistic federated datasets. Thus, there is both theoretical and empirical evidence to support the claims made in the paper, and Local SGD remains the simplest and most widely adopted federated optimization algorithm. This is why we choose to address the theoretical gap of explaining its \"unreasonable effectiveness\". We will include a remark about SCAFFOLD in our revision. \n\n## Experiments\n\n> The experiments only show the communication........\n\nTo clarify, in our setting, iteration and sampling complexity are equivalent, and both are $K$ times the communication complexity, as each stochastic gradient is computed using a new sample. This means that in the transition from Figure 1a to Figure 5, these complexities increase. And in Figure 1b, only $K$ is fixed, and we plot $R$ as a function of increasing co-variate shift, thereby precisely showing how all of these complexities would increase with co-variate shift.  \n\n> Comparing Figures 1a and 5......\n\nIndeed, in the regime where $R$ is large, heterogeneity has less impact on Local SGD. This is because, with a very large communication budget, one can set the step size very low, essentially making Local SGD resemble mini-batch updates. This is not the most interesting setting, which is why we report experiments with $R=5$ (a low communication budget) in the main paper. We observe that as the complexity of our task increases, for instance, by increasing the dimensionality of our problem to **d=50**, we obtain a similar figure to Figure 1a, even with a larger communication budget of $R=10$ (as in Figure 5); we will include these experiments in our revision. Also note that Figure 1b in the current paper illustrates how the communication budget must increase with rising $\\tau$. \n\n> The experiments are conducted only on synthetic......\n\nThere are dozens of papers, including several we have cited, that conduct experiments on other \"tasks.\" Whether academic papers truly use \"real\" datasets is questionable, and many experiments in Federated Learning are performed in industry using proprietary datasets. That said, we believe it is already well established (for instance, due to the work by Reddi et al. mentioned above) that Local SGD is a highly effective algorithm in practice. Are there any specific datasets that the reviewer thinks we should test on, especially where we can make a novel point by controlling both the covariate and concept shift (like we do in Figure 1a)? We will try to investigate whether we can artificially control covariate and concept heterogeneity on the FMNIST dataset, and if successful, we will report those results in our final version. \n\n\n## Partial Participation\n\n> The algorithm assumes full node participation.....\n\n**This is a significant extension for our work**. Let us consider the case of sampling each client from some meta-distribution over clients, i.e., $m\\sim P$, and assume we are interested in optimizing $$F(x) := \\mathbb{E}_{m\\sim P}[F_m(x)]\\enspace.$$ \n\nThis is arguably the simplest setting for studying partial participation and has been explored in Karimireddy et al. [28], Patel et al. [30], etc. These papers analyze the client sampling with a new set of clients sampled i.i.d. from $P$ each communication round, by assuming that the inter-client variance of gradients is uniformly bounded at every point, i.e., $$\\mathbb{E}_{m\\sim P}[\\|\\|\\nabla F_m(x) - \\nabla F(x)\\|\\|_2^2]\\leq G^2\\enspace,\\forall x\\in\\mathbb{R}^d\\enspace.$$\n\nWhile we can also provide all our results under this assumption, the primary objective of our paper is to avoid something akin to Assumption 7, and this assumption on inter-client variance is precisely that. One alternative is to only assume the inter-client variance assumption at the optimizers of the average objective $F$, analogous to Assumptions 4-5. However, this relaxation makes the analysis very challenging, as we must carefully handle the randomness in sampling a client and the randomness involved in sampling the stochastic gradients for that client. Due to multiple local updates, the stochastic gradients \"leak\" information about the sampled client, thus breaking a naive independence argument often used in the existing papers. We believe that extending our results to the partial participation setting is possible, as Lemma 2 essentially allows us to unroll the local updates to the last communication round, at which point we can utilize the i.i.d. property of client sampling. However, this extension would require significant additional work, which is why we leave this for the future. \n\n## Our Contribution\n\n> The significance of the contribution is unclear.....\n\nFirst, our paper goes well beyond the homogeneous setting—which is well understood (see Woodworth et al. [11], Glasgow et al. [23]) but unrealistic in practice—and analyzes the exact forms of heterogeneity that govern Local SGD’s performance. Prior work (e.g., Wang et al. [6,8], Patel et al. [25]) either aggregates heterogeneity into coarse metrics or imposes strong gradient‐similarity assumptions. We close this gap by highlighting a necessary and sufficient characterization, which we believe is intricately linked to covariate shift and concept shift (Figure 1), thus providing an important insight for practitioners who seek to balance local computation against communication (discussed in lines 334-342). \n\nAnd as far as the need for theory. Suppose one were teaching Local SGD in a graduate class. Would stating merely “Local SGD works well in homogeneous settings” suffice? Would we hold the convergence theory for, say, SGD, to the same standard? Perhaps not. Heterogeneity is what makes Federated Learning scientifically interesting. Thus, understanding precisely what heterogeneity does to Local SGD, an algorithm almost synonymous with Federated Learning, is a fundamental question at the core of the field. While there are still many open questions, we believe our results deliver both rigorous theory and actionable guidelines, thus filling a critical theoretical gap and offering clear, practical, scientific, and pedagogical value."}, {"review_id": "hEM3CzKKwY", "reviewer": "Reviewer_MhSC", "summary": "This paper investigates the convergence behavior of Local SGD in the presence of heterogeneous data across clients. The authors focus on understanding how second-order heterogeneity affects the performance and communication complexity of Local SGD. The main contributions are:\n\n1. A new lower bound that quantifies how convergence degrades with increasing second-order heterogeneity.\n\n2. A new convergence rate for local SGD.\n\n3. A synthetic regression experiment validating the theoretical predictions.", "questions": "Some minor concerns are listed here.\n\n1. In line 15, the authors state that \"$F_m$ is the stochastic objective\". This is not accurate: there is no stochasticity in $F_m$.\n\n2. In line 110, the authors state that \"without this condition, some clients may not benefit from collaboration\". This argument is vague to me. In terms of convergence rate, distributed/decentralized methods are almost always slower than the vanilla counterpart. \"Collaboration\" is necessary for other (realistic) reasons.\n\n3. In lines 133-136, the authors mention \"distributed proximal-point methods\" and cite [50]. But [50] proposes a Newton-type distributed method.\n\n4. In line 329, what does it mean by \"monotonic relationship\"? The plot is not monotonically increasing.", "limitations": "yes", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**\n\nI like section 6 which presents simple synthetic experiments to show the motivation.\n\n**Major concerns**:\nMy major concerns lie in the theoretical results.\n\n1. Theorem 1 presents a lower bound for **convex quadratic** functions.\n\n(a) Does the same lower bound hold for **any** functions satisfying the blanket assumptions? If not, the authors may consider to state their first contribution more precisely in Section 1 to avoid overclaiming.\n\n(b) In line 151, the authors state that \"when $\\phi_\\star$ is small and $K$ is large, the lower bound is dominated by the term $\\tau B^2 / R$\". I cannot totally agree with it. In the extreme case where $\\phi_\\star = 0$, all the local quadratic functions have the same optimum, so communication is not needed at all. Then, without stochasticity, the convergence rate is lower bounded by the worst conditional number of all the local functions, not $\\tau$, and the convergence rate should be linear, not $\\mathcal{O}(1/R)$. So the statement is somewhat pointless or inaccurate.\n\nAnother case is $\\phi_\\star$ is small but nonzero. Then when $K \\to \\infty$, agents never communicate and the algorithm never converges. This phenomenon, again, is not captured by the term $\\mathcal{O} (\\tau B^2 / R)$.\n\n(c) In line 158, the authors state that \"we extend the construction of Patel et al. by introducing an additional dimension\". I was only able to understand this sentence after reading the appendix, which indicates a need for clearer exposition in the main text. In addition, this sentence does not justify why we need $\\tau$ instead of other quantities, e.g., the worst condition number of all local quadratic functions; it seems the choice of $\\tau$ is arbitrary...\n\n2. The authors claim that Lemma 2 is novel and distinct from existing literature, but I have reservations about this assertion. In a recent line of research on decentralized optimization [1,2], a similar proof technique has been introduced. In particular, those papers consider using graph sequences with finite-time consensus in decentralized optimization. So consensus error will somehow \"disappear\" periodically due to the suitable choice of communication networks. The same proof technique has also been utilized in local updates (see, e.g., [3] and references therein). The authors may consider to compare the current work with this line of research.\n\n(a) Lemma 2 requires $\\eta < 1/H$, but in line 213, the authors state that \"our bound does require setting $\\eta = \\mathcal{O}(1/K)$\".\n\n(b) In line 214, the authors state that \"an alternative bound in Appendix I.3 that avoids this ($\\eta = \\mathcal{O}(1/K)$)\". However, I find the bound in Lemma 32 not informative at all: the consensus error will never vanish under the stated stepsize condition. Lemma 32 simply says that the difference between $x_m^t$ and $x_n^t$ is bounded by that between $x_m^\\star$ and $x_n^\\star$, which is trivially true because $x_m^t$ converges to $x_m^\\star$ as $K \\to \\infty$. If the algorithm does not converge with this stepsize choice, it is unclear what value these results provide.\n\n3. Theorem 2 states the convergence rate of local SGD.\n\n(a) How should I compare Theorem 1 and Theorem 2? Does the lower bound in Theorem 1 match the upper bound Theorem 2? If they are incomparable, then what is the connection between Sections 3 and 4?\n\n(b) Assumption 1 says $\\mu \\geq 0$, but Theorem 1 certainly fails when $\\mu=0$, as pointed out in lines 244-249.\n\n(c) Assumption 1 imposes $Q$-Lipschitz continuity of the Hessian, which, I believe, is referred to as “third-order smoothness” in the paper. However, Theorem 2 does not involve $Q$ at all. Does this imply that $Q$ has no impact on the convergence rate? If so, then what is the purpose of Section 5 then?\n\n(d) In lines 226-227, the authors claim that \"with a small $\\tau$, Local SGD can converge much faster than mini-batch SGD\". I am not convinced by this claim and believe it requires further justification. First, the dominating term in both rates is $\\sigma^2 / (\\mu^2 M K R)$ rather than the exponential term.  As such, the two rates appear essentially the same. the parameter $K$ has different interpretations in Local SGD and mini-batch SGD, so I do not believe the two are directly comparable. Therefore, the additional factor of $K$ in the exponential term of Theorem 2 does not carry much significance in my view.\n\n(e) In lines 227-228, the authors claim that \"when $K \\to \\infty$, the communication complexity of Local SGD for target accuracy $\\epsilon$ and large $K$ satisfies ...\" However, this is misleading. As $K \\to \\infty$, communication effectively ceases, and Local SGD will not converge to the global optimum. Therefore, the limit $K \\to \\infty$ does not reflect a meaningful or practical convergence behavior.\n\n4. In Section 5, the authors restrict the attention to quadratic objectives and provide an upper bound involving $Q$ (defined in Assumption 1).\n\n(a) How should we compare Theorem 2 and Theorem 4. Logically speaking, the bound in Theorem 4 should be no larger than that in Theorem 2. Is that correct?\n\n(b) How should we compare Theorem 1 and Theorem 4? Do the lower and upper bounds match? At least on the surface, they do not appear to align. How, then, should these two results be interpreted? Is one of them not tight, or are both potentially loose?\n\n(c) I do not see the motivation to include $Q$ in the analysis. In other words, why should $Q$ be the correct measure, rather than, e.g., the condition numbers of all the quadratic functions?\n\nIn addition to the technical issues discussed above, I strongly encourage the authors to improve the overall clarity and presentation of the manuscript.\n\n1. The introduction is difficult to follow, as it attempts to present too much information at once, which makes the narrative feel overloaded. I also recommend that the authors present the motivation of the work more clearly without too many technical details, so that readers can easily understand the problem setting and the significance of the results. A clearer and more focused introduction would greatly improve the readability and impact of the paper.\n\n2. On first reading, I expected Section 3 to start presenting the main results of the paper. However, the section opens with an extensive discussion of related literature, which detracts from the focus and makes me really confused about the purpose of this section.\n\n3. The authors frequently reference forward to materials that appear later in the paper. While occasional forward referencing is acceptable, excessive use can hinder readability and is generally discouraged in academic writing. \n\n(a) For example, in the very first paragraph of Section 1, the authors refer to Figure 2, which appears only in the appendix. This raises confusion: if the figure is essential for understanding the setup, it should be included in the main text; otherwise, if it is non-essential, the reference should be removed to avoid disrupting the flow of reading.\n\n(b) A similar issue arises in the second paragraph, where the authors refer to Equation (2) on page 2 before establishing sufficient context. Forward references like this can be disorienting for readers and should be used sparingly. I recommend reordering the content to introduce necessary concepts before referencing them.\n\n[1] Ying et al. Exponential graph is provably efficient for decentralized deep training. NeurIPS, 2021.\n\n[2] Nguyen et al. On graphs with finite-time consensus and their use in gradient tracking. SIAM J. on Opt., 2025.\n\n[3] Alghunaim. Local exact-diffusion for decentralized optimization and learning. IEEE TAC, 2024.", "was_revised": true, "final_justification": "This paper contains some nontrivial contributions, but I believe substantial improvements in writing are needed, ideally under close supervision. The work attempts to present three contributions within a single paper, but lacks cohesion and coherence. I suggest the authors improve the overall flow and structure, aiming to present a more complete and unified narrative.\n\nIt is regrettable that the authors expressed a strong perspective in their response to my concerns, yet may have deliberately chosen not to submit it as an official rebuttal. This approach risks undermining the transparency and fairness of the review process, and, even if the paper were accepted, could diminish the perceived credibility and impact of the work.", "rebuttal": ""}, {"review_id": "7a9dMyszYK", "reviewer": "Reviewer_9Ysu", "summary": "This paper provides a refined convergence analysis of Local SGD under the second-order heterogeneity and the third-order smoothness settings.", "questions": "**Questions**:\n\nThis paper gives a more fine-grained analysis of Local SGD. This may lead to different conclusions compared to the existing works in FL. Recently, [+2] showed that sequential FL is better than parallel FL (Local SGD) when the heterogeneity is relatively high, by comparing their bounds of sequential FL with the bounds of Local SGD [+1]. I am curious to know whether the new bounds (established in this paper) will cause a different conclusion compared to [+2]. Could you kindly compare the bounds between sequential FL and Local SGD? If possible (the time of rebuttal is enough), please provide some preliminary experiments (on quadratics or linear regression). I think the comparison can help improve the impact of this paper.\n\n[+2] Sharp Bounds for Sequential Federated Learning on Heterogeneous Data, JMLR, 2025.\n\n**Suggestions**:\n\n1. Figures: It would be better to use PDF format for figures.\n\n2. Comparison with the related works: It would be better to add the tables to present the differences (of the upper and lower bounds) compared to the existing works like Patel et al. [25]'s Table 1. They can be added in an additional page (if accepted) or in the appendices.\n\n3. Assumptions: Currently, the assumption $\\mathbb{E} ||\\nabla f(x;z) - \\nabla F_m(x) ||_2^2 \\leq \\sigma^2$ is seen as one part of Assumption 2. Since this assumption has appeared multiple times in the proofs, I recommend to write it as an independent assumption.\n\n4. Lines 222 and 228: It would be better to use `\\text{MB-SGD}` and `\\text{L-SGD}` in LaTex to improve the readability.\n\n5. Appendices: The current organization of the appendices are not clear, especially the sections of the upper bounds (Appendices E-J). The titles like \"Double Recursion for Consensus Error\" are not friendly for the readers who are unfamiliar with the settings. I recommend to use \"Proof of Theorem 1\" (see [+3]'s TOC of appendices) and put the current titles at the beginning of the corresponding sections to explain the purpose of the sections.\n\n6. Proofs: Adding some sketches of the proofs can improve the readability (see [+1]).\n\n7. Lemma 21: It would be better to add the proof of Lemma 21 for completeness.\n\n[+3] Minibatch vs Local SGD with Shuffling Tight Convergence Bounds and Beyond, ICLR, 2022.\n\n**Score**:\n\n1. Currently I give the score of 4. This is only because I have not yet checked all the proofs (I mainly checked the proofs of the upper bounds), due to the very heavy workload of NeurIPS. I know this is unfair for this good paper, so I will also consider the reviews of the other reviewers.\n2. However, I cannot guarantee a higher score (i.e., 6) for now, as this topic (the unreasonable effectiveness of Local SGD) has been studied for several years and this theory is still limited to strong convexity.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. This paper provides a more refined analysis for Local SGD compared to Patel et al. [25].\n2. The topic of explaining the unreasonable effectiveness of Local SGD is important.\n3. The amount of work in this paper is sufficient, and the theory is solid and rigorous.\n\n**Weaknesses**:\n\nI have not found any serious weaknesses. Some minor problems (and questions) are as follows:\n\n1. 1-st line of the equation between Lines 1209 and 1210: Should \"$+$\" be \"$-$\" before $2\\langle\\xi_t^m,\\xi_t^n \\rangle$?\n\n2. 1-st line of the equation between Lines 1213 and 1214: Same as Point 1.\n\n3. 1-st inequality of the equation between Lines 1213 and 1214: It is well known that $(x-y)^4 = x^4 - 4x^3y + 6x^2y^2 - 4xy^3 +y^4$. Thus, is it necessary to use Cauchy Schwartz inequality for $\\mathbb{E}[{(\\langle\\xi_t^m,\\xi_t^n \\rangle)^2}]$ here?\n\n4. 3-rd line of the equation between Lines 1229 and 1230: Should \"$=$\" be \"$\\leq$\"?\n\n5. 2-rd inequality of the equation between Lines 1253 and 1254: It uses $||x_t - \\eta \\nabla F(x_t) - x^\\star + \\eta \\nabla F(x^\\star) || \\leq (1-\\eta\\mu)^2 ||x_t - x^\\star||^2$ here. In fact, it is well known that $||x_t - \\eta \\nabla F(x_t) - x^\\star + \\eta \\nabla F(x^\\star) || \\leq (1-\\eta\\mu) ||x_t - x^\\star||^2$ (see [+1]'s Lemma 6). So I want to know whether this trick helps improve the existing bound. If not, why we use it here?\n\n6. 6-th inequality of the equation between Lines 1278 and 1279: Should \"$(\\nabla^2 F_m(\\hat x_t^m) - \\nabla^2 F_m(x_t) + \\nabla^2 F_m(x_t) - \\nabla^2 F(x_t)  )$\" be  $(\\nabla^2 F_m(\\hat x_t^m) - \\nabla^2 F_m(x_t) + \\nabla^2 F_m(x_t) - \\nabla^2 F(x_t) + \\nabla^2 F(x_t) )$? Is one term $\\nabla^2 F(x_t)$ missing?\n\n7. Line 1279: What does \"$\\in m \\mathcal{H}_t$\" mean?\n\n8. The last equality of the equation between Lines 1293 and 1294: The \"$=+$\" is a typo.\n\n9. Line 1295: The $\\eta$ before $\\nabla F_m(x_t^m)$ is missing.\n\n10. Line 1302: Should \"Using Lemma 16\" and \"taking a whole square\" be exchanged?\n\n11. Line 1362: Where the fact $(1-\\eta \\mu)^K\\leq \\frac{1}{2}$ is used?\n\n12. Line 1371: The phrase \"holds the hides\" seems a typo.\n\n13. Line 1394: The definition of $\\gamma_j = j- \\delta(j)$ is inconsistent in the context. Should it be $\\gamma_j = j-\\delta(t)$? In addition, the sentence \"note that the term with $1/\\gamma_{t-1}$ becomes 1 when $t-1=\\delta(t)$\" is also unclear.\n\n14. 3-rd inequality of the equation between Lines 1395 and 1396: Is $\\sum_{j=\\delta(t)}^{t-1}\\frac{1}{j+1-\\delta(t)}$ be upper bounded by $\\ln (t-\\delta(t))$? In fact, I think it is upper bounded by $1+\\ln(t-\\delta(t))$ if using the integrals. In addition, where the fact $..\\leq \\frac{1}{\\eta \\mu}$ before Line 1396 is used?\n\n15. Line 1401: $\\delta(j) = K(r-1)$ is unclear. Should it be \"$\\delta(j) = K(r-1)$ when $K(r-1) \\leq j \\leq Kr-1$\"?\n\n[+1] SCAFFOLD Stochastic Controlled Averaging for Federated Learning, ICML, 2020.\n\nIf the problems I raised above are wrong, please free free to point them out.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my concerns.\n\nConsidering the revisions promised by the authors during the rebuttal period, I tend to give a positive rating.", "rebuttal": "We thank the reviewer for their time and effort in reviewing our paper. Regardless of the decision, the reviewer's comments will be very useful to us in improving our paper. Not only did the reviewer carefully read through the main body, but also several parts of the appendix. We truly appreciate it! \n\nSince the reviewer stated that they did not find any major weaknesses in the paper and did not raise any major technical issues, we will attempt to address the questions the reviewer raised about sequential FL and also respond to the issues/typos in the writing.\n\n## Addressing Listed Weaknesses\n\n1, 2, 3: We agree with these comments. We apologize for this error with the sign. We will correct the Lemmas. The reviewer is right, one could state a simpler proof for these lemmas. \n\n4: Correct, we will add an upper bound after the first line in this series of equations. The conclusion should still follow. \n\n5: We suspect the reviewer missed a whole square on the LHS in their comment (based on looking at Lemma 6 in SCAFFOLD). Having the $(1-\\eta\\mu)^2$ term, as opposed to $(1-\\eta\\mu)$, is important, as we currently do it using Lemma 16 with a specific value of $\\gamma$. Note that it is easy to see (b) by just applying the mean value theorem to $\\nabla F(\\cdot)$ (to quickly verify that the functions were quadratic). There may be a way to utilize Lemma 6 of SCAFFOLD in conjunction with a different version of Lemma 16; however, the approach we take is effective in achieving the desired rate. If we misunderstood this comment, please let us know!  \n\n6: No, the additional term the reviewer mentioned would just be zeroed out because $\\frac{1}{M}\\sum_{m\\in[M]}\\nabla^2 F(x_t)\\cdot(x_t - x_t^m) = \\nabla^2 F(x_t)\\cdot\\frac{1}{M}\\sum_{m\\in[M]}(x_t - x_t^m) = 0$. It is our fault; we should have made that more explicit! \n\n7: It means the random variable is measurable under the sigma algebra generated by $\\mathcal{H}_t$. Perhaps we should have mentioned this notation before using it! \n\n8, 9, 10: Thanks for catching these. \n\n11: That shouldn't have been there (it's from an older version of the analysis), we are just using $1 - (1-\\eta\\mu)^K < 1$. Thanks for catching this!\n\n12: Yes. It should just be: \"hides the\".\n\n13: Note that for $j$ between two communication rounds, they are the same, as $\\delta(j) = \\delta(t)$. \n\n14: Yes, our bad, it should be $1 + \\ln(K)$, which of course only changes the numerical constant, but something we will correct. The $1/\\eta\\mu$ upper bound line should be removed; we were previously using it in the inequality above (a), but we ended up just upper-bounding $(1-\\eta\\mu)^{2(t-1-j)} - (1-\\eta\\mu)^{2(t-1-\\delta(t))}$ by $1$. \n\n15: Thanks, we will add that clarification about the range of $j$.  \n\n## On Suggestions about Writing\n\n1: We will use the PDF format for potentially better load-up on readers. \n\n2: We will include a table in the additional page. We have, in fact, created a table that is more exhaustive than that of Patel et al.\n\n3: This is a good point. Initially, we used $\\sigma$ for both assumptions for simplicity. However, after submission, we improved all our analyses to include different constants $\\sigma_2$ and $\\sigma_4$. One crucial takeaway from this analysis (which we would include in our revision) is that the $\\sigma_4$ terms actually improve more from increasing $K$ than the terms with $\\sigma_2$ do, something our current analysis ignores due to loosely upper-bounding the $\\sigma_4$ terms. This is actually an interesting insight, because in practice, the fourth moment of the noise can be significantly larger than the second moment. \n\n4: We will do that. \n\n5: We agree with this. In hindsight, we did not expect the appendix to be this long, and the current nomenclature might have been sufficient for a shorter proof. Still, our hope was that Section E would provide some structure and support for a reader unfamiliar with the proof style. Perhaps the fact that this is not the first appendix section makes this harder already! \n\n6: Again, we will restructure the current Section E so that it does a better job of providing a proof sketch. \n\n7: We will do that. \n\n## On Comparison to the Sequential Setting\n\nThank you for bringing this work [+2] to our attention; it is indeed interesting, and we were not previously aware of it. \n\nHowever, hopefully the reviewer recognizes that in many settings where Parallel FL is used, sequential FL (at least in the most naive sense) cannot be implemented. We are considering cross-device settings (or even cross-silo settings with many servers), where the total physical time would be too extensive for Sequential FL. Having said that, it is likely that many cross-device settings with partial client participation are already utilizing a hybrid approach between Sequential and Parallel FL, due to the structure of client sampling around the globe. So the comparison between these extremes is interesting. \n\nLet us compare the strongly convex rates in Corollary 4 of [+2]. The function sub-optimality they provide (translated to our notation) is given by (up to poly-logarithmic problem-dependent factors) $$\\text{\\textbf{SFL (L-SGD):}}\\quad \\mu B^2 e^{-R/\\kappa} + \\frac{\\sigma^2}{\\mu MKR} + \\frac{H\\sigma^2}{\\mu^2 MKR^2} + \\frac{H^3\\phi_\\star^2}{\\mu^2 MR^2}\\enspace.$$\n\nCompared to this, our guarantee (in Theorem 3) gets the following rate:\n$$\\text{\\textbf{PFL (L-SGD):}}\\quad \\mu B^2 e^{-KR/\\kappa} + \\frac{\\sigma^2}{\\mu MKR} + \\frac{\\tau^2 H\\phi_\\star^2}{\\mu^2R^2} + \\frac{H^3\\zeta_\\star^2}{\\mu^2R^2} + \\frac{H\\tau^2\\sigma^2}{\\mu^4KR^3}  + \\frac{H\\sigma^2}{\\mu^2 KR^2} \\quad \\text{for} \\quad R = \\tilde\\Omega(\\tau\\sqrt{\\kappa}/\\mu)\\enspace.$$\n\nDepending on the heterogeneity parameters, **some terms in our rate may be better than theirs**: for instance, when $\\ tau$ and $ \\zeta_\\star$ are small but $\\phi_\\star$ is large. But the opposite could also be true, because (quite surprisingly, perhaps due to their step-size) their heterogeneity term improves with larger $M$. This was not true previously (i.e., before our paper): as they highlighted in their paper, because their rates were strictly better than those of Kolosokova et al. for Local SGD. \n\nTo make the comparison a bit simpler, let us compare their and our communication complexities in the regime with a very large $K\\to\\infty$:\n\n$$\\text{\\textbf{SFL:}}\\enspace R = \\tilde\\Omega\\left(\\kappa + \\kappa\\sqrt{\\frac{H\\phi_\\star^2}{M\\epsilon}}\\right) \\quad \\text{v/s} \\quad \\text{\\textbf{PFL (our):}}\\enspace R = \\tilde\\Omega\\left(\\frac{\\tau}{\\mu}\\cdot\\sqrt{\\kappa} + \\frac{\\tau}{\\mu}\\cdot\\sqrt{\\frac{H\\phi_\\star^2}{\\epsilon}} + \\kappa\\cdot\\sqrt{\\frac{H\\zeta_\\star^2}{\\epsilon}}\\right)\\enspace.$$\n\nThe above rate clearly re-emphasizes that in the regime with a large $\\kappa$ and $\\phi_\\star$ but a smaller $\\zeta_\\star$ and $\\tau$ (cf. Remark 1), our communication complexity is better. Is it possible that their rates can benefit from a lower $\\tau, \\zeta_\\star$? **Yes, we think so (at least with strong convexity).**\n\nHere is what we propose: we will include a remark about the sequential FL setting, highlighting how our results alter the comparison to parallel FL presented in [+2]. Additionally, we are willing to include a section in our appendix that provides variants of the results of [+2] (both upper and lower bounds) while incorporating second-order heterogeneity. Upon reviewing their proofs, we believe this is possible (for a subset of their results) and will be a valuable addition to our paper. This should require approximately 6-7 pages in the appendix, as we can utilize some parts of our theoretical framework already. **Would the reviewer be more satisfied with this change?** \n\nUnfortunately, due to the new rebuttal guidelines, we cannot include any new experiment plots. However, we are running experiments in the setup of Figure 1 and will report the qualitative results to the reviewers during the rebuttal phase. We are also curious if SFL similarly benefits from having a lower second-order heterogeneity. \n\n## On the Need for Strong Convexity\n\n> However, I cannot guarantee a higher score (i.e., 6) for now, as this topic (the unreasonable effectiveness of Local SGD) has been studied for several years, and this theory is still limited to strong convexity.\n\nWe would like to emphasize that we have made our best effort to incorporate results in the general convex setting; however, the simplest trick of using a general-convex-to-strongly-convex reduction does not work (see lines 244-254). We provide a more detailed explanation of why strong convexity was so useful in our coupled recursions in our response to reviewer un1E. So far, all our attempts to rely solely on convexity to obtain a variant of Lemma 2 have not been successful. We understand the reviewer's disappointment that our results are limited to the strongly convex setting, but it is worth noting that our proofs are already quite complex. Given the attention the analysis of Local SGD has received, this only underscores that extending it to the convex setting is not trivial, and that a gap may exist here. \n\n## Closing Remarks\n\n> Currently I give the score of 4. This is only because I have not yet checked all the proofs (I mainly checked the proofs of the upper bounds), due to the very heavy workload of NeurIPS. I know this is unfair for this good paper, so I will also consider the reviews of the other reviewers.\n\nWe appreciate the reviewer's honesty and empathize with them about the reviewing load at NeurIPS! However, we hope the reviewer will consider both other reviews and **our detailed rebuttals** to their concerns before forming an unbiased personal opinion on the paper. This is especially important because some of the reviews contain major misunderstandings about our setting and results, which we do not believe applies to the reviewer, given that they have read our analyses carefully. Since our paper is currently borderline, the reviewer's final score could influence the decision."}, {"review_id": "FV5r9PwLQ4", "reviewer": "Reviewer_jRiD", "summary": "A new analysis of the convergence properties of Local SGD, a.k.a. Federated Averaging, is provided.", "questions": "See above", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Local SGD-type methods are very important and I appreciate this kind of papers with an in-depth study of the convergence properties.\n\nI would like to see a discussion of the following papers with important insights.\n\n1) In a series of papers [A,B,C], Mangold et al. have studied the properties of Local SGD, showing that linear speedup can be shown with a careful analysis.\n\n2) Variance-reduction is not discussed. In my opinion the Scaffnew algorithm [D,E] is the state of the art of local training type methods. So, heterogeneity / client drift can be tackled using control variates, in the convex setting (the relevance of variance reduction in local SGD-type methods for nonconvex problems remains an open question). So, the real question is how the error of the stochastic gradients behave.\n\n3) In the deterministic setting, the error of Local GD has been characterized in [F]. It depends on the gradients of the functions $F_m$ at the global solution $x^\\star$, which is a natural measure of heterogeneity, also standard in the analysis of SGD. So, I don't think the Euclidean geometry on the primal solutions, as considered in Assumptions 3-5, is the right criterion. It should be more the first-order information on the gradients that matters.\n\n\n\n\n[A] Magold et al. \"Scafflsa: Taming heterogeneity in federated linear stochastic approximation and td learning\" 2024\n\n[B] Mangold et al. \"Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation\" 2025\n\n[C] Mangold et al. \"Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up\" 2025\n\n[D] Mishchenko et al. \"ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!\" 2022\n\n[E] Malinovsky et al. \"Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning\" 2022\n\n[F] Malinovsky et al. \"From local SGD to local fixed point methods for federated learning,\" 2020", "was_revised": true, "final_justification": "The authors have made a significant effort in their rebuttal to address the points raised by the reviewers, including myself, in a way that is satisfactory to me. So, I am increasing my score from 4 to 5.", "rebuttal": "We appreciate the reviewer taking the time to evaluate our paper.\n\nBefore we being to answer the reviewer’s concern, we would like to re-emphasize: our goal in this paper is to study Local SGD, and not other algorithms that are based on Local SGD but add additional algorithmic blocks, such as use of proximal oracles, control variates, variance reduction, or any other correction to alleviate its fixed-point discrepancy/bias. While we acknowledge that all of these are important and have their own place in the literature on federated optimization, it is clear to us that, partly due to its simplicity and partly due to its practical effectiveness, **the most commonly used algorithm in practice remains Local SGD**. And despite over a decade of work, there are clearly still many theoretical gaps in our understanding of Local SGD, as highlighted in our paper and in many other papers that preceded it. Our goal is to provide at least some more clarity on these issues. \n\nThe papers the reviewer mentioned also acknowledge this gap, and papers such as those of Wang et al. [6, 8] highlight, for the same reason, that **the unreasonable effectiveness of Local SGD** is an important (if not the most important) gap in the theory of Federated Optimization. We believe that both our insights and analysis will complement the algorithms with other primitives. With this clarification about the scope of our work, we will now address the reviewer’s request to compare and contrast our work with existing works. \n\n  \n\n## On [A, C, D, E], Variance Reduction and Control Variates\n\nOf the three papers due to Manigold et al., A and C are not directly concerned with Local SGD, but with other algorithms, including SCAFFOLD and its variants. SCAFFOLD is a very interesting algorithm that popularized the use of control variates to correct for the effect of data heterogeneity, but as pointed out by the experiments in \"Adaptive Federated Optimization\" by Reddi et al., and further underlined by Wang et al. [8]: **SCAFFOLD and FEDAVG have roughly identical performance on many realistic federated datasets**. This is a trend we often see in the practice of machine learning, where simpler algorithmic primitives often work equally well or better (when accounting for the difference in hyperparameter tuning budgets). In particular, it is important to highlight that, at least in practice, it is not the case that\n\n> heterogeneity / client drift can be tackled using control variates\n\nBased on common wisdom (including from industry practitioners), Local SGD performs very well in practice, while SCAFFOLD (and other more complex control variate-based algorithms) tends to perform less well than expected (see Wang et al. [6, 8]). This further strengthens the case for providing a more fine-grained analysis of Local SGD, and we believe A and C are sufficiently outside the scope of our paper. Similarly, ProxSkip [D] (which we are **very familiar** with) and its follow-ups (including [E]) are interesting algorithms in their own right, but they are distinct algorithms and are nowhere near as widely adopted as Local SGD in practical settings. \n\nRegarding Variance reduction, and the reviewer’s comment:\n\n> the relevance of variance reduction in local SGD-type methods for nonconvex problems remains an open question\n\nWe discuss and cite Patel et al. [30], which uses variance-reduced variants of Local SGD to provide almost min-max optimal algorithms in the non-convex setting. In fact, second-order heterogeneity is crucial for demonstrating improvement using variance reduction. This paper, along with [25], in the non-convex setting, served as motivation for our work. We acknowledge the important role of Variance reduction and control variates in Federated Learning. However, these papers [30, A, C, D, E] are not directly comparable to us and only provide interesting motivation. That said, we hope that our analyses can inspire future studies on algorithms that utilize variance reduction in even convex settings when the second-order heterogeneity is low: thus bridging the gap to Patel et al. [30]. \n\n## On [B, F], Fixed-Point Discrepancy, and the \"Correct Geometry\"\n\nB is a more relevant paper due to Manigold et al., because it upper bounds the fixed-point discrepancy of Local SGD and attempts to provide a new analysis using it. While the paper offers a convergence guarantee (with untuned step sizes) in the deterministic setting, **it does not tune the step sizes to achieve a convergence rate in the stochastic setting**. On the other hand, our goal is to give explicit convergence guarantees, with tuned parameters, to fill any gaps in our understanding of the min-max optimal guarantee for Local SGD. \n\nIn our experience, using the fixed-point discrepancy to obtain convergence rates for Local SGD (as discussed in Appendix C) is hard. While bounding the discrepancy itself is useful and can offer important insights (as we also do in our Appendix C.4), **balancing convergence and discrepancy/bias is challenging** due to the complex terms involved in the upper bound of the discrepancy. This is why neither we nor Patel et al. [25] rely on a fixed-point-based approach, but instead use a consensus error-based analysis. It is also why Mangold et al. [B] do not provide a general guarantee for strongly convex functions explicitly: for example, their Section 5 either considers quadratic functions or the homogeneous setting, and in neither case, despite simplifications, does it provide a fully tuned convergence rate for Local SGD. \n\nRegarding Malinovsky et al. [53], we cite the paper and include a full section on the fixed-point discrepancy in Appendix C, where we also discuss it several times. The key difference with respect to their paper is that we want to emphasize the discussion on data heterogeneity assumptions, which is why, like Patel et al. [25], we also try to bound fixed-point discrepancy in terms of our data heterogeneity assumptions. Malinovsky et al. [53]'s result also suffers from the same issue as Mangold et al. [B] (as discussed above), namely, finding it difficult to provide explicit convergence guarantees in terms of data heterogeneity notions due to the need to balance discrepancy and convergence. \n\n> So, I don't think the Euclidean geometry on the primal solutions, as considered in Assumptions 3-5, is the right criterion. It should be more the first-order information on the gradients that matters.\n\nWe are unsure what the reviewer means by Euclidean geometry not being the right criterion. It is well known that any convergence guarantee for SGD must rely on some version of Assumption 3, or another notion of initial sub-optimality. It is true that in some contexts, convergence rates can be provided in terms of initial function sub-optimality, such as when providing convergence rates for stationary points (cf. \"The Complexity of Making the Gradient Small in Stochastic Convex Optimization\" due to Foster et al.). However, at least for strongly convex problems, one cannot hope to recover the optimum without bounding their Euclidean norm. \n\nOnce it becomes clear that something akin to Assumption 3 is necessary, Assumptions 4-5 are just corresponding heterogeneity conditions that bound the gap between the solution sets of different clients. Having said that, it might be possible to state some of our results in terms of assumptions about the gradients at the optima. For instance, using Assumption 5 and 1 (smoothness), note that we can get the following for any $x^\\star \\in \\arg\\min_{x}F(x)$, $$\\frac{1}{M}\\sum_{m\\in[M]}\\|\\|\\nabla F_m(x^\\star)\\|\\|_2^2 \\leq H^2\\phi^2\\enspace.$$ \n\nThis is essentially the first-order heterogeneity assumption studied in works such as Kolosokova et al. [18] and Patel et al. [25], among others. A similar, but not identical, version of first-order heterogeneity was studied by Wang et al. [8]. As such, our assumptions and the usual first-order assumptions at the optima are related; ours are simply more fine-grained (for instance, the demarcation between Assumptions 4 and 5, as discussed in Remark 1). Since our upper bounds are for the strongly convex setting, it is unclear if relying on the usual, more coarse first-order assumptions is any more insightful than using Assumptions 4 and 5. \n\nSimilarly, since Local SGD is a first-order algorithm, it is natural to consider the second-order heterogeneity assumption in Assumption 6, which measures the difference between the \"geometries\" of different machines. It is possible to define a different geometry that also accounts for local update steps, but we are not trying to find the best geometry for our assumption, as ultimately, our goal is to provide explicit convergence guarantees. We need to balance **how descriptive a geometry/assumption is and our ability to use it in our analysis**. The fixed-point perspective based analyses fall short here: while they provide very explicit operators characterizing fixed points and bias, it becomes challenging to give a simple convergence rate. \n\nIf the reviewer has a specific heterogeneity assumption or a geometry they would like us to comment on, we are happy to discuss it during the rebuttal phase.\n\n\n## Summary\n\nWe propose adding a remark about the techniques that rely on bounding the fixed-point discrepancy of Local SGD to give an analysis, and discuss [A, B, C, F] in this context, while deferring the reader to a more detailed discussion in Appendix C. Regarding [D, E] we will include them in our paper while discussing [30] and broadly the effect of variance reduction. **Would this be satisfactory for the reviewer?** \n\nWe hope that this rebuttal, along with **our detailed discussion of these papers in our revision**, will address the reviewer’s concern and encourage them to reconsider their score. We are happy to answer any other questions the reviewer may have, and we are looking forward to engaging during the discussion phase."}]

Author rebuttal:

Meta-review: This paper investigates distributed optimization using Local SGD with full node participation, focusing on its advantages over mini-batch SGD in heterogeneous settings. The authors present a refined theoretical analysis for convex objectives with higher-order smoothness by introducing a second-order measure of data heterogeneity. They establish matching upper and lower bounds on convergence complexity, showing that Local SGD achieves superior communication efficiency, particularly in low-heterogeneity regimes. The work provides a valuable theoretical explanation for the empirically observed benefits of Local SGD and is clearly written. The analysis offers meaningful insights and has the potential to be extended to other algorithms. Overall, the paper brings new theoretical understanding to a widely studied method.  

One final remark for the authors: I strongly recommend including a table that compares prior Local SGD rates with the current improvements and the benefits of local steps. Such a table would make the contribution of this work more transparent and accessible to readers.
Decision: Accept (poster)