Convergence of Distributed Adaptive Optimization with Local Updates
Authors: Ziheng Cheng
Margalit Glasgow
Venue: ICLR 2025 Poster (2025)
Keywords: distributed optimization; Adam; theoretical benefits of local updates
Primary area: optimization
TL;DR: first provable benefits of distributed Adam with local updates compared to minibatch baseline

Abstract: We study distributed adaptive algorithms with local updates (intermittent communication). Despite the great empirical success of adaptive methods in distributed training of modern machine learning models, the theoretical benefits of local updates within adaptive methods, particularly in terms of reducing communication complexity, have not been fully understood yet. In this paper, for the first time, we prove that \em Local SGD \em with momentum (\em Local \em  SGDM) and \em Local \em  Adam can outperform their minibatch counterparts in convex and weakly convex settings in certain regimes, respectively. Our analysis relies on a novel technique to prove contraction during local iterations, which is a crucial yet challenging step to show the advantages of local updates, under generalized smoothness assumption and gradient clipping strategy.

Published as a conference paper at ICLR 2025
CONVERGENCE OF DISTRIBUTED ADAPTIVE OPTI- MIZATION WITH LOCAL UPDATES
Ziheng Cheng
Margalit Glasgow
University of California, Berkeley heng chengêbe rkel ee edu
Massachusetts Institute of Technology mgl 1 agowemi edu
ABSTRACT
We study distributed adaptive algorithms with local updates (intermittent commu- nication). Despite the great empirical success of adaptive methods in distributed training of modern machine learning models, the thcoretical benefits of local up- dates within adaptive methods, particularly in terms of reducing communication complexity, have not been fully understood yet. In this paper, for the first time, we prove that Local SGD with momentum (Local SGDM) and Local Adam outperform their minibatch counterparts in convex and weakly convex settings in certain regimes, respectively. Our analysis relies on novel technique to prove contraction during local iterations. which is crucial yet challenging step to show the advantages of local updates, under generalized smoothness assumption and gradient clipping strategy.
INTRODUCTION
Leveraging parallelism is crucial in accelerating the training of modern machine learning models for large scale optimization problems. In distributed environments such as large data-centers or in the federated learning setting, where the devices working together spread apart, communication between the distributed workers is a key bottleneck. this work, we consider the task of
min f(x) == Eg (Fo;; E)]. ZER
(1.1)
in a distributed setting with M workers. Each worker has access to f via the stochastic gradient oracle V Fx;; E), where is independently drawn from the distribution D. In federated learning, this is known as the homogeneous setting, since all workers draw from the same data distribution.
Perhaps the simplest algorithm for distributed optimization is distributed minibatch stochastic gra- dient dexcent (SGD), in which at each iteration, each worker computes a minibatch of gradients, and gradient step is taken by averaging the gradient computed among the M workers. However, such an algorithm requires communicating at each gradient step, which may be expensive. Thus numer- works have proposed distributed algorithms with less frequent communication. A popular and well-studied algorithm is Local SGD, also known as FedAvg (McMahan et al., 2017), where each worker runs SGD independently and periodically synchronizes with others by averaging the iterates.
Despite the success of Local SGD in federated learning (McMahan et al., 2017), it may not ex- hibit good performance when training Transformerrbased large language models (LLMs). Many empirical studies suggest that adaptive methods (e.g.. Adam (Kingma & Ba, 2014)) are much bet- ter suited for natural language processing than vanilla SGD (Goodfellow et al., 2016; Zhang al., 2020: Kunstner et al., 2023; Pan & Li, 2023). Furthermore, as shown in Zhang et al. (2019; 2020), language models tend to have unbounded global smoothness and heavy-tailed noise, which may also contribute to the worse performance of SGD. Parallelizing adaptive methods requires even more expensive communication cost since additional terms, such as the momentum or the Adam denom- inator, need to be synchronized. Previous works on distributed adaptive optimization have utilized compression and quantization techniques to address this issue (Bernstein et al., 2018; Wangni et al., 2018; Wang al.. 2023). While Douillard et al. (2023) has shown the great empirical success of Local Adam, to the best of our knowledge, there are no theoretical results trying to improve training efficiency adaptive methods from the perspective of intermittent communication.

---

Published as a conference paper at ICLR 2025
In this paper, investigate distributed adaptive optimization algorithms in the homogeneous regime, in order to establish theoretical guarantees for the benefits of local iterations in reducing communication complexity. We focus on the convex or weakly convex setting'.
We propose distributed version of Adam, namely, Local Adam, with gradient clipping. Our al- gorithm also reduces to Local SGD with momentum (Local SGDM), with some specific hyper- parameter choices.
In Theorem 1,2, we establish the first convergence guarantee for Local SGDM in the convex setting, which outperforms the convergence rate of Minibatch SGDM. The rate we obtain is in line with the rate of Local SGD (Woodworth et al., 2020a).
In Theorem 3, establish convergence rate for Local Adam in the weakly convex set- ting. We show that Local Adam can provably improve communication efficiency compared to its minibatch baseline.
For the first time, algorithms, SGDM and Adam. This suggests that one can improve the training efficiency of large models by using intermittent communication.
able to show the benefits of local iterations for the two commonly used
Additionally, our results hold under generalized smoothness and heavy-tailed noise. Our result is the first high probability bound for distributed optimization algorithms with local updates, to the best of our knowledge. The conventional in-expectation rate seems fail to capture some important properties like heavy/light tailed noise distribution. The high probability convergence guarantee can sometimes be more informative and useful in practice (Gorbunov et al., 2020).
As for technical contribution, use a novel technique prove contraction for adaptive meth- ods, which bounds the consensus error between the iterates at different workers. This is a key step in proving benefits of local updates. Different from Local SGD, our update direction involves mo- mentum or even distorted momentum due to the denominator in Local Adam, making it challenging to disentangle these accumulated stochastic gradients. To address this issue, we define and analyze an auxiliary sequence which is conditionally independent of the latest stochastic gradient and thus can construct a martingale. We will introduce the technique in more details in Section 5.
1.1 ORGANIZATION
Section 2 provides the most related work to ours. Section 3 provides the problem setup, assumptions and the Local Adam algorithm. We then show our main results for Local SGDM in Section 4.1 and Local Adam in Section 4.2. Finally, in Section 5, we present the proof sketch of Local Adam, highlighting the technical challenges and our solution.
1.2 NOTATION
Let || || be the standard Euclidean norm of a vector or the spectral norm of a matrix. For any y E R the expressions + y. y, stand for coordinate- respectively. And x z means each coordinate - y is no greater than Furthermore, we use 2 Vz, |x| to denote the coordinate-wise square, square root and absolute value. We use Em [Xm]
sosse wise sum, product and division,
1 Xm The coordinate-wist clipping operator clip(: p) E2d R is
to denote the average
M
m=1
defined as (Xl,p(X, p)]; sgn([X) min))) (Xil( We use [N] to denote the set {1, 2,.,, NY. N}. For a subset 24 C Rd let conv(.) denote the convex hull of Oy and BR, (2a) denote the neighborhood of Po with radius Ro- Finally, we use standard D(,),2()) O(-) to omit constant factors and (-) to omit logarithmic factors.
Under the stronger assumptions of 3rd-order smoothness (Glasgow et al., 2022) mean smoothness (Patel et al., 2022), there are demonstrated advantages of local iterations in the non-convex setting. While our theoretical results are for the convex or weakly convex setting. it is likely that local iterations are advantageous in practice for non-convex objectives, just in the same way Local SGD has been shown to be advantageous in practice for non-convex objectives (McMahan al., 2017).
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
Theoretical benefits of local updates in distributed optimization. Algorithms with local up- dates have been used among practitioners for a long time to reduce communication complexity (McMahan et al.. 2017). In the homogeneous and convex setting, Local SGD and its variants have been shown to outperform the minibatch baseline, for fixed amount of gradient computations and communication rounds. Woodworth et al. (2020a) is the first to show that Local SGD can prov- ably outperform Minibatch SGD. Yuan & Ma (2020) develops FedAC to further accelerate Local SGD. In the heterogeneous case, Woodworth et al. (2020b) demonstrates the advantages of Local SGD when hetcrogeneity is very low. Algorithms with local updates have also been studied in the non-convex setting (Karimireddy et al., 2020b; Yang et al., 2021; Glasgow et al., 2022), includ- and adaptive methods (Reddi et al., 2020; Karimireddy et al., 2020a), though
ing momentum-Dee no advantage of local iterations over minibatch has been shown, without non-standard assumptions such as 3rd-order smoothness. Notably, Liu et al. (2022) is one closely related work to ours, which considers Local SGD with gradient clipping in homogeneous and non-convex setting and claims that the convergence guarantee is better than naive parallel of centralized clipped-SGD However, it still cannot outperform minibatch baseline (with batch size K for each worker in each round) and thus fails to demonstrate the benefits of local iterations.
Convergence of centralized Adam. Adam was first proposed by Kingma & Ba (2014) with con- vergence guarantee in online convex optimization. However, Reddi al. (2019) found a gap in the original analysis of Adam and constructed a counter example to show its divergence. Since then, many works have developed convergence analyses of Adam with various assumptions and hyper- parameter settings. Guo et al. (2021) assumed the denominator is bounded from below and above by two constants, which typically requires bounded gradient assumption or the AdaBound variant (Luo et al., 2019). Défossez et al. (2020) assumed bounded gradient and their convergence guaran- tee depends on poly(d). Zhang et al. (2022b); Wang et al. (2022) considered finite sum setting and showed that Adam converges to the neighborhood of stationary points. One closely related work to ours is Li et al. (2024c), which established a high probability bound without a bounded gradient as- sumption. However they assumed that noise is bounded almost surely. Another recent work (Wang et al., 2024) provided guarantee of O (1/=*) with dependence on poly(d). Beyond the guarantees on gradient norm given by non-convex analyses, stronger bounds (e.g., on function error) are known for Adam in the convex case.
Convergence of distributed adaptive algorithms. In the federated learning literature. Reddi al. (2020) introduced framework, FedOPT, to leverage both worker optimizer and server optimizer. Many works explored adaptive server optimizer while fixing worker side as vanilla SGD. The theo- retical results of local adaptive algorithms are much fewer. Some works have studied Local Adam and Local AMSGrad with fixed momentum state during local iterations (Karimireddy et al., 2020a; Chen et al., 2020; Zhao et al., 2022). They also needed stringent assumptions such as huge batch size depending on the inverse of target error, bounded stochastic gradients, vanishing difference between denominator, etc., which are not standard. Wang et al. (2021) explored adaptive worker optimizer based on centralized algorithm, where the state of worker optimizer changes in local up- dates. However, their analysis relied on an explicit assumptions (Wang et al., 2021, Assumption 1) on the contraction property of worker optimizer. Some recent works (Li et al., 2024a; Anyszka al., 2024) discussed Polyak stepsizes with an exact local proximal operator, which is inaccessible in most cases by gradient- based optimizers. To the best of our knowledge, there is no end-to-end convergence guarantee for distributed adaptive algorithms with local iterations.
PROBLEM SETUP
Consider the distributed optimization problem
min f(x) = Rq.D(F(( #ER
(3.1)
Here D is the data distribution and f is the population loss function. We consider setting with M parallel workers, and budget of R total communication rounds, and T total gradient computa-
tions at each worker. We will describe the implementation of the local and minibatch versions of
3

---

Published as a conference paper at ICLR 2025
centralized algorithm A. which uses single stochastic gradient in each iteration. And these illustrated in Figure 1.
Minibatch A
Local A
irrppp
Esrahe
Alsly)
Alstah
Alota)
Alota)
Als2,)
Alo
AGixx-)
Alo2
Alsix
A(g-)
2r+-1,0
Real Angls
Figure 1: Minibatch A v.s. Local A in communication round. Minibatch version computes the average of all KM gradients and then executes one step of A, while local version runs A independently for K steps at each worker.
In the local version of algorithm A, in each round r of the total communication rounds, each worker independently executes K = T R steps of local updates (according to the algorithm A). For a worker m, we denote the kth gradient computed in round r by g., Then the M workers synchronize the iterates and related momentum state. We Minibatch A denote a distributed implementation of A run for I rounds, where KM stochastic gradients are computed and averaged each step. This fair baseline to compare the local update algorithms to, since the number of gradient calls and communication rounds are the same.
Local Adam is shown Algorithm 1, which natural extension of centralized Adam (Kingma & Ba, 2014). The stochastic gradient is clipped by an coordinate-wis clipping operator with threshold p. After K steps of local updates, all the workers average their current iterates x; their first order momentum u,"" and their second order momentum vt," These averaged quantities become the values used at the beginning of the next local round. Note that there are two slight differences from original Adam. First, we do not involve bias correction here, i.e., u," and vt"h are not divided by 8 or - 33 respectively. Second, À in the denominator is in the square root, while outside of the denominator in original Adam. These modifications do not harm the spirit of Adam and made for the convenience of analysis.
3.1 ASSUMPTIONS
Throughout this work, we will use the following assumptions.
Assumption 1 (Loudee-bu f closed, twice continuously differentiable and #ERd"
inf f(x) =: f(x.) =: -00.
Assumption 2 (Smoothness). There exists some set S C Rd and L > O, such that for any x, Q,
[VV[(x) - < L|| - yyl
(3.2)
= 2L)())) f.).
(3.3)
Similar to Sadiev al. (2023), only requires properties of on subset Ω of Rd4, since can prove that all the iterates will not leave this subset with high probability. In contrast, the typical smoothness assumption requires (3.2) the entire domain.
4

---

Published as a conference paper at ICLR 2025
Algorithm Local Adam
Require: initial model zg, learning rate 7, momentum $1, A2 E (0, Set 20,0 = 20, Ug for = 0, ... R do
0, vo 0 for each worker E [M]
for each worker E [M] in parallel do
for k = 0, ... . 1 do
kr,k
m (3 ) Jr.k clip(o
Dr Compute clipped stochastic gradient
u = B1 + (1 31)9
Update Ist-order momentum
urk --- + +(1 (1- 32 g" Frik
Update 2nd-order momentum Di Update model
T rr,+1 = m
m
2 ur
10 + X2
end for end for
2 1-0 = Em kl u =
Em k 1441--1 =
Ur+1 =
Em [M
Communicate and average end for
There are many works (Zhang al., 2019; Crawshaw et al., 2022; Faw et al., 2023; Wang al., 2022; Li et al., 2024c) that make weaker smoothness assumptions (typically called "generalized smoothness"), most of which are in the form of (Lo, Li)-mmoothness:
| f()) & Lo + [x)], Vr E IR..
(3.4)
Li et al. (2024b) considers an extension called Ê-smoothness, which replaces the linear function of || fll in the right hand side of (3.4) with sub-quadratic function {(-). As pointed out in Li et al. (2024b, Corollary 3.6), all of these will induce Assumption 2 if S2 is some level-set of the objective function Therefore, we directly use this more general assumption to get cleaner results.
Assumption 3 (Bounded a- a-moment noise). There exists some set Ω C Rd, 2 4 and constant vector ž such that for any x E S
(F Vf(x)) 300
(3.5)
Let Jo0 == 1|01000
To get high probability bound under generalized smoothness, the assumption stochastic noise crucial. Light-tailed noise with bounded exponential moment (e.g., bounded, sub-exponential. sub- sub-gaussiant are considered in Harvey al. (2019); Li & Orabona (2020); Li et al. (2024c). There are also attempts for heavy-tailed noise with finite a-moment (Gorbunov et al., 2020; Cutkosky & Mehla, 2021; Faw el al., 2023). In the most literatures studying heavy-tailed noise, they restrict to the case where 1 < a < 2. However, in the materr of getting a logarithmic dependence on 1 1/5, where 8 is the confidence level, the essence lies in whether assume bounded exponential moment or just polynomial moment (see Appendix E for detailed discussions). For con- venience, we only consider a 4 in this paper, but our analysis methods can be extended to the case where < 4 with some additional technical computations.
Remark 1.
Remark 2 (Noise of minibatch). It follows from Petrov (1992) that if the gradient is estimated by batch of i.i.d samples with batch size N, the a-moment of noise has upper bound of:
N E - " =c(a)(o/VNN).
E (e.) L
(3.6)
where cla) is inbble--ddeeendeent constant. It is easy to see that this bound is tight when the noise Gaussian. Therefore, to get the rate for batch size N, we can just simply replace a with a //VN (up to a constant depending on a) in the original convergence guarantee for batch size
Fegg. C fa f(z) - f- 5 A}, then (Lg, L1)-smoothsess would imply Assumption for x To T A. Note that we may not obtain the optimal dependence Lo, La in this way though.
5

---

Published as a conference paper at ICLR 2025
4 MAIN RESULTS
In this section, we provide our main results for Local Adam and its simplified version: Local SGDM. For the first time, we will be able show the benefits of local iterations for the two algorithms, compared with their minibatch baselines in certain regime of M, K.
4.1 LOCAL SGDM
Before getting into Local Adam, start with simpler yet also important algorithm: Local SGD with momentum. Note that when B2 = 1 = 1, Algorithm will reduce to Local SGDM. We restate the complete version of Local SGDM in Algorithm 2 in Appendix C.
Assumption 4 (Convexity). There exists some set Ω IR. and constant 2 0 such that f is ju-strongly convex on 92 Le., for any x. E S2
(Vf(z) f(y),, v) pl| y11 f(v) 2 f(x) (Vf(z)
(4.1)
+ || yl1
(4.2)
Let Do == |00 xz Now we state the results for Local SGDM below. Notably. our results are the first convergence guarantee for distributed SGDM with local updates in (strongly) convex setting.
Theorem (Strongly convex, full version see Theorem C.4). Let Assumption 2, 4 hold for
MRR 1 1 31 = 22(1) and
Q: = [| - z.1l S v3Dg} and p > O. Further assume that K 2 log
||o||| | - 1n (a)). Then with probability no less than 1 8, Local SGDM yields
f(ē) - fo S exp (-
(-O(UE))
(.K.
0 )
0² Lo² 0²
( L P.
) (4.3)
L
MMKR PKKR
[1 [u²KR]
Theorem 2 (Convex, full version see Theorem C.5). Let Assumption 1, 2, 3, 4 hold for Ω =
MKR
{|l> 2,11 S v3Do} and μ 0. Further assume that K Z log 6 ||a||| 2/ dt t = -o)). Then with probability no less than 1 1-8, 8, Local SGDM yields
1 B1 22(1) and
1)
LD KR
oDo
L
((Do))B0**
f S. < Ô
Do
(4.4)
VMKR
K'R
KR
Remark 3 (Confidence level 8). does not appear in the bound since we have log 8
dependence.
Our method can also be applied Minibath SGDM (by substituting M, K with and with a see Remark 2), whose convergence guarantee is MMK
HR L
exp
if > 0,
PMKR
f(i) - f
(4.5)
LD R
Do
otherwise.
VMKR)
This rate matches the well-known in-expectation lower bound on the convergence rate of Minibatch SGD (up to logarithmic factors). In fact, our analysis improves the state-of-ther tteh-htrrtt art rate for strongly-
Lo²
convex SGDM (given in Liu et al. (2020b)), which has stochastic term as ò 42MKR In the
convex setting, rate is consistent with the state-of-the-art centralized in-expectation bound of SGDM in Sebbouh et al. (2021). Further notice that the last term in both (4.3) and (4.4) is due to the a R2 LD, In this case, our guarantee for Local SGDM is aligned with the rate of Local SGD in Woodworth et al. (2020a); Khaled et al. (2020) up to logarithmic factor. Therefore, we the benefits of local iterations in the large M and large K regime compared to minibatch baseline.
RR²
bias of gradient clipping and would be negligible as long as Ka-2 >
K
L
We defer the complete version and detailed proof to Appendix C.

---

Published as a conference paper at ICLR 2025
4.2 LOCAL ADAM
The convergence of Adam is much more difficult to prove. Reddi et al. (2019) pointed out that the original proof in Kingma & Ba (2014) in centralized convex setting was incorrect. Therefore, the convergence of Adam in for convex function is of independent interest and beyond our scope. Instead, we turn to consider Adam in the weakly convex setting,
Assumption 5 (Weak convexity). There exists constant for any I, E Rd.
> 0 such that I is T-weakly convex, i.e.,
(V)(x) f x-0. v) 2 --|1 y11?
(4.6)
f(v) 2 f(x) -
-- ull?,
(4.7)
Note that T-smoothness implies that Assumption 5 always holds with T = I.. Also note that here we assume the weak convexity holds in B for technical simplicity. Let H, = diag( Ve, + X2) > Ala
and A == f(ro)= f.. Furthermore, define an auxiliary sequence {27]*] as:
p,, { ( B1 /(1 31) if k #
(4.8)
(17 x1 B1) otherwise.
Let Fr, == Bm 2 Now we state the main result of Local Adam below (see Theorem D.2 for more general results on Moreau envelope).
Theorem 3 (Full version see Theorem D.3). Let Assumption 1, 2, ford Ω conv (BR, (Ra)),
where Qo == (z()) f. - 4 and Ru /D/(80L). Further assume K 2 log(MKR/0), /), (0/K-3/2ppp R 111)). Then with probability no
1- 31 = ((1), ||o 112 2n = (o) and 1 - -3 = Ö
less than 6, Local Adam yields
R- 1-1
TA R
LA
T.o?
+ (IAO)
KR
VV (
+
KR
+
MKR
K +
(KR KR
(4.9)
A
LA
The RHS of (4.9) consists of four parts. The first part is
which is the optimization term
R and determined by the upper bound of learning rate 1). The second term is
KR'
LAg2
MKR corresponding to the standard statistical lower bound from MKB stochastic gradients (Arjevani et al., 2023).
(LAo)
The third component is
which is sourced from the discrepancy overhead of doing local
K à R3 LAg -
2ia 1) da-2
iterations, And the last one,
is induced by the bias of clipped stochastic gradient
KR 222
and can be dominated when K
2
Our analysis method can also be applied to Minibatch Adam (by substituting M, K with 1 and o with a / / KM; see Remark 2), and the convergence rate is
LA 0
L R
LAG2 MKR
(4.
aligned with (up to logarithmic factor) the state-of-thee the-re- convergence guarantees for smooth weakly convex functions (Davis & Drusvyatskiy, 2019; Deng & Gao, 2021). Suppose K 3n-4 o² PR/(LA) and hence the last term in (4.9) would be dominated and negligible. Now we can ob- serve the benefits of local iterations. Note that both (4.9) and (4. 10) have the statistical lower bound 1/VMK K R. Hence when the statistical term dominates, both algorithms have similar worst-case rate. Once leave the nomsendominated regime, then Local Adam converges faster than Minibatch Adam whenever K v 6² RLA).. And the gap will increase as K grows until K x L/T.
Therefore, we conclude that in the large M and small regime, Local Adam would outperform Minibatch Adam. Since f is close to convex function when t is small, this is consistent with Woodworth al. (2020a). Please see Appendix D.5 for more comparisons about Moreau envelop.

---

Published as a conference paper at ICLR 2025
We defer further discussions the choices of other important to Appendix D.5. The complete proof is in Appendix D.
including $1,
PROOF SKETCH
In this section, we show high-level ideas in our proofs. We only demonstrate the Local Adam here since Local SGDM is special case of Local Adam (32 1) and has similar patterns.
As a common practice in the study of weakly convex function (Davis & Drusvyatskiy, 2019; Mai & Johansson, 2020), the norm of the gradient of the Moreau envelope can serve a proxy for near-stationarity. Here we use generalized Moreau envelope for adaptive algorithms, proposed by Alacaoglu al. (2020). For any positive definite matrix I and y > 0 such that "I = Tld. define the Moreau envelope of f as
1
(z) (x) == min f(V) + | ullit
(5.1)
yER"
27
With some abuse of notation, we define (x) (2)((x) = [n/2(1)). The common con- vergence metric for weakly-convex function correspondingly [ (-)1 which can bound [| as shown the following lemma.
Lemma 4 (Full version see Lemma D.4). Let E Po and y == arg f(x) + 2 1| =11 for 27
some H ž Ala and L/A 2 > 2 27/>. Then
v 5 fv() H(= ///7
IV 2 (2) (2)11m-1/A.
(5.2)
In the rest this section, we provide the proof sketch for general Moreau envelop.
For any integer 0 < / < we define r(),, E N such that / r(() +k(() and < K-1. We will omit the dependence on and let r = r(), = k(() if not causing confusion. Further define
172 91 == 97, 98
9 u
u m12 T,k: " = u H == diag( / of + X2)
(5.3)
Then Algorithm I equivalent to the following update rule:
{{
x Ty ) ) u, m Tz 7. (H,mT) ur
if mod K # 1,
244
otherwise.
(5.4)
Define an auxiliary sequence {=1T>) as:
{
(x/ - -3127" 2/10))(111 31) if mod K 11, (x - -1x,1/ -1 otherwise.
2+1 = [
(5.5)
1 2-
Let y: == arg min f(y) + l1y Zz > Define filtration F-1 = =. (( U F(-1)
and conditional expectation E, [.] [[--
As standard practice in distributed optimization, our proof mainly contains two parts: contraction and descent. Here contraction involves showing that the iterates of local training different workers will not diverge to different points. And decent involves showing that the objective value decreases each iteration. Our strategy with high probability, which are designed to ensure contraction and descent. And event Ey can directly imply the upper bound in Theorem 3. fact, event E, has the form of
inductively prove that some probabilistic event E, E Fi-1 holds
Eg = (Aj,a holds for all j < f. - 1, i E (1,2,3,4)}
(5.6)
where A₁, E F, (defined later) is also probabilistic event. As the components of E,, each Ags is designed to ensure either contraction or descent. We will prove the high probability bound of these components in sequence.
8

---

Published as a conference paper at ICLR 2025
5.1 BOUNDING THE TRAJECTORY WITH HIGH PROBABILITY
Similar to Sadiev et al. (2023), we only make assumptions on f and noise in certain subset St C RR However, we are able to show that all the iterates will not leave 92 with high probability. Specifically, it holds for all iterates before time I, using standard techniques for weakly convex optimization, we can upper bound the function value and Moreau envelope at E++1 by
fy 14 (3(+1) - (Z0)
(2(n) Σ
|
(z
+0 Σ j=U
Bm Vm(=)) 9
stochastic noise
+ O Σ
[V/(())) E. (a
j=0
discrepancy
+ O())
Σ
nH Vf(z)) (())
Mj. En
E 199
9
martingale
+ higher order terms.
(5.7)
To see that the last term is a martingale, note that Hr()) is independent of gj" since the stochastic gradient 9f is drawn during round Further note that Ey[9,"1 - 9j" is almost surely bounded thanks to clipping. Now (5.7) allows inductively bound 14+50 (2z) and thus bound || mH (f(z) wı After these preliminaries, we are able apply Berstein's 's inequality (Bennett, 1962; Freedman, 1975) to control this martingale. Hence the Moreau envelope at ž1+1 can be bounded by a constant with high probability. Combining this with contraction results below, we can show that all the iterates stay in Q with high probability.
5.2 CONTRACTION
Next, we aim to show contraction, i.e., ||=;"" x=!'] will not diverge during local iterations with high probability. This property is crucial for showing the benefits of local updates in distributed optimization. However, different from Woodworth et al. (2020a); Khaled et al. (2020), the update of x²" in Algorithm is in the direction of ((""))"""?" which distorts the gradient by both exponential moving average (EMA) and coordinate-we wise product. Thus, the weak monotonicity (4.6) can not be directly applied as in standard analysis of gradient descent. This will further impede contraction.
Our solution has two steps. Firstly, we try to diminish the negative effects of different denominators used in local iterations. Then we turn to deal with the EMA of past gradient in first order momentum. Lemma 5 (Informal). Define probabilistic events
Ar.1 == {{ 1/ 3 H H 31+ (1 - B2)B and for all m E [M].
(5.8)
A == (1 (H (H,))
< (1 -12) for all m. [M]]
(5.9)
where B, Bi are some constants. Define F., = E, n Ar,1, Fr, F1,1 0 Ar.
For B
Ö(K), = Ō(K), it holds that PP P(E,,)) 2 P(E.) 5/(4T), P(E,,2) 2 P(E,.) 5/(4T).
Event Ar,1 implies the denominator of each worker during local iterations tends to be stagnant and close to the averaged one after communication. Event Ar, suggests the denominator at each worker
is close to each other. The key idea is to control the magnitude of o, = (1 (2)
Σ
3 93
+
j=r(t)
3 +1 (r())- Since all the iterates stay in conv (B R. (Ra)), the squared gradient ( can be - bounded. Besides, we can handle the martingale induced by 33" E, 1 by Berstein's inequality.
The remaining term Ey j0y" 2 V (x=") is controlled by the property of clipping operator.

---

Published as a conference paper at ICLR 2025
Now that the denominator is relatively stagnant, the update of 2 is approximately preconditioned by Hr(t) for all m. Hence we can turn to handle the first order momentum. A vanilla idea is to do the following expansion:
| - I...... 2 || xtt lli 21/ (3² - , u + ((1))
(5.10)
By the definition of uz" however, would be influenced by noises from past stochastic gradients. In this way, urd - ue is not independent of x Iz and thus it is difficult to construct a martingale and apply Berstein's 's inequality. This the reason why we introduce the auxiliary sequence {z(")
defined in (5.5). Fortunately, noticing that x x E conv ((=) 2g jise), it suffices to show that || || will not get too large with high probability.
Lemma 6 (Informal). Define probabilistic event
1222 KA, Σ 1o j=rk
(1-31) 31)002
Ar,3 = {1277 2 A.ll S A
for all m, E [M].
212 B2)
(5.11)
where some constant. Define Eg,3 = E1 n A For = Õ(1) and " =
Ö( min 11/(K)),1/L)) it holds that (PE)),)) P(Er.) 8/((T)).
Event Ar, is the desired contraction property and can further imply that || x Pl. s v²o² K A/A when combined with event E.. In fact, for {z( J. we can do the following expansion:
| 2141llis, ||
24
2111?,, HH
(2 2 st R O(7)).
(5.12)
Informally speaking, Eg (g 9.¹¹ is roughly V) - V fx")), which is close to vf(²,")
ff(=") since || - r = 21 x x"11 113) = O11²). In this way, the middle term O(7) of
RHS above can be turned to 2n (27" 2 vf(=) vf(2(')) where the weak convexity can be
applied. Finally control the martingale induced by (=f" -6 o EELor" -9(") through Bersteins's 's inequality.
5.3 DESCENT
Finally, we are ready to prove the descent lemma, which is the last component of E,+1- Define
Ar, = {1 (f (2++1) f- +
" Σ I
H
(3))) & 22
(5.13)
12 1=0
We proceed with (5.7) and control the stochastic noise term by subtracting its expectation to con- struet martingale. As for the discrepancy overhead, we apply the upper bound of |x=)"" - x 1| which is induced by the event E, and utilize the O(7²) bound on ||z, - 1² Therefore, thanks to all the foundations above, are able to bound each of these terms.
Lemma (Informal). For sufficiently small r,, it holds that TP (F++1) 2 P(F.,)) 8/(4T).
8. After Therefore, we prove that (P((++1)) 2 P(E:) - 8/T. And by induction rule, P(ET) 2 1 6. carefully choosing the learning rate 17, we complete the proof of Theorem 3.
6 CONCLUSION
In this paper, we prove the benefits of local updates within distributed adaptive methods to re- duce communication complexity compared to their minibatch counterparts. We study Local SGDM and Local Adam under convex and weakly convex setting, respectively. We consider generalized smoothness assumption and gradient clipping, and develop novel technique to show contraction during local updates. Future works may include improved analysis of Local Adam, benefits of local adaptive algorithms in non-convex setting, advantages over non-adaptive methods, etc.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Convergence of adaptive algorithms for weakly convex constrained optimization. arXiv preprint arXiv:2006.06650, 2020.
Wojeiech Anyszka, Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. Tighter performance theory of fedexprox. arXiv preprini vrXiv:2410.15368 2024.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2): 165-214, 2023.
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. pp. 560-569, PMLR, 2018
Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pp. 119-128, 2020.
Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. arXiv preprint arXiv:2306. 16504, 2023.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang, Robustness to unbounded smoothness of generalized signsgd. Advances Neural Information Processing Systems, 35:9955- 2022.
Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-4899 2021.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):007- 2019.
Alexandre Défosse7, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02335,, 2020.
Qi Deng and Wenzhi Gao. Minibatch and momentum model-based methods for stochastic weakly convex optimization. Advances in Neural Information Processing Systems, 34:23115-23127, 2021.
Arthur Douillard, Qixuan Feng, Andrei A Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Mare' Aurelio Ranzato, Arthur Szlam, and Jiajun Shen. Diloco: Distributed low- communication training of language models. arXiv preprint arXiv:2311.0800. 2023.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference on Learning Theory, pp. 89-160. PMLR, 2023.
David A Freedman. On tail probabilities for martingales, the Annals of Probability, pp. 100-118, 1975.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International conference on machine learning, pp. 1252- PMLR, 2017.
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (lo- cal sgd) and continuous perspective. International Conference on Artificial Intelligence and Statisties, pp. 9050-9090. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Sys- tems, 33:15042-15053, 2020.
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability convergence for com- posite and distributed stochastic minimization and variational inequalities with heavy-tailed noise. arXiv preprint arXiv:2310.01866 2023.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprini arXiv:2112.03459 2021.
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv preprint arXiv:1909.00820 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebas- tian Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint wrXiv:2008.03600 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pp. 5132-5143. PMLR, 2020b.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference Machine Learning, pp. 5311-5319. PMLR, 2021.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rX2. 6980, 2014.
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint arXiv:2304.1 13960, 2023.
Hanmin Li, Kirill Acharya, and Peter Richtarik. The power of extrapolation in federated learning. arXiv preprint arXiv:2405. 13766, 2024a.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaic. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024b.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assump- tions. Advances in Neural Information Processing Systems, 36, 2024c.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007. 14294, 2020.
Hong Liu, Zhiyuan Li, David Hall, Perey Liang. and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint arXiv:2305. /4342, 2023.
Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-effiiee dis- tributed gradient clipping algorithm for training deep neural networks. Advances in Neural Infor- mation Processing Systems, 02222204-22211 2022.
Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momentum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 31(8):1754-1766, 2020a.
12

---

Published as a conference paper at ICLR 2025
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271, 2020b.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint 1eXX::19020098433 2019.
Vien Mai and Mikael Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. International conference on machine learning, pp- 6630-6639. PMLR, 2020.
Vien Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Be- yond lipschitz continuity and smoothness. In International Conference Machine Learning, pp- 7325-7335. PMLR, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcieen learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282, PMLR, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm lan- guage models. arXiv preprint arXiv: 02188, 2017.
Yan Pan and Yuanzhi Li. Toward understanding why adam converges faster than sgd for transform- ers. arxiv preprint arXiv:2306. 00204, 2023.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318. Pmlr, 2013.
Kumar Kshitij Patel, Lingxiao Wang, Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. Advances in Neural Information Processing Systems, 35:13316 16313328 2022.
V. Petrov. Moments of sums of independent random variables. Journal of Soviet Mathematics, 61(1):1905-196, Aug 1992. ISSN 1573-8795. doi: 10.1007/BF00132200. URL https: ///di. ///doi.orge maeeii.rgg11..0 1007 BF 00362800
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.097: 2019.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky. Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochas- tic optimization and variational inequalities: the case of unbounded variance. In Proceed- ings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 29563-29648, PMLR, 23-29 Jul 2023. URL https: /pproceedings mlr. wwwpsssveeaiee sadiev23a. html.
Othmane Sebbouh, Robert Gower, and Aaron Defazio. Almost sure convergence rates for stochas- tic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pp. 3935-3971. PMLR, 2021.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper- parameter. International Conference on Learning Representations, 2020.
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma. Tie- Yan Liu, and Wei Chen. Provable adaptivity in adam. arXiv preprint arXiv:2208 0990000000000000,,, 2022.
Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and lower bound of adam's iteration complexity. Advances Neural Information Processing Systems, 36, 2024.
13

---

Published as a conference paper at ICLR 2025
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving coamuunncation-ffficieee distributed sgd with slow momentum. arXiv preprint arXiv:1910.00645 2019.
Jianyu Wang. Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, and Gauri Joshi. Local adaptivity in federated learning: Convergence and consistency. arXiv preprint arXi::2106002305. 2021.
Jue Wang, Yucheng Lu, Binhang Yuan, Beidi Chen, Percy Liang, Christopher De Sa, Christopher Re, and Ce Zhang. Cocktailsgd: fine-tuning foundation models over 500mbps networks. In International Conference on Machine Learning, pp. 36058-36076. PMLR, 2023.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. Advances in Neural Information Processing Systems, 31, 2018.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcma- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-1000 10343. PMLR, 2020a.
Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281 1-222,, 2020b.
Jing Xu, Sen Wang. Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv: 106. 10874, 2021.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion non-iid federated learning. arXiv preprint arXiv:2101.11203, 2021.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient mo- mentum sgd for distributed non-convex optimization. In International Conference Machine Learning, pp. 7184-7193, PMLR, 2019.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in 2020.
Neural Information Processing Systems,
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint 1905 2019.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393, 2020.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01000 2022a.
Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems, 2--28386-2839,, 2022b.
Weijie Zhao, Xuewu Jiao, Mingqing Hu, Xiaoyun Li, Xiangyu Zhang, and Ping Li. Communication- efficient terabyte-scale model training framework for online advertising. arXiv preprint arXiv:2201.05500 2022.
Fangyu Zou, Li Shen, Zequn Jic, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pp. 11127-11133, 2019.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
Gradient clipping. Pascanu (2013) first proposed gradient clipping technique to address the issue of exploding gradient problem of deep neural networks. Since then, it has become standard practice in the training of language models (Gehring et al., 2017; Merity et al., 2017; Zhang et al., 2022a; Liu et al., 2023). Furthermore, from theoretical perspective, gradient clipping is also used for multiple purposes. including differential privacy (Abadi et al., 2016), distributed optimization (Karimireddy et al., 2021; Liu et al., 2022), heavy-tailed noise (Zhang al., 2020).
Generalized smoothness. The generalized smoothness condition was initially proposed by (Zhang et al., 2019) to justify gradient clipping, and was called (Lo, -mmoooothssssss The empirical evidence therein illustrated that the norm of Hessian matrix of language models depends linearly on the magnitude of gradient, contradicting the standard L-smoothness. A recent work (Li et al., 2024b) further generalized this condition to é-smoothness and proved convergence of classical SGD in this setting. Apart from bounding the Hessian through gradient, Sadiev et al. (2023) proposed to assume that the norm of Hessian is uniformly bounded in certain subset of whole space, in order to get high probability bounds for (accelerated) clipped-SGD. Gorbunov et (2023) further extended this setting to composite and distributed optimization without local updates. Here we follow the setting of (Sadiev et al., 2023) since (To, (/))-smoohhness would reduce to most cases. See Section 1. for details.
B TECHNICAL LEMMAS
Lemma B.1 ((Bennett, 1962; Freedman, 1975)). Let the sequence of random variables {X1] form martingale difference sequence, i.e. X[ = for all i 2 1. Assume that
conditional variances of def |EX? ( X1) exist and are bounded and assume also that there exists deterministic constant e > such that [Xi] S e almost surely for all i 2 1. Then for all b > 0, V > O and n
12
(-
b²
P
Σ 1=1
Xil
> b and 1=1
Σ
o
SV
s 2exp
(B.1)
2V + 2cb/3
Lemma B.2. Let X be random variable in R and X == clip(X, p). Then 1 - EX s 2p.
Moreover, if for some a > 0 and a 2
E[X] =
E - x0 < 00,
(B.2)
P and |x| S 2. p2 30, then
(2o)a [[X] - x S pa-
R - 1
E - E[ S (2o)
(B.3)
Proof. The first claim is from (Sadiev et al., 2023) and we show the proof here for completeness. To start the proof, we introduce two indicator random variables. Let
if [f P. 0, otherwise
1,
1.
if P
X T(x4x1>0)
17 = [
2'.
(B.4)
0. otherwise
Moreover, since |X|
< |x| + XX
x -
X
z/1 we have x S n. Using that
X min
{
1,
p X
X
x
P
X + (1 x)x,
(B.5)
X
we obtain
E X
x
E|X
+
P
x
x
X
E
X
1
X
(B.6)
X
X
P
x
x
15

---

Published as a conference paper at ICLR 2025
p [ (0,11) when X # we derive
Since
[E[] x [x[
i X
[M) X _c| |
(B.7)
- )|
EE
|0//E [n)
(E (n])
P E (n)
By Markov's inequality,
pe
[n)
E
PP
X 1/
2a
< E [|X - x
(B.8)
pa
20
P
Thus, in combination with the previous chain of inequalities, finally have
20
2o
0
[B[X] 2/ a
(B.9)
2
P
pf-1
For the second part, since
| x = celip(X, p) clip(z (z, p) S X - -z/
(B.10)
hence E
x² 0
E X
x1 S 0th By Jensen's 's inequality, have for any 9 E (0, 1),
E X E[X] < q - X - x1" + (1 9) "
[E[
x/
q 0 + (1 - (20)
(B.11)
pa--
Choose the optimal q
and we can conclude that
(20 ar
B| E[J]| S o (20) pa-T)
(20)
(B.12)
This completes the proof.
Lemma B.3. For M independent random vectors X1, X E Rdd such that E[Xmm]
0,
Xm|[Xm|| < o², the the following holds
404
E
[| Xm 117
(B.13)
M
Proof. We prove by direct calculation as follows:
7
E
Em
X
1222
<
+
Σ
(Xm; Xa)
M
M
m78
mnn
2
7
E
|mm!l ||2
+
(Xmy Xn)
M2
M2
(B.14)
+
(X
X,,2
M
M
mccn
4
M2
16

---

Published as a conference paper at ICLR 2025
Lemma B.4. For any set Ω
R and
0,
define B
{a E Rd By E Q2 s.t., || yll r..
Then
B, (conv(()) = conv(B,
(B.15)
Proof. For any x B, (coov((()))) exist y1 YN E and (A1,-.. ,NN) A for some N, such that
N
| ull ST, =
nnn
(B.16)
n=1
N
N
Then x - + (x - y) =
An (yn + x 1/ =
Anton where
12:
n=
In Un + y E (2)).
(B.17)
Hence E (S)).
On the other hand, for any x E conv (S))), there exist F1,""" ,N (2), ".."" .NN E Ω and (A AN) E AN, such that
An
||
Vol S r.
(B.18)
n=1
N
N
Let y =
Σ mm
AnDn E conv( Then |
y/1
S
An I Uoll S r and thus x E (,onc (22).
10
C PROOF OF LOCAL SGDM
We restate the Local SGDM algorithm here.
Algorithm Local SGDM
Require: initial model æo, learning rate momentum 31 E [0, Set 00,0 = Tp. 7 0 for each worker m E [M] for r = ... R 1 do
for each worker m E [M] in parallel do
for l: 0, K 1 do
9 V= kr 97th clip(o?...))
Compute clipped stochastic gradient
",', B1 u u 1 (1 31)9"'
Update momentum Update model
end for
end for
1 Em kl 1,411-1 = Em [ml
> Communicate and average
end for
C.I OVERVIEW AND MAIN THEOREM
For any integer 0 < / 11 we define r(1) N such that = r()KK and k(I) K-1. We omit the dependence on and let = r(t), k k(t) through out the proof if not causing confusion. Define x;"" x Si" gr 9thh 9T ui w Then Algorithm is equivalent to the following update rule:
( Bi - (1- B:) if t mod K & O, otherwise,
(C.1)
B UT-1 + (1- B:)
17

---

Published as a conference paper at ICLR 2025
t mod K * -1, otherwise.
2
(C.2)
Define an auxiliary sequence {=( as:
1
B1
It
if t mod K # -1,
B1
1
-
B1
2++1
B1
(C.3)
Ft
otherwise.
B1
1 81
Define probabilistic events (see (C.12) for definition of some parameters)
Ar.1 = {1127 - 2111 - Oy² for all m, E [M]]
(C.4)
Ar,2 = (((z)) - 1.)(1 / + ||++|1 x.112 S 2(1
TH1 1+1
// ) D
(C.5)
2
2
Besides, let
E = [Ag holds for all j < - 1, [1,2}}, E.1 := E, A..1
(C.6)
Now we present two of our major lemmas, the first of which is to show contraction and the second descent lemma.
A = max p2d MT
MT 20 20
Lemma
C.1.
Let
Ko² log" 2
29 log
22
If
s
8
8 02p2(a-1)
(1 - (1-
Do
min
and p 2 (30xx3xxx xc, 2G then the following holds:
2L
4 KA
8
2(E,1) P(E.)
(C.7)
2T
Lemma C.2. For any > let
2 22 2a
Za-ij
max
30 2Goo
ifR> 0,
J18
P Z
2 Do |2 ax
max
30 2Goo
otherwise.
6 4pDg
(C.8)
2
log
ip 0,
J.T
6
17
4D3
otherwise.
T=
81)2
ME
Lo²KA
-1/2
Velu PV T
min
if 0,
17 S
0² log
T
B
E
(C.9)
(1 -1- --)
Me
Lo²KAY
-1/2
Do
min
otherwise,
L
o² log
T 5
E
pVdlog
where A is defined in Lemma C.I, then the following holds
8
P(E+1) 2 F(E,.)) 27
(C.10)
The following is main result, from which will parse the implications in Theorems and 2. Theorem C.3. Let Assumption 1, 2, 3, 4 hold for Ω = {|| x. || S v3D,). Further assume that for any E Ω |x] I Gog- Then with probability 2 5, Local SGDM yields f()) $
18

---

Published as a conference paper at ICLR 2025
if
D
L
o²
T
Lo²KA
PVd
T
log
(1
31
HME
log
8
V
1i=E
VIE
log 8
if > 0,
T
T2
D
L
a²
T
V
Lo²KA
AVd
T
+
log
+
log
otherwise.
B2)2
Me
Do
8
(C.11)
Here
2 |2 20
Za-1j
max
c0 2G
if > 0,
Me
PZ
2 12
max
22
x0 2G
otherwise,
E
2 pdd
MT
MT
212 K 12
| 2a
(C.12)
A = max
log"
29 log
K
0² 0² 2
2
4nD0
log
if 0,
HT
1/ =
4DB
otherwise.
Ts
to Proof. We prove by induction that P(EE)) 2 for t 0,...... ,
T
When = 0, this is trivial. Assume that the statement is true for some t < T 1. We aim to prove that () 2
(t + 1)6
It easy verify the conditions in Lemma C.I, C.2 once (C.11) and
(C.12) hold. Hence we have
5 2T
(t + 1)5
P(E+1)) 2 PE,) - 2.
21
(C.13)
T
Therefore by induction rule, PEET) 2 1 - and this implies by event Ar, that
T-1 Σ
(J(z)) - (.) -1)
mm ) 2 (1
T-j
77 T
D3-
(C.14)
2
2
カ=
Let n/ I (1 / -
By convexity, we have
2(1 - (1 - (T)
f(8)
2(1
T
2
(C.15)
2
(I) Case a > 0.
2(1 " JTDD
f(i) - 14
1 (1 )
< 4(1
np
y < - =c.
2
(C.16)
(2) Case = O.
2(1 n4 T DD
4D
f(0) - f.
E.
(C.17)
1 1- -M
1/I
We now state and prove the implications of Theorem C.3 which yield the results stated in the main body of our paper.
19

---

Published as a conference paper at ICLR 2025
Theorem C.4 (Complete version of Theorem 1). Under the conditions Theorem C.3 and 0.
20
2a |
MT
||
assume - 31 = 2(1),
2a
2 Goo V Coo, and K 2 log
jie
8
Then with probability no less than 1 ò, Local SGDM with optimal 7,, p yields f()) - f. S E,
if
T 2 log JD
L +
o²
T
Lo² K μ²ee
log
MT 5
Ld
MT
20 2a
2(0-1)
log
+
+ 122
log
MMe
8
8
μEE
(C.18)
And equivalently, let :=: 1./1
f(8) J. exp (-0
(KK
0²
KR
log
μMKR
2(-11)
(C.19)
Lo 1oglog" (KR)
MKR
|0 2 (Fd)
log MKR
+
log
RRKR
5
1
K R
Proof. Plug the definition of in (C.11),
DDg
L
d²
Lo K log 8
PVd
T
T 2 log
+
log
+
+
log
μ
HME
8
1LzE
VIEE
DDg
LK
pdd
MT
K 22(a-1) 1)
20
+ log
log
1.25
K
(C.20)
DD
L
0²
T
Lo K log 8
MT
x log
+
log
+
1
MMM
1ize
DD
LK
id
MT
K 20 p (a-
+ log
log
E
1
K
Hence the optimal p is given by
1/a
K
0
2ia 13
x max
||01120
Vdlog
MT
0oo Goo
(C.21)
|
1laa
Note that
Goo o and this implies
L
o²
Lo K log
T > log
+
log
+
M
uze
+ log
L
||o
K
dlog²
MT 1-1
||o
2a
d log
MT
112E
8
DD
L
o²
La log
MT
Ld
MT
lo
2a
2(0-1)
x log
1
+
M
log
+
122e
+
V
1
log
(C.22)
MT
||o| 20 d2
It
2
In the last equation we use K
2 log
This completes the proof.
8
20

---

Published as a conference paper at ICLR 2025
Theorem C.5 (Complete version of Theorem 2). Under the conditions Theorem C.3 and 0,
20
MT
||
assume 1- 1- 31 2(1),
2 Go V Jos and K 2 log
8
Then with probability no less than 1 ò, Local SGDM with optimal 7), p yields f(i) - f. S E if
D
o²
T
Lo 2 K log
dL
Dollo
a 20
MT
+
log
+
+
log
(C.23)
Me
8
8
And equivalently,
L.D f(0) f. 2
DDo
KR
+
log 2
KR
VMKR
8
2(x-1)
Di
logs
MKR 5
| 2a
dLDo
a-1
Do
log MKR 8
K R3
K R
(C.24)
Proof. Plug the definition of A in (C.11),
D
0²
T
Lo K log
MT
pvd log
T
T
2
L
log
ME
e
Do
D3
LK
pdd
MT
K 20 2a (2(a11)
+
log
K
8
D8
0²
T
L K log
MT
L.K
pd
MT
2o 2a 1)
2
12a
L
log
log²
Me
K
(C.25)
Hence the optimal p is given by
1/a
K
Dol
p max
||0122
2a
oos Goo
(C.26)
Volog
MT o
Dollo
Note that
2 Go V oo and this implies
D
2
T
Lo
MT log
T N
L
+
log
+
8
M
D3
L
1 1
K
dlog
MT
1-1 +
Dollo
2.
dlog
MT
(C.27)
E
E
E
D3
2
T
Lo
log
MT 0
dL
Dollo
MT
L
+
log
+
V
log
M
8
8
2n
MT
|
2 #
In the last equation we use K
>
log
Solve and we get the upper
bound of f(i) f.. This completes the proof.
C.2 PRELIMINARIES
In this subsection, we show that event E, implics all the iterates remain in certain area, so that we apply all kinds of properties of f afterwards.
21

---

Published as a conference paper at ICLR 2025
Lemma C.6. If fnoVKA S (v3- - D2, Event E, implies that for all j S t, E [M], we have 2y 2g TJ Q. And |x>]" 23} S nov KAAAAAf for all m, n.
Proof. Event E, implies that for all j S L,
Jz x=l || S v2Do. || - -2 S no TooKAAS (v3- (V3-22)
(C.28)
Hence 3j E Q |=
x. v V3D, and 2 E Q. Also, notice that Iz E convizilis and
"y - 43 E conv (=) = Jisj We have
| - x. S v2Du, |> اااه nov K KA, || -yバ POVKAS (V3 v2) (C.29)
Therefore u.. Ty E Ω. This completes the proof.
C.3 PROOF OF CONTRACTION LEMMA C.I
In this subsection, we aim to show contraction, i.e., ||=;"= - won't be too large during local iterations with high probability. This property is crucial for showing the benefits of local updates in distributed optimization. However, different from (Woodworth et al., 2020a; Khaled et al., 2020), the update of xt" is in the direction of momentum "n which incorporates information from all past gradient. Therefore, we cannot directly apply (-ž" - xz (u( u('>> 2 0. Fortunately, noticing that 2²'" x" E conv(1z]" 2j hist), it suffices to show that ||="" 2 won't get too large with high probability. Besides, the update rule of 27"h is much easier to handle.
Proof. First note that by the upper bound of 17, Lemma C.6 holds. Since 2 = z 799
||=|1 - 2 = || 2/112 2n/ 24"" - 2/ .%" 9. ) + 1² 19 of 11
S ||="" =2/1/2 - 2n (2)T) =2², ((x"'")) V)(xz))) + 2n (x;"() - [)(x))1
+ 21 =t" - zh, V[((=")) V\(x,)) - 56th + ,. + 2/ (xx)') - v/(xa)
66 + 98
(C.30)
Event E, implies =t" "6"" E Z and thus by Va, y E 22 (x - V/(x) <((7) 2 11V/(6)
(2T 2 -
= (x) x.. (xx)))) - v)((;()) + +
2/ -xx"" - -f)).
2 (x))) x,, - v)(²'))
-
LIlE?"" - -2 - (xx"" - x1,0|² +
11 V {fxTr) - vf(2;))13
4L
3
[V - V((E))) L| =x¹² (x"" - x/')l
4T.
(C.31)
Therefore, for the second and third term in the RHS of (C.30),
-2n (2 2F, f=(='")) (zx²)) + 2 fx("") - \2(=)))12
7 [f - {=( + + - -2 - (I.1' - x²) I|?
S
(C.32)
By the update rule,
1731
2
||2 m 27 (x7" 211111==
|| 2it ||2
1 -1-6 31
n1
2
t-1
<
(1 - 31)
Σ 8 9
1 B1
j=rk
2(n31)²
Σ
81
[|
- Vf -
19
9 Vf
1 81
j=rk
(C.33)
22

---

Published as a conference paper at ICLR 2025
Let St == Σ -( - VV((z)) We further get
j=rk
LHS of (C.32) S - -, (S: 315 +
S + Σ
-
1 B1
j=rk
= - (S: (s, + 4nI((181)
1-1
Σ -
1 31
j=rk
(C.34)
Then plug in (C.30),
|| - 2 11 S || -2011 =/²11²= 2=_
" (St S--1)
4n (n3,13))
t-1
Σ 8 -
VV
+
1 - 11
j=nk
+ 21/ ( -x"" - z -V((a))V(((("))-
+ + +
V VV(xx)1
(C.35)
Notice that this recursive bound holds for any rK S i < t. Unroll it and recalculate the coefficients using n S (1 - /2/
1 - 2/+111 1|2+
7 St S
Σ
2m
(2
- 93
L
j=rK
Σ 4n V(()) 1
+
j=rk
2m 2 E 10
071 19" 93)
j=rK
d: martingale
2n (2)
m
2/
j=rk
clipping bias
+
4n² //t0::00~~(100000000000111111110 - 0 ワィ |1
j=rK
d:: martingale
+ 4n7 . 202
(C.36)
For O, define
2n m - 27
93
if event E, holds, otherwise.
(C.37)
0,
Then since event E, implies ||=mm - 2 S no KA,
1 m.n
< 2n - nov KΛ . 2pv d = 4njopp dK A dal
(C.38)
Var,(C < 4np 002 KA 20 = OKA.
(C.39)
23

---

Published as a conference paper at ICLR 2025
Let T = on =
By Lemma B.I.
Σ
m. 9
S b with probability no less than
j=0
1
8
1 2cxp
21 21-
(C.40)
2V + 2cb/3
4M²T
For (
|20 12a
1
2 S 2n/K non VAVVKAAA
(C.41)
pla-1)
4
For Q define
0gmn {
4n²
07 + 0 B -
10)" 0" []]]]]
if event Ej holds, otherwise.
0,
(C.42)
Then,
107 S 4n7² 4ppd = 16r2ppd def c, Var, Var,(07 < 167 E,1lV/(<))) V (.(xg))
(C.43)
10 33|1 64n
(C.44)
0 S b with probability no less than Let 7 o = 64 By Lemma B.I,
1/2
5
1 - exp
2 1
(C.45)
2V + 2eb/3
4M
8
Combine @, @, Cand thus we can conclude that with probability no less than P(E.) 22 event
4T
Eg holds and
|| 2 11? S 77 o KA for all m, n. This completes the proof.
C.4 PROOF OF DESCENT LEMMA C.2
Now we are ready to state the main descent lemma of Local SGDM.
Proof. Again, note that by the upper bound of 1). Lemma C.6 holds. Under event E,,
| I=1 = ج x.- 1| - 22n E - Fo, Em [ ) - n/" Em 5 |a("
I || x=11² 112 2 2n (Ze- Z., Em (= - 2n ( x. Em - vf(=(")))
+ 27)² 2 Ml L9th vf(x ||| + 2n Em /V [x)"))11
(C.46)
Since xt Ft, 2t E Ω for the second term,
(2t F., Em (4 = (Te F. Enn,. [x:"x)))) + (2, Ie, Bm (v)
= Em [1are x: V fx:")) + (xx - R.. vs("T)))
+ (Z+ It, Vx(xx)) + (z, - - Em fx(("")) vf(x)))
(C.47)
By smoothness,
Em [ - 2. f((""))) - LIE || 111131,
(C.48)
- | - 11
I.
f(z,) < f + (हe Z., vf(z,))
(C.49)
2
By j-strong convexity,
Em (<x)"" - F., {((x"))) 2 Em (fx") - ff + 1 ||ا77 - 11
(C.50)
2 f(()) fa + / -ل xx 112
2
24

---

Published as a conference paper at ICLR 2025
Therefore,
(Ze- Z. Bm = 2,, Em [f(x"')) + +2z - Em V f(xx"")) }]}
(C.48).(C.50)
(xx) f- 2110 1.. 12 - I.E || ==-1²²
+ + - F,, (z())) + (2e 1 ,t, Em V (2:" (x))))
(C.19) AM-OM
2 f(z+) - S. + クリ |.z- - F. 11 2 | - Tell2 L.Em [1 - -111
L (11z - 3z 112 + || 3 (1)
2
AM-GM 2 f(z)) - S. + 11 1| 22112
3L
(1]z, Fz 1 + Em ||
2
(C.51)
For the last term in (C.46),
Em V=<x") I112 - 6n)² [1-||1771 - -=al + |3 - 1 + [+
1
(C.52)
S 6nj² L 12 - 1.1 12 + + - ==1? + 2T.
(f(z)) - (.))
1
Combine all these inequalities plugging in (C.46) and notice that 17 6L'
|z - 12 xx,1= S (1
- 7//1
|| || -.1 -
m((( f.) + 4nL [||
11 + Em ||,"" - 2, 12]
2
27 Et Iz, E.,.Eml Em V ff<="))) + |Bml9 V f(xx")11
(C.53)
1-1
31 ) By Lemma C.7,
Define A, :=
Σ |لا| |ل, - T.+1ll where ars == 81- + 1 - 31 )
1=0
(3
we plug (C.85) in the above inequality and compute (C.53) + (1- (1-31)a x (C.84). Now let
b = 1| ==+ 2 (1)
(1 (1) A--1. Hence we obtain
1 1 B1 )
n/31 22
Det1 S (1- - T/p Φ.- (z+) - S.) + 4nL
Em 11l - xe|l + 64
I |
(1-3) 31 )
n/31
2
1-1
+ +32mL
(1 - 31)
8 84-5-1 2222Emllle - 3, +
1mm1999
1=0
27( (z - 2x,, Em m
+ 2n7²
Em [..
< (1 nu
2 /0, (((E))
f.) + 4n |1
m Fz
(1-3) 31 )
n331
2
1-1
+ +32nL
(1 - 31)
Σ
8 81-5-1
21 22 Em |1=m" - -,,131 + |mml997' - V.(aa'))l
1=0
2n (7l - Zx,, Em m
Vf 11) +2n Em
(1
$ <(1
nu
2 p
!
(f(z))
- f.) + 167L . 22²
2
11/31 )
2
1-1
+ +32nL
(1 - 31)
Σ 8 8
Bm 10 v ff {( 2
1 31
1=0
2n (3e - Ze,, El 19
[{(xT')] ))> + 2n7
Em |g
V
f
(C.54)
25

---

Published as a conference paper at ICLR 2025
Here in the second inequality [V(2)) 3 2L(((z)) f.). In the last inequality, apply
contraction results implied by event E,,1
Unroll this recursive bound and re-calculate the coefficients,
Σ D (f(z)) (1)(1- 2
74 y P4t1 2
S
1+1l 1
32n/ Lo KA
2m
(1
7H ) t-
[g 2t Bm vf(xT)))
2
1=0
+ 41/ Σ (1
4/11 1-5
Em 9 vf(2f))]1
j=0
(C.55)
Simplify P441 term,
Σ
(()) f-) y 1 x.112 S (1
" 2
TH y++
y
1
xx1 2 321/² KA
2
2
1=0
27
)
t-j
2j Fo, Em 13
E, E,(95"1
2
j=0
martingale
21
(1
1/14
j-j
2j F., Em -
(z(()))))
2
j=
$: clipping bias
+ 417
(1
nu /
1 10 vf(x")111
2
j=
(C.56)
For the last term,
41
TH )
Fm
10
[[(x;))]
S 81} 2
(1
TH 2
1-
||mm 9
E.
0 2 E,J
Em
(9""
)=0
)=0
3 martingale
+ 81 2
Σ
nu
)
E m 1o3 E
F. 11
2
j=0
+ 877
n1p
y
Em E, 19,9 f(x))))
2
1=0
@ clipping bias
(C.57)
we finally get
Σ 2 -
f-)
Tp y + 1 -xx1 < (1 2
nA
1+1 D + 32
nLKA +
1
no²
2
M /
1=0
+ ① 2 3 +
(C.58)
(1) Case / 0.
26

---

Published as a conference paper at ICLR 2025
For @, define
{
- 2m(11
7/ yr
(--((( (z) 2x. Em [9) - EE 1E,19"11>
if event Ey holds, otherwise.
9 {
2
(C.59)
Then since event Bj implies
||ا x--l 12(11
7111 3/2 Do.
2
K S 2n v2(1
N n Do 2pv
2
4(1
y 1/2
nu
2
npv 2dD
def c,
(C.60)
Var,(Si) S 4r)
1 7i1 2((-))) 2(1
} DJ
o²
M = 8(1
Ti 20 11 Dio"
(C.61)
2
2
2
M
(1 - (1-22 ) D
13 D8 08
Let b
V 16(1
111l
By Lemma B.1, Σ S3 S b with probability
2
H.M
no less than
12
21 ô
2exp
(C.62)
2V + 2cb/3
4T
For @, since by Lemma B.2,
|
2n
1, Vf(a")) |11 <
2n
(C.63)
2 1)
event E, implies that
TH y 22
114 5/22 //2 Do
|2 12. pa-1
S 2n)
(1
2
2
/=0
S 2
THlL 2 11/2 Do 2 1
(C.64)
14p-11
m D8
Here the definition of 1 and conditions of p in (C.12).
For @, define
f
8n² 77/4 y-
| 19,"
E, 197 11
E, 10 E,1o," [113]
if event E, holds,
0j
0,
otherwise. (C.65)
Then
10,1 S 81}2 4p2d 32n²² 2dd def c
(C.66)
Var,(0,) 5 64n 2
nH4 / 2(1-)) E,y Em 133
E, 10," 111212
Lemma B.3 S
6477
nP 2(1 2(t-))
4(2r)*
2
2
M
(C.67)
Let b- (1
n2 1+1 D2
23 30 uM2
V
By Lemma B.I,
Σ
0,1 < with probability no less than
5
1=0
12
8
1 2xx
21 1
(C.68)
2V + 2cb/3
4T'
For ④ by Lemma B.2,
16n
||
2x
(1
ny 1+1 D
<
20
(C.69)
(
1)
5
27

---

Published as a conference paper at ICLR 2025
8
Combine the above claims, with probability no less than 1(E,,))
we have (0+2+3+0) S
47
5 2 - Dj. By (C.58), these implies
Σ 2
(1(z)) - (.)
nl y t-j + |
-xa1l (1 =1
M1 1+1 DJ + 32
nLK A +
1
no²
2
2
M
j=0
+
(1
++1 DO
2
4/14 (- D 2
- 2(1
(C.70)
8
Therefore, we conclude that P(E++)) 2 P(E,,)
2T
(2) Case μ = O.
In this case, (C.58) reduces to
2 HHE)) 1 16+16 nLKA+ + 1
M (10 (C.71)
For @, define
2n 2g Ex Em 99 - E, (0,99"11)
event E, holds,
CJ
(C.72)
0,
otherwise.
Then since event Ej implies
|| x--l V2Do.
|G < 2n 22D 2pv = -mpv 2dDo def
(C.73)
a²
811² Df02
VGr,(G) S 4n²² 2D
(C.74)
M
M
Let b V 812 81/ 2T
Dg 5 M
By Lemma B.I, Σ
16
S b with probability no less than
j=0
6²
8
1 2exp
2 1
(C.75)
2V
2cb/3
4T
For ( since by Lemma B.2,
| 2a
V(( m7 |1112
(C.76)
p
event E, implies that
22 pla-1)
D2
@
S 27/( + 1)
V2Do
22
(C.77)
Here again use definitions and conditions in (C.12).
For @ define
817
Em 10 - 19 ]|[ E, Em 1yy E, 1g [133]
if event F. holds, otherwise.
0
(C.78)
0,
Then
10,1 < 8n7² 4p2 d = 32n p² def
(C.79)
(ar 64n E, E, " E, 1r 212
emmma R.3
S
64n
4(20)*
(C.80)
M
28

---

Published as a conference paper at ICLR 2025
D
2 04 2
Let V 5
By Lemma B.1,
Σ
0,1
- b with probability no less than
j=0
6²
8
1 2exp
2 1
(C.81)
2V 2cb/3
4T
For @ by Lemma B.2,
|2
Dj
O S 80j (1
+ 1).
(C.82)
p2(a-1)
5
8
Combine the above claims, with probability no less than 1(E -2
we have (+2+++0 v
4T
4 D. By (C.58), these implies
? (S(2)) (.) + 1 - 1 Dg + 16
IIKA+
11
22 + +1) +)+ 4
D
2
M
5 (C.83)
2DD
8
Therefore, we conclude that P(E++1) 2 P(E
27
31
Lemma C.7. Let A = Σ a.sil Tj+ill? where onj == 81 81-5-1(t -j j
). Under the
1- 31
j=0
conditions in Lemma C.2, then the following holds:
(1 31)2
32n
A -
A--1+ +
1- 31 [[]((2)))1
2
(C.84)
t-1
+ 41
Σ j=U
31
8--3-1
22 11,251
1,
|| 105" ([
1191
|| - Tell3 -
[16L
+ 32 [
1 31
4 11)
2 1-1
31
at-j-1
2L Em 1==," 11 + [B - V((x"))]1
1 B1
1=0
(C.85)
B1
2
Proof. By definition, | Ioll
|| 17a-I1111 x1-11
and
31
b - = 17² 11/2 2
1-1
=1/
(1 - 31)
3 j-1
Em
1=0
1-1
1-1
< 27
(1 31)
8
Em [[(2"']]
+
(1 - 31) Σ
31
gt-j-
En,,,, (f(IT') )
1=0
1=
< 2
(1 - 31)
8 (T,))
1=
+ +2 31) Σ 3
2L 2
||=5""
-,119 19
(C.86)
29

---

Published as a conference paper at ICLR 2025
Note that
t-1
[-|
(1 - B1) Σ
- (((z)
2
(1 31)
81
8
- v + +
5-
j=0
1=0
1-1
$ 2(1 - 31)
- -
Σ
2/
/=0
1-1
2 81) Σ
8-- (t j)
- 14
1=0
2L
Σ
01
10 -
+2
Vf
)=0
1-2
4L2
< 2L
Σ
at
( +
c - T, 1112
(1 31)2
j=0
(C.87)
Here atj = (9- + 1- 3
81
). For j S -- 2, we have ous 31 -1) Since
A Σ a 1 -z+1| 1| we can conclude that
TTz T 1111 s 1
1-1 Σ
+ 4n - -1)))) (1)
87-1-1
22 2 1|,25" - xx,12]+ +
|Em 07
V fa |1|
j=0
(C.88)
which implies (C.85). We complete the proof by plugging the above inequality in
A $ (2- 81)
+ 1 - Bi - Fe-1 11.
(C.89)
C.5 FURTHER DISCUSSION
Coordinate-wise clipping and global clipping. Lemma B.2 can be easily extended to R4, similar to Sadiev al. (2023, Lemma 5.1). Therefore, our results can be casily generalized to global
clipping operator clip, (X.,)) = min { 1, Pg X with threshold Pa pVd. We omit the |
details in this paper. Readers may also wonder why our Theorem C.4 and Theorem C.5 depend on poly However, if we assume ||o = = =O()), both of which are of order O ) then our convergence guarantee will not depend on poly(d) explicitly. Zhang et al. (2020, Corollary 7) claims that coordinate-wist clipping has better dependence on dimension d. But they simply upper bound Rg-D| F by / V (z, I) which is too pessimistic. In fact, if we assume Eç-D|| / F(x,, Il O(dm/2-1 E VF(x, E)ll)), both of which are of order Odd)) ), then there is still no difference between woordinate-wise clipping and global clipping in their setting.
Prior works on distributed SGDM with local updates. There are many works on Local SGDM in distributed setting. Liu et al. (2020a) studies Local SGDM in convex setting and rely on some strong assumptions to show convergence. Xu et al. (2021) analyze Local SGDM with bounded gradient assumption and the use a global momentum parameter during local iterations. Yu et al. (2019) considers non-convex Local SGDM but is only able to prove linear speedup. Wang et al. (2019); Cheng al. (2023) also study non-convex problem and use momentum to handle hetero- geneity in federated learning. All these works fail to show the benefits local iterations compared to minibatch baseline.
30

---

Published as a conference paper at ICLR 2025
D PROOF OF LOCAL ADAM
D.1 OVERVIEW AND MAIN THEOREM
For any integer 0 Σ t S T-1, we define r(t), k(t) E N such that = x(t))++((t) and k(t) & K-1. We omit the dependence on and let r(t), k k(t) through out the proof if not causing confusion. Define x; = x Dt == nn "t = g7.k " " Then Algorithm is equivalent the following update rule:
{ B Brul= (1 =1)
if t mod K # 0, otherwise,
U1
(D.1)
8 T1 (1 B1)9t"
02 + (1 - 32) m
if l mod K # 0, otherwise,
1/2
(D.2)
12T.-1 (1 32)
11 - 17( Hi!! -1 m
if t mod K -1, otherwise.
2++
m2
T 7B [[H m
(D.3)
Define auxiliary sequence
1
B1
Ft
if t mod K 11
1
81
2641
B
(D.4)
Tt otherwise.
B1
T++
1
-
B
Let
B1
c =
(la H1TH (H(m)
(D.5)
1
1 Bi
Then the definition of { implies
n)(HTT
-
mm
11311 (1
20+1
m
+
1 31
1- 31
n1331
[H, 1 (HHr)))1
(D.6)
1- 31
=n - -'( e.").
1
Finally, let yt == arg min fly) + yy Eel H
2-
Define probabilistic events (see (D.15) for definition of some parameters)
Ar,1 {3512 1 H 1 H = 1 (1 B2) and for all m E [M]]
(D.7)
Ar. = (HH (H)) $ (1 B1 for all m, n [M]
(D.8)
||207 - 21 I 0202
(1 (1- (1=33) for all m, n E [M]
Ar,3 =
KA, Σ
| <
x
212 - 3
j=rk
(D.9)
Ae ==
fo (200100 min f. +
"
|
ft
Moo)
(z,))l?r=3
11 24
(D.10)
12
j=0
Here := = f7(10) min f.P. Besides, let
E. = {A,, holds for all & t- - 1,i [1,2,3,4)}.
(D.11)
F4,1 = Pa n Ac, FA.2= == FA,1 O Ar,,, Fr.3 == F4,2 0 Ar.
(D.12)
31

---

Published as a conference paper at ICLR 2025
Theorem D.I. For L/A y 2T/X, let Assumption 1, 2, 3, hold for Q conv (Bro (Ru)),
A
where Oo= == (1)()) - min / - 2 - 1 ( - f and Ro = that for any x E 9 [ < G, [ )| no S Goo. and
Further assume
160A
1 (1 --)VVA 7 1- B1
1 - 3/ 2 min
(D.13)
K4/2B1 KMBBIG "B' K1/2B" K
24AA
If 7
then with probability no less than
6, Local
Adam yields
ET
R- R-1K-1 K-1
if V V (3r,
KR
1=0 k=0
LL 1/4
A
LAO²KA
LA
KTA
T 2
log²
(D.14)
mints, / /Gx)
(1 B1 P
(VB2 B1)E
Here
2
12 12
p 2 max
2n
30 2G
6K (C + 2%2
16p²
dMT
26 V (Goo
+ 0000000
1/2 dMT
B = max
log
log
X2
X2
8
X²
8
16Ko2
16p²
dMT
)00)000
log 1/2 1/2 dMT
B1 = max
log
26
X²
X
8
X2
220 p²d
MT
MT
2 K
20
2a
A max
log
20
log
2a
KØ²
a² 22
(D.15)
16
Proof. We prove by induction that P(E,) 2 1-
for t = ,
T
When = 0, this is trivial. Assume that the statement is true for some < T 1. We aim to prove
that PP ((EE+1) (1 + 1)6
By Lemma D.8, D.9, D.10, D.11, we have
T
5
(1 + 1)6
P( 2 IP( F.) - 4.
2
(D.16)
4T
T
Therefore by induction rule, P Ex
2 - 5 and this implies
T-1
Σ | 10 10) (z))
24AA
T
H
S
1/[L
= E.
(D.17)
Now we verify the conditions all the lemmas. Lemma D.7,
7
A
T>>
LAKA.
(D.18)
A
AA
In Lemma D.9,
7 <
22
A
IPO2KA
T>
(D.19)
GoLLoVAA
GZ
In Lemma D.10,
7 S min
(1 - 81)
LA
KTA
>
(D.20)
X
Kr'
L
[1
3
32

---

Published as a conference paper at ICLR 2025
24AX
[20
2a
Z
In Lemma D.11, by noticing that
= E, (D.113) is equivalent to Z
and
1/T
(1- 31) MyE
LA
-1/2
MA
< min
L
log
1/2 T
x² log
Apo
LpVdlog' 1/2 T (D.21)
8
which can be ensured long
LA
Ado ?M
T A 7
Loo
LAppd AAp2dlogg
T Z max
log²
(D.22)
(1 (1-B
8'
(VB2 B1)E
Here we use the fact that
7
Therefore we can conclude that all the lemmas hold
L
V
LLppd I
AAo2 MM
A
12O2KA
LA
KTA +
T T
log*
+ (1 3
+
.D.23)
E
/G
Finally, verify the upper bound of 1 B2 in Lemma D.9, D.10 and D.11 as:
1- B1)oVA A 1 1-81 1
1 - 32 S min
(D.24)
K1/BB1 KV/BB "B' K1/2B' K
Theorem D.2. Under the conditions of Theorem D.I, assume 1 B1 = Q(( and
|
2a 2a
2
1 1-32=
R1/2
Goo V 0o0 2
Go
20
(D.25)
MT
|
22
2a
K > log 8
Then with probability
less than 1 8, Local Adam with optimal n.P yields
R-1K-1
Hr (Zr,h)) S Sell
KR
P=0 k=
2
T
LA
MT
(L (L+KT)4
LA
||o 2a
3e 1y
MT log
log
o² K log
+
d
7M
8
8
8
6
(D.26)
And equivalently.
Σ
R- K-1
(1
S
A
LA
+
AAo²
log
KR
KR
R
KR
MMR 8
0=0 k=0
Zia-1 3a-2
(LAG))
MKR 5
(110
LA log 5
MKR
log
+
K à R
KR (D.27)
33

---

Published as a conference paper at ICLR 2025
Proof. Plug the definition of A in (D.14),
2do2
T
A
MT 12o2K
o +
(I+ (I++ +
Lopedlog J
T -
log
+
yM
A
L
dlog" MI
p² + K|lor1120 p2(1-a)
(D.28)
AAo 2
log
T
+
MT L2o2Klog
x +
(L+ (T)
7
2
A
L.K
d doog MT
p² + 12 p2(1-a).
K
Hence the optimal p is given by
1/a
K
0
20
11a
max
|101120
2a
0x: Goo
(D.29)
MT Vdllo
||or|
1
2a-1)
Note that
2 Go oo and this implies
8
2
T
A
K 12
log MT
(L+KT))
logs
7 2
8
8
8
+
LA
||01|20
dá
K
m
log
MT
+
o
2a
Na-zj
d log
MT
8
82
XAo²
log
T
LA
oo2k log
MT
(L +
KT) A
LA
o
2a
2a
d
log
MT
7M
8
8
(D.30)
20
MT
In the last equation
K 2 log
Solve and we get the upper
R- K-1
A
bound of KR
| H. (Zr,t)
K=0
Further note that A Ö(1), B Ō(K), =(KK)n Õ(1/VT) and we can get the upper bound of 3g as:
1 1- K3/2
(D.31)
This completes the proof.
X
Theorem D.3 (Complete version of Theorem 3). Under the conditions Theorem D.2, let and thus Ro {x: f(x) f- 4(f(zo)
L fc. Then with probability no less
A -
f(zo)
R-1K-1
than 1 6, Local Adam with optimal 17. P yields
A
Σ Σ
I ((r S if
KR
k=0
L
T
LA
MT
(L (++KT)
LA
||0
2a 2(-11)
MT 8 (D.32)
log
+
2
K log
+
d log
M
8
8
E
34

---

Published as a conference paper at ICLR 2025
And equivalently,
R-1K-1 Σ k=
T
LA
LAo2
KR
(V
2
V MKR
log
KR
R
KR
6
(IAA)
log
MKR
+ (101llaad 20
10-7
LA log MKR.
K R
KR
(D.33)
G + o²
Further, if1 82 x
where p is definded in (D.29), then with probability less than
p² log
dR 5
1 1828,
R-1K-1
Σ Σ
(V((2,)))1
2 (1+
Go 0000 0o0
TA
LA
+
LAo²
log
KR
+
(LAo)
log
MKR
KR 0=
R
KR
MKR
8
K R5
LA log
MKR 5 KR
+ (101l2aad -2)
)
30-2
(D.34)
Proof. By Lemma D.6, we have So C fz : f(x) - fo S 4(f(zo) f-).. f(xo)
fa. By Lemma D.4, have [V, S (zr,)),,, Therefore, the bound Solve e and we get the upper bound of
for T in Theorem D.2 will reduce (D.32).
R-1K K-1
KR (f
Now we turn to bound ||r]]. Note that H,41 diag( V Ur41 + 12) and
-
Σ
rrk
-j-jj
Em
13
j=U
rK-1
-11-
krk --j-- (Em
1 E, "
+ Em E, 1o
(D.35)
j=U
rK-1
S (1 - 32)
3rk
K
Bm
g 13
E2 E,
+ + + 332
j=U
where the last inequality is due to Lemma B.2. Define
[0,1s {
(1 -
11-32)32---2 K Em
if event E, holds, otherwise.
(D.36)
0,
Further note that
|10,kl S (1 B2) das
c,
(D.37)
Var, Var,([0,)) < 32 222 -11
2
By B,
g0 12 F, 9
M
(1 32) 32)2522 32rK -j
{ 2
BnLE
(D.38)
M
32) (.)2,2(rk ( -)1
(204 xo
+ 802 x
G2)
M
35

---

Published as a conference paper at ICLR 2025
Let Go + 300000 V= 2(1- 32)02 (o2 + +4G2))
G2 + 0
If
B2 x
then by Lemma
M
p² log di
rk
B.I, we have
Σ
10yl I b with probability no less than
1=0
8²
8
1-2 2 exp
2 dR''
(D.39)
2V + 2eb/3
which implies [H. S X + 20 + 20 Therefore, we have
IP FTT and || H, S x 2G + 20 for all r s R3 2 1 - 22..
(D.40)
And thus
Go + x00 ΣΣ Vf(zz))) 2 (1+
R-1K-1
TA R
LA
+
LAo²
log 1
+
(IAr) )
logs
MKR
KR
A
KR
MKR
Kà R3
5
r=0 0=
2(u-1) 30-2
+ (1orllaadd -d))
sa-2 )
20
LA log
MKR
K R
(D.41)
D.2 PRELIMINARIES
We start with theoretical properties of weakly convex function and Moreau envelop, which are peatedly used in our proof.
1 || 21lir for some H tzz Ala and
Lemma D.4. Let 2 E Rd and y u(2) arg min f(x)
27
L/x2 2 27/>. Then
(x) = (f)=)\(()) H(2 15--9 y)
(D.42)
7
(m)-min//() If further assume 1 (=) - min B < 24, 0 nsns T.'
then 2, y E Ro and
1
|VVf())) --1 S
x | H (=)]l
(D.43)
[H(2 -) v) -nVf(2))lm= S >1 Vf
(D.44)
( S 2 -1 (2) min))mn-ff- f.).
(D.45)
7
Proof. Since y is the minimizer,
H(y 2)
0 Vy [(v) 27
y1y - =11?/ Vz(())
(D.46)
7
and note that
v V
(z) (x) = v. [((((2)
1
(1x(2) - =1[2
H(2 - v)
(D.47)
2
If (T((() (2) - min p. < 24, then (²)=) - (2) and
(v) < 5M (v) < f(y) S 1M < (z)
(D.48)
which implies y, z E Zg-
By mean value theorem, there exists symmetric matrix - ~ H = Lld, such that
()(=) - V((r) H5 v) -) -
(D.49)
36

---

Published as a conference paper at ICLR 2025
Hence,
- - HH - I
x || V (z)lla 1.
(D.50)
|V/[()]|==-1 (1+ )
27L
v / (=)]
(D.51)
X
Also,
H( - - = (4 7 (1 AVVf())
=:
(D.52)
By noticing that
Ia AH = 77 n - 1/2 Ia.
(D.53)
have [H(2 - y) - -) <
Last,
min S (w) S 1(0)= (-)
-
1
= (=) - 1I (>)
(D.54)
27
This completes the proof.
Lemma D.5. xf S2, then
(x y. ) - vf(i)l1 S 2T| -
(D.55)
Proof. By mean value theorem, there exists a symmetric matrix -TLa 1 H 1 Lla. such that
- (xx y).
(D.56)
Therefore,
(o - - + + v (x
(-H + H²
(x y)
( 72
(D.57)
1|[1 - y
L
$ 2T y11².
X L, then for z E No it holds that [(=) Sa ( f..
Lemma D.6. 1f
Proof. By definition of Moreau envelop, the second inequality is trivial. Let y arg mig f(z) +
L || - 2|12. Note that x - +f(()= +
2 || =112 is 2L-smooth. Then we have
2
L - I1y =|12 + T.ly =112 ==1/(==) + flly =|12.
f(=) S (1)) +
(D.58)
Furthermore, by Lemma D.4
2 Ily - =||2
|V][( < s(y) - Sn.
(D.59)
2T.
Therefore, f(z) - f. S f1))(2) f. + Llly 2|1² 2(fi/(()) f.))
Next, we show that event E, implics all the iterates remain in certain area.
Lemma D.7. If 110
VKAA V
Ari
then event E, implies that for all g S 1,m [M], have
X
T60X'
2311= < 110 VKA A for all m, n.
2, E Pg . 2,th E Ω. And 1:
A
37

---

Published as a conference paper at ICLR 2025
Proof. Event E, implies that for all j S t,
fz(z,) min fo I 2A, 1|2 -211 S n1 VKA =
A
(D.60)
160A
Hence 2j E Qo || - =zill v
K A and 2j E BR (Ro) C Ω. Also, notice that Fj E 100
conv(ziligj C conv(St)) C Ω and
" zjj E conv 2x Jisj. We have
|aa - 211l < n0 KA aaj -
n1 2 -z,11
x VKAS
A
(D.61)
160A
Therefore by Lemma B.4, o. E B (conv = Ω
The following lemma shows that the second order momentum th does not change too much from (r(() during local training with high probability, which is also repeatedly used in our proof.
(K + +
16p² X2
dMT
26 VK(G,o 0 )o
log dMT
Lemma D.8. Let B max
log
X2
22
8
If p 2 max x3 20 then the following holds
8
P(E,,) 2(E.))2P((E)
(D.62)
4T
Proof. Lett rK + k. By the update rule of local Adam, we have
2 = sht Ur + (1 82)
Σ
B/ 99 9 > 3 Ur:
By2
(D.63)
j=rk
and hence
H = diag(
@ilag(Vv'' v0 + X2) - $2 K/2 diag Vo. er + X2) = 332 H
(D.64)
For the upper bound, for any index E [d]. by Lemma B.2,
E, 1 - of + E3 1.2 S 2 + 3G2
(D.65)
Therefore,
[o]"], S [ur]: + (1 (o) + +3022)
+ (1- 32) j=rK
Σ
lo - E3 107
(D.66)
Define
10Th
[
E5 R.
if event E, holds, otherwise.
(D.67)
0.
Event E, implies [0T]):
( |2 E. [ 18 Further note that [[07Ta| p² des c.
Var, (10))))) E,
[o } \ 3h >
E
[0Th
[ }}{
[o [Z](z)))
(D.68)
AM 1
2E,
| [1
+ SE,
- - [V
[Vf(=))
Lemma
S
20 + 2 G
Let b = BX2/2,V = 2Ko (02 + 4G22). Applying Lemma B.I, we have
Σ
10T < 6 with
j=rk
probability no less than
6²
2exp
2
(D.69)
2V + 2cb/3
4dMT
38

---

Published as a conference paper at ICLR 2025
6
which implies with probability less than
for any m [M],
47
V/t u + ( + 3G + (1 - 32) ur
+ +
82)
(D.70)
and thus
(1 BH,
(D.71)
D.3 PROOF OF CONTRACTION
In this subsection, we aim to show contraction, i.e., ||=;" x² will not get too large during local iterations with high probability. However, since the update of 2t involves the coupling of both first order momentum and second order momentum, it is much harder than showing the contraction of Local SGDM. Our solution below is in two folds.
We begin with showing contraction of the second order momentum in some sense.
Lemma D.9. Let B == max
16Ko
2
16p²
dMT log
,22
VK + 0
log1/2
log" 1/2 dMT
A2
X²
X2
8
1
no VKAGx S 20 then the following holds:
and B2 5 4K"
1f 2 max 2Gx
P(E(2) 2 1(E.1)
(D.72)
4T
Proof. Event Es, implies for all j S t, 2. 2 and for any index E [d].
[1m u/']i
(1 - 32)
ot-j
Lo
2
j=rk
$
(1 B2)
22
[0 - c Bj
j=rK
+
82)
B
j=rk
+
(1 32)
3
11 - [V<
j=rk
<
82) Σ /
10 E, 19 - |
j=rk
+ (1 -32)K- 40 + (1 - K 2G no VKA
X
32)
22
at-j
9
E,
+ +8 + -2
j=rk
(D.73)
Here in the second inequality we apply Lemma B.2 and contraction results implied by E
Define
8 at-j
E
1 - -o
if event E, holds, otherwise.
E
(D.74)
0,
Then we have
E
< 2pp
def
c,
(D.75)
39

---

Published as a conference paper at ICLR 2025
Var, (ar,
s 2
1o
B,
19
1 | || 2
< 2R,
(D.76)
< 4Bg
(0))) J [[(x3))
[
"
+4[VS(a7)))
160 G 40 0
Let = B, = 4Ko (0 + +4 and by Lemma B.I, we have
Σ
|>
< b with
b=rk
probability no less than
b²
8
1 2xxp
21
(D.77)
2V + 2cb/3
4dM2T
8
This implies with probability no less than
4M²T
1
8 K d% 31 32)
(D.78)
Combine this inequality and event Fr,1,
H,
H,
V2, + >21 17 2/7
H.
otth + X2
2/ + X2 v uttt X2 + V + X2)
v 1r X²
(D.79)
1 (1 - B1
(V 1/T
X2 + o0f x2)
3 (1 B1
1
The last inequality due to event E and B2 S
We can conclude that under event E.,
4K"
8 the inequality above holds for any m, [M], which implies
with probability no less than P(E,,2) P(E.))
47
8
4T
Now we are ready to prove contraction of zt
2 pdd K
MT
MT 2 2 2ex
Lemma D.10.
Let A
max
log
8
20
log
02 02p2(a-1) S
If n S
A (1 (1-B)) B1)22)
min
jr P 2 max (30 2G 2G and
60KT'
64L
(1- 12 min ( (1- B1) (1 (1-31)0
VA, 1- B1
(D.80)
4BB 212B,G
4B
then the following holds:
8
P(Ers) 2 P(E,2)
(D.81)
4T
Proof. If mod K == 1, then - = for all m, n and the claim is trivial. Below we assume that mod K # -1. The update rules implies
|| 1 (D.6) || 2/ 1i,,
2n 2/""
23
+ e
+e()) H.
2
+ n? (H -1m)--((0 ( e!hh) (H²)
Cي + e Hr
(D.82)
40

---

Published as a conference paper at ICLR 2025
Note that the first order term is
21 2f 24, (H,") (0) + + (H,)) "(x + +e()) Hr
(2 x (((=")) - vf(x?)))
+ 23 2/ 16 "6 Vf(2²') + +v((aa)
+ (=t" 2 (H!") - cT (H - H.
(D.83)
+ 25 26, (HI) 12)
And for the first term above,
(x7" - =i, V[(x"))) - v)(xT))) = (x) - x (x]")) - vs(x}))
+ (2( z - (x/" x3), (f(xa)) - v((x?))
2 (x n V fxxx²) - vf(x{))
L ||(=T" 25²) (x."" -0m-=f'163 2
X
AL [V) Vf(=?)]
(D.84)
By definition of { and event Er,,,
11/31
2
[I(27" mh -2,)) - -(x," =.))
||(H,")) -1;f))-;[[10 1,,
1 - 31
n1.1
[|((HT]]) (H) 11' + [1(HH)))- - uz) 222)1
2
B1
A0.1.A11
17331
)
2
[[C] 32) H. + 4 | -u, u1'l 2
S
2
1
81
H.
(D.85)
Besides,
@ < 4 (HTT)) eg (H,")-'e"l? 1e211
+4 (H. Ta)o7 (H,) Ta)gr
11
(+)
(mx)
+ 4 g
g:¹
+ ff Vf(="")
+ [[x")(²²"* f=(aa))
(D.86)
1
[2]
<
-| - 1,, + 2n,K . (4).
(D.87)
1
(
||= = ll + 2n (N*).
(D.88)
(+) (D.5)
31
2
[[((ET))) - (H,TT))
-- J'1 ". - [(1,])- -1 - [(-)))-'] uz 11 H.
1- B1
B1
2
[|[(01]]]] -(HTm, ) (H²)) + (H un, 1 Hr
2
1 B1
+ +[[[(H])
-1 (HE (n/") )1 [|:r]]
Ar,1,Ar,
31
[a[(1 B1) 1| + 4((1 B2) (v]]" -.>)
5 2
1 B1
[1 (B2) 2
=8
Billupa 1 H, + B² 1|x - utt 1
1- 1-B1
(D.89)
41

---

Published as a conference paper at ICLR 2025
2 H, + (11) La)oot - 96
2
(*+) 2
11-1
S 2 - 111
9 HH. + [(1 - 32) 1lo7 9.¹h 112 112 =]
S 2(1 22) [B9] 18
!- + 2B32 (100 g.dh - - + V ff(z²) IV/C) }
(D.90)
Here we repeatedly apply [H; - Tall I (1 - B2) and || [(,"") - (H;)) (1))))
(1 - B1 by event Er Plug in (D.82),
(D.83)
5 9t o Vf(="") + (D.84)
|1-411 - - 1 |:-
2f =f'1.2.
21
2
m
2
2n (x =²,, Vf(2+)) f
(o.0)
(D.84) +
29)
L
|1(21" - -2-²) - (x," x; || h + À
[Vʃ(a²) - V(
1
4L
(D.81)
27
(2 + ( + n7² 1
L
1|= - -2() - -xx7" - xf})| H. + A
< 11 - 2f H. + (***) x) + 2n)
-
x
TL
1
(D.87)
+ 21
||
= =,112 Hr
+
2nk (x) + 21/K (**))
1nK
(D.86)
+
4n/
(+)
+ (**) 1000
oe \><),)) + V 1| + [V ((
1
27L
<(1 +
|1 2 2 (***)+
Â || - ) - (.. - 1
2K
407
+ (/7
+
|| [x) ) イイ
4n² 11 - - V
(3)
+ +80 K ((*) + (**))
<1+ + 2K || 11 2m (,. - x; V v((a))) + -IVS(r))- -
1
(2:)
- 2n m - ,,.
3m - 96 -f(''') + +V(())) + 817² (1)
(D.85) 4nL
( 1133
(1- 11 )
2
[[[ 32)B11 ||4 1| + 4/lu6" u4 11
À
(D.80) + 64n2K K
(Bi(1- B2)
(D.90)
B |1 l2 + B² [[uu:" - u u
+ 167/² K(1
16 - 32)² 12
(1- B1
$ +1+ + 2K
|||271 -2/11 + (tt) + 807 (#)
- 2n( ( m
24
-2,1
m
96
Eg 197T - 9/1
2n
21 26 , Ee(g:" 9h - - -V(xx²) + - -V
m n
331 - (22)
+ 24n
uf'l H + 65nj K
Bil uu
1 + 16 K ((1 12,
1 - 31
(##1)
S (1+ + 1 >= - =ē 112,
+ (13) + 817 . (t) - 2n =z m
21 96
96
mm
93
Lemma B.2 8y72 K
2 123c
+ (ftt)
+
2a--1) 1)
(D.91)
42

---

Published as a conference paper at ICLR 2025
nL
In the second to last inequality we apply 8K(1 - B2) - (1 -1--- B,)² and notice that by definition of {u²"). ).
X S (1 -B12.. Also
u = = -1-811 Σ
95 - ur.
(D.92)
jmrk
which implies
| T | S (1 -1--11 B1) Σ
81 119
H. + 8
||u,
12
(D.93)
H
j=rk
|/u]" - u.il S (1-3)) Σ 100 93 Hr
j=rk
t 2 (1) Σ
8/-1
1107 -9
-V(GT)
H. .]
j=rk
(D.94)
And thus
t
Σ 1lu"- - u/l1 Hr
22
Σ
03 - -V H.
H, +
j=rk
j=rk
(D.95)
Unroll the recursive bound (D.91) and note that (1 +
)
1 k 33
K
||a| 244 1l.r. S
Σ j=rk
2m(1 +
1 )
m
9, 96 - 93
2
martingale
(1 + K
ym- [-2n { - - "
(V[('))) -V
j=rK
+ +4
Σ
17" 12199 - 93 (xxx)) + V( + 72T7
Σ
| Th 11
j=rk
j=rk
+ +195n/ K
(1 B22 B²
|/ H.
2
(1-
B1 Σ
m H.
24
|20
2a
(1 /3133
1 B1
p²aa-11 1)
j=rk
(D.95)
1
+ 2n
< 1+ Σ
(1+ 2 y
-2n (17 V((z)) v((la))
V V {(
K
L
j=rk
-1-B2)² B2 B3
+ 144
Σ
1 1100
Th
93
V + V(x})) + 1957/
||u H
(1 - }3)
j=rK
1
322
2
24 K2
1
2a
+ +487²K K
B
1 H
2n (a 1)
1 B1
j=rk
(D.96)
K
Note that by definition, u, = =(1 (1-
3/
BmoK- + BK ur-1- By Schohrr inequal-
f=1
ity.
K
|/ 11 S 1 || 111 +
|| F K-k
(D.97)
3=1
43

---

Published as a conference paper at ICLR 2025
Therefore, event E implies
(1-
1-3
(1- (1-3))0AA
|
1| 212 - B2)
(D.98)
1 1- 3
By Lemma D.5, and | [V[(,))]| G.
Lemma D.5
n 0²0²² KA
||=-1
#[+1
11
!
+
G1rTK K
X²
288n2 2
|107 {( 119 [
A
j=rk
- 92
B
+ +967 K
Σ
110 - +
1- $1
X
j=rk
(D.98)
KA
24n 2 K2
12
2a
+
10A
A
p2(a-1)
(D.99)
1202
Lemma B.2
22 1² Ko²
1 + knl
KA
+
X²
2n0,7²
Σ
|100]
-(x3))1--111l33 -
max
M
j=rk
8: mastingale
(1 1 - Bg
B3 G2 +
17 O² KA
24
2 1. (a 1)
+ +
1 31
101
Define
21((1 +
/r
(
(3) - 22
93
E,
m 19
9,1)
if event E, holds, otherwise.
K
0,
(D.100)
1
V
f((a - - {[
if event Ej holds, otherwise.
0m
(D.101)
0,
1²00 2X
2 20007 +
Then (D.99) implies ||
113, <
KA+
Sj m.n
05. Note that
X
M
j=rk
j=rk K
by Lemma B.2,
0 < 4p²d dl
def
(D.102)
Vor,(07)) < 1110, v {(()))|
(D.103)
o2KA Let b 212 = O*K.
K. Then by Lemma B.
Σ
0mh < b with probability no less than
j=rk
82
2 5
2exp
(D.104)
2V + 2cb/3
SMT
8
This implies with probability no less than
8T'
o²KA
Σ OT
Vm E [M].
(D.105)
212
j=rK
Also note that
2412 d
1 m.
|
< 67
170T X
VKA. 4pvd=
VKA del
(D.106)
44

---

Published as a conference paper at ICLR 2025
Var,(5, 1 6n
na A
KA
2
-20²
"2n/"0² or
KA.
(D.107)
n/'0² 4X
721/"0 0t X²
Let b
K KA,V
K2 A. Then by Lemma B.1,
Σ
S b with probability no
J=rk
less than
6²
6
1
exx
2
(D.108)
2V + 2eb/3
8M22
This implies with probability no less than 1 - 8T
0700²
Σ
K A, Vm, [M].
(D.109)
42
j=rk
We now turn to deal with
Σ
11,""11.
j=rk
t
Σ
19
11
v
j=rk
j=rk
2
||0
-V +2 Σ
V((x7)) |1 + 2KG2
j=rk
jork
Lemma B.2
I
2
Σ
-
100T0
+ 2K(0² + G²).
j=rk
(D.110)
Then
Σ
1195 2 < 2
8THh + +2K(o² + +²2) under event E, Therefore, by (D.105),
j=rk
j=rk
0² KA
(1-3/)
+ +K +G² S 212 B2)
(D.111)
2
jerk
In conclusion, combining (D.105), (D.109), (D.111), we have
KA
1
(1 -1- 81)
2 TP((P 8
P
P { F., and |
Σ
l0
13
for all m,
X
212 82)
4T
j=rk
(D.112)
D.4 PROOF OF DESCENT LEMMA
After laying all the groundwork above, we are now in the position of showing the main descent lemma.
Lemma D.11. Assume that p 2 mmx max(33 2G and
3
T
npvd
T S
11 X
log
LA
log
log
VA,
S
AM
8
8
(1 81
(
12
B1)
p²d
(D.113)
mL
3
LA
0²02
A
17 20
20
A
8
KA
S
20
X
T
XyM
T
2(a-11 1)
T
and
(1
11-33)
(1-
<
<
(D.114)
47
4)
X
26
45

---

Published as a conference paper at ICLR 2025
Then the following holds:
8
P(B(+1) 2 P(Er,) 47
(D.115)
1 | - yll is (- T
Proof. For any E R. since v² - and H, 2 XTa + f(v) +
x)
2n
convex with respect to || ||.,. Note that under event E,, 2e E Sg. Let y arg min f(y)+ + 27 1
y
Bllir, and by Lemma D.4, y/s E Go. Then
f(v)) 1 1/4- 21 12, s f( || 112411-2el1 -1441-2e111 zellir.
1 M1 vel.2 (D.116)
2 x
27
24
Recall that the definition of } implies
(H," u4
(1.1(
2(+1 2t
31 1-31
11131
(D.117)
[H
1H -1
(HHT)) g:
$1
-n( 1
(0.T c.r)
81 (Ia (H. )-
Here et"
1 31
(1 Bi B.)npvd
DY 160A
Also, since || - Ezll v
(1 B1)A
1
=
Ro, we have Eot1 E S and
f(z(+1) - f(v)) S fz)) + (V.(zz)) Z(41 - 2x) +
| - -zel3 ff(1)
2
L
(V) 3t+1 - y1) + タタ
|
y/
1|
マ |lEze+1 - 11
(D.118)
I
(V)()) E ve)
コog velli,
+
| Eellis.
21
Combine this with (D.116),
+
1 L
77
7
3/1 11
7
7
1
11,,
+
7
---1 - Zel
2
2
2
Hr(Z+41 -zt)
2+11 Ut, Vf(2,))
17
Em (H.") + ][ 1/t Vf(z.) Hm, (H (000 + +
( - n11 V Vz(z,) H, (11 + =e7")
(D.119)
Vf(E)) - H. (( 10."" + e, !| H
21 - nH, - U1 Vf(z:) - H,K, [ (Hrm)-1
9 nm + c. c(ri))
+ +41lIV((=:) E.m (1 ]]] |- 4m R
V f ((= /"¹ H=
4n E.,. (H, Ia)g.
4n |m -ep0 2
46

---

Published as a conference paper at ICLR 2025
By Lemma D.4, we have
2 V -
- Hm w.
,111,,((33)) - V/(E)) - Em [v]
21 11 (3))) Em sf
H
Mn E. (L) H, H.Th.) )
(D.44) //( + 88
2
5 16
Bm ( + 87 Bm (H.(") La)g,"
11.-
+ (3x n nH, Em [Vf(e("
9T-1 -
(D.120)
Also,
(2 ((=nH()) - Ve, (H," & 7 [V H, 4 16
(D.121)
Further noticing that < 2 and by AM-GM incquality, we conclude that 4
LHS of (D.119)
2
s [V 2 H- -,:11//(()) - E.. [[,""\ + 97 Em (H,( Ia)g.")
H,--
An Em ( [VV((>)))>))))))))))))<>))) ,7.1 || H
+ 5- (H, eTr] H+
+ +(2+ - nH, (V)(z) vr, Em [f(x)") 9
zt
(D.122)
It mod K 11 then +( = r(t) = + and event E,, implics
1r 3 1+ (1 (1-33)B 11 7 47'
(D.123)
f (2(+1) S f(vi) +
| Va 112...
2n
(D.124)
1 n/47
$ f(y)) +
|| velles.
2y
On the other hand, if mod K * -1, then r(t + (1 r(t)) = r.
He(t-1) (Z(+1) S f(y)) + 27
|z441 Ve vell?r..
(D.125)
47

---

Published as a conference paper at ICLR 2025
Hence the following always holds:
fn ( (2++1) S f (z+)
2y1
1
1|
ye vell?r,
+
1 117447
|| - ye yelliA
24
24
(D.122)
77
S
HH (2t)
11 - 1// 1/11221
87(11 + --
1
(1 + m/47)
[() 1| H. + 9// - Em (1 ]]| N., +9 (H! l2)g7
+
+
1 - -r/A
Benl (V[(())))) - म. 2
(1
1/44/))
A11
+ 5- || (
H
H.
+
767 + y - a/1)
(1
1//4//)
2 -HHH -nH,+' yı, Em V (zx"r -
+
717 + -
(D.42)
(2+) - ( H. + 5n/
S
|| [ - - + 67) Em (H. -eer) mm
A7
H.
+ 107 [((+)) - E. V
2
100 10mm (H,, Ia)gr""
1+ 1/4
(ze - 1 - y1, Em Ví(x)')) - -
+ フ +
(D.126)
Sum over f and we get
f7 B (3++1)
S (x++)
(200
17 Σ
5n7²
Em (V( 13 + 6n Σ
|mmm (11g")
111
#3 by
5=0
10n
| fz,) - E. (( || + 10n Σ Em. [ - -41),²"
+
x 1=
1170)
1 + 7
Σ 1=
(3)- nH n (()
f)(3)) Uo Fm E. V( - 95m
711 + +
(D.127)
By AM-GM inequality and notice that Fe; 2e E Ω
-
< V - E., [
(D.128)
< -2.
Em [f
Under event Eg,s.
Fm ( (H(")) 12)
< (1 - 3² Rm
|19T 1| |H-1
(D.129)
H.
[31(1 - -B2)
|| (HIT)
1 1| <4
B2mm
|| 112
(D.130)
1 B1
By the definition of ui- we have
1-1
Em
1u
m
1 n1
2
< S1 31) Σg 81 1 Em [10350 11,1
1=0
(D.131)
(1 - B1)
(31/v
(2)
- Em
2 |193
B K/2
H (3)
1=0
48

---

Published as a conference paper at ICLR 2025
Plug these inequalities above in (D.127),
H 1) (2(+1) - ff
7
5n²
Bm [V(a))) - 13'
+
8
(5)
Ay
(D.128)
20v
+
[2a112] - - + (VV}(z)))
Em [f
A
1=0
(D.11))
1)
(1
- B1)(v 32 - 31)
48,3
(1- 32) 1
Fm
1103"
2
H -6)
(+).
(D.132)
By AM-GM inequality and Lemma D.4,
Em
<
41
|1oT" v f(x)") (V/G))
f - Bf
16(rL)²
Bm Emllsr VJ [( - L Em.ll 11 - 1e + L - -x(1]]
1 1/
H1 (3
X2
(D.133)
Therefore, we achieve that
1n (artt1) (E(+1) S S.H0 (20)
V (15))) Hmj
+
5n2²
Bm ((xx)) -
x7
j=U
407
+
[L-||z] - 2,1 + (V) - Em [f
X
0=0
160m(1
32) - B1)(2- - 31)
=,11]] + (+).
(D.134)
By (D.160), (D.164) in Lemma D.12, under event E1,3,
1| - 1,13- <
31
64Tp (1V)(e))) M +
1,2
x2 A
1 - 31
+ A2
36n2 2
(1 - B1)
Σ Bi-i-1
j-1
1122200
KA+ + Em - vf(=;))1
X2
i=r(j)K
(D.135)
Hence
12 - 11 <
B1
64m²
Σ
+ x2 A
La
1 B1
1=
1=0
(D.136)
+
36r/²
t-1
11² 1222
KA + Em
1007 -
X2
X²
j=0
Additionally by Lemma 1.
1- t-1
64n² t
A,
A3
Σ (1,))
2
1 31 1=0
1=0
367²
t-1
T1222202
+ X2
(1- B1)
Σ
KA+ Em, 19,
V((=T))) )12
X2
j=0
(D.137)
49

---

Published as a conference paper at ICLR 2025
n
(1
11-B8
-1)²
Therefore, by noticing that A, 2 0 and
X
16
Σ |2 - 2zl1² j=0
6 I- $1
2
1/311
64
Σ
[f((,))]
+
36
Σ
1-1
q
12202
KA + Em 1 - vf(23))11
X
X2
j=0
1=0
(D.138)
For the third term of RHS of (D.130),
5n)²
10n²
Σ E -
9f =
Σ
Em 9j
E,19,
E,
E Vf(aa') B, 10
Ay
xy
Lemma B.2 10m²
2 12:
[|Em
Lo
1و 111
Xy
22
j=0
10n7
|l
E,19
E,
199 B3 19,5 111
j=0
martingale
10r)²T
2a 2
o²
Ba
xy
2a-1)
M
(D.139)
For the (+) term of RHS of (D.130).
1 1+10 4/47
2 mLl Vf(z,) us E. (f(x") 9;71)
711 1 7 -/A)
+ // //4
22 nH (1) (z,z yリ B, f(a"") - I6, ا
7(1 + > A/
1=0
1 + // /
(z) h リリ EE, FF 19" 9
7(17 + 7 T/2)
(D.140)
martingale
AM-GM 27
|2 13
H (T) v1) - + 30
+ 2
7 1=1
120
(a
(D.44)
2
60t/T |2o 13
1/
Σ
[V
||2
60
(a- 1)
1=0
Here we remark that ② is a martingale because H H.() only depends on stochastic gradients drawn strictly before round r(j) and thus independent of 93" which is drawn during round r(j).
50

---

Published as a conference paper at ICLR 2025
Plug (D.138),(D.139), (D.140) in (D.130),
10nOT
2
o²
S f. (E++1)
Vf(y;) FF
+ @
2a
+
12 j=0
by
(2(a-1)
M
407 +
Tn8L'0² A2
+ 17 L22
KA + Em 19," - Vf(27))1
KA
X
(A(1 31))²
X2
==
160
32)
Σ
Vf(2f))] 121'002 KA
Emll99
1(1
B1)(v/22 - -1)
X²
60nI
|2
12
22
+ @
A 22(a-1)
1T
| 12(a-1)
2a
+ x²
S (20) 12 1=0
Vf | +0 00
2a
by
M
160n [18( 118("I.11 )2 + (1- 32)
Σ
Bm 119 - [({(5)))1
(1
- B1)(vB2 - 31) 1=0
160nT
1
18( 18(21181 12 + (1-1111)) 32)
1²"
KΛ
4
(1- 31)(v32 31)
X2
60nT ||20|]
12
+
20
+ 2
p2(a-1)
10n T
|2
2n
0²)
< (z00 12
V [1;))
+ +
2a
H+0)
xy
(2(a-11
M
1=0
160n
20 2
t
+
Em
|19] m
vf(x;))11 E, 110 v((o5))) |1
X (1 (1)(1
- (31)
j=0
@ martingale
50nJ
122202
64
60nl 120
KA+
A
X2
(1 (1- (1-B:)(V3, 31)
(2(a-1)
$ f/ (zo)
17
[f(y)) 1=1 +
10n202
+
60nT
T222
KA+
60n7
|20 20
12 1=0
MyM
X2
A
22aa-1)
+ 1 +
2
(D.141)
where in the third inequality, we apply (1- B-) s 7L
X
For D define
10n² 2
[1]
Em
19,
T - E, E,(0, - E,
Em Bm
E,
if event E, holds,
0,
Xy
0,
otherwise.
(D.142)
Then event F, implies
Σ 02 1=0
and notice that
10n² 2
40n² p²d def X7
10,1 <
4p²d
c,
(D.143)
X7
10n²)
2
2
Lemma B.3 S
1120² 2
(ar,(0,) 5
E2
E 0g
E,
1600
(D.144)
Xyy
XyM
51

---

Published as a conference paper at ICLR 2025
1 1100² 2
Let 6 A/4, = 1600T
Then by Lemma B.I,
Σ
0,1 S with probability no less
XyM
==
than
B
1 1 2exp
2
(D.145)
2V + 2cb/3
127
For o define
160g
20( )2
Em 96
if event E, holds,
A (1- - 31)
0,
otherwise. (D.146)
Note that
160n
20 20(%
.4p daf
leyl -
(D.147)
A (1 Bi)(
32 - -1)
1601
20 )2
E,E. 9
Var,(E)) S
7 (1- 31)( 32 -11)
M
(D.148)
1607
20 20(%) 22
04
A (1- - 31)( 32 (1)
M
160n
20( (0
To
Let b A/4.
Then by Lemma B.1, Σ & S b with
(1 31) F2 - 31)
M
j=0
probability no less than
6²
8
1- 2exp
(<
2V + 2eb/3
21
12T
(D.149)
For @, define
1 1 1/47
/ n/1 n) f(zz (
- fy 1m [ g;
if event Ey holds,
(1 1 -
0,
otherwise. (D.150)
Then event E, implies
Sj and notice that by Lemma D.4,
1=0
| - 93) - - H
7|, - nH Vf(z,) - - 3111
A HrG) (z,) 111
2/11 fr
(D.151)
5
274
Therefore,
27
2
2Ad des
K9 S
2pVd = =Anp1
(D.152)
?
X
7d
2m
0² I
4ni²0² XM
Var,(S)) <
[V
(D.153)
(5)
M
Let b = A/4, V = 100no² 2
Then by Lemma B.I.
XM
6²
5
P
41 > b and
Var, (G) V
< 2 exx
<
(D.154)
2V + 2bb/3
11TT*
1=
==0
52

---

Published as a conference paper at ICLR 2025
Note that by Lemma D.4 and event Es,
[Vf(2))) 1och _ (5 (( min f?) -
4A
(D.155)
7
7
01 1 AM ==
4nf0
24A
40
Var,(S)) S
mig S
+
S.V.
(D.156)
AM
1=0
8
Therefore, combining @, 2 3, with probability no less than P(E{,) - 3
event E holds
12T
and
Si
These implies
4
==0
==0
1=
17 (0(+))((((+)))
min
7
7
+
10
T
60n/T'
122
K
60nT
2 22
12
XyM
X2
22
j=0
H.U (1)))
2A
12
(D.157)
In the last incquality, we apply
00
A
60m T
L22
A
60nT
22 20
A
T
KA
(D.158)
XyM
12
12
12
12
Therefore, we can conclude that P(E(+1) 2 P(E,,)
4T
31
Lemma D.12. Define A = Σ
[T - 1 where atj == 1/-5-1(t -j + 1 31
). Under
3=0
the same conditions in Lemma D.11, event E,, implies
A < (1- (1 11)))
64n/
A-1+ +
2
1- B1
(D.159)
3617² 2
t-1
172 L22
(1 - B1) Σ
8 at-j-1
K + Em 1,, - -VS
+
X2
X2
j=rK
Proof. By the update rule, it always holds that
31
1 Fz 12 =
31-1
(D.160)
- Br
By AM-GM inequality and event Er,
[ 1- n72 Em ( -1 1/th 11|2
2n
< 2n1 2 Em (H(L1) 1T-1112 1|
Em 11601111000000000 T.-1l?
X2
(D.161)
2n²
Em H uT-1l || < 417
+
Em 10ml 12-1112
53

---

Published as a conference paper at ICLR 2025
Event E implies 2j , 2z." E (Q)) for all j S t and thus
L-1
Em |0--1 U--1/ 2 < (1 (1)
Σ
81-5-1E
Em ||19, 331l²1
j=rk
$ 21 - 81) Σ
81-5-LE
Em ||07 V + -E
Em B. - [[
j=rk
1-1
2 - 81) Σ
81
1--5111
Em
- 1,11 + -
- -
j=rk
1-1
L222 X2
< - 81) Σ
$1
8
KA + - -
j=rK
(D.162)
1-1
t-1
| 2 H S
(1- Σ
+
(1
31)
Σ
3
-V
- [
1=0
11=2
/=
11,2
(-1 Σ
L-1
+
1-1
8
Em Vf(x') (T,,,
(1 B1)
Σ
3 - Em -
5=
HF²
j=0
< [V+())) : +
(1-31)
t-1
3/-5-11,3
xz 12
X2
j=0
(1-31) 31)
1-1
0
ot-j-1
|Em 9
vf(2f))11 + -
X²
j=0
2L
(1- 31)
< <2/ 1|
1 1/ +
1 Σ
|| x 113
X2
X2
j=0
(1- 31) 1-1
81
-t-j-1
|Imm 99 -
+ BB.
X2
j=0
2L
2 1-1
/2/ 2
+
|| - 12
+
X2
x
(1- 31)
Σ
8
ot-j-1
Emm
X
0=0
(D.163)
54

---

Published as a conference paper at ICLR 2025
31 ). (t - j 1-31"
Here azj
For j S 2, we have ons S (1 -1)ac-1.5
Since
A Σ an 1 - -i+1 11=, we conclude that
L2
4n2
122220
E - Tz-1 64n2
|V m +
Ac-1
+
B1)
Σ
8 3
KA+ + 101 V
x2
X
X
j=rk
32n)² 31) 1-1
Σ
11
8
[E -
V/
Em
Vf(2)) -
1=0
I
S 6412
|Vf
H.
Ac-1
x2
3611²
1-1
L220
(1 B1) Σ
8 8-1-1
KA + Em
x2
22
j=rK
(D.164)
and
A, S. -
Tt 1/-1 T4
(D.165)
1
B1
This completes the proof.
D.5 FURTHER DISCUSSION
Compared to other results under centralized weakly convex setting. Theorem D.2 can reduce in (D.27) (Petrov, 1992)), and v VMK
to Minibatch Adam (by substituting M, with 1 and a with
the convergence guarantee is
Ne-1)
LA
AAo2
LA
3a
H f (
+
(D.166)
R
7MKR"
(MK)
Therefore, in centralized setting with iteration number Rt and batch size 1, our guarantee for squared norm gradient of Moreau envelope
LA R
AAo²
LAga
+
+
(D.167)
RR
R
LA
The last term is induced by the bias of clipped gradient. For simplicity, let R 2 term can be dominated by the first term. Then we obtain
so that the last
o²
LA R
XAo²
(D.168)
7MKR
In the previous literature of weakly convex function (Davis & Drusvyatskiy, 2019; Alacaoglu al., 2020; Mai & Johansson, 2021), 1), f is typically non-smooth and stochastic gradient is assumed to have bounded second order moment. This is weaker than the smoothness assumption but stronger than that of noise with bounded moment. There are a few existing results for smooth objective (Davis Drusvyatskiy, 2019; Mai Johansson, 2020; Deng & Gao, 2021), but they set r T.. Overall, our result is the first convergence guarantee for smooth weakly convex function with < T. and noise.
Dependence 82. The default setting of 33 in the Adam optimizer of PyTorch is 0.999, which a constant close to 1. Adam with small B2 has been shown to diverge in some examples (Reddi al., 2019). However, if it is too close to 1, e.g., B2 > OTT-1), then the denominator would
55

---

Published as a conference paper at ICLR 2025
be too stagnant to provide adaptivity. Therefore, to derive proper range for 32 is crucial in the theoretical analysis of Adam.
On the other hand, 32 is notoriously difficult to handle under centralized setting. In finite sum case, Zou et al. (2019) assumes $2 2 1 O( Shi et al. (2020) suggests that B2 2 O(n suffices, where is sample size. Zhang et al. (2022b) claims Adam can converge to the neighborhood of stationary points with constant radius if 32 2
((n Further, Wang et al. (2022) shows Adam can converge to stationary points if 32 is sufficiently close to 1, but the explicit bound is missing. In streaming data case, Défossez et al. (2020) shows 32 can be a constant but relies on the bounded gradient assumption. (Li et al., 2024c) suggests 32 2 1 - ÖT
As for distributed setting, works discussing the range of A3 are much fewer. Our theory requires 32 2 1 - For distributed Adam, Karimireddy et (2020a); Zhao et al. (2022) fixed the denominator during local iterations and thus did not discuss the range of [3.. To the best of our knowledge, our result is the first one show the ÓR à) dependence with respect R. Nevertheless, it is an interesting question to improve the dependence on K. Since K is usually constant in practice, our results suggest B2 2 Ö(R b) in essence. Still, believe that the dependence on K has room for improvement. We leave this for future work.
Dependence on A. in the denominator of Adam is aimed to avoid numerical instability, and usually small constant in practice. Note HI, diag( VV, + X2) and e, is the EMA of squared past gradients. Informally, v, vanishes as r grows and thus H, would gradually reduce to Ala. In the worst case, H, be bounded by constant. In conclusion, the LHS in (4.9) is roughly the averaged squared gradient norm if is not too small. It is worth noting that À can be arbitrarily small even 0 in (Défossez al., 2020; Wang al., 2022; 2024). However, their results all depend on poly(d). It is still an interesting question to get dimension-fres result with small X.
Dependence on B1. The default setting of 31 in PyTorch is 0.9, constant away from 0 and 1. In the centralized setting, Li et al. (2024c) requires 81 1 - O converge, which is too large. Défossez et al. (2020) shows O ((1 )) which is the state of the art result to the best of our knowledge. However, it relies on the bounded gradient assumption. Regarding the dependence on 31, our convergence rate in Theorem D. suggests O ((1 31) -)) Although it also supports any constant choice 31. we leave the exploration of better dependence for future work.
E FAILURE OF STANDARD SGD WITH HEAVY- TAILED NOISE
The convergence of standard SGD in high probability is widely studied. If we assume the noises light-tailed, egg., sub-exponential, sub-gaussian, then SGD can get high probability bound depending on log g. However, if only finite variance is assumed, Sadiev et al. (2023) has shown that standard
SGD fails to get high probability bound having logarithmic dependence on In fact, this claim is still valid when the stochastic noises only have finite ath-moment, as shown Theorem E. below. Therefore, gradient clipping is necessary to get the log bound.
Theorem E.1. For any 0, 8 (0. 1), and SGD with the iteration number T and learning rate there exists an I ID-problem satisfying Assumption 1, 2, 3, 4, with Ω = R. and = Jt, such that, if 0 1) L/L, then
( VT))
P(f(xr) - f 20
(E.1)
81/0
Proof. We follow the construction of the counter example in Sadiev et al. (2023). To prove the above theorem, consider simple ID-problem f(x) Lx2 /2. It is easy to that the considered problem is L-strongly convex, L-smooth, and has optimum at x, = 0. We construct the noise in an adversarial way with respect to the parameters of the SGD. Concretely, the noise depends on the
56

---

Published as a conference paper at ICLR 2025
number of iterates learning rate 77, target precision the starting point zo, and the moment bound a such that
(F(((()) Lx, oc2+
(E.2)
where
0.
ift T (1 g > V
2E
I
A,, with probability 2,4a
&
(E.3)
1
0,
with probability 1 A'
otherwise
A,
with probability
2.4a²
2
L .1
where max
}
We note that E
[Er] and EVVF(m): Vf(x)) Further-
170
more.
1
B| S
A
+
Aa
(E.4)
24a
2Aa
which implies that Assumption 3 holds. We are interested in the situation when
P ff 5 8
(E.5)
2E
for 8 E (0, 1). We first prove that this implies (1 (1-nL)²(uu) contradiction and assume that
V L
To do that we proceed by
2s
(1 - (1-n |200| > V T,
(E.6)
By construction, this implics that & = 0, V. E (0.....2 .T 1}. This, in turn, implies that xт
(1 - nL) rv. and further, by (E.6) that
2
(f((x)) - f. = =P
FT 2
1.
22 L
Thus, the contradiction shows that (1 (TT |zu| -
Using (E.3), we obtain
L
f(x1) 1(1 -nL)² vo + notr-11
(E.7)
Furthermore,
2
((((TT) - f.2 P
(1 - -n xo + n 2
L
125
Ino 2 11
(1 (
(E.8)
2s L
P
InoET
2 2
2
25
1
TP
15T-1/2
170
Now 2 25 E2
then 1. Therefore,
110
2 T
1 = P
|r-1l 2
-
(E.9)
57

---

Published as a conference paper at ICLR 2025
25 2
2 25
L
28
yielding contradiction, which implies that and we have
2 i.,.e 17 S 2
In this case, A
110
Lo
110
2 2
82 (f((T) - f. 2...265
E) 2P
15T-11 2
(E.10)
170
Aa
2/
2
L
This implies that I
Combining this inequality with T 2
log
yields
2nL
2e
V log Lxg
T.
T=
Ω
811/ V
(E.11)
2
This concludes the proof.
58


Reviews:
[{"review_id": "ebYxDPZDri", "reviewer": "Reviewer_FvoJ", "summary": "The paper analysed the Local Adam method, which performs local Adam-like updates and intermittent communication. The paper provides a high probability convergence analysis for local Adam with heavy-tail noise, and demonstrated its advantage against mini-batch sgd in some regimes. The analysis also covers the local SGDM method.", "questions": "I did not go into the technical details in the appendices so I cannot attest to the correctness of the statements, but I have some questions/concerns with the followings in the main text:\n\n1. In page 2 line 77 the author claimed that \"The conventional in-expectation rate seems fail to capture some important properties like heavy/light tailed noise distribution.\" Can the author please elaborate on this? It seems to me that the in-expectation convergence is stronger than the high probability convergence presented in this paper since one should be able to convert the in-expectation convergence to high probability convergence using Markov inequality.\n\n2. The paper claim to cover the $(L_0,L_1)$ smoothness case, but I fail to see how is this the case? It seems to me that all the theorems presented in the main paper are based on Assumption 2, which is just the usual smoothness assumption. \n\n3. Regarding Assumption 3: \n    - I was under the impression that most existing works make their heavy-tail noise assumption in the form: $\\mathbb{E}\\lVert \\nabla F(x,\\xi)-\\nabla f(x)\\rVert^\\alpha\\leq \\sigma^\\alpha$, i.e. a upper bound on the norm of the deviation. Here it seems to be an entry-wise upper bound. Can the author please elaborate more on how does the result based on the entry-wise upper bound translate to the usual result based on the usual norm upper bound? \n    - Remark 1: it seems a bit curious that the authors does not deal with the case $1<\\alpha \\leq 2$ which is what most existing works deal with, but instead consider the case with $\\alpha \\geq 4$? The authors claim that it's easy to extend the analysis to the case where $\\alpha < 4$, then why not just include it here which will certainly make the results more easily comparable to the existing results?\n    - Regarding the $\\lVert \\mathbf{\\sigma}\\rVert_{2\\alpha}d^{\\frac{1}{2}-\\frac{1}{2\\alpha}}= O(\\sigma)$ assumption in the theorems. This seems to relate to the entry-wise noise bound. Can the authors elaborate on this and its consequences in the convergence rate (e.g. whether or not it's introducing additional dimension dependence compared to other works)?\n\n4. For Theorem 3, can the author please elaborate more on the convergence criteria $\\lVert \\cdot\\rVert^2_{H_r^{-1}}$. I understand that some existing works used convergence criteria similar to this one, but it nonetheless seems a bit unnatural to me. In particular, since $H_r$ is defined with respect to $v_r$ and $\\lambda$, algorithm iterates and hyperparameter, it seems that the convergence is algorithm/parameter-dependent. Wouldn't we be able to claim any convergence rate if we set $\\lambda$ large enough? Could the authors please explain the choice of $\\lambda$ as well?\n\nI would be happy to raise my score if the authors can provide more clarities regarding these questions/concerns.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper is a technical tour de force and the first one to analyse local methods with adaptive updates without some artificial assumption. The algorithm also incorporates the clipping mechanism to deal with the heavy-tailed noise. I think overall this is a pretty impressive display of technical achievement.", "weaknesses": "see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YW1JrRdzou", "reviewer": "Reviewer_jJw9", "summary": "The paper studies distributed adaptive algorithms with local updates in the homogeneous data regime, aiming to establish theoretical guarantees proving the benefits of local iterations in reducing communication complexity. Specifically, the authors analyze a distributed variant of Adam - Local Adam with gradient clipping, which also reduces to Local SGD with momentum (Local SGDM). They establish that both Local SGDM and Local Adam can outperform their minibatch SGDM / minibatch Adam in convex / weakly convex settings, respectively.", "questions": "- What are the advantages of the proposed algorithms over non-adaptive methods in terms of theoretical guarantees?\n\n- The paper claims that \"there is no end-to-end convergence guarantee for distributed adaptive algorithms with local iterations.\" However, this seems inaccurate. For instance, [3] introduces the Extrapolated SPPM algorithm, which replaces local SGD-type training with the computation of proximal terms, and [4] provides tighter convergence theory for the same algorithm. Both approaches use adaptive strategies based on gradient diversity and Polyak step sizes, and their results hold in heterogeneous data settings.\n\n[3] Li, Hanmin, Kirill Acharya, and Peter Richtarik. \"The Power of Extrapolation in Federated Learning.\" arXiv preprint arXiv:2405.13766 (2024).\n\n[4] Anyszka, Wojciech, Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. \"Tighter Performance Theory of FedExProx.\" arXiv preprint arXiv:2410.15368 (2024).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The work is the first to offer high-probability bounds for distributed optimization algorithms with local steps.\n\n- Some assumptions are relatively weak; for example, smoothness and (strong) convexity are required on a subset rather than the entire space.\n\n- The first theoretical convergence guarantees showing that Local SGDM and Local Adam can outperform their minibatch versions in some regimes (large $M$ and $K$ regime, where $M$ is the number of clients and $K$ is the number of local steps).\n\n- The paper is well-written and easy to follow. The authors clearly introduce the problem and the paper's contributions.\n\n- Despite a few limitations, this work represents an important theoretical contribution to understanding the empirical success of Adam with local steps as observed in prior research.", "weaknesses": "- The paper addresses only the homogeneous data case, where all clients have access to the same data. Client drift from data heterogeneity - one of the main challenges for local training methods - is not explored.\n\n- The noise assumptions are somewhat restrictive (see, e.g., [1]). Specifically, the authors assume a bounded $\\alpha$-moment of the noise with $\\alpha \\geq 4$. In contrast, most works only assume this condition for $\\alpha \\in (1,2]$, and recent high-probability and in-expectation convergence rates have been obtained under the strictly weaker condition $\\alpha \\in (1,2)$ [2].\n\n[1] Khaled, Ahmed, and Peter Richtárik. \"Better theory for SGD in the nonconvex world.\" arXiv preprint arXiv:2002.03329 (2020).\n\n[2] Puchkin, Nikita, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. \"Breaking the heavy-tailed noise barrier in stochastic optimization problems.\" In International Conference on Artificial Intelligence and Statistics, pp. 856-864. PMLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FKhIWo53t9", "reviewer": "Reviewer_ouZP", "summary": "This paper analyzes the convergence rates of Adam/SGDM with local steps, showing that local steps can improve the convergence rates in the homogeneous setting.", "questions": "See the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* This paper analyzes the convergence rates of Local SGDM and Local Adam, showing that their convergence rates are better than Minibatch SGDM and Adam.\n* Overall, the reviewer feels that the result shown in this paper is not very surprising, but it is solid.", "weaknesses": "* In Assumption 3, the authors assume $\\alpha \\geq 4$. The reviewer feels that this assumption is a bit different from the assumption commonly used in the existing literature. For instance, [1] used a similar assumption (see Assumption 1), while they called that the stochastic noise is \"heavy-tailed\" when $\\alpha<2$. Although the authors claimed that it is easy to extend their analysis to the case where $\\alpha>4$ in Remark 1, the reviewer feels that the authors should show the analysis with arbitrary $\\alpha$ if this extension is really easy. \n* In Theorem 1 and 2, the authors omit the dependence of $\\beta_1$ by using $1 - \\beta_1 = \\Omega(1)$. Thus, we can not discuss the effect of $\\beta_1$ on the convergence rate. The reviewer feels that it would be better to show the precise convergence rate, at least in the Appendix.\n* Theorem 1 and 2 used the assumption that $\\| x - x^\\star \\| \\leq O( \\| x_0 - x^\\star\\| )$. Thus, these theorems only hold when the set of feasible solutions is bounded. Similar to these assumptions, Theorem 3 used the assumption that $f(x) - f^\\star$ is bounded.\n\n\n## Reference\n[1] Zhang et. al., Why are Adaptive Methods Good for Attention Models?, in NeurIPS 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kO01NtFtZc", "reviewer": "Reviewer_3h9b", "summary": "The authors consider problems from distributed optimization and federated learning, where communication can be a bottleneck. In this setup, they analyze the celebrated Local SGD method with momentum, clipping, and Adam steps. In this context, they provide new theoretical convergence rates under heavy-tailed distribution assumptions that hold with high probability.", "questions": "(see weaknesses)", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The considered problem is important in modern optimization. Using local steps is one of the possible strategies to mitigate the communication burden. The assumptions and goals of the paper are very challenging. I have not checked the proofs in detail (that is why I choose confidence 2), but the final theorems seem to be reasonable and consistent with those in previous papers. Overall, this paper appears to be a solid and technical mathematical work that extends the known results of Local SGD.", "weaknesses": "At the same time, I want to point to some weaknesses: \n1. The choice of Assumption 3 is unusual. In most previous works, this assumption holds with $1 < \\alpha \\leq 2,$ while the authors choose $\\alpha \\geq 4,$ which is a much stronger assumption. What is the reason for that? The reason should be discussed in the main part.\n2. In many places of the paper (abstract, contributions, ...), there is a claim that Local SGDM outperforms the minibatch counterparts. But this is not true in general. [1] point to some regimes when Local SGD is worse. Moreover, (4.5) can be much better than (4.4) if $\\sigma$ and $M$ are large. In this regime, the third term in (4.4) can dominate.\n3. I agree that when $K$ is large, Local SGDM can outperform Minibatch SGDM. However, looking at (4.4), due to the third term, it is clear that taking $K \\to \\infty$ is a suboptimal choice (we can't just take $K \\to \\infty$ because one global iteration would take an infinitely long time), so there should be an optimal choice of $K^*,$ and I'm not convinced that for this choice of $K^*$ Local SGDM will be better than Minibatch SGDM.\n4. The rate (4.9) of Local ADAM, in the way it is presented now, does not provide meaningful convergence guarantees due to the norm $||\\cdot||_{H_r^{-1}}.$ What happens if the maximum eigenvalues of $H_r$ are huge? I think the authors should bound $H_r$ somehow to get a a more meaningful rate.\n\nConclusion: Despite all these weaknesses, I think that the authors did a very nontrivial and technical mathematical work, which I appreciate. However, due to time limits and technicalities, I cannot check the proofs in detail, so I will choose a low confidence.\n\n[1]: Woodworth, Blake, et al. \"Is local SGD better than minibatch SGD?.\" International Conference on Machine Learning. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)