Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration
Authors: Ahmed Khaled
Satyen Kale
Arthur Douillard
Chi Jin
Rob Fergus
Manzil Zaheer
Venue: NeurIPS 2025 poster ()
Keywords: communication-efficient optimization
local sgd
stochastic optimization
distributed optimization
Primary area: optimization

Abstract: Modern machine learning often requires training with large batch size, distributed data, and massively parallel compute hardware (like mobile and other edge devices or distributed data centers). Communication becomes a major bottleneck in such settings but methods like Local Stochastic Gradient Descent (Local SGD) show great promise to reduce the global communication need. Local SGD consists of three parts: a local optimization processes, an aggregation mechanism, and an outer optimizer that uses the aggregated updates from the nodes to produce a new model. While there exists an extensive literature on understanding the impact of hyperparameters in the local optimization process, the choice of outer optimizer and its hyperparameters is less clear. We study the role of the outer learning in Local SGD, and prove new convergence guarantees for the algorithm. In particular, we show that tuning the outer learning rate allows us to (a) trade off between optimization error and stochastic gradient noise variance, and (b) make up for ill-tuning of the inner learning rate. Our theory suggests that the outer learning rate should sometimes be set to values greater than $1$. We extend our results to apply to when we use momentum in the outer optimizer, and also introduce a novel data-dependent analysis of Local SGD that yields further insights on outer learning rate tuning.  We conduct comprehensive experiments with standard language models and various outer optimizers to validate our theory.

Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration
Ahmed Khaled" Princeton University ahmed. echiiieernnnt edu
Satyen Kale
Arthur Douillard
Google Research
Google Deep.indd
satyen@satyenkall. com
douillardOgoogle com
Chi Jin
Rob Fergus NYU, Meta fergus@cs Srtgua@cc.ny.ccomm edu edu
Manzil Zaheer
Princeton University Princeton, NJ 08544
Google DeepMind
manzilzaheer@gmill.cc com
mnij@princeton. edu
Abstract
Modern machine learning often requires training with large batch size, distributed data, and massively parallel compute hardware (like mobile and other edge devices or distributed data centers). Communication becomes major bottleneck in such settings but methods like Local Stochastic Gradient Descent (Local SGD) show great promise in reducing this additional communication overhead. Local SGD consists of three parts: local optimization process, an aggregation mechanism, and an outer optimizer that uses the aggregated updates from the nodes produce impact
new model. While there exists an extensive literature on understanding of hyperparameters in the local optimization process, the choice of outer optimizer and its hyperparameters is less clear. We study the role of the outer optimizer Local SGD, and prove new convergence guarantees for the algorithm. In particular, we show that tuning the outer learning rate allows us to (a) trade off between optimization eтror and stochastic gradient noise variance, and (b) make up for ill-tuning of the inner learning rate. Our theory suggests that the outer learning rate should sometimes be where we use momentum in the outer optimizer, and we show similar role for the momentum-adjusted outer learning rate. We also study acceleration in the outer optimizer and show that improves the convergence rate as function of the number of communication rounds, improving upon the convergence rate of prior algorithms that apply acceleration locally. Finally, we also introduce novel data- dependent analysis of Local SGD that yields further insights on outer learning rate tuning. We conduct comprehensive experiments with standard language models and various outer optimizers validate our theory.
values greater than 1. We extend results to settings
Introduction
Training very large scale machine learning models requires lot of compute. This compute is often centrally controlled by a single entity and tightly connected in data center. Gradients are constantly synchronized, hardware failures are controlled and mitigated, and things (mostly) run smoothly. Building this training infrastructure is expensive, however, and centralized control might be desirable for all models. This has led to surge of interest in decentralized collaborative training of lcage-scale models across different, potentially poorly connected clusters (Douillard,
Part of this work was done during an internship at Google DeepMind. Currently Apple.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Feng, Rusu. Chhaparia, et al., 2023; Jaghouar, Ong, and Hagemann, 2024; Jaghouar, Ong, Basra, al., 2024). This has motivated the adoption of federated learning algorithms training language models, chiefty for scalability and communication efficiency rather than data privacy. Efficient parallelization strategies also factored in the remarkable recent training of DeepSeek V3 and RI on a tight budget (DeepSeek-Al, Liu, et al., 2024; DeepSeek-AI, Guo, et al., 2025).
foundational algorithm in distributed and federated optimization is Local SGD (Wang, Charles, et al., 2021). Many popular algorithms fit in the FedOpt template (Reddi et al., 2021) (Algorithm 1), including FedAdam (Reddi et al., 2021), FedRR (Mishchenko, Khaled, and Richtárik, 2022: Mali- novsky and Richtárik, 2022), DiLoCo (Douillard, Feng, Rusu, Chhaparia, et al., 2023; Jaghouar, Ong. and Hagemann, 2024) and many others. FedOpt solves the minimization problem een f(x) given access to M different computational nodes and unbiased stochastic gradients of f. FedOpt consists of three main components: an inner update loop on every client, an aggregation of the client updates, and then an outer update step taken on the server.
Algorithm The FedOpt Algorithmic Template
1: Input. Update rules LocalUpdate and OuterUpdate. Initial point zo-
2: for communication rounds r 0, l........ R 1 do
3: Broadcast 2, to each node m
4: for each node m parallel do
5: Set Vm,r.0
6: for local steps 0, 1,.... H do
7: Set ym,r,4+1 = LocalUpdate nm r.h), for stochastic gradient Im,r, at sm end for Communicate Um.,.H to the server.
8:
9:
10: end for
11: Compute the update or "outer gradient" Á. 1
Em=i M Em=I(ym,r.t I,)).
12: Update Ir+1 = OuterUpdate(xr. A.,
13:
end for
When both the local and outer update rules correspond to gradient descent (i.e. Tnew Zold 3A for some stepsize 3 and update vector A), the corresponding algorithm is Generalized Local SGD. If we additionally take the outer stepsize to be 1, we get Local SGD. Local SGD simply does H steps of SGD on each node, and then averages the result after applying the updates. This is the most common form in which the algorithm is analyzed, as in e.g. (Stich, 2019; Khaled, Mishchenko, and Richtárik, 2020; Woodworth, Patel, Stich, et al., 2020; Koloskova et al., 2020; Glasgow, Yuan, and Ma, 2022; Patel, Glasgow, Zindari, al., 2024). In practice, different choices of outer optimizers perform better. For example, Dil DiLooo/OpeeDii.oo outer optimizer (Douillard, Feng, Rusu, Chhaparia, al., 2023). This has motivated much analysis of different outer optimizers and their impact (Reddi et al., 2021; Malinovsky, Mishchenko, and Richtárik, 2022: Jhunjhunwala, Wang, and Joshi, 2023: Sun et al., 2024). However, our theoretical understanding of the fundamental Generalized Local SGD algorithm remains limited. In particular, it not clear why the bilevel optimization structure of the algorithm is helpful from optimization perspective, even in the i..dd. setting where the data distribution is the same on all the nodes. Additionally and the best of our knowledge, we have no explicit expressions for what the ideal learning rate pair (17, 7) for the inner and outer updates, respectively, should be. Empirically, outer optimizers employing Nesterov acceleration have the best performance, yet to the best of our knowledge why or how it improves convergence is not known.
use SGD with Nesterov Momentum as the
Contributions. Our paper takes steps address the above questions and makes the following contributions.
We conduct a novel, tighter analysis of Generalized Local SGD (Theorem 1) that shows the outer learning rate plays a dual role. It (a) interpolates between two extreme regimes: taking many effective steps at the cost of higher variance to taking fewer steps but at reduced variance and (b) increases the algorithmic robustness to hyperparameter tuning by making up for ill-tuned inner learning rates. The latter holds even in the absence of any stochastic gradient noise.
We extend the above analysis cover Generalized Local SGD where the outer optimizer also uses momentum (Theorem 2) and show that this gives additional leeway in tuning 7.

---

We provide a convergence analysis for Local SGD with an accelerated outer optimizer and unaccelerated inner optimizer (Theorem 3), showing that using Nesterov acceleration in the outer loop achieves better dependence on the number of communication rounds R in the drift terms compared to standard Local SGD and improving upon the convergence rate of FedAc (Yuan and Ma, 2020).
We also derive a data-dependent, high-probability guarantee for the convergence of Local SGD with GD as the outer optimizer (Theorem 4) that shows further benefits of tuning the outer stepsize in more nuanced settings.
We additionally conduct an extensive empirical analysis for training large-scale language models with various outer optimizers (gradient descent, accelerated gradient descent, and Schedule-Fiee gradient descent).
We now review related work, then proceed to main results.
2 Related Work
There is a rich literature on algorithms for communication-effiiiee distributed optimization for federated learning (Konečný et al., 2016), where multiple clients collaborate on solving a machine learning problem (Wang. Charles, et al., 2021). Federated learning algorithms are designed to reduce the effect of data heterogeneity (Karimireddy et al., 2020; Wang, Charles, et al., 2021; Murata and Suzuki, 2021), ensure the data stays private (Wei et al., 2020), deal with intermittent or cyclic client availability (Eichner et al., 2019), among other issues.
As models have grown larger in size over the past few years, going from a few million parameters to billions (Brown et al., 2020), the scale of training runs has also grown to include many more devices divided across multiple computing clusters rather than a single cluster (Diskin et al., 2021; Huang, Huang, and Liu, 2022; Borzunov et al., 2022: Douillard, Feng, Rusu, Chhaparia, et al., 2023). Even within a single datacenter, training runs now involve tens of thousands of GPUs (Jiang et al., 2024). This has motivated researchers to develop and use algorithms inspired by the federated learning setting for large-scale training instead. Examples of such algorithms include DiLoCo (Douillard, Feng, Rusu, Chhaparia, et al., 2023), its open cousin OpenDiLoCo (Jaghouar, Ong, and Hagemann, 2024), DiPaCo (Douillard, Feng, Rusu, Kuncoro, et al., 2024), and others (Liu et al., 2024; Liang et al., 2024; DeepSeek-AI, Liu, al., 2024). Federated learning methods thus have found use in pretraining and fine-tuning language models (Jaghouar, Ong, and Hagemann, 2024; Yang et al., 2025), and may prove particularly important for scaling even larger models in the future (lacob et al., 2024; Sani et al., 2024; Rush et al., 2024). We note that the use of methods for federated learning even for i. distributed training is not new, and is perhaps being "re-discovered" training runs grow too large to fit on single clusters. For example, Lin et al. (2020) argued that using Local SGD can be more efficient than traditional Minibatch SGD in some settings. Ortiz al. (2021) also conducted experiments studying the trade-offs of using Local SGD in training image classification models.
The most popular algorithm in the federated optimization literature is Local SGD or Federated Averaging (Wang, Charles, et al., 2021). It is generalization of minibatch SGD that, rather than communicating at every step of the optimization process, communicates only intermittently. Local SGD shows remarkable efficiency in many settings in practice, and therefore its convergence and generalization properties have been the subject of intense theoretical investigation over the past few years (Stich, 2019; Khaled, Mishchenko, and Richtárik, 2020; Woodworth, Patel, Stich, et al., 2020; Woodworth, Patel, and Srebro, 2020; Patel, Glasgow, Wang. al., 2023; Glasgow, Yuan, and Ma, 2022; Gu, Lyu, Huang, et al., 2023; Patel, Glasgow, Zindari, et al., 2024). Many variants of Local SGD exist, including those that use random reshuffling instead of i.i.d. sampling locally (Yun, Rajput, and Sra, 2022; Mishchenko, Khaled, and Richtárik, 2022), adaptive methods such as Adam (Reddi et al., 2021; Wang. Lin, and Chen, 2022), and modifications handle data heterogeneity (Karimireddy et al., 2020; Mitra et al., 2021), personalization (Hanzely et al., 2020), or additionally use gradient compression (Haddadpour al., 2021; Safaryan, Hanzely, and Richtárik, 2021). Generalized Local SGD, where we use two stepsizes (as in Algorithm 1), is known to be important in managing the trade-off between converging quickly and converging to a mismatched point in heterogeneous distributed optimization (Woodworth, Patel, and Srebro, 2020; Charles and Konečný, 2020; Patel, Glasgow, Zindari, et al., 2024). Our focus here is on the homogeneous or i.i.d. data setting; Here, the most related works are (Karimireddy et al., 2020; Malinovsky, Mishchenko, and Richtárik, 2022;
3

---

Jhunjhunwala, Wang, and Joshi, 2023; Sun et al., 2024) and we discuss our work's 's relation to theirs in detail in the next section after reviewing some preliminaries.
Theory
In this section we conduct the study our main algorithm, Generalized Local SGD (Algorithm 1 with LocalUpdate(y.s) g) = Ai and Outer SuterUpdate(1; A) x - -7A). We first review some preliminaries, then present main results.
3.1 Preliminaries
We are solving the optimization problem min f(x), where we assume f satisfies the following curvature and regularity condition.
zER
Assumption The function f differentiable, convex, has L-Lipschitz gradients, and has minimizer T..
We suppose that we can access a stochastic stostosttifirst-ordeer oracle that given a point æ returns a gradient g(z) that satisfies the following assumption.
Assumption 2. Given point
R the stochastic gradients g(x) Rd are (a) unbiased in
expectation E [9(x)] V f(x), and (b) has variance bounded as IE [19(2) v((()] 0², where [.] denotes the expectation operator.
Our setting distributed, but with identically distributed data: there are M different nodes, but they all sample stochastic gradients from the same data distribution in an i.i.d. (independent and identically distributed) manner. We denote the inner product between two vectors and by (a, and by ||-1| the corresponding Euclidean norm. For the purpose of theoretical analysis, can write Generalized Local SGD succinetly as
gm,r.0 Er+
9m,r. Stochastic gradient of V/.r.h
1m = Um,r,
710m. for m 1,..,, M in parallel and 1,,1,... I..., H 1 in sequence.
1-1
M
1r+1
Er 7
Σ
Σ
Im.rh-
(GE--OC-SGGD)
M
K=U
m=
To simplify our analysis, we follow (Stich, 2019) and define the virtual sequences
M
M
def
Σ
def
Σ
Ur
Um.r..s
gr.h
Im,r.h
M
M
(1)
m=1
m=1
In
def Er 1mm. = vf((mnnh))
Irhh def
Er [gn.]
3.2 Main convergence result
Recall that we consider Algorithm the particular case when LocalUpdate(w. = 1g and OuterUpdate(zz, A) - A.
Existing results on the convergence of Gen. Local SGD. When the outer stepsize y 1. the convergence of (GEN-LOC-SGID) is very well understood, with tightly matching upper and lower bounds (Khaled, Mishchenko, and Richtárik, 2020; Woodworth, Patel, Stich, al., 2020; Glasgow, Yuan, and Ma, 2022). particular, the best rate for the algorithm
R- 111
f(x.( f(c.)) )
( RH
L| - I.11?
o 1|00 x.ll
Liod |100 10-xali' 2=11²²
RH Σ
Σ
yr.hk
+
(2)
VMRH
#
h=0
The first two terms the above convergence guarantee show that increasing the number of local steps has the same effect as increasing the number of communication rounds R, and are identical to the convergence guarantee doing RH steps of SGD with minibatch size M. Local SGD differs from ordinary minibatch SGD in the last term, which shows different scaling between H and R.

---

where increasing R helps more than increasing H. This is because increasing H incurrs additional client drift that slows down the convergence of the algorithm the presence of stochastic gradient noise. When the outer stepsize is allowed to vary, the convergence of the algorithm is less clear. Karimireddy et al. (2020) gives the following convergence rate in the absence of data heterogeneity,
E (1 E x ((x.) = O -1| a||=0-z.1|
+ VMR
R
for specially chosen and pairs. This rate matches that of Minibatch SGD, but does not recover the convergence rate of vanilla Local SGD given by Equation (2). Jhunjhunwala, Wang, and Joshi (2023) also give guarantee for Generalized Local SGD with a specific outer learning rate that is always least and that depends on the heterogeneity of the iterates across the different clients. Since the analysis is conducted in the heterogeneous setting, the local stepsize required to scale with H/H. guarantee that applies to any outer learning rate the nonconvex, heterogeneous setting given by (Sun et al., 2024).
The limiting factor existing analysis that we forced choose the local stepsize 7) scale as LH whereas to obtain Equation (2) we sometimes need to choose to be much larger, on the order of T. If we aim accurately characterize the convergence of (GEN-LOC-SGDD), our analysis has to encompass both large and small local stepsizes 1).
New analysis. We now present our main convergence theorem for (GEN-LOC-SGI)).
Theorem 1. Suppose that Assumptions I and 2 hold. Then the iterales generated by Generalized Local SGD run with local stepsize >> O and outer stepsize y > 0 for R communication rounds and with H local steps per round satisfy,
TEE E Brat -
((x.) S S00
aD [mp-0. 112 1
+ n0² maxior.) LxPo²
(3)
M
provided the stepsizes and y jointly satisfy nL + (7
H) S } and where (a)+ max(a, 0).
Implications of Theorem 1. Before giving a proof sketch for Theorem 1, we first discuss its implications. Observe the stepsize condition 1) + (7 1) + H) is asymmetric in and y; That
is, when 7 S 1, we are allowed to choose v/ larger than 9 LZz ). This crucial to obtain the rate of Equation (2). Indeed, when 7 = 1, the requirement on reduces to nL I 1 and we can choose following (Woodworth, Patel, Stich, et al., 2020)
4
1= min
47.1 V
M Milan-
Lo
Plugging this choice of 7) yields the convergence guarantee of Equation (2). Alternatively, when 8nyL 1, the stepsize requirement is met if we choose nyyH 1 and we immediately get the Minibatch SGD guarantee. In particular, choose 0 ( and y= (LH
the rate then becomes
(yomt. - fxx) <
SL SLilrr--
7.a2
7.8
SR
4LMH
where yout denotes the average over all iterations and clients as in Equation (3). Then for R large
enough we choose 7, O (v LD and this gives us the minibatch SGD rate HoT
fYont) - f(x.) LD3 aD
VMRI
This confirms the intuition that at the extremes, manipulating the stepsizes y and allows us to interpolate between minibatch SGD and (vanilla) Local SGD, as observed by (Woodworth, Patel, and Srebro, 2020). In fact, Theorem allows us to go step further and get an explicit expression for the optimal inner and outer stepsizes depending on the problem parameters. This is given by the following proposition.
Proposition Let h().)) 7) be defined as
h(m,,) = wH + LLo Lo² +
D²
7) 1)rx
(4)
M
Consider the optimization problem:
1
min h(n,))
subject nL (1
(5)
The solution (n",," is given by comparing the following two candidates.
5

---

1. Candidate (n'A,7A ( defined by Y = 1 and n'a = -min( 12 n'A) where 7'A is the unique positive root of the cubic equation
2LHo + 17 1²
D
0.
RH
2. Candidate (nts VB) for the regime 7 2 with 4nL 1, where (a) the constraint is enforced with equality:
(B((1) = 1 π 4im -1). and (b) diB is the unique positive root of the cubic equation
D2 + 2Lo2 Hn - It
=2 ( - 1)+ 1)3
MH
The optimal solution (ni"; (7") ) is the candidate pairfrom ((rha Ta), (7 } that yields the smaller value of h(n,,))
The proof of the above proposition is straightforward and follows by writing the KKT conditions for the optimization problem in Equation (5). A consequence of Proposition 1 is that in the case of ill-tuning of the inner stepsize 7), a large outer stepsize 7 can make up for it. For example, if O and n < (1)) we can make up for this by choosing as QIH Thus, we can interpret the outer learning rate y as having two dual roles. (a) It allows us to interpolate between minibatch SGD (y > 1) and vanilla Local SGD (7 = 1), giving us the better of the two rates, and (b) it provides us some additional leeway in hyperparameter tuning by making up for ill-tuned inner learning rate 1).
Our theory suggests that in the worst case, choices of y are not useful from an optimization perspective. We should either choose 7 = or > 1. This can be seen even on quadratic objectives, for example if f(x) = =Qx for some positive definite matrix Q. then a straightforward computation gives the expected iterate after // local steps and R communication rounds is E [zt]] (1-7)) + y(I (Q)))az From this, it is clear that if 1) chosen such that (I n7) has eigenvalues smaller than 1, we should choose 7 2 1. While if (I n2)" " has any eigenvalues larger than 1, we should just choose y = 0 (i.e. just don't 't apply the algorithm at all). In other words, 7 can make up for learning rate that is too small, but not learning rate that is too large. This observation does not exclude that 7 < 1 can be useful from a generalization perspective, as noted for the case of single client by Zhou et al. (2021), in the presence of data heterogeneity, as noted by Charles and Konecný (2021), or in the presence of specific stochastic gradient distributions (see Section 3.4).
Proof sketch for Theorem 1. We first start by expanding the update for the round iterate x,+1 -x 1r41 3r + 3r x. similar (Karimireddy et al., 2020) to get,
H-1
H
||r+11 2.112 = =||E, - 2.11² 2yn
Σ
(x,
Ix, Fr.hh + 722
Σ gr,h
h=0
H-1
H-1
H H-1
= =112, - 2,112 2nm
Σ
(I,
yr Ir.h) - 2ym
(yr, - 2., gr.h) + +
gr.k
h=
h=0
h=
where Ir.A is defined as in Equation (1). Karimireddy et al. (2020) and Jhunjhunwala, Wang, and Joshi (2023) control the inner product - (z, Vr,h- by either using smoothness Young's inequality; This would force us bound the stray Ilyr.. - x, 1|2 and take the local stepsize rj to be small in order to ensure convergence. Instead, we rely on bounding this quantity directly by viewing it as the regret in the online convex optimization sense with respect to the comparator Z,,, Observe that the virtual sequence of averaged local iterates satisfies Vr.h+1 standard regret analysis we have
Vr.h 1Wrrb and thus through
EnL - (I,, Vr Br.n) -1lrrA xrll
H
Σ h=
21
2
The negative terms - -1 - xr, in Equation (6) turn out to be crucial in obtaining an analysis that works for all 17 and not just small 77. With this change and through carefully bounding the variance terms following (Khaled, Mishchenko, and Richtárik, 2020; Woodworth, Patel, Stich, et al., 2020), we obtain the guarantee of Theorem 1. The full proof is provided in Section B.2.
Comparison with results on related algorithms. Malinovsky, Mishchenko, and Richtárik (2022) analyze closely related variant of the algorithm that uses federated random reshuffling (Mishchenko.

---

Khaled, and Richtárik, 2022) as base. This is a significantly different algorithm that doesn't 't allow for an arbitrary number local steps H and depends on posessing finite-sum structure. Nevertheless, we can still specialize (Malinovsky and Richtárik, 2022, Theorem 2) approximately to our setting, by using H the number of data points an epoch. In our notation, their convergence guarantee reads
E [ ( E m.)] f(x.) s so
I100 =-1
97HR + H
under the conditions Hn S & and 1 y LnH Their theory thus also suggests that ? 2 can be useful. Optimizing over 1) and y yields the convergence rate
1
E / ( x, f(x)) f(x.) S
this rate is the same as gradient descent for R steps (since the finite-sum structure means that per- epoch we approximate one step of gradient descent when 7) is small). similar rate is derived in (Li, Acharya, and Richtárik, 2024; Li and Richtárik, 2024) if we have access to the proximal operator (i.e. do many local steps H particular show that an outer learning rate greater than 1 can be particularly useful for improving the convergence of FedProx (Li, Sahu, et al., 2020) in the heterogeneous setting when the smoothness constant varies significantly between different clients.
modified objective). Li, Acharya, and Richtárik (2024) in
Analysis with momentum. Our analysis suggests that values of are potentially very useful, but in practice such values are rarely used. One reason this might be the case is because the momentum effectively acts as a stepsize multiplier, i.e. in the presence of momentum parameter μ the effective outer stepsize becomes ?
I-p Our next theorem establishes this rigorously.
Theorem 2. Suppose that Assumptions I and 2 hold. Suppose that the outer update is gradient descent with momentum, Outer DuterUpdatee(r, -aatee((,,,,,,.., ) = Ir +, + u(x, x,-1) with momentum
-A,,1
parameter js (0,1) and the local update is gradient descent LocalUpdate(()
y 'g9 in
Algorithm 1. Let the step sizes n. 7 satisfy 1LL
1 (Tx H. S ]
and MuLH S T6. Then I-p
after R rounds of communication, the averaged iterate satisfies
E [f f(x.) (
p)11 - xx12
7 + no² max I- 1-xx1)
my o²
MY
M
1 M
where y defined as the average of all local iterates across training (as in Equation (3)) and (a)+ max(a, 0).
The proof provided Section B.3. Theorem shows the requirement on the outer stepsize is relaxed from requirement on y to requirement on T- allowing to reap the same benefits of observed earlier if we also tune μ. Momentum thus changes the range of stepsizes allowed but does not fundamentally alter the uter stepsize tradeoffs. This benefit was first observed in (Sun et al., 2024) for nonconvex optimization with small local stepsize provided we use an additional momentum buffer. Our work gives direct theoretical support to this observation even with a single momentum buffer and allowing for large 17.
3.3 Convergence with accelerated outer optimizer
We now consider the use acceleration. To the best of our knowledge, the combination of an accelerated outer optimizer with unaccelerated inner optimizer, in e.g. DiLoCo (Douillard, Feng, Rusu, Chhaparia, et al., 2023; Jaghouar, Ong, and Hagemann, 2024), has not been analyzed in the literature before. We take steps towards addressing this gap and understanding the convergence properties of such algorithms by considering Nesterov's 's accelerated gradient descent (Nesterov, 2018) 8) the outer optimizer and (stochastic) gradient descent the inner optimizer. The following theorem gives a convergence guarantee for this setting.
Theorem 3. Suppose that Assumptions I and 2 hold and the stepsizes satisfy 2Lm S 1 and 7 S 1. Suppose that the outer update is accelerated gradient descent with Nesterov momentun follows
1 Ir - -
2r+1 2, -
Er+1 = (1 - Tr 1 1 + Tr+ 2,
7

---

with parameters 7/- zir+2l and LocalUpdate(y, 9) y 119 in Algorithm 1. Then after R rounds of H steps, the final iterate uR satisfies
2_ and the local update is gradient descent
742'
E [[(uR]] f(a.) 211200 x.112
RL RLL
mo R
7 H
2M
2M
To understand the implications of the above guarantee, we specialize it with a tuned pair of learning rates (7, 11) below.
Corollary 1. In the same setting as Theorem 3, selling 7 = in Equation (7), and choosing
1/3
1/4
== y==my -min
2MD2 LO
4D²
4M
2L
Ho
where D = =1 - z.!l and the final iterate satisfies
B[s(un)] - (xx.) 0
LD
LA/302/3 + 12/4
L2
oD
(8)
R2H RM//3H1/
VMRH
Equation (8) shows that in the absence of noise, obtain rate accelerated in R but not H. This intuitively makes sense, since we do acceleration only in the outer loop. In the presence of noise, we have in the worst-case the unimprovable =DD
VMRH term and two additional noise terms that characterize the drift suffered by this algorithm. Notably, the drift terms have much better dependence on R compared to Local SGD, as given by Equation (2). Yuan and Ma (2020) analyze FedAC, an accelerated variant of Local SGD that uses acceleration locally and applies simple averaging as the outer optimizer. Their algorithm enjoys the convergence rate
([ (xx.) O
LDZ RH
g2/9g2/$p" RHI75
, 1//2
aD
VMRH
Comparing with Equation (8), algorithm enjoys better dependence on R and M in the denomina- tors of the two drift terms while using momentum sequences only on the server.
3.4 Data-dependent convergence result
To further understand the role of the outer stepsize, we now present data-dependent, high-probability guarantee for Generalized Local SGD in Theorem compared the rather worst-case analysis of Theorem 1. This analysis may also provide insights into practical tuning of the outer learning rate Theorem Suppose that Assumptions I and hold. Then Algorithm with outer update 7 and local update y y 199 if the local stepsize satisfies S I then with probability least 8 the ieertes generated satisfy
--1
100 - x x.11
Σ
Σ
-((x)) s vr
+
ym
Σ r.
1lemial mm²
RH
MRH
RH
P=0 h=
+
[1 T/n
Σ
Σ Israil
n + 7
max
119m.rall m.h
Σ
na
Σ m.r.h
Mg !|
RH
M
MR
The proof of Theorem 4 provided Section B.5. Compared to Theorem 1, the guarantee we obtain here is weaker in some areas, e.g., the variance term ?no does not benefit from increasing M. On the other hand, this guarantee is a niigh-probabiling and data-dependent guarantee. To the best of our knowledge, this is the first high-probabile Theorem 4 allows us to observe another potential benefit of using 7 + 1. To see how, let us make the simplifying assumption that [| || G and ||9m,ral|| G2. Observe that by the triangle inequality we have G < G2, but in fact G1 can be significantly smaller than G2, particularly the later stages of the optimization process, due to the variance reduction effect of averaging together the gradients on different nodes. Then we can rewrite the above guarantee as
convergence guarantee for Local SGD in the literature.
& +mn +ymo² +|1- NHC?
GH ?
S Ô RH The y that minimizes this upper bound is given by the following proposition.
+noV
(9)

---

Proposition 2. Let g(z) = + bæ z c a, 0.
i 2 b++. e, then v /a/bb- + e) minimizes
i - e 0 and S b - c, then va/ (b c) minimizes 9.
Otherwise, x
minimizes g.
Applying this lemma to Equation (9) one can see that simple averaging is suboptimal depending on the variance and relative magnitudes of 1₁ and G2. In particular, the first condition in our setting
dg nRH
nH 2 n( + x²) + nH.
where 2 indicates that the inequality holds up constant factors of the terms on both sides. Since +HG 2 o². This condition essentially asks G2 G1. we simplify the above condition to 1
db
d2 the noise is large relative to the "optimization term" sf RH or not. In the latter case, choosing 7 > 1 helpful, and the outer optimizer acts as a form of momentum that helps reduce the optimization term d HG2.
further. On the other hand, the second condition yields 7 1 and requires that a² RH This is an especially dosinateee regime, which we may expect to observe towards the end of the training process. In this case, decaying the outer learning rate to y < 1 allows the algorithm to maintain convergence despite the high noise magnitude. When the optimization term and the noise term are of the same order, then y = 1 is the optimal choice.
4 Experiments
We conduct two sets of experiments: (a) solving convex optimization problems to provide the most direct verification of the predictions of our theory, and (b) training transformer based language models. Due to limitations of space, we present only highlights of the results here and most of the details and ablations are provided in the supplementary materials (Section A).
4.1
Convex optimization
We conduct experiments on the quadratic objective fxx 11( xx1)l² where Q = A E Rd for d 50 and the en- tries As are all drawn from a normal dis- tribution Ar ~ (O, 1) for 1 1,....d d
1.4
512
107
and j = I,...,d, d, and 2, is similarly drawn from the standard d-dimensional Gaussian. We use stochastic gradients of the form g( vx(x) + v, where the e's are random vectors drawn from the Gaussian with mean and variance o², v (N0, o2). We evaluate the performance of Algorithm 1 for various values of a, {10-3 10-2, 10-1 0.5, 1,5, 10, 15, 25, 50). For each we perform an extensive grid search over E (0.001, 0.01, 01 0.5, 0.9, 1.0, 1. 1.25, 1.5, 2 to determine the best one in terms of mini- local steps, and fix
10.0
157
1877
207
30"
30
(a) Optimal y VS
(b) Loss for different d.
Figure 1: Effect of varying noise magnitude and outer learning rate for quadratic optimization.
mum average loss over the last ten rounds. We use 1000 rounds and H
7 0.001 in all cases.
Figure I(a) shows how the optimal value of y varies with different noise levels a. We observe that, as increases, the optimal decreases from 1.0 to 0.1, as predicted by our analysis. Figure ((b) also illustrates the loss trajectories for different noise levels with the best %
4.2 Transformer pretraining
Setup Following the DiLoCo paper (Douillard, Feng, Rusu, Chhaparia, et al., 2023), we experiment using Chinchilla decoder transformer (Hoffmann al., 2022) on the C4 dataset (Raffel al., 2020). The architecture hyperparameters identical from the DiLoCo paper (Douillard, Feng, Rusu,

---

Bida Ricdall 18-7
Bide Finalal 1h.t
Pale Peatee L.-O
fntripe: 2075
Harge 23,7
111-7 Beices, (iee 24-500 12:03
Ristes, 18e0 1111 S6G50 15.32
125 12.4
Thiiinn Stope
Thiiing Stape
Thaiiin Stope
(a) 150M
(b) 400M
(c) IB
Figure 2: Scaling distributed pretraining, at 150M, 400M, and 1B parameters. The x-axis shows the total number of training steps, including both local and communication steps. The y-axis shows the perplexity achieved by each method. Legend represents final perplexity values.
Chhaparia, et al., 2023) and are given in Section A.1.1. We fix the batch size at 512 and the sequence length at 1024. We experiment at different scales, from 150 million to 1 billion parameters. For all experiments, the inner optimizer AdamW (Loshchilov and Hutter, 2019) trained with cosine learning rate schedule defined across the total amount of steps. The inner optimizer state is never shared across replicas, and is passed from one round to the other.
Methods We compare three distributed methods, using different outer optimizers: SGD(Ir=1) (equiv- alent to simple averaging of local models (McMahan al., 2017)), Nesterov (equivalent to DiLoCo (Douillard, Feng, Rusu, Chhaparia, et al., 2023)), and ScheduleFree-SGDD (SF-SGD) (Defazio et al., 2024). We use SF-SGD substitute for outer learning rate scheduling, though it still requires tuning hyperparameters. We also include two "high- coigunhcommiiiaiinn " data-parallel baselines: one with the global batch size as the local per-replica batch size used by the distributed methods, and one with the same batch size as the global batch size (M x the local per-replica batch size) used by the distributed methods. The latter requires either more GPUs and more thus communication, or gradient accumulation and thus more time. The latter also has an equal flops budget as the distributed methods. We tuned all our optimizers on the pretraining setting on separate validation set. We also considered using SF-Nesteroy, but it was hard to tune and unstable.
Results Table 1 gives the optimal hy- perparameters per scale, and Figure 2 gives the perplexity curves. The per- plexity was calculated on the C4 val- idation set. Consistent with the pre- dictions of our theory, we found that an outer learning rate greater than 1.0 performed best for SF-SGD and a rel- atively large effective outer learning rate also performed best for Nesterov; Moreover, acceleration consistently improved performance relative to the bascline Local SGD. In the supple- mentary material, we report the effect of varying the number of local steps (Section A.1.2), the number of clients/replicas and different ways of FLOPs allocation (Section A.1.3), and gradient variance (Section A.1. We also include the validation results for all the main experiments we ran in Tables 3 to 5.
Hyperparameter
Selected
Range considered
Number of inner steps H Peak outer LR for Nesterov Peak outer LR for SF-SGD bl for SF-SGD
50, 500
50 to 2000
0.7
0.1 to 2.0
2.0
1e-4 to 10.0
0.2
0.0 to 0.99
Peak inner learning rate (150M)
4e -4
4e
Peak inner learning rate (400M)
4e
4e
Peak inner learning rate (1B)
2e
2c
Table I: Optimizer hyperparameters for the three eval- uated sizes. All are based on the transformer architecture, chinchilla-style (Hoffmann et al., 2022).
5
Conclusion and Future Work
In this paper, we studied the impact of the outer learning rate on the convergence of Local SGD through two novel convergence theorems that characterize its role in balancing a trade-off between convergence speed and stochastic gradient variance. We have also studied the impact of using momentum in the presence of an outer learning rate, and provided new convergence analysis for using Nesterov acceleration
the outer optimizer. One limitation of our results is that we only consider the i..d. setting; Studying the impact of data heterogeneity is therefore natural next step. Another avenue for future work is to investigate the role of adaptive outer optimizers in enhancing robustness to client failures and communication delays.
10

---

References
Bauschke, Heinz H. and Patrick L. Combettes (2009). "The wwrg/bbs/0900 00000 0807.
Theorem Revisited". In:
arXiv preprint XXiv:0906.0807, URL:
Borzunov, Alexander, Dmitry Baranchuk, Tim Dettmers, Max Ryabinin, Younes Belkada, Artem Chumachenko, Pavel Samygin, and Colin Raffel (2022). "Petals: Collaborative Inference and Fine-tuning of Large Models". In: arXiv preprint arXiv:2209.01
Brown, Tom B., Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler. Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei (2020). 'Language Models are Few-Shot Learners". In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual. Ed. by Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin. URL: hwwph:tts////t https:::/pproceediug neurips. cc/cccc///oo wwtpaper///c////pccccctcceeea / 2w2000020hhhaa 1457 1457 (bw9674188ffB Charles, Zachary and Jakub Konecný (2021). "Convergence and Accuracy Trade-Offs Federated Learning and Meta-Leernnnng" In: The 24th International Conference
.tmll.
Artificial Intelligence and Statistics, AISTATS 202 April 13-15, 2021, Virtual Event. Ed. by Arindam Banerjee and Kenji Fukumizu. Vol. 130. Proceedings of Machine Learning Research. PMLR, pp. 2575-2583. mlr. mlr.press press aasss/v1300 2/330/caares21e lesleea.aaall
URL: http::/proceedingg
Charles, Zachary and Jakub Konečný (2020). "On the Outsized Importance of Learning Rates in URL: https: //tp:://////ivvi arxivv org/ abs/
Local Update Methods". In: arXiv preprint arXiv:2007.0083
0007700877
DeepSeek-AI, Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang. Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang. Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangho Hao, Guanting Chen, Guowei Li. H. Zhang, Han Bao. Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang. Lecong Zhang, Liang Zhao, Litong Wang. Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang. Meng Li, Miaojun Wang, Mingming Li. Ning Tian, panpan Huang, Peng Zhang, Qiancheng Wang. Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang. R. Chen, R. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T. Wang, Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie. Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q. Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang. Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, Y. K. Li, Y. Q. Wang, Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang. Yi Yu, Yichao Zhang. Yifan Shi, Yiliang Xiong, Ying He. Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou. Yuduan Wang. Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song. Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang (2025). DeepSeek-RI- RR:: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. DeepSeek-AL, Aixin Liu, Bei Feng. Bing Xue, Bingxuan Wang. Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Haowei Zhang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Li, Hui Qu, J. L. Cai,, Jian Liang, Jianzhong Guo, Jiaqi Ni, Jiashi Li, Jiawei Wang, Jin Chen, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, Junxiao Song,
11

---

Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Lei Xu, Leyi Xia, Liang Zhao, Litong Wang. Liyue Zhang, Meng Li, Miaojun Wang, Mingchuan Zhang, Minghua Zhang. Minghui Tang. Mingming Li, Ning Tian, Panpan Huang, Peiyi Wang, Peng Zhang, Qiancheng Wang. Qihao Zhu, Qinyu Chen, Qiushi Du, R. J. Chen, I. Jin, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, Runxin Xu, Ruoyu Zhang, Ruyi Chen, S. S. Li, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shaoqing Wu, Shengfeng Ye, Shengfeng Ye, Shirong Ma. Shiyu Wang. Shuang Zhou, Shuiping Yu, Shunfeng Zhou, Shuting Pan, T. Wang, Tao Yun, Tian Pei, Tianyu Sun, W. L. Xiao, Wangding Zeng, Wanjia Zhao, Wei An, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang. X. Q. Li, Xiangyue Jin, Xianzu Wang, Xiao Bi, Xiaodong Liu, Xiaohan Wang. Xiaojin Shen, Xiaokang Chen, Xiaokang Zhang, Xiaosha Chen, Xiaotao Nie, Xiaowen Sun, Xiaoxiang Wang, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xingkai Yu, Xinnan Song, Xinxia Shan, Xinyi Zhou, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, Y. K. Li, Y. Q. Wang, Y. X. Wei, Y. X. Zhu, Yang Zhang, Yanhong Xu, Yanhong Xu, Yanping Huang. Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Li, Yaohui Wang. Yi Yu, Yi Zheng, Yichao Zhang. Yifan Shi, Yiliang Xiong. Ying He, Ying Tang, Yishi Piao, Yisong Wang. Yixuan Tan, Yiyang Ma. Yiyuan Liu, Yonggiang Guo, Yu Wu, Yuan Ou, Yuchen Zhu, Yuduan Wang. Yue Gong, Yuheng Zou, Yujia He, Yukun Zha, Yunfan Xiong, Yunxian Ma. Yuting Yan, Yuxiang Luo, Yuxiang You. Yuxuan Liu, Yuyang Zhou, Z. F. Wu, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhen Huang, Zhen Zhang. Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhibin Gou, Zhicheng Ma. Zhigang Yan, Zhihong Shao, Zhipeng Xu, Zhiyu Wu, Zhongyu Zhang, Zhuoshu Li, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Ziyi Gao, and Zizheng Pan (2024). "DeepSeek-V3 3 technical report". In: arXiv preprint arXiv:2412. 19437777
Defazio, Aaron, Xingyu Alice Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, and Ashok Cutkosky (2024). "The Road Less Scheduled", In: arXiv preprint arXiv:2405 15662, URL:
https://arXiv. org/ ////ab//2/4/0 15682.
Diskin, Michael, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Quentin Lhoest, Anton Sinitsin, Dmitry Popov, Dmitry Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, Denis Mazur, Ilia Kobelev, Yacine Jernite, Thomas Wolf, and Gennady Pekhimenko "Distributdd Deep Learning in Open Collaborations". In: Advances in Neural Information Processing Systems (NeurIPS).
Douillard, Arthur, Qixuan Feng, Andrei A. Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Mare' Aurelio Ranzato, Arthur Szlam, and Jiajun Shen (2023). "DiLoCo: Distributed Low-Communication Training of Language Models". In: arXiv preprint 100i::23111.811100 URL.: https://arXiv.
.rrgsiiii.rr///eoeeee www.oooggg...oo.o..oo... abs//311...../. 08105.
Douillard, Arthur, Qixuan Feng, Andrei A. Rusu, Adhiguna Kuncoro, Yani Donchev, Rachita Chhaparia, Ionel Gog, Mare' Aurelio Ranzato, Jiajun Shen, and Arthur Szlam (2024). "DiPaCo: Distributed Path Composition". In: arXiv preprint arXiv:2403. 10616. URL: https : / arXiv.
org/abs/2400 10616.
Eichner, Hubert, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar (2019). "Semi- cyclic stochastic gradient descent". In: International Conference on Machine Learning. PMLR,
pp. 1764-1773.
Glasgow, Margalit R., Honglin Yuan, and Tengyu Ma (2022). "Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective". In: International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event. Ed. by Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera. Vol. 151. Proceedings of Machine Learning Research. PMLR, pp. 9050-9090. URL: httph:://///t http::://proceeding mww.prrss.///ee..mmmmm.c v111 gl glasgow22a html. Gu, Xinran, Kaifeng Lyu, Sanjeev Arora, Jingzhao Zhang, and Longbo Huang (2024). "A Quadratic Synchronization Rule for Distributed Deep Learning". In: International Conference on Learning Representations.
Gu, Xinran, Kaifeng Lyu, Longbo Huang, and Sanjeev Arora (2023). "Why (and When) Does
Local SGD Generalize Better Than SGD?" In: arXiv preprint arXiv:2303.00 200320013.1115 URL: https:
//arXiv. wwwpxvvv.ogg//ee abs/ 2303. 01215.
Haddadpour, Farzin, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi (2021).
"Federated Learning with Compression: Unified Analysis and Sharp Guarantees". In: The 24th
International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event. Ed. by Arindam Banerjee and Kenji Fukumizu, Vol. 130. Proceedings of Machine Learning Research. PMLR, pp. 2350-2358. URL: http: http://proceedings . mlr, ppess/v130 haddadpour 21a. html.
12

---

Hanzely, Filip. Slavomír Hanzely, Samuel Horváth, and Peter Richtárik (2020). "Lower Bounds and Optimal Algorithms for Personalized Federated Learning". In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 6-12, 2020, virtual. Fd. by Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-'Tien Lin. URL:: https: / /ptpr/eeer...gs...///e/e//./..se neurips cc/paper/2020 http//hahhhhhhaaa 177 (tcf7/92231169337751111
Abstract. .tmml.
Hoffmann, Jordan, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre (2022). "Training Compute- Optimmal Large Language Models". In: Advances in Neural Information Processing Systems (NeurIPS).
Huang, Chao, Jianwei Huang, and Xin Liu (2022). Cross-Silo Federated Learning: Challenges and Opportuniries. aiv: 2206 12949 LG]. URL: https: / aarpariivvvvooo/..e wwwg.ooggga... hts//bbs/220..... 12949.
Iacob, Alex, Lorenzo Sani, Bill Marino, Preslav Aleksandrov, and Nicholas Donald Lane (2024). "Worldwide Federated Training of Language Models". In: arXiv preprint arXiv:2405. 14446.
Ivgi, Maor, Oliver Hinder, and Yair Carmon (2023). "DoG Is SGD's 's Best Friend: a Parameter-Free Dynamic Step Size Schedule". In: arXiv preprint arXiv:2302. 1202. 2022.
URL: https: //axivv org/
abs/2302. 12022.
Jaghouar. Sami, Jack Min Ong, Manveer Basra, Fares Obeid, Jannik Straube, Michael Keiblinger, Elie Bakouch, Lucas Atkins, Maziyar Panahi, Charles Goddard, et al. (2024). "INTELLECT-I
Technical Report". In: arXiv preprint arXiv:2412.011 152.
Jaghouar, Sami, Jack Min Ong. and Johannes Hagemann (2024). "OpenDiLLoCo: an Open-
Source Framework for Globally Distributed Low-Communication Training". In: arXiv preprint
arXiv:2407.0783 078522 URL: https: http:///.........////rs/ea/ wtw//as/////0/// 07852.
Jhunjhunwala, Divyansh, Shiqiang Wang, and Gauri Joshi (2023). "FedExP: Speeding Up Federated Averaging via Extrapolation". In: URL: https: /
Jiang. Ziheng. Haibin Lin, Yinmin Zhong, Qi Huang, Yangrui Chen, Zhi Zhang, Yanghua Peng, Xiang Li. Cong Xie, Shibiao Nong, Yulu Jia, Sun He, Hongmin Chen, Zhihao Bai, Qi Hou, Shipeng Yan, Ding Zhou, Yiyao Sheng. Zhuo Jiang, Haohan Xu, Haoran Wei, Zhang Zhang, Pengfei Nie, Leqi Zou, Sida Zhao, Liang Xiang, Zherui Liu, Zhe Li, Xiaoying Jia, Jianxi Ye, Xin Jin, and Xin Liu (2024). "MegaScale: Scaling large language model training more than 10,000 GPUs". In: 2/st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pp. 745-760. Karimireddy, Sai Praneeth, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh (2020). "SCAFFÓLD: Stochastic Controlled Averaging for Federated Learning". In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Viriual Event. Vol. 119. Proceedings of Machine Learning Research. PMLR, mlr. www.s/eesiiivve http///v1/kkaaiiiiiiiii http//aiiiiidddddrro html.
pp. 5132-5143. URL: httt:://proceeee
Khaled, Ahmed, Konstantin Mishchenko, and Peter Richtárik (2020). "Tighter Theory for Local SGD on Identical and Heterogeneous Data". In: The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy).
Ed. by Silvia Chiappa and Roberto Calandra. Vol. 108. Proceedings of Machine Learning Research. mlr. press/ prres/vv00 /v10///0////// 1100///yyumm///// 20a. html. Koloskova, Anastasia, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich (2020).
PMLR, pp. 4519-45299 URL: http::/proceeddiiiiiee
"A Unified Theory of Decentralized SGD with Changing Topology and Local Updates". In: Proceedings the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Vol. 119. Proceedings of Machine Learning Research. PMLR, pp. 5381-5393. 1v11 19/ h/koloskovaa0a.....mmommmmmaaaaa html.
URL: http: //proceedings .mw.. mmlr. press//eeeeee /v1//v//
Konečný, Jakub, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and
Dave Bacon (2016). "Federated Learning: Strategies for Improving Communication Efficiency". In: NIPS Private Multi-Party Machine Learning Workshop.
Li, Hanmin, Kirill Acharya, and Peter Richtárik (2024). "'Th power of extrapolation in federated learning". In: Advances in Neural Information Processing Systems 37, pp. 224236-124291 Li, Hanmin and Peter Richtárik (2024). "On the Convergence of FedProx With Extrapolation and Inexact Prox". In: CoRR. arXiv: 2410. 01410 [math. OC]. URL: http: / arxiv org/ abs/ / 2410. 0114101.
Li, Tian, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith (2020). "Federated Optimization in Heterogeneous Networks". In: Proceedings of Machine Learn- ing and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4 2020. Ed. by Inderjit S. Dhillon,
13

---

Dimitris S. Papailiopoulos, and Vivienne Sze. mlsys.org. URL: http::::/t//oeeeediiiiii mas.syyynnnnmmnsss......m org/book/316. pdf.
Liang, Feng, Zhen Zhang, Haifeng Lu, Victor C. M. Leung, Yanyi Guo, and Xiping Hu (2024). catpruuniiaatoo--fffcieeee Large-Scale Distributed Deep Learning: a Comprehensive Survey". In: arXiv preprini ar arXiv:2404.061 14. URL: https: / //rvvv..vvvvva////////a//aaaa wttpooo/ abs/2404 //////24400011...11
Lin, Tao, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi (2020). "Don't Use Large Mini- batches, Use Local SGD". In: 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. URL:
Liu. Bo, Rachita Chhaparia, Arthur Douillard, Satyen Kale, Andrei A. Rusu. Jiajun Shen, Arthur Szlam, and Marc' Aurelio Ranzato (2024). "Asynchronous Local-SGD Training for Language Modeling". In: arXiv preprint arXiv:2401.09 109115. URL: https: / /aiv.ir.vvva///i/ www.aaiwwv/.v.aaaaaa.e.....weeae ats///0a/24111 09135. Loshchilov, Ilya and Frank Hutter (2019). "Decoupled Weight Decay Regularization", In: 7th Inter- national Conference on Learning Representations, ICLR 20/9, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. URL: /tttpp:://pprrreee
ceet/forummidee P1d-Bkg6R.CC
Malinovsky, Grigory, Konstantin Mishchenko, and Peter Richtárik (2022). "Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization". In: arXiv preprint arXiv:2201.1 1066. URL: /tttps://arX.e .tw.v..og//v.....o.ooo...o..ooll ab// /t//abbb/22....//// 1 11066.
Malinovsky, Grigory and Peter Richtárik (2022). "Federated Random Reshuffling With Compression and Variance Reduction". In: arXiv preprint arXiv:2205.039) URL: https: / org/ abs/ 2205. 03914.
McMahan, H. Brendan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Ar- Learning of Deep Networks from Decentralized Data". In: Proceedings of the 20 th International Conference on Artificial Intelligence and Statistics (AISTATS).
cas (2017). "Conmunication-Effeee
Mishchenko, Konstantin, Ahmed Khaled, and Peter Richtárik (2022). "Proximal and Federated Random Reshuffing".. In: ICML. Vol. 162. Proceedings of Machine Learning Research. PMLR,
pp. 15718-15749.
Mitra, Aritra, Rayana Jaafar, George J. Pappas, and Hamed Hassani (2021). "Achieving Linear Convergence in Federated Learning Under Objective and Systems Heterogeneity". In: arXiv preprint exii:211220000
URL: https: htt//arivvvo//////////// abs aaaaa////// 2202. 2102.07053.
Murata, Tomoya and Taiji Suzuki (2021). "Bias- Variance Reduced Local SGD for Less Heterogeneous Federated Learning... In: Proceedings of the 38th International Conference on Machine Learning, ICML 1021, 18-24 July 2021, Virtual Event. Ed. by Marina Meila and Tong Zhang. Vol. 139. Proceedings of Machine Learning Research. PMLR, pp. 7872-7881. URL: http: h h/ppoceedings...... mwt.press/ www.preeevvvee 1119//13/////// murata21a a. htmll.
mlr.
Nesterov, Yurii (2018). Lectures on Convex Optimization. 2nd. Springer Publishing Company, Incor- porated. ISBN: 3319915770.
Ortiz. Jose Javier Gonzalez, Jonathan Frankle, Mike Rabbat, Ari Morcos, and Nicolas Ballas (2021). "Trade-Offs of Local SGD At Scale: an Empirical Study". In: arXiv preprint arXiv:2110.08133
URL: https: / //axiv..//vvvv/// otrgii.rg//aioo.aooooooooooooaae worg/abs/21100 001233....3......
Patel, Kumar Kshitij, Margalit Glasgow, Lingxiao Wang. Nirmit Joshi, and Nathan Srebro (2023). "On the Still Unreasonable Effectiveness of Federated Averaging for Heterogeneous Distributed Learning". In: Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities. URL: https: / wwwnreeeeeeeeeeeeeeeee wwt./eeet/ooueee devSSssbbrsssssss.........
Patel, Kumar Kshitij, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U. Stich, Ziheng Cheng. Nirmit Joshi, and Nathan Srebro (2024). "TTh Limits and Potentials of Local SGD for Distributed Heterogeneous Learning With Intermittent Communication". In: arXiv preprint htggabs/2400 11667.
arXiv:2405. 1667. URL: https: //atti
Raffel, Colin, Noam Shazeer, Adam Roberts. Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu (Jan. 2020). "Exploring the limits of transfer learning with a unified
text-to-text transformer". In: J. Mach. Learn. Res. 21.1. ISSN: 1532-4435.
Reddi, Sashank J., Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan (2021). "Adaptive Federated Optimization", In: 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May ht////ormmmdddieee
3-7, 2021. OpenReview.net URL: https: http///ppeeeeieeeeeeeeeeeeeeeeee
Rush, Keith, Zachary Charles, Zachary Garrett, Sean Augenstein, and Nicole Elyse Mitchell (2024).
"DrJAX: Scalable and Differentiable MapReduce Primitives in JAX". In; International Conference on Machine Learning (ICML) Workshop.
14

---

Safaryan, Mher, Filip Hanzely, and Peter Richtárik (2021). "Smoothnesss Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization". In: NeurlPS, pp. 25688-25700
Sani, Lorenzo, Alex lacob, Zeyu Cao. Bill Marino, Yan Gao, Tomas Paulik, Wanru Zhao, William F. Shen, Preslav Aleksandrov, Xinchi Qiu, and Nicholas D. Lane (2024). "The Future of Large Language Model Pre-training is Federated". In: arXiv preprint arXiv:2405. 200::2405...833....
Stich, Sebastian U. (2019). "Local SGD Converges Fast and Communicates Little.. In: 7th Inter- national Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, .et/ form??dd Seeffdd-Siig -.d.SggnnRRcF...
2019. OpenReview.net. URL: https::/openreetee
Sun, Jianhui, Xidong Wu, Heng Huang, and Aidong Zhang (2024). "On the role of server momentum in federated learning". In: Proceedings of the Thirty-Eighth AAAI Conference gence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Four- teenth Symposium on Educational Advances in Artificial Intelligence.
Artificial Intelli-
A1/22//AAA22/////A DOT: 10. . 1609 / /aai.. v38113. 29439. URL: https:
AAAI Press. ISBN: 179-1-57735-8877
//doi.org/10. 1609/ /aaa..aaa..... v38113..... 29439.
Wang. Jianyu, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman. Martin Jaggi, Tara Javidi. Peter Kairouz. Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li. Luyang Liu, Mehryar Mohri. Hang Qi, Sashank Reddi, Peter Richtarik. Karan Singhal, Virginia Smith, Mahdi koltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sehastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu (2021). "A Field Guide To Federated Optimization". In: arXiv preprint Arv:v:2107 006977. URL.: https://arXiv. org/ 2207 .09.177.697....
Wang, Yujia, Lu Lin, and Jinghui Chen (2022). "Communication-Eficee Adaptive Federated Learning". In: ICML. Vol. 162. Proceedings of Machine Learning Research. PMLR, pp. 22802- 22838.
Wei, Kang, Jun Li, Ming Ding, Chuan Ma. Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor (2020). "Federated learning with differential privacy: Algorithms and performance analysis". In: IEEE Transactions on Information Forensics and Security 15, pp. 3454- 3469.
Woodworth, Blake E., Kumar Kshitij Patel, and Nati Srebro (2020). "Minibatch vs Local SGD for Heterogeneous Distributed Learning". In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, viriual. Ed. by Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin. URL: https::/t//ppooott h/tpp:/:///rooeiiings. wwwpeeeiiiinnnnnnnnineeeeeeeeeee www.neeurrcc.cm ccciiiss.cccceeeeeeo pappp//022222 2020/hash//
457 Woodworth, Blake E.,, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro (2020). "Is Local SGD Better than Minibatch SGD?"
a (00.272824888bb. 2at-24448abb--bbtraaaaeeee html..
In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Vol. 119. Proceedings of Machine Learning Research. PMLR, pp. 10334- 10343. URL: http:/ http///roreeennn.eeee wwweeeiiinnsm..r................ fulur.pres/// htt////oooorhhh0... html.
Yang, Yuning. Han Yu, Chuan Sun, Tianrun Gao, Xiaohong Liu, Xiaodong Xu, Ping Zhang, and
Guangyu Wang (2025). "SPD-CFL: Stepwise Parameter Dropout for Efficient Continual Federated Learning". In: arXiv preprint arxiv:2405.099 09394.. URL: https: h/tp://ax/vvvvv/// wtwg//bs//// aa//aa///2220/ /405. 09394. Yuan, Honglin and Tengyu Ma (2020). "Federated Accelerated Stochastic Gradient Descent". In: Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual. Ed, by Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin. URL: https: //proceedings. neurips. cc pppp://pp/////////////// Abstract html.
Yun, Chulhee, Shashank Rajput, and Suvrit Sra (2022). "Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond". In: International Conference on Learning Representa- lions. URL: httpa: h /ttp///ppeeeeeeee/ee/eeee wwtp:nee/foorreooo irruummdd=dddi wdbdddwbp222mm1
Zhou, Pan, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan (2021). "Towards Un- derstanding Why Lookahead Generalizes Better Than SGD and Beyond". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin.
15

---

P.S. Liang, and J. Wortman Vaughan. Vol. 34. Curran Associates, Inc., pp. 12900-27304. p/occcding... neurips cc paper - files paper 2021 file e55.c8777ccc77244000005adddd--ee pdf.
URL: https : :
16

---

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: All theoretical claims made by the abstract are substantiated by corresponding theoretical results, and we report the results of the experiments as well.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of convergence results after each theorem.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

We include the complete proof in the supplementary and a proof sketch for the main theorem in the main paper.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We disclose the the data used, details of the architecture used, and all optimizer hyperparameters.
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 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 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 can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
18

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they 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: [No]
Justification: The datasets are openly available, and some training code will shared. However, much of the training code is proprietary and won't be shared.
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/
public/guiden Selliic/guies//Ce (CodeSSmmissionooll
for more details.
While we encourage the release of code and data, we understand that this might 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:
/ httppsccccppccccccceeccccecccl //guidessss.eeeeeer CooeeSbmm ssi asionPolicy 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.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
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:
See our response the reproducibility question.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experiments are conducted at large scale, involve extensive hyperparameter tuning, and replicating them many times for statistical significance would be too costly.
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).
19

---

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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror 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 or figures symmetric error bars that would yield results that are range (e.g. negative enror 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:
We provide the details of the FLOP budget the supplementary.
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 well 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 make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///uwu..pppuu//////pppetptte stc/public//eee [ ines?
Answer: [Yes]
Justification:
Our contribution is primarily theoretical and complies with the ethics guide-
lines.
Guidelines:
The answer NA means that the authors have not 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 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: Our contribution is primarily theoretical and does not affect any societal applications directly.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
20

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: The training data are the publicly available C4 and CIFAR-10 datasets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com aomdaatseets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
21

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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 assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourced experiments or 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 in the main paper.
According the NeurIPS Code of Bthies, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourced experiments human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
22

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification: We did not use LLMs for any core component in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: httpp//pps..c/ooeeeeeeeeeeeeeeee for what should or should not be described.
23

---

Supplementary material
A
Supplementary experimental details
this section we provide the details on the language model pretraining experiments discussed
main text.
A.1 Language model pretraining
We study the impact of using various outer optimizers on large language model pretraining. We utilized Chinchilla-style decoder transformer architectures (Hoffmann al., 2022) trained the C4 dataset (Raffel et al., 2020), consistent with common practices in large-scale model training (Douillard, Feng, Rusu, Chhaparia, al., 2023). The following subsections detail the specific hyperparameters. variations in training configurations (such as the number of inner steps and replicas/clients) and analyses of optimizer behavior, including learning rate scheduling and observed gradient cosine similarities.
A.1.1
Hyperparameters details
We show in Table 1 the hyperparameters considered and kept, and in Table 2 the architectural hyperparameters. We the SentencePiece tokenizer with a sequence length of 1024 for all models. We tuned all our optimizers on a separate validation set. We also considered using the Schedule-Fire Optimizer with Nesterov acceleration on top but it was hard tune and unstable. We include the validation results for all the main experiments we ran in Tables 3 to 5.
Table 2: Model Configuration for the three evaluated sizes. All are based on the transformer architecture, chinchilla-style (Hoffmann et al., 2022).
Hyperparameter
150M
400M
IB
Number of layers
12
12
24
Hidden dim
896
1536
2048
Number of heads
16
12
16
K/V size
64
128
128
Vocab size
32,000
A.1.2 Varying inner steps
In Figure 3, we compare the stability of different outer optimizers when varying the synchronization frequency. We experiments a different amount of inner steps, from 50, to 2000. All experiments are run in pretraining from scratch, with 150 millions (150M) parameters. We note that the synchro- nization frequency decreases (number of inner/local steps increases), performance decreases. Notably, averaging (in orange), is relatively constant w.r.t the synchronization frequency: its performance stay stable from H = 250 to = 2000. On the other hand, using Nesterov with high outer learning rate (in light green) is particularly unstable, its performance decreases by 10.7%, this indicates that the learning rate should be tuned alongside the synchronization frequency. On the hand, SE-SGD (in blue) has minimal degradation of performance (4.2%), highlighting the schedule-free property when varying hyperparameters.
A.1.3 Varying replicas flops budget
When increasing the number of distributed replicas, two options are possible: (a) Keeping the local per-replica batch size constant and thus increasing global batch size and flops budget, and (b) Keeping the global batch size/flops budget constant and thus reducing the local per-replica batch size.
We present in Figure 4 results of the first option with x-axis the flops budget for single model size (150M). It worth noting that increasing the number of replicas improves the performance of Nesterov (in green) and SF-SGD (in blue) but the gain quickly plateau. On the other hand, increasing
24

---

18.5
18.0
Perplexity
17.5
17.0
Average
Nesterov, LR=0.7
Nesterov, LR=1.0
16.5
SF-SGD
0
250
500
750
1000
1250
1500
1750
2000
Number of inner steps H
Figure 3: Varying the communication frequency, i.e. number of inner steps H, when pretraining from scratch at 150M parameters.
20.0
Data-Parallel vary steps
Data-Parallel vary batch size
19.5
Average vary replicas
Nesterov (Ir=1.0) vary replicas
19.0
SF-SGD vary replicas
Perplexity
18.5
18.0
17.5
17.0
16.5
16.0
10
10
FLOPS
Figure 4: Pareto front of the flops perplexity, comparing various approach sealing the flops budget: increasing the number of steps, increasing the batch size in data-parallel, and increasing the number of replicas for federated learning.
the batch size for data-parallel (at the cost of more communication, because more DP replicas) or the number of steps (at the cost of longer training) still rapidly improves perplexity. Therefore, wish to highlight here a disadvantage of federated learning methods seldom mentioned: while those methods are extremely communication-effccienn, and be made flops-efficient, their flops-efficiency disappear as the number of replicas increases.
To this problem, several hypotheses could be raised, such as the decreasing cosine similarity between outer gradients as the number of replicas increase, even when using an i.i.d. data split across replicas. In Figure 5, report the average similarity across whole training for different number of replicas. For momentum- based methods (Nesterov, SF-SGD, the similarity decreases from 30% at M = replicas 10% M 16 replicas. Full details across training steps be found in the appendix.
Finally, note that we didn't 't investigate further the second option of keeping the global batch size/flops budget constant and thus reducing the local per-replica batch size. We found that dividing the batch
25

---

size by the number of replicas leads quickly to a local per-replica batch size that is critically low, and further reduces the Hlps-efficiency. More investigations should be pushed that direction.
A.1.4 Schedule-free but not tuning-free
The schedule-free method of Defazio et al., 2024 enables not doing any learning rate scheduling, greatly simplifying training configuration. However, it doesn't mean it hyperparameters--umme turrssttunnngeee Indeed, we found out that we had to extensively tune the initial learning rate (to 2.0), remove learning rate warm-up contrarily to what is advised, and use particularly low bl decay: 0.2, as illustrated in Figure 6.
A.1.5 Pretraining: outer learning rate scheduling
Schedule-free SGD enables not having to manually scheduling the outer learning rate. Therefore, we wondered if we could improve the SotA federated learning baseline, DiLoCo (Nesterov outer optimizer), with an outer learning rate schedule.
investigate in Figure three schedules: constant in (Douillard, Feng, Rusu, Chhaparia, et al., 2023), cosine decay, and linear after a plateau. For the latter we consider a constant plateau for 10% and 25% of the total steps. For each method, we also tuned the peak outer learning rate. We don't use any warm-up in the outer optimization always found it to be harmful.
We find that constant outer learning rate is the best performing schedule. It's unclear how the other schedules are interacting with the inner learning rate scheduling. possible solution, investigated in this report, would be to increase the number of inner steps H the inner learning rate decreases (Gu, Lyu, Arora, et al., 2024).
A.1.6 Cosine similarity between outer gradients
We display the cosine similarity between outer gradients, across scales (150M, 400M, and IB) in Figure 8, and across replicas (for 150M, from 2 to replicas) in Figure The solid line represent the mean, and the shaded area the standard deviation. We normalize the x-axis as a percentage of the training in order to compare models which have done different amount of steps (e.g. 24,000 steps for 150M vs 30,000 for 400M).
Cosine similarity between outer gradients
0.35
Cosine similarity between outer gradients
0.250
Average
Average
Nesterov
0.225
Nesterov
SF-SGD
SF-SGD
0.200
0.25
0.20
0.150
0.125
0.15
0.100
0.10
0.075
2
6
10
14
16
150M
400M
18
Number of replicas M
Model Size
Figure 5: Cosine similarity between outer gradients across different number of replicas (left) and model scales (right). We average the similarity across the middle 50% of the training.
26

---

Neslarew, Constart LK-1 35
200
Neaturow, c2ae decey wi pept LS- 10.30
Neateres, constort
114
5F-5CD
Traiiing Steps
Figure 7: Which outer learning rate schedule use?
Figure 6: Tuning b1 decay has a major impact on performance, and its value must be very low.
Average SF-SGD
Average SF-5GD
Average SF-5GD
similenty between cuter gradients
Casine similerity between
Cosine similarity between
% training
% training
% training steps
(a) 150M
(b) 400M
(c) 1B
Figure Similarity between outer gradients across steps and scales.
27

---

Average Nesterov
Average
Nesterov
Cosine similarity between outer gradients
Cosine similarity between outer gradients
SF-SGD
0.18
n.a
0.
0.5
0.4
02
0.
training steps
training steps
M=2 replicas
(b) M=4 replicas
1.0
1.0
Average
Average
Nesterov
Nesterov
Cosine similarity between outer gradlents
SF-SGD
Cosine similarity between outer gradients
SF-SGD
0.8
0.8
0.0
0.6
0.0
022
0.4
0.5
0.8
1.0
0.0
0.2
0.8
0.5
0.8
1.0
training steps
training steps
(c) M=8 replicas
(d) M=16 replicas
Figure 9: Cosine similarity between outer gradients across steps and number of replicas.
28

---

Table 3: Complete hyperparameter sweep results across model scales and configurations. All experiments use C4 validation set with sequence length 1024 and batch size 512.
H
M
Algorithm
Learning Rate
Perplexity
Model Size
Data-Parallel Baselines
Data-Parallel
18.07
150M
Data-Parallel
4x BS
16.89
150M
Rata-Parallel
15.28
400M
Data-Pa Iata-Parallel
4x BS
13.21
400M
Data-Paralles
13.38
1B
1
Data-Parallel
4x BS
11.34
IB
Local SGD Experiments
50
SGD
1.0
17.75
150M
50
4
Nesterov
0.7
17.25
150M
50
Nesterov
1.0
16.38
150M
50
4
SF-SGD
2.0 (8=0.2)
16.88
150M
50
SGD
1.0
14.90
400M
50
4
Nesterov
0.7
13.71
400M
Nesterov
1.0
>30
400M
50
4
SF-SGD
2.0 (3=0.2)
13.95
400M
SGD
1.0
13.67
1B
50
4
Nesterov
0.7
12.51
IB
SF-SGD
2.0 (3=0.2)
12.40
IB
Varying H (Local Steps) at 150M, M = 4
150
4
SGD
1.0
17.58
150M
150
Nesterov
0.7
17.90
150M
150
4
Nesterov
1.0
16.79
150M
150
SF-SGD
2.0 (3=0.2)
16.96
150M
250
4
SGD
1.0
18.20
150M
250
Nesterov
0.7
18.09
150M
250
4
Nesterov
1.0
17.12
150M
250
SF-SGD
2.0 (3=0.2)
16.97
150M
500
4
SGD
1.0
18.44
150M
500
Nesterov
0.7
17.95
150M
500
4
Nesterov
1.0
18.15
150M
500
4
SF-SGD
2.0 (3=0.2)
17.18
150M
1000
4
SGD
1.0
18.18
150M
1000
4
Nesterov
0.7
18.16
150M
1000
Nesterov
1.0
18.75
150M
1000
4
SF-SGD
2.0 (6=0.2)
17.29
150M
2000
SGD
1.0
18.11
150M
2000
4
Nesterov
0.7
18.40
150M
2000
Nesterov
1.0
18.36
150M
2000
4
SF-SGD
2.0 (f=0.2)
17.59
150M
Varying M (Number of Nodes) 150M, H 50
50
2
SGD
1.0
18.64
150M
50
2
Nesterov
1.0
16.81
150M
50
2
SF-SGD
2.0
(3=0.2)
17.13
150M
50
8
SGD
1.0
18.38
150M
Nesterov
1.0
16.27
150M
50
8
SF-SGD
2.0 (f=0.2)
16.92
150M
SGD
1.0
19.86
150M
50
16
Nesterov
1.0
16.25
150M
50
16
SF-SGD
2.0 (3=0.2)
16.75
150M
29

---

Table 4: Additional outer learning rate sweeps for different outer optimizers. All experiments 1 150M model size with = 50 and M 4.
Algorithm Learning Rate
Perplexity
SF-SGD Learning Rate Sweep (B 0.2)
SF-SGD
0.1
>30
SF-SGD
0.5
22.89
SF-SGD
1.0
19,42
SF-SGD
1.5
18.32
SF-SGD
2.0
17.98
SF-SGD
3.0
17.96
SF-SGD
4.0
18.09
SF-SGD
5.0
17.51
Nesterov Learning Rate Sweep (Cosine Schedule)
Nesterov
0.3
17.16
Nesterov
0.5
17.06
Nesterov
0.7
16.93
Nesterov
0.9
17.19
Nesterov
1.1
17.56
SGD Learning Rate Sweep
SGD
0.3 (fixed)
21.04
SGD
0.3 (cosine)
17.68
SGD
0.5 (cosine)
16.63
SGD
0.7 (cosine)
18.84
SGD
1.0 (cosine)
19.21
Table SF-SGD 3 parameter sweep at 150M model size with rate y = 2.0.
50, M 4, and outer learning
3 Value
Perplexity
0.0
>30
0.05
16.88
0.1
16.78
0.2
16.89
0.4
17.15
0.5
17.35
0.7
17.93
0.9
19.07
0.95
19.65
0.99
20.51
30

---

Theory
B
Guarantees for Local SGD
First, we recall our setting and define some notation. We consider the problem minimizing a function f in distributed setting with M workers performing Local SGD. Let z, denote the global model parameters at the beginning of round r. Each worker m initializes its local parameters as Um Iy and performs H local SGD steps according
0m.r,+11 Ym.rr, 79m.r.h
where Im.r.h (ym, + mm,rh the stochastic gradient with noise nr,r and Im.r. (1m,,r.)) is the true gradient. By Assumption we have [9m.r.] Im,r.h After local steps, the global model update can be equivalently written 3y+11 Ir, 79 Σ H-1
Ir.h where 9r.h = + >M Im.r.h is the average gradient across workers and yr, M m=1 Mm...h is the M 1m=19m.r.
average model. Note that these two last sequences are virtual sequences and not actually computed.
We also define F 20 7 Σ hh=0 9r.h intermediate quantity used in the analysis. Table
H-1
summarizes some of the notation we use throughout this section.
Table 6: Key notation.
Symbol
Description
Symbol
Description
M
Number of nodes
Fr
Global iterate at round r
H
Local steps round
Averaged local iterate
R
Communication rounds
Ir.h
Averaged stochastic gradient
7
Inner learning rate
Smoothness constant
Outer learning rate
a²
Gradient variance bound
μ
Momentum parameter
D
|| xо
initial distance to optimum
B.1 Algorithm-inddepedeett results
Lemma 1. (Karimireddy er al., 2020, Lemma 6) Let f be convex and L-smooth function. Suppose
that n < 2 let (x(x) = fxx).. Then
L.
[z, - T1)l) < 1 211
Proof. The proof is provided for completeness only. We have
- - = |a v1 (=)
- 2 2n (r Vf(x) vf(r))
(10)
By the Baillon-Haddad theorem (Bauschke and Combettes, 2009) we have
(x y. y. Vfz f(()) 2
Using this in Equation (10) gives
[T)(() - - -| w/1 (n -n) (7f(()-v[([))
1 S then n 2 and therefore [TT,(x) (x) $ || vl2
Lemma 2. Let .I...... Un be real numbers. Then,
n
y
<
y
72
k=
31

---

Proof. This is just the arithmetic mean-root root mean square inequality and we include the proof solely for completeness. Let be random variable that takes the value of with probability n. and let g(x) Vz. Observe that
Σ Jem
1aal E (g()).
Since g is concave function, by Jensen's inequality we have that IE [g( - (E [x]). Therefore,
Mu = E = g [Y)
v
Lemma 3. (Variance of Sum of Conditionally Independent Random Variables). Let Zi... Zn be random variables such that Zg satisfies
E 2 = 0,
and,
E
[2]11]] = of;
where E, [1] denotes expectation conditional on Z1, 72, Zi. Then,
27
n
E
2
Proof.
E
Z
E
E
Σ
2
E
E
Σ
Z
+ 1 11 +2
Σ Zio Zn
E
E
Σ
Zi
+ o
The cross-term En-1 surable with respect to the sigma-algebra generated by Zz,..., Zn- 1- Continuing,
2
(2(22))
-
Zi, 2m
vanishes because En- [2m] = 0 and Σ Z; is mea-
i=1
E
Σ
2
E
Σ
2
+ o
Recursing we get,
E
Z
2
This completes the proof.
Lemma 4. (lvgi, Hinder, and Carmon, 2023, Lemma 7). Let S be the set of nonnegative and
nondecreasing sequences. Let V1, U2,...bu be a sequence in S. Let C, E Ft for all = 2,2..... T and let X, be a martingale difference sequence adapted F. such that [Xe] S C. with probability 1
for t 1,2,.... ... T. Then for all 8 (0, 1) and X, E Fi-1 such that X, S C. with probability 1,
we have that with probability at least 1 8 - Prob (3t & T EICC C. c) that for all > 0
Σ 1=1
viX;
< 88lt
0., Σ
(X; X.) + +000
i=1
where 00,5 log
60 log 6t
32

---

Lemma 5. Suppose we have
rk+1 S (1 + a)r bōg +
Then,
rgeak
+ c bK b
min I
Proof.
Let wk+11
We have
I-a"
Wk417k41 S (1 + 0) Wk+1 17k bw O6 + cwk+1
wkrk bw + cwk+1.
Telescoping,
K-1 WKTK I Woro b Σ
K-1
Wj+10 10 + Σ
Wj+1-
j=0
1=
Rearranging,
K-1
Woro
Wj+1dj S
k Σj
Wj+1
1=0
b أΣح Wi+1
K-1
b
We have Wik
Wk-1 14a
wo (I+a)t:
Therefore,
K-1
Wo
10++1
+ 1+a)) a)+
100
(1 aa
1=0
K
(1 a)K²
Therefore,
K
ro(1 + a)*
Σ
w 15 <
+ c
k- Wg+1 j=0
bK
b
Finally, it remains to use that + a S ea
B.2 Convergence guarantees without momentum
We begin with a lemma that establishes the regret of the local optimizer. Often the regret is measured against the optimal point (like x.,) but here we instead utilize against the initial point yr,0 Zr. Lemma 6 (Regret against starting point). For any learning rate O, the inner product between the displacement from the initial average iterate and the average gradient satisfies,
H
H-1
1
Worh Ur.0. 9r.h) _
1r 11
-lu Vr.n 12
2n
h=
h=0
Proof. We begin by using that Vr,h+1 = Yr.h - 19r. and expanding the square as 1 Vr.oll2 1|yr.h 199r, - 0l
11 Vr.ol 102 n llg 112 2n (Ur.n 2r.0 gr.))
Rearranging isolate the inner product term, we obtain
I|ur.A vr.oll || v1,oll + 1l
(Ur. Ur.u. 9r.k.)
2m
33

---

Summing over h from 0 to H - 1,
11rr,h Br.0012 -11yr.44 3r.oll
Wnnh 1r.0
2 ll
21)
H-1
H 4-1
(llyrn - -1:b011-11u br,al1
7
Σ
ll 11
2n h=0
2
h=
The first sum telescopes
(llv, -1bbaa-1ll -110h.41-8.001 -Br,ol3)
1111,0 -rrool -012-11 -11 - vnool
= =-llyr, - -Bholl
Therefore,
#1 WNr Vr.00 gr.))
11 ynoll
11
Σ
21
2
1=0
h=U
1|
yr.oll
11
2n
Lemma 7. (Local client drift bound). Suppose that Assumptions I and hold. Then in Algo- rithm GEN-LOC-SGD for all r and h, in T, then
M
11um,r. Ds 21
M
m,
Proof. Let Tr (Um,r,t) U, 19m.r.h where Iun,r. h is the stochastic gradient, and Ty (ym,,,,)) y - m,, is the corresponding expected gradient update. We have
Umrr,11 Darrh41 (ym,),)))))
TT, (U).rh))
=Ty (ymmm,
T (u).mi)))) + Tn(Um.m)) - T F (Ua...)) (Ta (ym.rh)) Tr (u
-1m,hmm T., + [Em.r. En.rih,,
where Em,rc
(y,, Ty, (Bmm.rh))
mmmrr is the noise term. Define Vr.h
M7 Σm, 118mm Nerr,
It follows that
M
Vr
1
Σ
1Vm.r Ve.rAtzll
M
m,3=1
M
Σ
(2m,,,)) - Ty(Venmiill + I1Em.r.h - Eelniel??
M
m1,5=
+ 2 (Tmm))) (N)(m))) Samil ).
Taking conditional expectation gives
M
Er [Vr
Σ
(Jm,)))) - -T,(U,,n)) IEn [[lem.n - Samall?]
M
87
34

---

Finally, using the fact that [[T,(x)) tion 2, we get
TT,lill - 12 yll whenever 1j S E (Lemma 1) and Assump-
M
E [Vr++1]
S
1
Σ
Ilmmn - -arnll + +
M
m,a=1
Vr,h + 2172
Therefore by taking unconditional expectation and recursing from h 0 where all local iterates equal to F, (so Vr, = 0), we get E [V.A]] & o²
Proof of Theorem I. W begin by analyzing how the squared distance to the optimal solution changes after one round of communication. From the update rule, we have,
H
H Σ h=
||,++1 - x2112= = 1|,,- 2+11² - 2n7
Σ
(Ir xt, gr.h) + np?
gr
(11)
h=0
We rewrite the inner product term as
(Ir T.. Tr. = (x., Ir, Brch)
(xx yr, Ir,h + (Urch Ir. 9r.h).
Summing over all local steps we obtain
#-1
(rr T.. 9r.h)
(x. Mr, Dr.n +
Wnih 2t 9r.h)
A=
4=0
h=0
Applying Lemma we get
H
11
1 - ynoll 11
Σ
(2r
gr,g)
Σ
(x. Vr.h: Ir.))
+
11gm
(12)
21
A=U
h=0
h=0
Observe that since Dr.H
vr.
17
== Ir.hs Equation (12) becomes,
H1-1
H-1
H-1
H
H
Σ
(2,
x. gr.h)
Σ
(a. Vr.hi Pr.h)
"
Σ Ir
+
n
11 11
A=0
h=0
Plugging this back into Equation (11),
H
||,,11 - I2112 $ ||x, 2 2077
Σ
(x. - Dr.h:
h=0
H-1 + +m
H
+ + - 1)
Σ
Irch
h=0
h=0
Let us take expectation conditional on II,...,
E, ||
x=113]
S ||,,
12112 + 2mm
Σ Er Krx Dr.he gr,1a)]
(13)
#-1
mm²
E, |llmall
+ +122(07 - 1)
Σ gr.h
A=
For the squared norm of the average gradient:
E,
[²]
= E,
Er
1 1rih [²]]
E,
Ey
|| - I1,a + ||
+ E, [m
M
35

---

where we use Er,A-1 [ to denote expectation conditional on the o-algebra generated by all the stochastic gradients up to and including step h Substituting this into Equation (13),
rn Ho²
Er || - 2.12] = 1|,, - x=112 + 207
E, [(r. - Drchn
M
h=
(14)
11 + 70
11
E. || -
Σ
Ir.h.
h=0
A=U
Now we bound the inner product term:
Ep [xx Br gr.h)]
Er, [1E)= 1 [(x+ Br, gnAll]
Er
{I= Ur.h. Fr.h
M
1
Σ
Ep [(o++ - Driho Fm.nh))
M
m=1
1
Ey Ker Vmarchh + Umarc Dr Fm.r,t))
M
m=1
Σ
Ex
Σ
Ep
Kymmr - Ur (m.
M
M
Using Young's inequality for the second term,
E, 1x=- Vr,h. gr.h
(15)
M
Ilm.r
Vr.tol?
Σ
E,
(xx Ne Im.rchh +
Σ
E,
11 1l?
M
M
2a
2
m=1
m=1
M
Vr
Br (xx, Me mmrth
E
(16)
2a
2M
where Vr,A
L
Em= Er [Ilmm.n 3raall?] by definition. By the convexity of f.
17
(x, Un Jm,r.hh (x., Um.rch (f(ymrr)))
< f(x)) - f(ym,r.h) -1( - [(xx))
(17)
For the variance term, when 17 < T. we use Lemma 7
M
Vr. =
Σ
E,
[1mm.n 11
M
m=
M
M
[1ummrr Usurr 112)
E,
M
M
m=
$=1
M
Σ
[lummrr No.r,ael
M
< 2m² o s 2n220 H
(18)
By smoothness.
Am..r 21= [V 2L(((m))))) f(x.)).
(19)
36

---

Plugging Equations (17) to (19) back into Equation (16) we get
-11
aL)
M [ f(x))) + g202H
B, [xx Mrrt gr.)l -
Σ m=1
(Br
(20)
M
a
Substituting (20) back into our main recursion (Equation (13));
Er || - 2.11²] s 1|,,, 2.112
21 -LL)
H-1
Σ Σ (Ep (f f(xx))
2n y0² H²
a
7p Ho²
H-1
Σ Ey [Ilmn 112] + - 1 T)
H-1
Σ gr,h
+ 7Tp
M
(21)
We now have two cases. Case If y 1, then we have by Lemma and Jensen's 's inequality applied ||-11.
H 1
H-1
11 lo
E
grch
= E,
(gr.h
Er (0r.il))
+
E,
h=0
h=0
h=
# Σ
E
(gnn
Ex [9min))
+
EE [L - [gr
H Σ
27
E,
(gr.h
E, (9r.N))
+
Σ
E, [...
4=0
0²
H
E,
Trch
M
h==
H1
<
H
EE
||
11]
(22)
M
N=0
Using Jensen's inequality and smoothness we have
M
E,
|| 11
E,
M
A
Σ Ep
| [Vmm
M m=1
2L M
E, [f(Um.n.h) f(xx))
(23)
M
m2
37

---

Using Equations (22) and (23) into Equation (21) we get
||: No 12] S 1| J.
Er
207(11 aaL)- - (1 ( 1)H)
H M
(,, ((mmma))-((xx) + 211¹ 20222² H²
M
h=0 m=1
H²1
M
2117| aL
Lnn(1 (
|rr - x.112
Σ
Rrr (((m,r)) - [(x)))
M
201² 2 H2
721
+
M
2n yo H2
11
= ||,,, - xx,11 - H1 - aI.. Im + (y- 1) [8+41]
M
(24)
where in the last line we defined
H-1 M
8p41
Σ
Σ 1=0 m=1
(f(mm.r))
f(x)))
(25)
MH
Case 2. y S 1, then we can simply drop the last term in Equation (21) and use Equation (19) get
E, ||r++1 - s0.13] z ||-r - xx.12 2077(1 aL - nL)
#-1 M
(E, [[(Mmrr))) - -((x)))
M
h=0 m=1
21 20² ?m²Ho² Ho² +
M
2n 2 H2 7m Ho²
1,, z.1 1 aL aL- ALL-nLA -nL)EE [8+t1]
a
(26)
where in Equation (26) we again used the definition in Equation (25). Looking at both Equations (24) and (26) and taking the maximum we get that for any 7
E, [|art1 x111²] ||,,
12112-
-2 ((1 aI- aI-1 + - 1) [5.+1]
2 H² 17² maxt HHH?
M
where (x)+ max(xx is the ReLU function. Putting a 21 1
we get
E, [|:441 x. ||,,, x.12 17 21 (7 H)) [8.+1]
ALm H² - 17² max HH2
Under the requirement that the stepsizes 11, satisfy
nl(1 + - 4'
we obtain our recursion
E, [|ær+1 z, =_12]
m7. H < ||,,, 2.11
E, 8,_1 + 2 22 17 max{x? 2 2
2
M
Taking unconditional expectations and rearranging we obtain.
E 8, [,-1]
2
E ||,,,
x.1l 12
E ||0.41 xx 1=]
+ 2L 2
2n max 1)
H
M
38

---

Summing both sides as r varies from 0 to R - 1 and dividing by 1/R we get
E
E 6
| z.1l²
| xz 1²1]] + 8
2n max 1)o?
YRH
Dropping the negative term and using Jensen's inequality gives
R-1H-1 M (0mm)a)) f(ax)) -
R
E f
E
6r+1
MRH
R
==
h=0 m=1
r=0
2 2.11
2n max (y. 1)0²
+ 8L o
MRH
M
and this the statement our theorem.
B.3
Convergence guarantees with momentum
Proof of Theorem 2. We analyze the momentum variant of Local SGD:
H-1
Σ
grch ) + 1l(x,, xr-1).
Tr+1 = Iy - 17
h=0
Define
2, Fr. +
H
(Ir 11-
1 p
Then
2p41 Zr
gr.k-
h=0
We have
|r++1 x=.12= =112, =211,=112rr
1=
17222
H-1
Σ 9r.h
2m
H-1
Σ
(2r
F. Ir.h)
(1 22
1==0
h=0
1,212
H
2777
H-1
= 1|,r 22.12+ +
(1 22
gr.h
(I, x. gr.h)
(27)
h=
h h=0
277//44
(Ir - -y-1.
11
Following the same proof as Theorem we can bound (in expectation)
2m7
H
2/222
#-1
H
E. [xx, - Tu, gr.)))) + (1 (1-1)²
Er
gr.h
E, [dr+1
2(1 - 11)
A=0
h=
(28)
122 o
2
7 p 4Tmp3 o² H2 +
7
7
max
M
because the local optimization procedure is the same- the same analysis holds line-by-line, only replacing 7 by r- and requiring instead that
1 -1 (
1
n
1+
H +
(29)
1
39

---

Using Equation (28) in Equation (27) (after taking expectation in the latter) we obtain
Er ||ar41 x.1l²]
1, 1- ==,1 -x
nn
H
Ey
8,41
4L4) 3 700 H2
2(1
11)
1 1
(30)
1j² Ho² M
7 max ((--m)
2
2
H-1
Σ
(or
34 11
In the following, we use the shorthand G,
We now proceed to bound (Iy-1 Tr. G₁) without using the bounded iterates assumption. We
Σ Ir.h-
Ee (2+-1- 2r, 9r.h) note that by definition:
Zr - ---1 - - + 1 x2-
Expanding this out recursively, we get the following formula:
G
8=0
For our analysis, we'll bound the inner product
(0,-1 Zr, G,)
m77
Σ
Gr
==0
r-1
(G. Gr)
m
We will actually bound the sum of the momentum terms over r, i.e. E, (pr-1 - Wr, G.). We have
Σ (r--1 - Ir. Gr)
7Y
*G,
!n'
ΣΣ (ulr-slG G.) G.
2p
To bound the first term above, let A the R x matrix whose (r, s)th entry equals por-ol, and let
T = G2l.... Then
ΣΣ (ul-
We now apply the Gershgorin circle theorem bound this sum, observe that largest sum of absolute values of entries a row satisfy
1+2
(R-1)/2
Σ
11= 24
(R-11/2
1 1 2p (8+1/2
1 1 μ
1
Then, we have
Tr(TATT)
< 1 1
1 11
TT(TT)
=
1 11
Σ 1.,l1
1 -
Therefore, taking expectations we have
R-1H-
n
207T
207744
E [ar
Tr-1,9r.N
R [xr-1 G+)
1 1
11
0
h=0
0
R-1
#-1
2mp
my
E
Σ
gr.h
(31)
40

---

Using Lemma 3 we have
H 1
H M
H-1
Σ gr.h hb
+E
Σ 9
0 H
H-11
+ H
Σ
M
h=0
o²
+ 2
[6.41]
M
where in the last line we used Jensen's 's inequality and smoothness. Using this result in Equation (31)
we get
2
R-1H-1
Σ
Σ
E
- 11-1. S B
4myip
o²RH
2LH
R-1
E
8 r
1 M
2(1 11)
(32)
Rearranging and summing up Equation (30) then using Equation (32) we have
2(1 17
E || - 11 S |100
x.112
E
8r+1
1t)
1 1
r=0
4T,y 70² R
3 H2 112
122
my 2077 R²
max
R +
M
1 1-
1
1 p
11
M
Observe that under the condition
MULH 1
1- 4
16
the last inequality becomes
R-1
E ||2a - 2=113 $ 11:0 - xx11
77, H
E
8 8
4(1 - 11)
r=0
+ =Li 3 700 H2
17 Ho²
7 (1-1)
1 20711 0² R M
1- R
max
R +
M
1 11
11
Continuing the proof and rearranging we get
8-+1 S 4(1 w)ll 20 - 1.12
4no²
(- i , 1) + 1 - M
81771 0²
22 + 16
max
HR
M
It remains use Jensen's inequality.
B.4 Acceleration proofs
We recall the algorithm under analysis as
ym.r.0 = for m 1....,M M
0m,r, 1 Um.r. 199m,r. for h O,I,..., H -
H-1
Ur+1 = Ir. 7
gr.h
h=0
H-1
2r41 = 7/-
yr.h
ソ=0
Er41 = (1 -1-18 Tr+1] Ur+1 Tr+12r+1.
where Irch = 1/2 Σ Dm=1 Im,r,ho 7r 2(++1) and T, = -..3 Note that under the above, Um,r,h
Um,r, and Uy,h 37 ΣM Umrrch We first derive two intermediate lemmas, then proceed to the main proof.
41

---

Lemma 8. Suppose that the local stepsize satisfies have
S
1
Then, for all h E [H 1] and we
21
1
H [10m.rall]]
Lny on
0 H
Hf(u++1)
S
E [f(mm.r
E
+
M m,
2M
h/=h
Proof. By smoothness,
L
f(un,+1)) & f(ur,)) + + (Vf(u,)); un/41 - Uu,,)) + |lun+t1- u,,
2
LOp
=f(ur)) - (V)(u,,)),nn))) +
2 11gni
Taking conditional expectation we have
E, [[(u,A+1) S [(u,,))
7
Σ
M
(VI(Ur)): VI((m.))))
L17
Lnj
1
V (u
M
2M
2
M
m=1
m=1
M
Lai²0²
< f(unk)
1
Σ m==1
[V(mm))) [ ([)(( - VI(um,r,taI)
+
2M
2M
LT7
M
+ 2M
V f (um.r.)))
m=1
f(unk)
V [(,,))))
711 - Ln)
Σ
" Vn, +
Lnfo²
2
2M
2M
where Vr,A- M m= (ur,h) V (um,rr,))
1
Em=1 ||ur,h um,r, 11? Taking
conditional expectation, dropping the [V,
term and using Lemma we have
711-10 Ln)
Lii222 2M
E [f < [f(
E
| (MM., +
+ 122
2M
Observe that in the current scheme, Im,r.h telescoping yields
(um,rra)) Suppose that 1 Laj 2 2.2 using this and
M #-1
2ap 2 h) + 2
H
E [f( < E [f(())))
Σ
Σ Wh
[1 +
Σ
R'
4M
2M
m=
h k/
Using Jensen's 's inequality on ur.h
57
Σm
Umard
M
DM
11 Um we obtain
H-1
LIfo² h)
H-1
[f((+++))] S M m=1
Σ
[(mm.rth)
17
Σ
E
10m
-1?1j002
Σ
R.
2M
h'=h
W=h
Summing up both sides as h varies from to H we get
H-1
Hf(u++1) M
1
Σ
E (y
Σ
E
[
[3]
2M
M.KH
H1-1 Define G, = DD Ir.h and G, D Tr.h- The following lemma characterizes the evolution of the momentum sequence 21, ....... Lemma (Momentum sequence bound). For any r 2 0, the momentum sequence satisfies:
222022
E, [| [13] ||2,- 2=.12 " E,
|
7. (2, I., E, [Gr]).
M
42

---

Proof. Expanding the square,
z x.1 2=11== = 11, - Ix + 1" 2/// (2r Ix. Gr)
Taking expectations and using Lemma 3.
021102211
E, || x-11²] |||,, ==11² 7, B, [|o,1²]
7/ (2r Faa R, [Gr])
M
Proof of Theorem 3. Define the potential function
2 Φ. = r(r 1)((f(u)) f(x+))
2r 2+ 11?
Using Lemma and Lemma 9, we have
E,
[r++|] t
[(x)) (r ()(r + 2)H +1 ((x)))
2
+
Er |ll žr-1 v. |1 || xx 11
??/
H H-1
Lnf H²
n Tf
$ (r + 1)r +
Σ
(B.lf(ummnna) - f(x))
7
Σ
Erll ImaN [12]
+
M
4
2M
2
MAKH
m=
r(r + 1)H1 (f(u,) f(xx))
+ m(( 1)2 E,1l G, 1| + noo (r + 1)2H
2( + 1) xz, Z.,EI,Grr))
2M
Σ
[2(r + (E, (Um,r)))) fxx))) + r(r 1),E, (VUm,r.)) (f 2(r 1)(2, v., Er (0, 10)
M
M.KC
=:A
(r+ (+++)(++2) 2)m
H-1
yn(r 1)2 E, [|| Gr |1
Σ
Σ
Elll Im.rch [13]
4M
m.CC
(r + 1)(r + 2) 02 H² +
(r+ 1)(r + 22
mo? (r 1)2 H
+
2M
2
2M
Now, we bound the terms above separately, First, we bound A. Fix any m, h < H. We have, using convexity of f.
2(r + () - f(xx)) + rrr + 1)ff - f(u,)) - 2(r () - Io. -I.. Im.r,h)
< 2(r + 1)(ym,r, - Fa. Im. , + r(r + 1) 13m,,, ur Imn,thh) 2(r + 1)(2, - Fa, Im.
((r + 1)(r + 2)ymmrr - r(r + 1) 1)ur 2(r 1)ar,gm,r.h
(r+ 1)(r + +2) - Fr, Im.r.h)
=-n(r= + () + 2) Σ (9m.r.hh-9mmr.b.)
Mch
Hence,
2(r + (J - ((x,)) + r(r ((mena)())))) [(u,)) 2(r + 1)(2r Ie, E, (.m, S (nn(r + 1)(r + 2)
Σ
Ear (emml@mmmh,Bmmmm..
Rch
43

---

Since A equals the sum of the above over all m, h < H and dividing by M, we get:
A -n(r 1)(r +
Σ
E
B.llam.r (..mm..........b....
M
m.k Rich
(r () + 2)
E,
E
Im,r. II -
Σ
Im.r,h 1|?
2M
m
RCH
where in the last line we used the algebraic identity that for any sequence of vectors to..... UH
ED
E
(Ue, v%))
1
Σ
Un 11
Σ
2
bcH och
RCH
Next, we have
B (r + 1)(r + 2)m
Erlll Imrr. 11+++ yn(r + 1)2
Σ
Σ
E, Gr [1²]
4M
2
m. k/=h
x + + 1)(r + 2)m
Erll Im.r. [13] + Mn( + 1)²
Er
Σ
Imach 112
4M
2M
m
hcH
m
hCH
Hence, we have
A+ A+BS
7/ + () +2)
Σ
Ryy Σ
rm. 112- Σ
||
Jmarch !1?
2M
h<H
hCH
(r + 1)(r + 2)m7
Er |ll Iminh 11 + (n(rr + 1)²
E,
Σ
Im.r. !1?
4.
2M
m
NSH
m
hcH
(rr +
Σ E3,
Im.rr A 1|2 11 2)]
2M
n(r + ()(r + 2)
Er I1 Imrrc 1131
4.M
since 7 < implies >(r + (r +
(r + 1) - 1 -1 0, and the second term has
positive coefficient with a negative sign.
So overall, we have
(r 1)(r 22
+ (++1)(1
2
2r 1)2
E, [++++]] - 22 x
2M
2 mo² Ro2R²1
2M
RR L o2
2M
2
2M
Summing up from 0 R 1, and taking expectations, get
R Lm 22
2 +
mmo² R
E E
4 <
2M
2
2M
Thus.
R2t ( - ((x)))
2 xo
V. 1|
R L
L2
Oow R
< 1 5
mm
2M
2
2M
which implies that
2 xo Ia 112
RL
R
7110 R
[[[(uR)) [(x.)
R2
2M
2M
The proof of Corollary is straightforward by substitution and is omitted for brevity.
44

---

B.5 Data-dependent guarantees
Lemma 10. Lel I be a convex and L-smooth function. Suppose that we run SGD on I on M parallel nodes as follows
Vmn,r,U Tr: 1m,,1,411 = ymn.r. 19m
where m =
0.1,... H -7-1, 1, and gi.r.h 92.r.h.-.. IMrr. are ii.d stochastic gra- dient estimales such that 1 [ Vy(mm,rr,h) where Er,, []] denotes expectation conditional
on all information up to and including round r and local step h, and 119m,,, V (ym.r,) S a. M
Define further yr.h To Em Mm,,rh- Let Vg,h
> 2==1 l1 vr, Then for all rj S +
we have with probabiliy at least 1 - thatfor all h = 0, U......,
Vra S 4104n/ 02 + 1)0/-1,65
where 0n.8 log
60 log 6h
Proof. Define
A,
1mm...111 Morr.4+1ll*
(33)
M
We will bound Art first, and then use it to bound Vr, later. We have
gm.r,++1 Us ym 799m,r.h [y,.,, 19a.r,h
"m,r, f (Ymmrch) - 17 rmmmhhh V [fmm Borrc 1V [VV.,,) -n 10..k V (W
[Vmm,r,h n/ (ym...h) [Haur 17 [y [[gm,r. go.r.h) (V (9m.mr))) V foll
Therefore
1mm.r.111 Us.r,/+11l 112 (ym,,,)))) (ys,,, 1|2
+ 1/2 || (fm,rch - k,, - (V (1Mm.rh)))) (V),,,))) 1|2
(34)
2n (1m,r)) - (ye,,, (9m.n,h 9..r,)) (Vf(ym,n)) V (y),r))))
We define Pm,r.h the stochastic gradient noise node at round step h: Pm.th Im.r.h v (ym.r.)) Then we can write Equation (34) as
11m, / || (ym,,,)))) - (y,,ys 12 +n/ Pm... Parch 112
-21 (T (ym,,,,))))) Ty (Ms,,, Pm,,,, Parr,))
(35)
We now the inequality ||a b11² < 2||a||2 2/1b11² to get
1m,.hh11 Ve.r,,t11 2 < T (Um, Tn (Us.r.h) 112 +2n |I Pmrr.hh 112 4 Pl 2n (Tr (Jm,),))) - -T,, (M).,,))) Pm..rh par.h))
By Lemma 1, we have
[1Vm,r;k411 Ms.r 11 I1 yarrch 2n 20m2l1,,,,,tll 2nj 1P
2n (Tr, - (Bo...)))) Pmrr. Pe.r.))
Now, we consider the inner product term, observe
(T, (ym,,,))) - TT, (y n Pm,r. Po.r,a)
(Ty (.)), (y(().)) + TT (2).a) T.(Be.n))imm.... - Po.r.h)
(T (Wm... Ty(Ue,n),, Pmr.ch Pa.rhh) + (Ty(Urn)) - (y(uar)); Pmurh Psirch)
(T, (ym.r.)) Tr((inn) Pm.r. Pa,r,)) + (- (-(Ty(Ne,,,)) TT (2 - -Peannh - pmnr.)))
(Ty (Vm,r.h)) -T, Pmo.c Pa.n,h) + (yares))h) (y),h) Pa.rc Pmrrhh
45

---

Averaging with respect to s and m
M
1
(T (y
To(lu.h) + (vr.h)))) Ty N... Pm.n Parnh
M
M
M
(Tm,r))h -Tn (ubaaa Pmard Porr.h)
M
M
(Ty(Horrhh)) Tr (Mr Ps.rch Pmmrrsh
M
m=
Σ
Σ
(Ym,,))) Ty,,r, Pm, ps.r.h)
(36)
M
Averaging Equation (35) with respect and and using Equation (36) we get
M
M
M
M
Uym..h - Ne,r,hil 4xp²
M
11ym,r,t11 - Us.r,+11
Σ
Σ m=1
M
M
M
mh
M
M
2n
ΣΣ
Typ(ee,) Pmor Darch)
M
Using Ar,h defined in Equation (33) we obtain the recursion
Ar,++1 S A
4n²
Σ
M
P 11
2n
Σ
M
Σ
M
(Te(ym.nN) - (y,lnnn) Porr.))
M
M m=1s=1
m=1
Now observe that Il 11 S o² by assumption, therefore
2m
M
M
Ar,++1 S ArA + 22
(1(m)))) - To,,rr,) Pmin - Parr.))
M
Recursing the above inequality we get
2n
Ar. S Ar.0 412
ΣE>
(Um,,,)) Ty (yr,k)) Pmar,k pstr,k)
M
R=
2m
h
M
M
= =2
(T,()m.nk)) (y,,n,s), Pm.rkk - po.r,k)
(37)
M
k=
where we used the fact that since Vm,r.0 = Usrr.0 = for all m, then Ar,o O. Define
1
Hr,h
llym. Vr.all
max fr.ks kSh
(38)
M
m=1
M
M
1
1
X
(Vm..hh)) - Tr(Ur,h) Pmrrh - Ps.r.)).
(39)
Thin
M
m=
Let E,,h []] denote the expectation conditional all information up and including round and local step h. Then,
Er [Xrx] = 0.
Furthermore, we have by the triangle inequality, then our assumption on the noise followed by Lemma that almost surely
(1m,,))) - (yr,n,,, Pm,rch Po.r,b))
< TT (Jm,.rtt) - T,, (Vr.)) [|pm,r, - Pa.r,ull
Tr (Jm.r.h)) T,, (vr,)) (llpmar, + (lPs.r,
< 20 [T(m,,)) - T (2r,)))
< 2o || 1mm - Vr.all
(40)
46

---

By the definition of Xr. (Equation (39)), the triangle inequality, Equation (40), and the definition of Hr.h (Equation (38) we have almost surely
M
1
(T (Umm.,n))) -
Ty (Urrb))) Pmn.rth Psyy,h)
Fr,
M
M
M
Σ
(Tm - TT (yr Pm, - Parrhall
1r,h sml
M
M
20
1
Umm.. VrsAll
Fr,
M
m=
.M
11 yrah
20 31
mmml
Pr.hh
$ 20.
Then by Lemma 4 with y/ Pr.h have with probability at least
P X
S 8
G₂ 1,5
Σ
X2 P. + 4028
A==
k=U
b V 00-1,,4ho02 + 402
16p 0 1
(41)
Observe that
h-1
h-1
M M
Σ
Pr.k
x,
ΣΣΣ (Tm,,)))))) - TT,(Mr,)), Pm,rk Parr,k)
M
k==
k=0 m=1=11
Using this and Equation (41) to upper bound the right hand side of Equation (37) we obtain
Ar, < 4n7² 0²h + - +1
s 4n 02 2h 20 +
2a
2 + (4 2048a)
(42)
2a
where we used that 2ab < aa + 10² in the second step. Let Ny, max4-s Ar,k. Observe that the right hand side of Equation (42) is increasing in h, therefore
Nra 2 + 1) 11
+ 2048a) +
(43)
2a.
Observe that by the triangle inequality followed by Lemma 2
1
Hr.h
1lmmrrh yrrtel
M
M
M
1ym... - Norr.all
M
m== ==1
M
l1ym. Vern
M
Aph-
47

---

It follows that F S V Arn. Using this in Equation (43) we gel
T Ar.h-1
Ara S1 1100 2048a) +
20
Kr,
S 01 (14 2048a) +
2nx
Rearranging we get
1 2a
Nech S ( 2048a)
Put a = 1, then
Ar S 4104n 0² 110
(44)
Now that we have our bound on Ay,s, we can use it to bound V as follows
M
Umm,r vr.a
(45)
M m=
Observe that by Jensen's incquality
1lym,r.h Vrall 112
1
Σ Uarr.
Um M
M (Umerch Norrch)
(46)
M
Combining Equations (45) and (46) we have
M
M
Vr <
ΣΣ
limmh No.r.tel = Arnh-
M
m=1s=1
Combining this with Equation (44) yields the lemma's statement.
Lemma 11. (Per-round regret). In Algorithm the iterates in single communication round satisfy
H-1
|2,41 xx1l² < ||,,, - xx 2222"
11 11 + 2ym 11
19r,
h=0
h=
aall
arn
2
M
19m.r,ll
2mm
1 1-1
Σ
(ymrrr Ios Io, 9m..)h))
M
h=
h=0
where >> 0 is arbitrary and
M
S2 max [|yr,h Br,
Cs
max
Σ
I1 Vr.h 11?
M
Proof. Define the virtual sequences
M Σ
Jr.h =
Im.rh
Fr.0 = Fr.
Fr.h-1 = Fr.h -T19r..
M
m=
We have
|1 - =2,12 = =1
xx11² + 1 2ym (Kr,n Ir.hh
(47)
48

---

The inner product term can be decomposed as
(1y,, Ze Ir.h) = (2r, - Br,h, Ir.h) - (ymm - In, 9r,h)
(48)
Observe that Fr.h Iy y Σb=d Dr,s and Urrh Ir 1) Σ 1-11
Dr,s-
Therefore,
h-1 (7 1)n1
| - yr.h
gr.s
1 11 111/r.
Mr.DD
$ 1 1 Se,
where S2 max, I1 Vr,oll- Using this Equation (48)
(Ir,h Vr 9r.h) $ | Gr.lll 11 $ - -- 11
(49)
Plugging Equation (49) into Equation (48) we get 1 Za 9r.h) I
7 S2
I1gr,a (yrn Iaa Br.h)
M
= =2 119rshll
Σ
Urn - In Im,nh)
M
m=
M
M
= 11 7 62 11
(rrn ymund Imrr
Σ m=1
(umrh - Ix, Im.r (50)
M
M
m=1
For the second term in Equation (50) we have
M
M
1
Yr. Um. rm. S
11 3m.r. llgm..all
M
M
m==1
m==1
Af
am
M
200
2
m=1
M
Qm
(51)
2007
2
M
m=1
Plugging Equation (51) into Equation (50) we get
M
(Err - Fay Ir.h) S 7/
11
+
C3
a7
1
Σ
119m,
20m
2
M
m=1
(52)
1
(ym, Fas Io, Im,r.t)
M
mm
Plug Equation (52) back into Equation (47) to get
|1r - 2.112 < | - -xxl" 7
+ 2ym - G2 11
753
amm
Σ
Ilom,r.l12
2mm M
Σ
Wm,r. Ea Im...h)
M
Recursing we get
H-1
H H-1
||z xxll < || - Ix 2 21
I1g 1 + -
1gr,
h=0
h=0
H
ary
2
2
1mm
(ym,r.h Das Hm.r,t))
M
h=0
mml
49

---

Proof of Theorem 4. Starting with the per-round recursion lemma, we have
|,,+1 x.ll? 1 1,,, I.
+ 2n
11rr
11 212 + 2yn 1 -2
Σ
19r,all
h=0
h=0
HS3H
ar1 2
M
H-1
2mm
H 11-1-
19m.nall
(ym.r - Ioa Im.r.h)
M
M
m=
h=
h=0 m=1
Observe that
Mrr.0ll
-1
gr.k
h
1
19 Il
$ 17
11gr,kl
(53)
k=0
Since this holds for any h, we have that < n > Moreover, by Lemma 10 we have that with probability 5 and an application the union bound that for all r, h
H-1
gr.8 where C2 is defined in Lemma 11.
M Σ
Vm.r.h - Fr.h 11&5 4104m H,
(54)
where = 2- -2llg 60 log
and used that H + 1 2H. Since this bound holds for all h, we have
M
63
max
Um.r.h - Ur, 11&s 4104nfo2HH
M m=1
Therefore by Equation (53) and Lemma 10
H 4-1
H
2
| - x..11 S 1|,,, - -xal1 + 7212
Σ
19 12 +++ +2271 17
1gr.
h=0
410471802H² an1²
M
#-1
?
2mm M
H
(ym.r, 2x Imnr,.))
M
h=0
h m=1
Let Sm.rch = Imn,rh Vy(mm,rhhi) Then,
H
H 1-1 Araall
4104m1202
|| x0112 5 || - Iz 112 + 11
1g 11 + +2 7!1?
2m1 1
M #-1
2ym M
H-1 M
+
110m,r 11?
(u Fa, (.(mm,))))
2
M
m== h=0
h=0 m=1
H
2nm
(ym.n
Iz, Em,rthi)
M
(55)
where Sm,rch = Imrrh
f Define
M
Mrhh
Ilum,r.h - Iall.
D max P PSr.ash
M
m
50

---

Let
M - Ios Sm,r,hh?
X
Σ
(ym,r,h
Vr,h
M
m=1
Let Fr.h-1 denote the sigma algebra generated by all randomness up and including step r, h 1. Note that
M
Eyra-1 (Xrsh]
Σ
Exn, (1lmrrch - Ias Sm.rch?
Dr.h M
M
(um.r,h Bay Ben (Sm,
Fr,h
M
m=
0,
where we used that Vr.A and Mm..r. are both - and that the noise has mean zero. The edge cases Xy.0 are handled similarly. Moreover, using the assumption that ||5m,,, || S almost surely and the definition of Dy
M
X|x
1
Σ m==1
(Um.n - Di Sminyto
Dr.h
M
M
11 xellllEmmaal
M m=1
M
Σ (1.6)
M m=1 1
Applying Lemma 4 on Xr,h with Ur,h Dr.ho Cr. = Nrch = 0 we have
R-1
H-1
M
Σ r=
(ym.r.h - Ii,y In, km)
S &I RH,
(56)
M
0=
where is defined before. Using Equation (56) in Equation (55)
2
Σ
(mmrh
Fx. (f((m, I ||z0 x.11²
|
7221) 1
Σ
M
m,rkh
r.h
R-1
2 19r,
410471700211
27 11 - 7/ 12
Σ
+R.
(57)
a
aryr²
+ 2 M
Σ
119m, + 2ym
16 RH
m.rkh
Let
R-1
2
21047m70217²
Ω - 221 Σ
11 + + 71
Igr.all
+ R
n,
r=0
h=0
(58)
arm?
2
2 M Σ
11
m.r.h.
Then by convexity and Equation (57) we get
|
zz.12 2
||20
+ + 2ym x=.l 2
167 167R. RH
2ym
Σ
(ym.r Is, (ymmmr
M
march
< |0000 x=112 Ω + 2mm
16 RH
(59)
51

---

where in the second line we used that Is is the minimizer of f and therefore (mm,.h v.: Vf(ym,r,)) 2 0 by convexity. not difficult see that this guarantee in fact
applies not just on | - x. I| but on any Tr. Let d, = 1|,, x-ll and d, max,'s dpr Observe
M
Vr =
Σ
Ummrrh - Ix S
Ill sm.r.ol + 1|, - xxlll
M
M
m=1
1g
1|,r, xzll
M
H
n
Σ
Σ
+ 1|,,, - Ix
(60)
M
Using Equation (60) in Equation (59) we get
Jn S dg + 32muo RHvn.
$ db + 32yMLo RH
Σ
1gm.rs
+ 32ymio v RHdR
M
m.h
$ d Ω +
32ymiov RH
+ n²
Σ lem.r.ull
+
M
Therefore
2
de s 2d] + 20 20 20 RH + 27²
max Σ llmmrrslll
(61)
M
By the triangle inequality applied twice and the definition of dR.
Ilum,r, - xall < || 1mm
y.m. /1 + 11l0m. x.
1
Im.rch
+ 11um,rr, - -xall
0
1l + I1ym,r00 F.Il
118 |l + dR
H
< 11
19 + dR-
h=0
Therefore
M
M H-1
Vmm.. - xx 5 7
199m.r.ull + da
M
M
m=1 A=
52

---

We now use the inequality (a + 6)2 6)2
< + 26 to get
M
2
27 =
1ym.n - xall
M
m=1
H-1
l ))
2
S 2
1
2d
M
172
h=0
2
2nj²
Σ
+
20
M
Finally, using our bound on d given by equation (61)
2
)
222 S 4dg - 440 2 RH + +672
1
Σ
llmmmtll
M mut
Therefore
R. max 22.
1,8
I 4dg + 49 81 RH 6n)²
Σ
max
M
mnh
By Equations (57) and (58) and the last equation,
2
Σ
Wmmrhh
Ia, V S |1:0 - x..1² - x.1l² +Q+ 2m HOV RH
m.rch
2
(32ymua RHH)
dR + 2++ $ db
+4 [6] + 2 2048 + 6rf² R
max m.k
Σ
Ilam.r
M
2
(32ymuo v RH)
1
dh
d + 0
+ [cb + 2224 RH + Gnj² R
max
M
< d3 & + 62 + 2/ 20 RH + 4dh + 2
max
(62)
M
m.
Dropping the -d, term, we get
27m M
(Um, Iz, (f(mm,)))) S 5ch 6Ω 870473 RH +n72
>
1l9m.r.tlll
max
M
mirsh
#
24624 2
< 5 + 6r
Ila 112 +2 17 Σ
ler.alll
+ RH
ruh
0=0
h=0
3
Σ
llgm.r.ll 87047 RH 6n²²
max Σ
M
M
m
53

---

Dividing both sides by 2ynRH gives
Σ
(ym.. Lo. (I(mmn))))
5d
3
Σ
11gmall 11?
MRH
RM
RH
r.b
6
7/
R-1
2
24624n0²
+
(63)
RH
a
30n
6n
Σ
8704m12
0² +
max
> Ilom.r.ull
MRH
M
m.rch
mah
Observe that by optimizing over a we have
24624no Hr.
300
3n
Σ
119m.r.hl $2
(24624n02Hr)
Σ
11gm 11?
MRH
MRH m.rch
m.nkh
$
544noi
Σ 11
MR
Using this Equation (63) followed by convexity completes the proof.
54


Reviews:
[{"review_id": "E1b75xHdUr", "reviewer": "Reviewer_GxxH", "summary": "This paper presents a tighter convergence analysis of Generalized Local SGD in convex settings, highlighting the critical role of the outer learning rate. In particular, the authors show that appropriately setting the outer learning rate can: (1) interpolate between vanilla Local SGD and standard SGD, achieving the better of the two convergence rates; and (2) compensate for an overly small inner learning rate. Additionally, the paper provides (a) convergence guarantees when the outer optimizer uses momentum, and (b) the first high-probability convergence bound for Generalized Local SGD. Finally, the authors validate their theoretical findings through experiments on both convex optimization tasks and transformer models.", "questions": "Why is the high-probability bound in Section 3.3 referred to as an \"adaptive convergence result\"? The term \"adaptive\" might be somewhat misleading, as it typically reminds people of adaptive gradient methods such as Adam", "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 is a nice theory paper, with solid technical contributions.\n\n2. The theoretical insights are valuable and provide practical guidance for setting the outer learning rate.\n\n3. The experiments align with the theoretical findings well. In particular, when properly tuned, Generalized Local SGD outperforms vanilla parallel AdamW within a fixed number of training steps.\n\n**Weaknesses**:\n\n1. The writing could be improved. In particular, the presentation of Theorems 3.5 and 3.6 is overly technical. The authors should better highlight the key takeaways and practical implications.\n\n2. The experimental section lacks clarity. For example, in Figure 2, it is unclear what the numbers in the legend refer to. Do they refer to the wall-clock time? I could not find an explanation in the main text or figure caption. Additionally, the authors should clearly introduce all algorithm abbreviations used in the figures in the captions.", "was_revised": true, "final_justification": "All my concerns and questions have been addressed. I would like to keep my positive rating.", "rebuttal": "Thank you so much for your review and positive evaluation of our work.\n\n1. We agree that our use of \"adaptive\" in Section 3.3, as we do not mean adaptivity in the same sense as Adam or AdaGrad (i.e. algorithmic adaptivity), but rather in the sense of obtaining data-dependent guarantees. We will modify the term \"adaptive\" to instead be \"data-dependent\" and thank the reviewer for pointing this out.\n2. We will reorganize the presentation of Theorems 3.5 and 3.6 to highlight the key takeaways and defer the more technical discussions. The core observation from  Theorem 3.5,  is that momentum allows us to use an effectively larger stepsize but does not alter the outer stepsize tradeoff shown by Theorem 3.3. Similarly, Theorem 3.6 shows that when noise magnitude dominates the optimization error (e.g. in later training stages), using $\\gamma < 1$ helps maintain convergence. Conversely, when the optimization term is larger than noise, $\\gamma > 1$ acts like momentum to accelerate convergence. When both terms are comparable, $\\gamma = 1$ (simple averaging) is optimal. \n3. We thank the reviewer for pointing this out. Figure 2 shows the total number of training steps (i.e. $R \\times H$ where R is the number of communication rounds and $H$ is the number of local steps). We will clarify this and add a short table or glossary with all the abbreviations we use."}, {"review_id": "qH28PKTklQ", "reviewer": "Reviewer_DffW", "summary": "This paper analyzes the role of the outer learning rate in Local SGD, proving its impact on convergence and showing it can compensate for suboptimal inner learning rates, sometimes requiring values exceeding 1. The theoretical framework includes extensions to momentum-based outer optimizers and introduces an analysis for tuning insights. Experiments on language models validate these findings.", "questions": "Please see Strengths And Weaknesses", "limitations": "Please see Strengths And Weaknesses", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "1.\tThe paper analyzes local SGD methods in the homogeneous setting. However, the heterogeneous setting is more common in convergence analyses for similar local SGD methods (e.g., [1]). Could the authors discuss the challenges of extending their analysis to the heterogeneous setting? \n\n2.\tSince this work does not propose a new method, I would like to assess its contributions along the following dimensions:\n\na)\tTheoretical Novelty:\n\nAre there any new frameworks or techniques in the theoretical analysis compared to prior works like [1][2]? If so, the authors should highlight these differences more explicitly.\n\nb)\tPractical Impact: \n\nFor optimization methods, it’s not recommended to introduce new hyperparameters if not necessary, due to the cost of hyperparameter tuning. Gen-loc-SGD has more learning rates that need to be tuned compared with vanilla local SGD. Are there some dramatic improvements due to the introduction of the outer learning rates?\n\n3.\tSome suggestions for writing:\n\na)\tClarity of Notation (Lines 54–55 & Algorithm 1):\nThe phrase “for what the ideal learning rate pair ($\\eta$, $\\gamma$) should be” is unclear. The roles of $\\eta$ and $\\gamma$ should be defined earlier, ideally in Algorithm 1, rather than later in Section 3 (Lines 116–118).\n\nb)\tMathematical Notation:\nVectors (e.g., parameters x and gradients g) should be consistently boldfaced for better readability.\n\n[1] Hao Yu, et al. On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization. ICML 2019.\n[2] Stich, SebastianU, et al. Local SGD Converges Fast and Communicates Little. ICLR 2019.", "was_revised": true, "final_justification": "Given that my concerns are addressed, I'd like to raise my score.", "rebuttal": "Thank you so much for your review.\n\n1. \"Could the authors discuss the challenges of extending their analysis to the heterogeneous setting?\" Our primary setting is large language model training, as in DiLoCo and similar works, and there the training data is i.i.d. Additionally, we would like to point out that in the heterogeneous setting, the guarantees for Local SGD are very pessimistic; that is, small degrees of heterogeneity result in much worse theoretical guarantees for Local SGD compared to Minibatch SGD, as discussed in [3, p. 5-6], and it is not clear under which assumptions the algorithm should be analyzed (see [12]). Because we wanted to focus on when Local SGD is superior to the alternatives, this is one more reason we focused on the i.i.d. setting. \n\n**That said, we believe extending our analysis to the heterogeneous setting is possible.** Lemma B.6. still holds, but Lemma B.7. should be adjusted to handle function heterogeneity. If we make the same assumption as [1, Assumption 1.2 (3)], then this is possible at the cost of an extra $H$ factor. Modifying the rest of the proof of Theorem 3.3 with the revised Lemma B.7. is straightforward. The biggest drawback is that the conclusion will be too pessimistic compared to Minibatch SGD. We believe it might be possible to use assumptions such as second-order similarity and second-order smoothness, as in [4], to get around this, but this requires significant modifications not just to Lemma B.7 but to the main proof strategy of Theorem 3.3, and we leave it to future work.\n\n2. \"Are there any new frameworks or techniques in the theoretical analysis compared to prior works like [1][2]? If so, the authors should highlight these differences more explicitly.\" Yes, there are. First, our algorithmic framework is significantly different; Neither [1] nor [2] consider the use of outer learning rates or outer momentum, with both using simple averaging (equivalent to fixing the outer learning rate at $1$) and [1] considering *local* momentum. Our framework enables us to study the conditions under which using *outer* learning rates and momentum is useful. This difference in framework is the primary reason why we compare against [5, 6] in the discussion after Theorem 3.3 and not [1, 2]. Second, the analysis of Local SGD always involves bounding the so-called \"client drift\", or how far the local iterates stray from each other between synchronizations. In [1] this is controlled in Lemma 4 and in [2] this is controlled in Lemma 3.3. Both of these control the drift by bounding the maximum squared norm. We control the drift using a combination of the local regret against the starting point (Lemma B.6) and the maximum squared norm (Lemma B.7). This more fine-grained control allows us to show the benefit of using a large outer learning rate. To the best of our knowledge, a regret guarantee like Lemma B.6. has not been used in the literature before. In order to use this lemma, we also have to conduct the analysis *per communication round* rather than per training step as in [1, 2]. We will revise the next version of the manuscript to highlight these novel contributions.\n\n3. \"For optimization methods, it’s not recommended to introduce new hyperparameters if not necessary, due to the cost of hyperparameter tuning. Gen-loc-SGD has more learning rates that need to be tuned compared with vanilla local SGD. Are there some dramatic improvements due to the introduction of the outer learning rates?\" Yes, the performance degradation when not using an outer learning rate is significant. In our experiments, vanilla Local SGD consistently underperforms compared to using outer optimizers. For example, with the 150M model at H=50, M=4, it achieves a perplexity of 17.75, while Nesterov with lr=0.7 reaches 17.25 and SF-SGD with lr=2.0 achieves 16.88. These represent improvements of 2.8% and 4.9% respectively. The performance gains become even more pronounced at larger model scales: for the 1B model, vanilla SGD achieves 13.67 perplexity while Nesterov (lr=0.7) and SF-SGD (lr=2.0) reach 12.51 and 12.40 respectively, representing improvements of 8.5% and 9.3%. Because we can tune the outer learning rate at a smaller scale (this is what we did here) and therefore at a much smaller cost, we believe the additional hyperparameter is justified. There are very few reliable ways of squeezing out an additional 8%-10% performance at the 1B scale at the cost of one additional hyperparameter that can be tuned at a smaller scale.\n\n4. Thank you for your comments on improving clarity. We will define the learning rates $\\gamma$ and $\\eta$ in Algorithm 1 and use bold faces for the vectors.\n\nWe thank you for your review and hope our discussion above sufficiently addresses your concerns.\n\n[1] Hao Yu, et al. On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization. ICML 2019. \n[2] Stich, Sebastian U. Local SGD Converges Fast and Communicates Little. ICLR 2019.\n[3] Woodworth, B. E., Patel, K. K., & Srebro, N. (2020). Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33, 6281-6292.\n[4] Zindari, A., Luo, R., & Stich, S. U. (2023). On the convergence of local sgd under third-order smoothness and hessian similarity. In OPT 2023: Optimization for Machine Learning.\n[5] Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., & Suresh, A. T. (2020, November). Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning (pp. 5132-5143). PMLR.\n[6] Jhunjhunwala, D., Wang, S., & Joshi, G. (2023). Fedexp: Speeding up federated averaging via extrapolation. arXiv preprint arXiv:2301.09604.\n[12] Patel, Kumar Kshitij, et al. \"The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024."}, {"review_id": "PNaZQNdLnI", "reviewer": "Reviewer_advP", "summary": "The paper seeks to better understand the role of the outer optimizer and its hyperparameters in the i.i.d Local SGD setting. Specifically, the main results of the paper are (1) a convergence theorem for generalized Local SGD with arbitrary inner and outer learning rates with SGD being the inner and outer optimizer, (2) an extension of the first theorem but using SGD with momentum as the outer optimizer, and (3) a high probability guarantee for the iterates of generalized local SGD. The authors provide analysis of each result, illustrate how their high-probability theory is borne out in practice, and position their results within the existing literature. Finally, the authors provide empirical results on a toy convex problem that is illustrative of their theoretical analysis and provide empirical results on language model pre-training of decoder-only transformers following the DiLoCo setting.", "questions": "- Is the use of a schedule-free outer optimizer instead of SGD with a schedule is due to the theory not allowing for scheduled outer learning rates? If so, mentioning this could be helpful for the reader. \n- How is perplexity calculated in Figure 2? (e.g., what data, what batch size, etc)\n- Why does Theorem 3.5 not use an EMA for the momentum? \n- For LLM experiments, were the hyperparameters swept at each scale or were they swept only at a smaller scale?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is well written, the work is effectively placed within the context of the existing literature, and the connection to and demarcation between new and existing results is clearly stated. \n- To the extend of my limited understanding of convergence analysis proofs (I am not intimately familiar with the proofs from existing work, but I did read through the math in the main text), the authors theorems seem sound and to the best of my knowledge, they support what is mentioned in the implications sections/contributions. \n- The empirical evaluations correspond with the theory, and the LLM experiments are conducted at a reasonably large scale.\n\nWeaknesses: \n- **Reproducibility** Having a single table with all hyperparameters swept would be beneficial for reproducibility. Currently, the ranges presented in Table 1 leave some guesswork to the reader, and I’m not sure the actual values used can be found from an attentive read of the appendix. Moreover, it would be beneficial to provide the final performance of all different hyperparameters swept in the appendix. This will help further improve the reproducibility of the paper and will be of use to practitioners reading the paper and wondering about the performance of different outer learning rates in the appendix. I will raise my score if the above concerns are adequately addressed (e.g., provide in line the tables of values you will report in the appendix and the final performance of HPs swept). \n\n- **Impact** The practical guidance that can be gleaned from the current theory seems limited. I think the theoretical results are interesting and will certainly help improve our current understanding of the outer learning rate’s role in Local SGD and could potentially lead to more practical improvements down the line (why I recommend accepting). However, from my understanding, the current theory does not suggest practical improvements to the Local SGD algorithm beyond: 1) tuning the outer learning rate is important and 2) noisy outer gradients require a lower outer learning rate. Could the authors comment on the above? \n\n- **presentation** Most of the captions could be more self-contained.", "was_revised": true, "final_justification": "I have increased my score. I recommend accepting the paper.\n\n**Issues resolved:**\n- Missing hyperparameters and final loss values for each.\n- Misunderstanding of the momentum used in the proofs.\n- Clarification of scheduled learning rates for the outer optimizer.\n- Clarification of the use of a schedule-free outer-optimizer.", "rebuttal": "Thank you so much for your review and positive evaluation of our work.\n\n1. (Reproducibility) We did not report all of the hyperparameter sweep results in line with reporting in prior work which reported the best hyperparameters only. We are happy to report all the experimental results we have done. Here are the results of the hyperparameter sweeps we will include in the appendix:\n\n| H | M | Algorithm | Learning Rate | Perplexity | Model Size |\n|---|---|-----------|---------------|------------|------------|\n| - | 1 | Data-Parallel | - | 18.07 | 150M |\n| - | 1 | Data-Parallel | 4x BS | 16.89 | 150M |\n| - | 1 | Data-Parallel | - | 15.28 | 400M |\n| - | 1 | Data-Parallel | 4x BS | 13.21 | 400M |\n| - | 1 | Data-Parallel | - | 13.38 | 1B |\n| - | 1 | Data-Parallel | 4x BS | 11.34 | 1B |\n| 50 | 4 | SGD | 1.0 | 17.75 | 150M |\n| 50 | 4 | Nesterov | 0.7 | 17.25 | 150M |\n| 50 | 4 | Nesterov | 1.0 | 16.38 | 150M |\n| 50 | 4 | SF-SGD | 2.0 (b=0.2) | 16.88 | 150M |\n| 50 | 4 | SGD | 1.0 | 14.90 | 400M |\n| 50 | 4 | Nesterov | 0.7 | 13.71 | 400M |\n| 50 | 4 | Nesterov | 1.0 | 30 | 400M |\n| 50 | 4 | SF-SGD | 2.0 (b=0.2) | 13.95 | 400M |\n| 50 | 4 | SGD | 1.0 | 13.67 | 1B |\n| 50 | 4 | Nesterov | 0.7 | 12.51 | 1B |\n| 50 | 4 | SF-SGD | 2.0 (b=0.2) | 12.40 | 1B |\n| 150 | 4 | SGD | 1.0 | 17.58 | 150M |\n| 150 | 4 | Nesterov | 0.7 | 17.90 | 150M |\n| 150 | 4 | Nesterov | 1.0 | 16.79 | 150M |\n| 150 | 4 | SF-SGD | 2.0 (b=0.2) | 16.96 | 150M |\n| 250 | 4 | SGD | 1.0 | 18.20 | 150M |\n| 250 | 4 | Nesterov | 0.7 | 18.09 | 150M |\n| 250 | 4 | Nesterov | 1.0 | 17.12 | 150M |\n| 250 | 4 | SF-SGD | 2.0 (b=0.2) | 16.97 | 150M |\n| 500 | 4 | SGD | 1.0 | 18.44 | 150M |\n| 500 | 4 | Nesterov | 0.7 | 17.95 | 150M |\n| 500 | 4 | Nesterov | 1.0 | 18.15 | 150M |\n| 500 | 4 | SF-SGD | 2.0 (b=0.2) | 17.18 | 150M |\n| 1000 | 4 | SGD | 1.0 | 18.18 | 150M |\n| 1000 | 4 | Nesterov | 0.7 | 18.16 | 150M |\n| 1000 | 4 | Nesterov | 1.0 | 18.75 | 150M |\n| 1000 | 4 | SF-SGD | 2.0 (b=0.2) | 17.29 | 150M |\n| 2000 | 4 | SGD | 1.0 | 18.11 | 150M |\n| 2000 | 4 | Nesterov | 0.7 | 18.40 | 150M |\n| 2000 | 4 | Nesterov | 1.0 | 18.36 | 150M |\n| 2000 | 4 | SF-SGD | 2.0 (b=0.2) | 17.59 | 150M |\n| 50 | 2 | SGD | 1.0 | 18.64 | 150M |\n| 50 | 2 | Nesterov | 1.0 | 16.81 | 150M |\n| 50 | 2 | SF-SGD | 2.0 (b=0.2) | 17.13 | 150M |\n| 50 | 8 | SGD | 1.0 | 18.38 | 150M |\n| 50 | 8 | Nesterov | 1.0 | 16.27 | 150M |\n| 50 | 8 | SF-SGD | 2.0 (b=0.2) | 16.92 | 150M |\n| 50 | 16 | SGD | 1.0 | 19.86 | 150M |\n| 50 | 16 | Nesterov | 1.0 | 16.25 | 150M |\n| 50 | 16 | SF-SGD | 2.0 (b=0.2) | 16.75 | 150M |\n\n## Additional Learning Rate Sweeps (150M, H=50, M=4)\n\n| Algorithm | Learning Rate | Perplexity |\n|-----------|---------------|------------|\n| SF-SGD | 0.1 | 30 |\n| SF-SGD | 0.5 | 22.89 |\n| SF-SGD | 1.0 | 19.42 |\n| SF-SGD | 1.5 | 18.32 |\n| SF-SGD | 2.0 | 17.98 |\n| SF-SGD | 3.0 | 17.96 |\n| SF-SGD | 4.0 | 18.09 |\n| SF-SGD | 5.0 | 17.51 |\n| Nesterov | 0.3 (cosine) | 17.16 |\n| Nesterov | 0.5 (cosine) | 17.06 |\n| Nesterov | 0.7 (cosine) | 16.93 |\n| Nesterov | 0.9 (cosine) | 17.19 |\n| Nesterov | 1.1 (cosine) | 17.56 |\n| SGD | 0.3 (fixed) | 21.04 |\n| SGD | 0.3 (cosine) | 17.68 |\n| SGD | 0.5 (cosine) | 16.63 |\n| SGD | 0.7 (cosine) | 18.84 |\n| SGD | 1.0 (cosine) | 19.21 |\n\n## SF-SGD Beta (b) Parameter Sweep (150M, H=50, M=4, lr=2.0)\n\n| b value | Perplexity |\n|---------|------------|\n| 0.0 | 30 |\n| 0.05 | 16.88 |\n| 0.1 | 16.78 |\n| 0.2 | 16.89 |\n| 0.4 | 17.15 |\n| 0.5 | 17.35 |\n| 0.7 | 17.93 |\n| 0.9 | 19.07 |\n| 0.95 | 19.65 |\n| 0.99 | 20.51 |\n\n2. (Impact) Yes, it is true that our theory as it is provides limited practical prescriptions. We are primarily concerned with understanding the role of the outer learning rate and how it should be tuned, but have not directly provided a theory-based schedule for it; this task we leave to future work. One crucial takeaway from our theory, which is not common in practice, is that it sometimes pays off to try outer learning rates greater than 1.0. To the best of our knowledge, the current literature (e.g. [7, 8]) did not sweep for such learning rates, going up to 1.0 and no higher. Our work shows that for Schedule-Free SGD as the outer optimizer, a learning rate of 2.0 performed best. We will highlight this recommendation further.\n\n3. (Captions) We will expand the captions to be more self-contained in the revised manuscript. Thank you for pointing this out.\n\n4. \"Is the use of a schedule-free outer optimizer instead of SGD with a schedule is due to the theory not allowing for scheduled outer learning rates? If so, mentioning this could be helpful for the reader.\" The main reason we used it was to remove the variable of (outer) learning rate scheduling. The theory can be extended to scheduled outer learning rates, but in its current form  it does not allow for them. We will mention this.\n\n5. \"How is perplexity calculated in Figure 2? (e.g., what data, what batch size, etc)\" Perplexity is calculated on the C4 validation set, with sequence length 1024, and batch size 512 for all model scales. The tokenizer is SentencePiece.\n\n6. \"Why does Theorem 3.5 not use an EMA for the momentum?\" Our way of writing the momentum update is equivalent to using EMA for momentum. [9, Lemma 7.2] shows it is equivalent to the update $m_{t} = \\mu m_{t-1} + g_t$ and $x_{t+1} = x_t - \\eta m_t$. By unrolling, this corresponds to $x_{t+1} = x_t - \\eta \\sum_{k=0}^t \\mu^k g_{t-k}$. For classical EMA written as $m_t = (1-\\alpha) m_{t-1} + \\alpha g_t$ and $x_{t+1} = x_t - \\gamma m_t$, unrolling we have $x_{t+1} = x_t - \\gamma \\alpha \\sum_{k=0}^t (1-\\alpha)^k g_{t-k}$. Thus putting $\\mu = 1-\\alpha$ and $\\gamma (1-\\mu) = \\eta$ we can see that they are equivalent up to a rescaling of the learning rate.\n\n7. \"For LLM experiments, were the hyperparameters swept at each scale or were they swept only at a smaller scale?\" We swept them at the 150M scale, with a small number of additional trials at higher scale.\n\nThank you so much for your detailed comments.\n\n[7] Douillard, Arthur, et al. \"Diloco: Distributed low-communication training of language models.\" arXiv preprint arXiv:2311.08105 (2023).\n[8] Liu, B., Chhaparia, R., Douillard, A., Kale, S., Rusu, A. A., Shen, J., ... & Ranzato, M. A. (2024). Asynchronous local-sgd training for language modeling. arXiv preprint arXiv:2401.09135.\n[9] Garrigos, G., & Gower, R. M. (2023). Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235."}, {"review_id": "wSTiBVGLaB", "reviewer": "Reviewer_GcXM", "summary": "This work studies the impact of outer learning rate in Local SGD through a theoretical lens of convergence bounds. The theorems show the inverse relation between optimization error and gradient variance with different regimes of outer learning rates. The analysis is also extended to the momentum-based outer updates.", "questions": "a. What changes would be needed to make for a non-convex analysis on outer learning rates?\n\nb. Are there empirical results on end perplexity for a grid of local and global learning rates? I wanted to see how the relation between the local and the global learning rates (of theorem 3.3) translate to convex and non-convex objectives in practice.\n\nc. For clarification, does theorem 3.3 imply that larger $\\eta$ (local learning rates) might result in an accumulated gradient with large variance, which needs to be counterbalanced by a smaller $\\gamma$? Would we achieve the same effect with a larger $H$ (local steps)?\n\nd. A follow up to the above question would be, under what setting of local and global learning rates we can minimize the FLOPs?\n\ne. For Figure 9 in the Appendix, why are we seeing high gradient similarity near the end of the training for the left plots and why are we seeing low gradient similarity for the right plots? Furthermore, line 283 states \"... noise-dominated regime, which we may expect to observe towards the end of the training process.\" Why is that so? \n\nf. For Figure 1b, why does the loss start high for low variance setting of $\\sigma = 0.001$?\n\ng. For Table 1, SF-SGD case, why are outer learning rates with magnitudes >2 detrimental?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\na. The work is well-motivated and the manuscript is well-written. The objective of the paper and the theoretical treatment were easy to follow.\n\nb. The authors have done a good job of building the related work section, it would be extremely helpful for the beginners in this area.\n\nc. The theorems are followed by insightful discussion which captures the key points well.\n\n___\n**Weaknesses**\n\na. The theoretical analysis is limited to the convex objective functions.\n\nb. There's a lack of clarity in the empirical results in terms of the relation between local and global learning rates. E.g., For Section 4.1, is the local learning rate $\\eta$ supposed to be in the \"higher\" or \"lower\" ranges according to the upper bounds set through Theorem 3.3. Some more questions are detailed below.", "was_revised": true, "final_justification": "The authors have addressed my questions about non-convex analysis satisfactorily and clarified the empirical results, hence I would like to keep my score to \"Accept\".", "rebuttal": "Thank you so much for your review and positive evaluation of our work.\n\n1. (Non-convex analysis). Our theorem mainly relies on the two lemmas Lemma B.6 and Lemma B.7; Lemma B.6 holds regardless of convexity, but Lemma B.7. does not. We would need to relax Lemma B.7. to handle non-convex objectives, but this lemma in turn relies on the fact that gradient descent is contractive (Lemma B.1.), which is not true for arbitrary non-convex functions. We believe it is possible to use similar tools as in [10, Theorem 4.1], but this requires adding the bounded gradients assumption and using a different approach for the theorem derivation that starts with the smoothness inequality. Alternatively, we can use the approach of [12] of bounding this sequence by a sum of gradients at the cost of an extra $H$ factor in the Local SGD variance term.\n\n2. (LR grids) The local learning rate is always fixed in our experiments is fixed to $\\frac{\\eta_{\\mathrm{baseline}}}{\\sqrt{M}}$ where $\\eta_{\\mathrm{baseline}}$ is the local learning rate that was tuned on the minibatch SGD baseline for each model scale and $M$ is the number of nodes (see Table 1 in the main paper). We only varied the outer learning rate otherwise, since what is important for our analysis is the ratio of outer to local learning rate. We have included a table with all the experiments we’ve conducted varying the outer learning rate in our response to Reviewer advP.\n\n3. (Implications of Thm. 3.3) Theorem 3.3 shows there are two sources of noise for Local SGD: the second term in equation (3) scales with $\\eta$ and $\\max(0, \\gamma-1)$ but not $H$, and the third term scales with $\\eta^2$ and also $H$. In addition, we also have to satisfy the constraint $\\eta L (1 + (\\gamma-1)_+ H) \\leq 1$. For tuning the outer learning rate, if either $\\eta$ or $H$ are larger, we are forced to use smaller $\\gamma$ in the same way. However, the convergence of Local SGD will suffer more under larger $\\eta$ than larger $H$, all else being equal, because larger $\\eta$ will increase both noise terms while larger $H$ only increases the latter.\n\n4. (Minimizing FLOPs) To minimize iteration complexity given a fixed number of clients $M$ and local steps $H$, we ought to choose the outer learning rate to make up for a small inner learning rate and to vary with the number of local steps. Depending on the magnitude of the gradient variance, choosing an outer learning rate larger than 1 can also be useful. We found that outer learning rates can be tuned at a smaller scale and transfer as-is to larger models. For example, with the 150M model at H=50, M=4, it achieves a perplexity of 17.75, while Nesterov with lr=0.7 reaches 17.25 and SF-SGD with lr=2.0 achieves 16.88. These represent improvements of 2.8% and 4.9% respectively compared to the baseline with no outer learning rate. The performance gains transfer and become even more pronounced at larger model scales: for the 1B model, vanilla SGD achieves 13.67 perplexity while Nesterov (lr=0.7) and SF-SGD (lr=2.0) reach 12.51 and 12.40 respectively, representing improvements of 8.5% and 9.3%. Of course, in practice, we control the number of clients $M$ and also have to consider FLOP efficiency from a systems perspective, e.g. normally increasing $M$ comes at the cost of decreasing the local batch size or alternatively increasing $\\sigma^2$. This complicates the trade-off; Figure 4 shows the result of varying the number of clients/replicas in practice on FLOP efficiency. A study of FLOP efficiency would have to take into account the specific hardware we have available, and what the minimum batch size needed to saturate the GPU computation is.\n\n5. “For Figure 9 in the Appendix, why are we seeing high gradient similarity near the end of the training for the left plots and why are we seeing low gradient similarity for the right plots?” For all of them except SF-SGD in Figure 9 (c), we do observe low similarity towards the end of training (lower than 0.1). For SF-SGD in Figure 9 (c), we do observe a spike in similarity towards the end but are not sure why this is the case. \n\n3. “Furthermore, line 283 states \"... noise-dominated regime, which we may expect to observe towards the end of the training process.\" Why is that so?” This is an empirical observation made in prior work [11], and the intuition is that towards the end of training the gradient norms are smaller so the relative magnitude of the noise is higher compared to the gradient norms.\n\n4. “f. For Figure 1b, why does the loss start high for low variance setting of $\\sigma = 0.001$?” All of the losses are reported after one communication round– the figure should start at r=1 not at r=0. They would all start at the same value if we started at r=0. Since we cannot upload PDFs or figures, here are the trajectories in tabular form:\n\n\n### Figure 1 (b) tabular\n| σ     | Round 1      | Round 2      | Round 3      | Round 4      | Round 5      |\n|-------|--------------|--------------|--------------|--------------|--------------|\n| 0.001 | 1.421e+07    | 3.965e-02    | 3.050e-03    | 7.399e-04    | 5.203e-04    |\n| 0.01  | 1.421e+07    | 6.859e-02    | 6.751e-03    | 1.370e-03    | 7.368e-04    |\n| 0.1   | 1.421e+07    | 1.919e-01    | 2.858e-02    | 1.052e-02    | 6.916e-03    |\n| 0.5   | 1.421e+07    | 1.051e+00    | 2.031e-01    | 1.059e-01    | 7.660e-02    |\n| 1.0   | 1.421e+07    | 1.220e+00    | 3.663e-01    | 2.674e-01    | 2.948e-01    |\n| 10.0  | 1.421e+07    | 2.333e+01    | 8.727e+00    | 6.208e+00    | 5.305e+00    |\n\n5. “g. For Table 1, SF-SGD case, why are outer learning rates with magnitudes >2 detrimental?” They weren’t really detrimental, they just did not help very much. Here are the results of our grid search on a 150M parameter model with $H=50$ and $M=4$.  Very small outer learning rates were a lot more detrimental, as they did not allow for enough progress.\n\n## Additional Learning Rate Sweeps (150M, H=50, M=4)\n\n| Algorithm | Learning Rate | Perplexity |\n|-----------|---------------|------------|\n| SF-SGD | 0.1 | 30 |\n| SF-SGD | 0.5 | 22.89 |\n| SF-SGD | 1.0 | 19.42 |\n| SF-SGD | 1.5 | 18.32 |\n| SF-SGD | 2.0 | 17.98 |\n| SF-SGD | 3.0 | 17.96 |\n| SF-SGD | 4.0 | 18.09 |\n| SF-SGD | 5.0 | 17.51 |\n\n\n[10] Glasgow, M. R., Yuan, H., & Ma, T. (2022, May). Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics (pp. 9050-9090). PMLR.\n[11] Faghri, F., Duvenaud, D., Fleet, D. J., & Ba, J. (2020). A study of gradient variance in deep learning. arXiv preprint arXiv:2007.04532."}]

Author rebuttal:

Meta-review: This paper provides a clean theoretical result about the optimal "outer learning rate" of local SGD (a distributed version of SGD consisting of local gradient updates, aggregation and a outer update stages). The reviewer all agree that the contribution of the paper is solid and useful in optimization practice of distributed training.

The concerns seem to be minor, and the authors addressed them well during the rebuttal stage.
Decision: Accept (poster)