Faster Convergence of Local SGD for Over-Parameterized Models
Authors: Tiancheng Qin
S. Rasoul Etesami
Cesar A Uribe
Venue: Accepted by TMLR ()

Abstract: Modern machine learning architectures are often highly expressive. They are usually over-parameterized and can interpolate the data by driving the empirical loss close to zero. We analyze the convergence of Local SGD (or FedAvg) for such over-parameterized models in the heterogeneous data setting and improve upon the existing literature by establishing the following convergence rates. For general convex loss functions, we establish an error bound of $\mathcal {O}(1/T)$ under a mild data similarity assumption and an error bound of $\mathcal {O}(K/T)$ otherwise, where $K$ is the number of local steps and $T$ is the total number of iterations. For non-convex loss functions we prove an error bound of $\mathcal {O}(K/T)$. These bounds improve upon the best previous bound of  $\mathcal {O}(1/\sqrt{nT})$ in both cases, where $n$ is the number of  agents, when no assumption on the model being over-parameterized is made. We complete our results by providing problem instances in which our established convergence rates are tight to a constant factor with a reasonably small stepsize. Finally, we validate our theoretical results by performing large-scale numerical experiments that reveal the convergence behavior of Local SGD for practical over-parameterized deep learning models, in which the $\mathcal {O}(1/T)$ convergence rate of Local SGD is clearly shown.

Published in Transactions on Machine Learning Research (03/2024)
Faster Convergence of Local SGD for Over-Paramettrizer Models
Tiancheng Qin
tqberilkooiseei edu
Deportment of Industrial and Systems Engineering, Coordinated Science Laboratory University of Ilinois at Urbana- Champaign
S. Rasoul Etesami
etesamil dellinoois. edu
Department of Industrial and Systems Engineering, Coordinated Science Laboratory University of Blinois at Urbono- Champoign.
Cesár A. Uribe Department of Electricol and Computer Engineering Rice University
couribe@rice.cot edu
Reviewed on OpenReview: https: // openreviee. net/ formm? VBAKc4DtZ1
Abstract
Modern machine learning architectures are often highly expressive. They are usually over- parameterized and can interpolate the data by driving the empirical loss close to zero. We analyze the convergence of Local SGD (or FedAvg) for such over-parameterized models in the heterogencous data setting and improve upon the cxisting literature by establishing the following convergence rales. For general convex loss functions, we establish an error bound of O(1/T)) under a mild data similarity assumption and an error bound of OKK/T) otherwise, where K is the number of local steps and T is the total number of iterations. For non-convex loss functions we prove error bound of O(K/T). These bounds improve upon the best previous bound of O(1/Vn7) in both cases, where n is the number of nodes, when no assumption on the model being wer-parameterized is made. We complete our results by providing problem instances in which our established convergence rates are tight to a conslant factor with a reasonably small stepsize. Finally, we validate our theoretical results by performing large-scale numerical experiments that reveal the convergence behavior of Local SGD for practical wer-parameterized deep learning models, in which the O(1/T) convergence rate of Local SGD is clearly shown.
1 Introduction
Distributed optimization methods have become increasingly popular in modern machine learning, owing to the data privacy/owuerdee /ownership issues and the scalability of learning models concerning massive datasets. The large datasets often make training the model and storing the data in a centralized way almost infeasible. That mandates the use of distributed optimization methods for training machine learning models. However, critical challenge distributed optimization to reduce the communication cost among the local nodes, which has been reported a major bottleneck in training many large-scale deep learning models (Zhang et al., 2017; Lin et al., 2017).
One naive approach to tackling this challenge is using the Minibatch Stochastic Gradient Descent (SGD) algorithm, which generalizes SGD to the distributed optimization setting by averaging the stochastic gradient steps computed at each node (or client) to update the model on the central server. Minibatch SGD has been shown to perform well in a variety of applications, see, c.g., Dekel al. (2012); Cotter al. (2011). Recently, Local SGD (Stich, 2018; Mangasarian, 1995) (also known as Federated Averaging) has attracted significant attention appealing alternative to Minibatch SGD to reduce communication cost, where

---

Published in Transactions on Machine Learning Research (03/2024)
during a communicttin round, several local SGD iterations are performed at each node before the central server computes the average.
Local SGD has been widely applied in Federated Learning (Li et al., 2020), and other large-scale optimization problems and has shown outstanding performance in both simulation results (McMahan et al., 2017) as well as real-world applications such as keyboard prediction (Hard et al., 2018). At the same time, recent works have studied the theoretical convergence guarantees of Local SGD in various settings (Li et al., 2019; Koloskova et al., 2020; Gorbunov et al., 2021; Qin et al., 2020; Yang et al., 2021). Specifically, an O( (T)) convergence rate was shown for strongly convex loss functions (Karimireddy et al., 2020), where is the number of nodes and T is the total number of iterations. Morcover, an O( VnT
convergence rate was shown for general convex
loss functions in Khaled et al. (2020). In addition, an O( VxT convergence rate was shown for non-convex loss functions (Yu el. al., 2019; Haddadpour & Mahdavi, 2019). When the Polyak-L.ojasiewier condition is assumed, Haddadpour & Mahdavi (2019) showed O ( convergence rate for non-convex loss functions and Maralappanavar et al. (2022) showed ((exp(-T/K²) convergence rate, where K is the number of local steps. 1 These works made substantial progress loward understanding the theoretical convergence propert ies of the Local SGD. Their results are for general models without the over- parameteriization (or interpolation) assumption.
However, despite past efforts, the current results have shortcomings in explaining the faster convergence of Local SGD compared to Minibatch SGD, which is significant especially when training large-scale deep learning models (McMahan et al., 2017). In Woodworth et al. (2020b), the authors give lower bound on the performance of local SGD that is worse than the Minibatch SGD guarantee in the i.i.d. data setting (i.e., when all local loss functions are identical). The situation is even worse in the heterogeneous data setting (i.e., when local loss functions are diffcrent), which is the sctting that we consider in this paper. Local SGD is shown to sulfer from "client drift", resulting in unstable and slow convergence (Karimireddy et al., 2020), and it is known that Minibatch SGD dominates all existing analyses of Local SGD. (Woodworth et al., 2020a).
On the other hand, key observation for explaining the fast convergence of SGD in modern machine learning was made by Ma et al. (2018) that says modern machine learning architectures are oflen highly expressive and are over-vvranee parameterizeed Based on both theoretical and empirical evidence (Zhang et al., 2021; Chaudhari ct al., 2019), most or all local minima in such over-parametrizer scttings are also global. Therefore, the authors in Ma et al. (2018) assumed interpolation of the data: the empirical loss at every data point can be driven to zero. Under such interpolation assumption, a faster convergence rate of SGD was proven (Ma et al., 2018; Vaswani al., 2019). Furthermore, it was shown in Ma et al. (2018) that under certain conditions, mini-batch size larger than some threshold m² is essentially helpless for SGD. This is important since, in distributed optimization, it means: for Minibatch SGD, larger batch sizes will not speed up convergence, while for Local SGD, more local steps can potentially speed up convergence. This provides a new direction for explaining the fast convergence of Local SGD for large-scale optimization problems as well as its faster convergence compared to Minibatch SGD.
Motivated by the above studies, in this paper, we formally study the thcoretical convergence guarantecs of Local SGD for training over-parameterized models in the heterogeneous data setting. Our results improve the existing literature and include the natural case of training large-scale deep learning models.
1.1 Related Works
Adopting Neural Tangent Kernel (NTK) framework of analysis, two recent works, Huang et al. (2021); Deng et al. (2022) studied the convergence rate of Local SGD for specific over werrparameterizedd Neural Networks and showed error bounds that are ((exp-TT/K²) and O(exp(-T/K)) respectively. However, both works focus on very restrictive and somewhat unrealistic types of Neural Networks. Huang et al. (2021) only considered two-layer fully connected Neural Networks with ReLU activation, and they require the width of the Neural Network to be Q(N4), where N denotes the total number of data samples in the training set?, which is not very realistic in practical applications. Likewise, Deng et al. (2022) considered fully connected Neural
The PL condition a generalization of strong convexity and requires the loss function to exhibit quadratic growth, which is very strong assumption.
2This parameter N written as n in the original work Huang et al. (2021).
2

---

Published in Transactions on Machine Learning Research (03/2024)
Table 1: Existing theoretical bounds for local SGD for heterogeneous data. GC and NC stand for general convex and non-convex, n is the number of nodes, T the number of total iterations, and K is the number of local steps (R = T/K is the number of communication rounds).
Objective
Convergence Rate
Over-parrmeetrzied
Extra
References
Assumption
GC
No
Khaled al. (2020)
VnT
NC
00
No
Koloskova et al. (2020)
VnT
NC
(
No
PL condition
Haddadpour & Mahdavi (2019)
NC
O(exp(-T//L
Yes
PL condition
Maralappanavar et al. (2022)
GC
O(L/T)
Yes
> (5)
This work
GC
O(K/T)
Yes
This work
NC
O(K/T)
Yes
This work
Networks with ReLU activation but with multiple layers, and they require the width of the Neural Network be ()(11), which is not practical in large-scale problems. As a comparison, we give analysis under the weer-parameterized regime for strongly convex, convex, and non-convex loss functions that include the natural case of training large-scale Neural Networks but is not limited to it, which is much broader analysis.
The work Li et al. (2022) also studied the convergence of Local SGD for weraparameteiize Neural Networks. Utilizing the no critical point property of extra-wide Neural Networks shown in Allen-Zhu et al. (2019), they relaxed the commonly seen L-smoothness assumption of the local functions and proved the convergence of Local SGD but did not show an explicit convergence rate. Employing a new notion called ilerate bias, Glasgow al. (2022) recently showed lower bounds for the convergence rate of Local SGD without the weer-parameterized assumption that matches (or nearly matches) the existing upper bounds, showing that without the over-parameeterized assumplion, the existing upper bound analysis is not improvable.
1.2 Contributions and Organization
Our main contributions be summarized follows:
For general convex loss functions, we establish an error bound of O(I/T) under a mild data similarity assumption and an error bound of O(K/T), otherwise. Before our work, Zhang & (2021) showed the asymptotic convergence of Local Gradient Descent (GD) in this setting but did not provide an explicit convergence rate. To the best of our knowledge, the best convergence rate in this setting was O(1/VTT) (Khaled et al., 2020) which was achieved without assuming the model being pver-parametreized.
For nonconvex loss functions, we prove an error bound of O(K/T). To the best of our knowledge, the best convergence rate in this setting O(1/VnI) (Koloskova et al., 2020) which was achieved without assuming the model being over-parametreizel.
We provide two problem instances to show that our convergence rates for the case of general convex and nonconvex functions are tight up to constant factor under a reasonably small stepsize scheme.
we validate our theoretical results by performing large-scale numerical experiments that reveal the convergence behavior Local SGD for practical over pee-paramettrized deep learning models, which the OL//T) convergence rate of Local SGD clearly shown.
In fact, by establishing the above error bounds, we partially prove the effectiveness of local steps in speeding up the convergence of Local SGD, thus partially explaining the fast convergence of Local SGD (especially when compared to Minibatch SGD) when training large-scale deep learning models.
Our analysis builds upon the techniques used in Ma et al. (2018) and Vaswani et al. (2019) for analyzing centralized SGD in the perrparaaettriiee setting and applies them to analyze both the local descent progress
3

---

Published in Transactions on Machine Learning Research (03/2024)
and the global descent progress in Local SGD. Specifically, we adopt new techniques in the proof of Theorem that directly relate the local progress with the global progress instead of measuring the progress made by x where we made use of the consensus error, i.e., 1 Di= -x to improve convergence, which is in contrast to prior works. The new technique allows us to use a constant stepsize that does not scale with K and to establish better bounds. In the proof of Theorem 2, we use the techniques in Ma al. (2018) and Vaswani et al. (2019) to bound both the global descent progress and the consensus error of Local SGD. These techniques may be of independent interest to the readers.
In Section 2, we formally introduce the problem. In Section 3, we state main convergence results for general convex and non-convex local functions. We also provide lower bound to show the tightness of our convergence rate bounds for reasonably small step sizes. We justify our theoretical bounds through extensive numerical results in Section 4. Conclusions are given in Section We defer all the proofs to Section A.
2 Problem Formulation
We consider the problem of n nodes [n] = (1.2...., that collaboratively want to learn an over-parameterized model with decentralized data as the following distributed stochastic optimization problem:
min f(x) = 1 Σ M(x).
(1)
XE3
where the function fi(x) A DE Ex),,) denotes the local loss function, & is a stochastic sample that node has access to, and D, denotes the local data distribution over the sample space Q, of node i.
A Assumption (Bounded below, L-smooth, unbiased gradient). We assume f(x) is bounded below by S (t.e., a global minimum erists), f((x, {.) is L-smooth for every E [n], and f(x, Ei) an unbiased stochastic gradient of f((x).
Moreover, for some of our results, we will require functions fa(x; to be p-strongly convex with respect to the parameter as defined next.
Assumption (p-strong convexity). There erists a constant p 2 0, such that for any x, E Rd i [n]] and & E U4 we have
fx(x 2 + (Vfl(, y) + 1|x y1?
(2)
If jr 0, 0, we simply say that each Si is convex.
The peramearaetr setting, i.e. when the model can interpolate the data completely such that the loss at every data point is minimized simultaneously (usually means zero empirical loss), can be characterized by the following two assumptions (Ma et al., 2018; Vaswani et al., 2019):
Assumption 3 (Interpolation). Let x* E arg argmin, min fxx). Then, fx(x", = O, Vi E [m], & E Ωz Assumption 4 (Strong Growth Condition (SGC)). There erists constant such that Vx E IR4, i [r]]
BE,DD V 41 < (l)
(3)
Notice that for the functions to satisfy SGC, local gradients at every data point must all be zero at the optimum x². Thus, SGC is a stronger assumption than interpolation, which means Assumption 3 implics Assumption 2.
The SGC assumption can be viewed as an adaptation of a mild assumption, Strong Growth with noise, i.e.,
Bg-D IV 2 < p ( +
(4)
to the over-pane over-parameten pore-paameterize// httteeedd//ntteplaationn setting, which implies that the gradient with respect to each point converges to at the optimum, suggesting that. 0 in (4). The Strong Growth with noise assumption is
4

---

Published in Transactions on Machine Learning Research (03/2024)
generalization of the Bounded Variance assumption commonly used in the stochastic approximation setting, I.e.,
BE Vx, < [x)()))]*++++
The work Vaswani et al. (2019) discusses functions satisfying Assumption 4 (SGC) and shows that for linearly separable data, the squared hinge loss satisfies the assumption. In addition to that, we perform experimental verification in Appendix B using the same problem setup as in Section 4.1 (training over-parameterized ResNet18 Neural Network on the Cifar10 dataset) and show that Assumption 4 (SGC) indeod a valid assumption for over-parameteriveed models in practice.
When the local loss functions are convex, we define the following quantity [0, 1] that allows measure the dissimilarity among them.
Definition 1. Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with l 2 0. Let
x E arg min [xx). We define as the largest real remmeer such that for all x1,... Xn E IR and
X == Ei= Xi, we have
Σ ( 2 df(x) f(x))).
(5)
If Assumption 2 and Assumption 3 (Interpolation) hold, the left hand side of (5) is always non-negative, which implies 2 0. In particular, by taking Xi = Xn we have S 1. Moreover, as the local loss functions become more similar, c will become closer to 1. In particular, in the case of homogeneous local loss functions, i.e., f4 Vi, using Jensen's inequality we have c
In the next section, we will proceed to establish our main convergence rate results for various settings of strongly convex, convex, and nonconvex local functions.
3 Convergence of Local SGD
This section reviews Local SGD and then analyzes its convergence rate under the over-parameterized setting.
In Local SGD, each node performs local gradient steps, and after every K steps, sends the latest model to the central server. The server then computes the average of all nodes' parameters and broadcasts the averaged model all nodes. Let T be the total number of iterations times {0, K, 2K.. .......2 T' RK)3, and in every iteration t, Local SGD does the following: i) each node performs stochastic gradient updates locally based on (f, Ex), which is unbiased estimation of fx),,, and ii) if is communication time, i.e, I, it sends the current model to the central server and receives the average of all nodes' models. The pscudo-code for the Local SGD algorithm is provided in Algorithm 1.
the algorithm. There is a set of communication
3.1 Convergence Rate Analysis
We now state our main result on the convergence rate of Local SGD under over-parameterized settings for general convex functions.
Thcorem 1 (General convex functions). Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with = 0, and let e be defined as Desivition Moreover, let
i or L 1+112 otherwise,
Wt
and define W ET- we and ST A 1 ET- ()) If we follow Algorithm 1 with stepsize r S 1 and K > 2, then
W
K k 1
Elf(**) - f
mccTT + 2(1 c))
3To simplify the analysis, assume without loss of generality that divisible by K, L.e. T RK for some N.
5

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm Local SGD
Input: x; (0) x( for E [n], number of iterations T,, the stepsize 7,, the set of communication times I.
2: for t = O...., T 1
3: for i= 1....,,h Th do
Sample 4, compute (5( (++g) (t)
x V (
(1)
X;
6:
if
+ 1 E I then
(++1)
(++2)
x
2j=1
else
((+1)
(1+2)
x;
x;
10: end if
11: end for
12:
end for
As special case, if we choose 17 21. we have
1
2| - 12 -15(x")-11) cKT + 2(1 c)
(6)
The convergence of Local GD for general convex loss functions in the over- over-parameterized setting was shown earlier in Zhang& & Li (2021) without giving an explicit convergence rate. 4 Instead, for similarity parameters O and 0, give convergence rates of O1/TT) and O(K/T) for Local SGD, respectively. The significant. difference between the convergence rates for the case of > 0 and in the local loss functions is critical to the performance of Local SGD, which also complies with the simulation findings in McMahan et al. (2017). To the best of our knowledge, Theorem provides the first O(1/T) or O(K/T) convergence rates for Local SGD for general convex loss functions in the over-parameterized setting. On the other hand, in Section 3.2, we provide a problem instance suggesting that in the worst case, the O(K/T) convergence rate obtained here might be tight up to a constant factor.
suggests that having slight. similarity
direct consequence of the O(1/T) 0, closer look (6) and the weights wı reveals that 1 if E I or (+1 E I, implying that at least the first and the last local steps during each communication round is "effective". This, in turn, shows that local steps can speed up the convergence of Local SGD by at least a factor of 25.
It worth noting that the speedup effect of local steps when convergence rate shown in Theorem 1. When
For the case of non-convex loss functions, we have the following result. Theorem 2 (Non-convex functions). Let Assumplion 1, Assumplion 4 (SGC) hold. If we follow Algorithu with stepsize 17 S 3kLp' and K 2 2, we will have
9(f(xo) - f³) 1/T
min 0StST-1
As a special case, if we choose 7) 3KLp we have
E) (xx) 051ST-1
min
(7)
T
'In fact, a convergence rate of O(IVVT) was discussed in Zhang & Li (2021). However, the argument in their proof seerss to have some inconsistencies. For more detail, please see Scction D.
SSimilar to Woodworth et al. (2020a), we compare the convergence rate of Local SGD to Minibatch SGD with R T/K steps and batch size K times larger than that of Local SGD. The convergence rate of Minihatch SGD (for over-parameterived setting), stated in Theorem 6 in Vaswani al. (2019), 4LK3+to)]>x(0) -x when O. On the other hand, according
T analysis and using Lemma which is at least times slower than rate SGD 21. (00) x*1 which times slower than Local SGD.
show the convergence rate of Minibatch

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem 2 provides an OKK/T) convergence rate for Local SGD for non-convex loss functions in the over- parameterized setting, which is the first ((1/T) convergence rate for Local SGD under this setting. However, this rate is somewhat disappointing as it suggests that local steps may not help the algorithm to converge faster. This is mainly caused by the choice of stepsize y = 3k which is proportional to 1/K. On the other hand, in Section 3.2, we argue that, this choice of stepsize may be inevitable in the worst case because there are instances for which the choice of stepsize 1) greater than (1//K) results in divergence of the algorithm.
3.2 Lower Bounds for the Convergence Rate of Local SGD
In this section, we present two instances of Problem (1) showing that the convergence rates shown in Section 3.1 are indeed tight up to constant factor. First of all, we restrict to the scenario when Local SGD is run with stepsize 7 S I, it is known from Nesterov et al. (2018) that Gradient. Descent can provably diverge for stepsize 17 > T. Then, we show that when Local SGD is run with stepsize L, and under the weer-paameterrized regime:
1. for general convex loss functions, there exist functions fi satisfying Assumption 1, Assumption 2 and Assumption 3 (Interpolation) with μ 0 and = 0 in Definition 1, such that Local SGD incurs an error bound of - Q((K/TT
2. for non-convex loss functions, there exist functions fs satisfying Assumption 1, Assumption 4 (SGC), such that Local SGD with stepsize 17 2 LK will not converge to first-order stationary point.
Proposition (General Convex Functions). There erists an instance of general convex loss functions f satisfying Assumption 1, Assumption 2 and Assumption (Interpolation) with = 0 and c in Definition 1, such that Local SGD incurs an error bound of [(xT) - =S[K//TTTT
Proof. Consider Problem (1) in the following setting. Let n = 4R 4T/KK, d and fi(x) = 4 f2(x) [a(x) _... (x) = 0. Then ((x) = 12, and clearly every fi is L-smooth and satisfies Assumption and Assumption 3 (Interpolation) with μ 0, c O. Suppose Algorithm is run with stepsize v) S H. and initialized at x" = 1. We will show that (fnx) f*) 2 KL To that end, first we note that the global optimal point is x* = 0, and local gradient steps for all nodes except. node keeps local variable unchanged. Moreover, since 1) S I/L, we have x [o, Vt E [2]] Therefore, (x*} J is non-inereasing
167
sequence that lies in interval [0, 1]. Thus, we only need to show f(x²) 2 KL
16T
(r+1)K 2 0 and x, (r+1)K-1/2 = x for Next, we claim that (++1) 2 a-1 x Vr. In fact, since x = 2,..., n, we have
((+1)) 1
(r+1)K 11/K-1122 1/2
n -
1
x
i=1
Therefore, we can write
f(xT)=
T
(x
>
L n
(
22
L
(1 16R
2R
T
KL
2n
2n
2n
n
16T
which completes the proof.
Proposition 2 (Non-convex Functions). There exists an inslance of nonconver loss functions Si salisfying Assumption 1, Assumption 4 (SGC), such that Local SGD with a stepsize n 2 2 will not converge to a first-order stationary point.
Proof. Consider Problem (1) in the following setting. Let n = 2, d= and ==) = f(()) b
Then ((x)
L 42² and clearly every fi is L-smooth and satisfies Assumptions (SGC) with p 2. Suppose 4
We note that 77 S 1/L is standard requirement when applying SGD-like algorithms on L-smooth functions, e.g., Bubeck (2014). Many numerical experiments also show that stepsize r) > 1/L will cause divergence. other words, when Local SGD is run with stepsize 7) > 3, there are problem instances that Local SGD perfroms paorly
7

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm is run with stepsize 7 I 1/L and initialized at x" = 1. We want to show that for such distributed stochastic optimization problem, if we run Algorithm for any stepsize v) 2 LK the gradient norm at any iterate will be lower bounded by min [V 2 L2
2
16'
First, we note that the global optimal point is x* = 0, which the only critical point. Since 7) S I/L, we have xi 2 0, vt E [7], and local gradient steps for node 2 will always increase the value of x Next, we
2 then x*" 2 1, Vr, and prove it by induction. First notice that x = 1 2 1. Suppose claim that if 17 LK
grk 2 1, then
(x+1)K-1 Σ
[r+1)k =x - 11
V12(x2)
t=rk
(++1)K-1
L
= +1
Σ
X22
2
(r+1)K
-1
2 1 2
Σ
L
2.
LK
2
t=rk
Since x1 (r+1)K-1/3
2 0, we have
x((+1)K_ (r+1)k (x)
(rt1)K-1/2) 21.
+ +x2
which proves the claim. Therefore, 2 1, Vi E [T] and x 2 0, Vt [7], which implies x 2 1/2, Vt [T]. This shows that [Vf(x')] 2 I2/16, as desired.
Remark 1. According to Proposition 2, in the worst case a stepsize of r S O(1/K) for Local SGD is inevilable. This in view of Vaswani el al. (2019) implies a convergence rale of at most (K/TT).
4 Numerical Analysis
In this section, we conduct some numerical experiments where we use Local SGD to train an over-parameterrzeed ResNet18 neural network (He al., 2016) on the Cifarl0 dataset (Krizhevsky et al., 2009). This is a standard setting of nonconvex functions under over-parameelerizatiinn We also conduct another set of experiments focusing on general convex objective functions, where perceptron is trained for syuthetic linearly separable binary classification datasct.
4.1 ResNet18 Neural Network for Cifar10
We distribute the Cifar10 dataset (Krizhevsky et al., 2009) to = 20 nodes and apply Local SGD to train ResNet18 neural network (He et al., 2016). The neural network has 11 million trainable parameters and, after sufficient training rounds, can achieve close to O training loss, thus satisfying the interpolation property.
For this set of experiments, we run the Local SGD algorithhm for R = 20000 communication rounds with a different number of local steps per communication round K = 1, 2, 5, 10, 20 and report the training error of the global model along the process. We do not report the test accuracy of the model, which is related to the generalization of the model and is beyond the scope of this work?. Following the work Hsieh et al. (2020), we also use Layer Normalization (Ba et al., 2016) instead of Batch Normalization in the architecture of ResNet18 while keeping everything else the same.
We first sort the data by their label, then divide the dataset into 20 shards and assign each of 20 nodes shard. In this way, ten nodes will have image examples of one label, and ten nodes will have image examples of two labels. This regime leads to highly heterogeneous datasets among nodes. We use a training batch size of and choose stepsize nj be 0.1 based on grid search of resolution 10-2, The simulation results
Withoot data augmentation, the final test accuracy of the madel this experiments around 80%.
8

---

Published in Transactions on Machine Learning Research (03/2024)
are averaged over 3 independent runs of the experiments. We show the global landscape of the result in figures la and 1b, where the training loss and the reciprocal of the training loss over the communication rounds are reported, respectively. The decrease in the training loss can be divided into Phase 1, Phase 2, and a transition phase between them, as shown in figures 3a, 3b, and 3c.
As figure 3a shows, the first 3000 communication rounds, the reciprocal of the training loss grows nearly linearly with respect to the number of communication rounds. This strong evidence of the ((1/R) (K//T) convergence rate of Local SGD as stated in Theorem 2. We can also see that in this phase, the decrease of training loss depends only the mumber of communication rounds R regardless of the number of local steps K, thus validating Theorem 2.
Phase 1:
After R 6000 communication rounds, as the training loss further decreases (below 0.01), we can observe from figures 3c and figure a clear linear dependence of the reciprocal of the training loss and the total itcrations T (notice in figure 2 all lines share similar slope). This corresponds to a (1/TT) convergence rate of Local SGD. In fact, we conjecture that in this phase, the model has moved close enough to the neighborhood of global optimal point, which simultaneously minimizes the loss at every single data point. Therefore, every local step moves the model closer to that global optimal point regardless of at which node it is performed, causing the aggregation step to be no longer meaningful and resulting in the convergence rate of ((1/T) instead of O(1 / R). Another possible explanation is that in Phase 2, the iterates eventually reach a locally convex region and so resemble the convex regime.
Phase 2:
The experimental results provided here have two important implications:
First, from the upper bound in Theorem 2, lower bound in Proposition 2 and the experimental results in Figures 1,2,3, we can imply that for over-parameterized deep learning models, Local SGD indeed converges at 0(2 ( rate", which is strong characterization of the algorithm's actual convergence rate.
Second, the phenomenon of the two phases also gives an important empirical implication that in real implementations of the Local SGD algorithm, it might be better to adjust the nunber of local steps during each communication interval to enforce more frequent communication at first (as in Phase the ((1RR) = OKKTT) convergence rate suggests local steps are more or less useless) and less frequent communication later on when one observes the training has entered Phase (by, e.g., observing training loss S 0.05).
To conclude, have performed large scale experiments that reveal the convergence behavior of Local SGD for practical over- parameterizee deep learning models. We observe from the experiments that the decrease of the training loss can be divided into Phase 1, Phase 2, and a transition phase between them. The convergence rate of Local SGD in practice can be OKK/T) (Phase 1), or O(1/T) (Phase 2), or somewhere in between (transition phase). Experimental results in Phase strongly support our thcorctical findings in Theorem 2, while experimental results in Phase partially support it and also raise new interesting questions.
4.2 Perceptron for Linearly Separable Dataset
We generate a synthetic binary classification dataset with N 10000 data-points uniformly distributed in a d 100 dimensional cube [-1, Then, a hyperplane is randomly generated, and all data points above it are labeled '1' with other data points labeled '-1', after which the two sets of points with different labels are "pulled apart' to add a small gap between them. This ensures the dataset is linearly separable and satisfies the interpolation property. We divide the dataset among n = 16 nodes and apply Local SGD to distributedly train a perceptron to minimize the finite-sum squared-hing loss function:
1 f(w) N
Σ
(0, yoo w.)
STf taken into consideration the factor of K, then the between O(K/T) (Phase 1), and O(I/T) (Phase 2).
9

---

Published in Transactions on Machine Learning Research (03/2024)
1/Training Loss vs. Commmunication Rounds
Training Loss vs. Commmunication Rounds
2.00
Local Steps K
800000
Local Steps 2
Steps
Local Steps
Local Steps K 5
Local Steps 5
Steps
Local Steps
Local Steps
1/traiming loss
Local Steps K 20
Training lass
1.25
400000
200000
0.50
2500
5000 7500 10000 12500 15000 17500 20000
2500
5000
7500
10000
12500 15000 17500 20000
Communication Rounds:
Communication Rounds:
aa)
(b)
Figure 1: la: Training loss vs. communication rounds with different local steps. 1b: 1 T/Trinnig loss vs.
communication rounds with different local steps.
1/Training Loss vs. Iterations
800000
Local Steps 1
Local Steps 2
Local Steps 10
600000
1/Training less
Local Steps K 20
400000
200000
0
50000 00000000000000000000000000000000
Iterations:
Figure 2: 1/(Training loss) vs. Total number of iterations T with different local steps.
We partition the dataset in three different ways reflect different data similarity regimes and evaluate the relationship between training loss, communication rounds, and local steps for Local SGD under each of the three regimes. As in Section 4.1, we plot both the training loss and 1/(training loss) vs. the number of communication rounds. We stop the algorithm after at most 106 comnunication rounds or if the training loss is below 10-4. We choose stepsize = 0.075.
1. Even partition: The dataset is partitioned evenly to all nodes, resulting in i.i.d local data distribution. The simulation results for this regime are shown in Figure 5a,4a.
2. Pathological partition: The datasct is partitioned by 17 hyperplanes that parallel to the initial hyperplane. Distances between adjacent hyperplanes are the same. Each node gets assigned one of the 16 'sicees' of data points. This is a highly heterogeneous data partition since 15 out of the 16 nodes will have only one label. The simulation results for this regime are shown in Figure 5b,4b.
3. Worst case partition: All data points assigned to one node. The other 15 nodes have empty datasct. This partition corresponds to the setting in Example 1. The simulation results for this regime are shown in Figure 5c,4c.
An O1/TT) Convergence Rate:
In general, we can clearly observe that the reciprocal of the training loss grows linearly with respect to the number of communication rounds, well as linear speedup of the
10

---

Published in Transactions on Machine Learning Research (03/2024)
Transtiion
Phano
3.75
Local Stepa 1-1
Locel Stege 5-2
37.5
Local Stess
Local Steae
900000
Lace
Lacal Stage 5-5
35.0
Stezs
Loca Step' 5
Loca Sega
Local Stups 20
Local Steza
32.0
#00000
0.75
1.5
500
1003
Commoniicaaon founds:
1500
2000
2000
3003
3000
3502
9003
Communiation Roondb:
4500
5000
5500
6090
Conmenttatton Feondic
10000 19460 IMAE
(a)
(b)
(c)
Figure 3: 1/(Training loss) vs. communication rounds for different phases. 3a: Phase 3b: Transition phase.
3c: Phase 2.
convergence rate with the number of local steps in all three regimes. This implies an - convergence rate for Local SGD, validating our result in Theorem 1. The simulation results suggest that despite the O(K/T) worst-case upper bound, the optimistic (1/TT) convergence rate in Theorem 1, as well as the effectiveness of local steps, can generally be expected in practice. We also notice cases where Local SGD converges faster than the O(1/T), remark that this is also reasonable since Theorem 1 only provides lower bound for the convergence rate of Loca SGD.
Effect of Data Heterogeneity: While in general, Local SGD enjoys an = = O(1TT) convergence rate, data helerogeneity is still a key issue and will cause the algorithm to become slower. Comparing the convergence rate of Local SGD under the three different partition regimes, especially the slow convergence of the worst case regime stands in contrast with the similar fast convergence of the other two regimes, we can see that having at least little data similarity among different nodes is crucial for the convergence rate of the algorithm, as we predicted in Theorem 1.
bvan Faittinn
Nathologiaaa Bart
Wor.
6.100
Lecal shap
Grys sime
Teral stge
Local
Slos
B 0085
6.33
0.055
0.02
6132
0.82
02
06
06
10
0:30
00
12
3.5
62
04
35
C8
10
(a)
(b)
(c)
Figure 4: Training loss vs. communication rounds with different local steps under the three data partition regimes. 4a: even partition regime. 4b: pathological partition regime. 4c: worst case partition regime.
5 Conclusion
We studied the theoretical convergence guarantees of Local SGD for training parametteeee models in the heterogeneous data setting and established tight convergence rates for strongly-convex, convex and non-convex loss functions. Morcover, we validated the effectiveness of local steps in speeding up the convergence of Local SGD in various settings both theoretically and using extensive simulations. However, our theoretical results fall short of explaining the effectiveness local steps in the later phase of training non-convex over-parameterized Neural Notworks, as observed in our experiments. We leave this important issuc as a future research direction. Our results partially explain the fast convergence of Local SGD (especially when compared to Minibatch SGD) when training large-scale deep learning models.
11

---

Published in Transactions on Machine Learning Research (03/2024)
Even Puntlion
Pathological Parttton
Wore:
3009
100.0
Lnnel Mem
12c8 exee
300
10:30
Vine
6003
3000
2009
2530
Communccton Founds
Commincctionn Noundr
Tea
Communcction Foundo
(a)
(b)
Figure 5: 1/ ((Training loss) vs. communication rounds with different local steps under the three data partition regimes. 5a: even partition regime. 5b: pathological partition regime. 5c: worst case partition regime.
As future work, one interesting direction would be generalize our results to the partial node participation sctting, which is practical in federated learning. Another interesting dircction would be to further study and quantily the two-phase convergence phenomenon of Local SGD when training large-scale neural norkorks, as we discussed in Section 4.1. This may need combining the interpolation assumption with the special architectures of neural networks (see, e.g., (Allen-Zhu et al., 2019; Du et al., 2019)).
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252 PMLR, 2019.
Jimmy Lei Ba, Jamie Ryan Kiros, and GeofTrey Hinton. Layer normalization. arXiv preprinl 161706660006650 2016.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. ar preprint orXi:: 1rxXix1405.440 405. 2014.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):224018, 2019.
Andrew Cotter, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. arXiv preprinl arXie:1106.4514 2011.
Ofer Dekel, Ran Gilad- Baaad-Baccrach,, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Local sgd optimizes overparameterized neural networks in polynomial time. In International Conference on Artificial Intelligence and Statistics, pp. 6840 6861. PMLR, 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp.
PMLR, 2019.
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556 3564. PMLR, 2021.
Farzin Haddadpour and Mchrdad Mahdavi. On the convergence of local descent methods in federated learning. Xix preprint Xiv: 1910.190111 1425, 2019.
12

---

Published in Transactions on Machine Learning Research (03/2024)
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Frangoise Beaufays, Scan Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint vrXie:1811.03604, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 770-778, 2016.
Kevin Hsieh, Amar Phanishayee, Onur Muthu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference Machine Learning, pp. 4387-4398. PMLR, 2020.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning, pp. 4423 4434. PMLR, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5393. PMLR, 2020.
Alex Krizhevsky, GeofTrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Tian Li, Anit Kumar Sahu, Amoet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50- 60, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint arXio:1907.02180 2019.
Xiaoxiao Li, Zhao Song, Runzhou Tao, and Guangyi Zhang. A convergence theory for federated average: Beyond smoothness. arXiv preprint Xrx: 11.0211,,,,8,, 2022.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXin:1112.01889 2017.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power interpolation: Understanding the effectivenes of sgd in modern pver-parametrzed learning. In International Conference on Machine Learning, pp. 3325 3334. PMLR, 2018.
LO Mangasarian. Parallel gradient distribution in unconstrained optimization. SIAM Journal on Control and Optimization, 1916119916 1995.
Shruti Maralappaanaarr, Prashant Khanduri, and BN Bharath. Lincar convergence of decentralizod fodavg for non-convex objectives: The interpolation regime. 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communicttion efficient. learning of deep networks from decentralized data. In Artificial intelligence and slatistics, pp- 1273-1282, PMLR, 2017.
Yurii Nesterov et al. Lectures on conver optimization, volume 137. Springer, 2018
Tiancheng Qin, S Rasoul Etesami, and César A Uribe. Communication-cficien decentralized local sgd over undirected networks. arXiv preprint orXiv:2011.0220 2020.
Zhaonan Qu, Kaixiang Lin, Jayant Kalagnanam, Zhaojian Li, Jiayu Zhou, and Zhengyuan Zhou. Federated learning's blessing: Fedavg has linear speedup. Xiv preprint Xr0:::007 056600 2020.
13

---

Published in Transactions on Machine Learning Research (03/2024)
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXh::1055.090 080100970000777 2018.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statisbics, pp. 1195-1204, PMT.R, 2019.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning. arXio preprint arXiv:2006. 037,, 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp.
PMLR, 2020b.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprinl arXin:2001.1122 11200 2021.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Chi Zhang and Qianxiao Li. Distributed optimization for degenerate loss functions arising from over- parameterization. Artificial Intelligence, 301:103575, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commumications of the ACM, 6d(3):107-115 2021.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning, pp.
PMLR, 2017.
14

---

Published in Transactions on Machine Learning Research (03/2024)
A Proof of Theorems
(0) 2 as the average of the stochastic gradients evaluated at all nodes, and Ft E ( 12 as the expected distance to the optimum solution.
Define g()) Ei= V
A.1 Preliminary Propositions
Proposition 3. Let f I be an I.-smooth and convex function and x" E arg zin f(x). Then,
1
2L fx(x)]1 - f(x) - f(x")
(8)
Proposition 4. xet== n X,. For any x' E TRd, we have
71
X
x Σ
| x112 + +n|xx x'13.
(9)
As consequence, we have the following inequalities:
X: - -112 5 i=1
(10)
|x - x112 < Σ
|x| - x'112.
(11)
i=1
A.2 Proof of Theorem 1
Let x* min f(x). From Assumptions (Interpolation) and 2, we have vx((", &)) 0, which implies
x Ergg ((,, Vi E [n], & &EΩ;
zéRd
We first bound the progress made by local variables x; in one local SGD update as follows: Lemma 2. Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with = 0. If we follow Algorithm with stepsize n S It we will have
Beg ||, ++ x²1 < || - x²11 -(f((x)))
(12)
Proof.
1+1 1
Eey x
- x21
Egg | x- 1/V fi +
= ||x xx" x=1 - -112-27(xx; -x", v.((x()) + Ee (x( 1
(2)(8)
||x| - x11 (x.))x - f((x") - - -xxxx11 x3113)
<
+ n Ee
( - ff(("" ..9
(1 |/)) -x 1|2 (2n 2L (ff(i((((x)) - f((x*))
(n5 ===
||* x" 2 m({x(xt) fx(x)))
15

---

Published in Transactions on Machine Learning Research (03/2024)
Next, we bound the progress made by & in one communication round as follows:
Lemma 3. Let Assumption 1, Assumption and Assumption 3 (Interpolation) hold with μ = 0. Assume that the nodes follow Algorithm with stepsize 1J S 21, and let wi ift E I or art+1e2 EI, and we = c otherwise. Then, for
0, I,..., R 1, we have
(M4))-1
E E|X x²133= -
12 17
Σ t=
wxB[f(x)-- f-}.
Proof.
|||x
1)K x²1 (r-)KK
El| -
1
n
(++1)K x1
n
(9) 1
E|
E
(--1K=
x 11
n
E E|
(1I2K- x1
71
(r+1)K-1
(12) 1
E
||x; k< - x2112-1
Σ (f(x²) - f((x1)]
1
Σ E|xx
(r+1)k
- ( 12
(x+1)K-2
(6)
K
x²112
E(f((**)) - fa(x') - 1 Σ Σ
cBif(x') - f(x)))
i=1
t=r
[ (++))=11 ) - [(xx)) Σ
1
E||x; (r+1)K
(r+1)k-2
=
= x"1 17 Σ w,Elf(x()
f- - (x) ( f%
1
E
x
(r+1)K
12
n
Ti
Since Ti 2 0, we can bound Ti as
Ti
(++1)K-1
" (r+1)K-1
- (1+1))-1 (x
+ (r+ 112
71
12
E x
1)K x(++))=11 + 1/ 1
E [ 1-1]-1 _ | + 111
71
2/1
E[((
;
(+1])-1 ( Vf((x (+H1K-1 -g (+
E||x (r- 1)K- -(
1112 2n Σ E ((((t(() - -xx())))xx((()))) (()(++))(-1)
+ ク |x
L
[1]] x (
(n sb)
2
21
1
Σ
B(f((((+1)K-1)) -((xx (++1)(-11)
f((xx!
n2
-27B1/(x(+1))8111)
2n
Elfi(x(++1)
11).
n
16

---

Published in Transactions on Machine Learning Research (03/2024)
Therefore,
Ti 2 Ti
Blf (x) (++)) )).
Substituting back we get
E| E| - 11
(r+1)K-2
I <BIi** K
x1 -
Σ
w w(E(f(X)) - 84
!
El x
1]1k -1) fx(x))
72
(nBIf(x (x (x+1)---1))
7
[x)
111)))111]))
72
(x41)K2
= =|lx** x
wx(l((x)) - - f(x"))
t=rk
(r+1)K-1
= Bl|x** x²12
wxB[f(x')) - .M
t=
To complete the proof of Theorem using Lemma 3, we can write
B x x=1 B|i RK
12
RK-1
<E|x R- 1)K - xx112
(R-
Σ
wrElf(x') - fr1
(=(R-1)K K)
T-1
S... (1)x(0) -x111 -1 Σ
wy (x
Therefore, we can write
-1111x10) lxx(0)
-x112
K||x (0) -x"112
w. (xx
1-1
n/W
(cKT 2(1 c)])
Theorem 1 now follows from Jensen's inequality.
A.3 Proof of Theorem 2
Define V. == Σ [|x 112 to be the expected consensus error and = Ef(x()) f(x*) to be the
expected optimality gap. Moreover, let = [) be the expected gradient norm of the average iterate.
We first establish the following descent lemma to bound the progress of x in one iteration:
Lemma 4. Let Assumption 1, Assumption 4 (SGC) hold. If we follow Algorithm 1 with stepsize nj S 3k
and K 2 2, we have
1
2 3 g
Et1l S Tih, +
(13)
17

---

Published in Transactions on Machine Learning Research (03/2024)
Proof.
=x((x(0 = (
1 71
[x(( (1 )
$ {Bf(x
fx(
)) +
L
E
[x(
(4) 11
2 1=1
1=1
To bound the term Ti, can write
((V)(x((). 1 Σ (
-E(V)(x
(x( )
=E/V 1 (V 1 [(Vii((() -V
2, V 11
1
a
E|| f (9) ()((11))1
2n
2 >
L
[1|x(1-xx 1
2n
1=1
L
V
-
2
where in the third inequality we have used (a, b) 2 -blla|12 1116112.
Next, in order to bound T2, we have
2
V (x). 1
(3)
fx
20
a 2B [V V)((1)
E
|*)))))
n1
n
22ph: + 2L 2V²
Putting everything together and subtracting f(x") from both sides of the resulting incquality, get
L Vi) +
Lnd (2phe + 2L2
c++ S en7 h4
2
(1 (ta)
2
I 6 3 3 VV.
Next, we bound the consensus error V₁ using the following lomma:
Lemma 5. Let Assumption 1, Assumption & (SGC) hold. Assume the nodes follow Algorithum 1 with stepsize
1) S 3kL and define (() = max. Then,
V, E 3n Kp
2p
Σ hj-
(14)
(=r(t)
18

---

Published in Transactions on Machine Learning Research (03/2024)
Proof.
V = E n
||x - 1
i=1
Σ (
Σ )=
- k2
Σ
ng )|²
(z7(1)
1-1
Σ
EI
Σ
+ Σ ng' 1|
1=1
(0)(
(mr(1)
(10)
2
Σ
EI| Σ 7V
X=1
j=r(()
1ip(1 - -0))
(
2 S -(1))p
{}))(())
(=)
S 2t - -(1)lp
Σ Σ
E
- -
(()(
4-1
1-1
s 2nn Kp
Σ
hi + 2n0 K Kpl?
Σ Vs.
(=1(()
j=r(1)
Since 1) 5 -. we have
3k
1-1
(-1
V s 27
Σ j=r(1)
h1
+
Σ Vj.
4Kp
j=r(()
Unrolling all V,,j = -(f)...., - 1, and noting that p 2 1, we have
Σ
V/+ + 2 Kp
Σ hj
4Kp j=r(1)
j=r(1)
1-2
1-1
t-2
t-2
Σ
Vj2n²Kp Kp
Σ
hi +
Σ
V1 + 2n² Kp
Σ
hT)
4Kp
4Kp 4Kp j=r(()
(=)
(=r(t)
j (=イ(()
1-1
.... (1 + 4Kp
k 2k2 Kp
KKp
Σ
hj
(=r(1)
i-1
S <31RKP Σ h5.
j=r(()
19

---

Published in Transactions on Machine Learning Research (03/2024)
To complete the proof of Theorem we combine (13) and (14) by applying telescoping (13) to get
1
2
1
h4
co
n
Σ
Vi
3
f=
(14)
T-1
S Co + 2n 2
11
KP
Σ hj
j=r(1)
T-2
+()+K
= = + 21) K2
hy
1
t=
T-2
< + 211 K2
h
1=0
(n' (
T-1
e 9p
+
h4
1=0
T-1
2
S + 9
h4-
t=0
Therefore, we have
T-1
9eo n
9e0
h4 S
min
h S
T
0S1ST-1
n,T
t=
This completes the proof for Theorem
B Experimental Verification of Assumption 4 (SGC)
Here, we perform experimental verification of Assumption (SGC) with the same problem setup as Section 4.1. For verification purposes, we use centralized SGD to train the aforementioned ResNet18 neural network the Cifar10 dataset for total of 1000 epochs, and we plot the global gradient norm and the maximum of per-sample gradient norm of the model well as the ratio between the two gradient norms in Figure 6.
It is shown in Figure that throughout the training, the ratio r max,, (V..)) never exceeds 4000, and after a transient phase quickly stablizes aroung 500. Since Assumption requires that
[V([]]
Eg BE.DD.I (VXx, < p Vi,
while we always have
E ES [x((xx + < max (x)x
&
and in most cases
Bg.,D. (f & max Vxxxx
we have verified that Assumption (SGC) a valid assumption for over-parameterized models in practice.
C O(exp(-T)) Convergence for Strongly Convex Loss Functions
For strongly convex loss functions, an error bound of O(cxp(-T)) can be achievod under the over-parameterized setting, where T the total number of iterations. Before our work, the best-known convergence rate was O(exp(-T/K)) (Qu et al., 2020; Koloskova al., 2020).
20

---

Published in Transactions on Machine Learning Research (03/2024)
4000
Global gradient
sample gradient
Ratio between two gradient norms
3500
3000
Log of gradient norm
2000
1500
-8-
0 200
400
600
800
1000
Number of epachs
Figure 6: The global gradient norm, maximum of per-sample gradient norm and the ratio between them vs. number of epochs. The red line is the global gradient norm and the orange line the maximum of per-sample gradient norm, they plotted in log scale whose values correspond tothe y axis the left. The blue line is the ratio between the two norms whose value correspond tothe y axis on the right.
Theorem 3 (Strongly convex functions). Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with > 0. If we follow Algorithm with stepsize 1) S L/L, we will have
B|xx(7 (T) x2 11))))))))))) |xx x1,
where x(1) = Ei x: is the average of all nodes' iterates at time step t. As a special case, if we choose = 1/L, then
E (T) x21 s (1 4) (0) xx1
(15)
It was shown in Qu et al. (2020); Koloskova et al. (2020) that Local SGD achieves a geometric convergence rate for strongly convex loss functions in the over- parameeaaeter setting. However, both Qu al. (2020) and Koloskova et al. (2020) give an O(exp(-T//M (K) convergence rate, while convergence rate is O(exp(-7)) The difference between these two rates significant because the former rate implics that local steps do not contribute to the error bound (since the convergence rate essentially depends
the number of comnunication rounds R = T/K). In contrast, the latter rate suggests local steps can drive the iterates to the optimal solution exponentially fast. The difference between the rates in Qu et al. (2020); Koloskova et al. (2020) and Theorem 3 can be explained by the fact that Qu et al. (2020); Koloskova et al. (2020) use a smaller stepsize of 7 (xZZ), while our analysis allows a larger stepsize of 1) 1/L.
C.1 Proof of Theorem 3
Let x* arg min fxx). From Assumptions 3 (Interpolation) and 2, have ff ( 0, which implies x* E arg min &x), ei [n], & E Ωz
We first bound the progress made by local variables x; in one local SGD updale as follows:
Lemma 6. Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with μ 0. If we follow Algorithm with stepsize n S t, we will have
x & - 1²1
(16)
21

---

Published in Transactions on Machine Learning Research (03/2024)
Proof.
++ x22
E2 X
ee; ||X - x - f 1
||x]
x11 #122-2nyxx; x", vs(((()) + + + 2/11
(2)(8)
S
||x - x'11 - (n(f((x,)) -((x')))x))))))))()))) -
+ g <) f((xx ,()1
= (1 n,))| x12 (2n 2TTx) - ,((x'))
(n 2 (1 - - - x²1 -x11?
Using Lemma and Proposition 4, we can bound the progress made by x one communication round as follows:
Lemma 7. Let Assumption 1, Assumption 2 and Assumption 3 (Interpolation) hold with > 0. If we follow Algorithm with slepsize y S t. we will have
E||x(++1) - x=1 S (1 E x11
= 0, 0, R 1.
Proof.
E (r+1)
x-1 = B1|
(r+1)K xx11
1=1
(22)
E||x; (r+1)k x21
(16)
Σ (1 mu11a K < 11
= (1 - nu)
K x - x²1
C
The proof of Theorem 3 now follows by simply noting that
Bl|x(T) x+ 1| E x 112
< (1 nn) 14 E R- 1) -x11
... S (1 nh1r x0) x
C.2 Perceptron for Linearly Separable Dataset, Strongly Convex Case
To evaluate the performance of Local SGD for the paraamteeeter model with strongly-convex loss functions, we adopt the same experimental setup as Section 4.2 but add a correction term to the squared- hinge loss to make it strongly convex and run another experiment on the pathologically partitioned dataset. The result shown in Figure The O(exp(KKR) Ocxxp(-T)) convergence rate can be observed from the figure, validating result in Theorem 3.
22

---

Published in Transactions on Machine Learning Research (03/2024)
Strongly Convex
Local steps K- 50
Local steps K= 20
steps 10
steps
10a
steps K-
Local steps K=
Taining
10-1
10-3
10-3
20000
40000 60000 80000 100000 120000 140000 Communication Rounds: R
Figure 7: Local SGD for the over- per-paaameterized model with strongly-convex loss functions. Training loss vs. communication rounds with different local steps under the pathological data partition regimes. Training loss is in log scale.
D Discussion on the proof in Zhang & Li (2021)
In Section 9.3.2. Discussion on Theorem 3 of the paper Zhang & Li (2021), the authors stated that M, 2 min; Ii , which essential to their result the Discussion, which can be interpreted as an O /T convergence rate. However, this inequality does not hold. A simple counterexample is when of the local nodes finds the optimal point after the first local step, in which case hi,n (0) = and hi, = 0 for all t 1,2,.. Ti 1, and Ma min, a; ET--1 ht,(t) I as z.. However, this contradicts the claimed inequality M, 2 min; T. T
23


Reviews:
[{"review_id": "ieOfD4giZD", "reviewer": "Reviewer_SVJV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strength*: The paper derives novel convergence bounds for local SGD, which improves general understanding of local SGD performance in over-parameterized setting.\n\n*Weaknesses*: see below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper establishes new convergence results for local SGD. The results are derived under over-parameterized setup. The convergence rates improve upon the existing best known rates for convex and nonconvex loss functions. Some problem instances are given to imply the results are tight.  Numerical experiments validate the results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The comparison with convergence results between local SGD and SGD in over-parameterized setting is insufficient. It particular, how the analysis, assumptions and results differ from (Ma et al 2018, Vaswani et al 2019). \n\n2. Because the main contributions of the paper is the improved convergence rate, it would be better to have a table summarizing the results, along with the existing works. The table shall compare the convergence bounds and assumptions. \n\n3. More discussions on the assumptions are needed. In particular, when Assumption 2 and 3 are satisfied. The paper referred to (Vaswani et al. 2019) for examples, which is unclear and insufficient.\n\nOther minor comments:\n\n1. The assumption that f is lower bounded, L smooth and stochastic gradient is unbiased should be put in Assumption block. \n\n2. Page 4 Section 3 typo: nodes\n\n3. In Algorithm 1, step 4 should be nabla f_i? Also, Step 7 should be sum_j x_j? Step 6-10 should be moved outside the loop of update?\n\n4. In Theorem 1, should be algorithm 1.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UIv9HcwR65", "reviewer": "Reviewer_NakU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Rigorous theoretical analysis with clear assumptions.\n- Tight lower bounds confirming analysis.\n- Extensive experiments on deep nets validating theory.\n\nNo major weaknesses were found.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Main Arguments:\n- Modern machine learning models are often over-parameterized and can interpolate the data by driving the empirical loss to zero. \n- Existing analysis of Local SGD (FedAvg) convergence does not fully explain its faster convergence compared to Minibatch SGD in practice when training large neural networks.\n- By assuming interpolation, the paper provides tighter convergence rates for Local SGD that depend on the total number of iterations T (compared to existing results depending on number of nodes n).\n- This partially explains the faster convergence of Local SGD and effectiveness of local steps when training large neural networks.\n\nContributions:\n- For general convex functions, proved error bounds of O(1/T) under a mild data similarity assumption and O(K/T) otherwise (improving on best previous O(1/sqrt(nT))).  \n- For non-convex functions, proved an error bound of O(K/T) (improving on best previous O(1/sqrt(nT))).\n- Provided problem instances showing the analysis is tight up to constants for small stepsizes. \n- Validated theory with large-scale experiments on deep neural networks exhibiting the O(1/T) convergence.\n\nKey Findings:  \n- Local steps can speed up Local SGD by a factor of at least 2 even in the worst case.\n- Slight similarity in local functions is critical for the fast O(1/T) convergence rate.  \n- Experiments show two-phase convergence: O(K/T) initially and O(1/T) later when close to optimum.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please fix typos in the following places:\n- Theorem 2 stepsize bound;\n- Page 4: There is a typo after the phrase \"The server then computes the average of all nodes...\".", "broader_impact_concerns": "This work is primarily theoretical in nature. Hence, there is no identifiable potential for negative societal impact arising from this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tWHGB8J7hD", "reviewer": "Reviewer_cCmn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n**1.** The manuscript is well-composed, with a clear presentation and delineation of contributions.\n\n**2.** The paper addresses an important and already long-standing problem of understanding a practical distributed training method: Local SGD.\n\n**3.** Analysis is done for various settings: strongly convex, convex, and non-convex loss functions.\n\n**4.** Experiments are performed for both a synthetic problem and a practical task with real data.\n\n# Weaknesses\n\n**W1.** The paper falls short in demonstrating a decisive improvement in performance through the use of local steps, akin to previous studies on Local SGD. The convergence bounds are optimized for the minimum $K$, leaving ambiguity about the additional methodological insights derived from this research. Besides, the discussion after Theorem 1 says that \n> local steps can speed up the convergence of Local SGD by at least factor 2\n\nHowever, the explanation provided is unclear. It does not say how exactly the number of local steps affects convergence.\n\nTheorem 2 doesn’t demonstrate any advantage of using local steps, showing results typical for local methods, which necessitate scaling the step size inversely to the number of local steps. I am curious if this result improves upon previous studies.\n\nHowever, the conclusion says that\n> Moreover, we validated the eﬀectiveness of local steps in **speeding up the convergence** of Local SGD in various settings both theoretically and using extensive simulations.\n\nwhich seems to be not fully supported.\n\n**W2.** The lower bound results rely on a highly specific set of parameters $n, R$, limiting their general applicability.\nIt is known that Gradient Descent can provably diverge for step size $\\eta > 1/L$ (Nesterov, 2018). Thus, it would be odd to expect a different result for a variation of this method.\nProposition 2 proof raises a question: what if there is a small scaling factor in front of $2/(LK)$? Can this fix the issue of non-convergence? Moreover, I do not see how it implies the conclusion of Remark 1 that a step size has to be $\\eta \\leq \\mathcal{O}(1/K)$.\n\n**W3.** Validity of the interpolation condition in practice is questionable. It restricts the local gradients' values at the optimum but does not necessarily correspond to near-zero values of the local losses, which seems to be observed in experiments. It's also unclear if the Strong Growth Condition (SGC) is realistic for distributed deep neural network training. The paper presents these assumptions as more suitable for such problem setting. However, their validity is not explored in experiments.\n\n**W4.** The experimental results display a multi-phase behavior of training loss reciprocal not anticipated or explained by the provided theoretical findings. The authors claim that their theory shows improvements coming from using local steps. However, Figure 1a clearly shows that in the first phase, it is not really the case.\n\nThe second experimental results implication seems to go against a common wisdom of reducing the number of local steps throughout optimization. The claim \n> enforce more frequent communication at ﬁrst\n\ncontradicts the results of Figure 1a, which shows that doing more than 1 local step does not bring improvements.\n\n## Questions\n**Q1.** Assumption 1 is a stronger version of the standard (strong-)convexity typically used in distributed optimization. It requires the inequality to hold for any realization of random variables $\\xi_i$. Why this modification is used? Is it necessary for obtaining the results, or it can be done for a more standard assumption as well?\nThe same question holds for Assumption 2. If $\\mathcal{D}_i$ is a uniform distribution typical for distributed learning settings leading to a finite-sum scenario, then the interpolation condition has to hold for every single local data sample and not just for the average local loss $f_i$.\n\n**Q2.** Can the presented results be obtained as a special case from a more general analysis of a non-overparametrized setting?\n\n**Q3.** Why the data was distributed across clients exactly in this way?\n\n**Q4.** Why are the convergence curves in Figure 4 of the Appendix truncated prematurely for smaller numbers of local steps?\n\n### Minor\n\n1. The paper has non-functioning links and references, and the outline isn't displayed properly. Local SGD, referred to as Algorithm 1, is incorrectly labeled as Algorithm 0.\n\n2. > Furthermore, it was shown that a mini-batch size larger than some threshold $m^*$ is essentially helpless for SGD\n\nPlease support this claim with a direct reference. Ideally, with a mathematical explanation as well.\n\n3. It is recommended to add details on the step size tuning, as the current description limits reproducibility.\n\n4. Paper organization is unconventional with the Conclusion followed by Theorems’ proofs, which are typically put together in the Appendix. If the authors want to highlight a novel analysis technique, it would be helpful to provide a proof sketch with core insights.\n\n5. The abstract’s claim that Local SGD is analyzed in a *“heterogeneous data setting”* is misleading, given that the interpolation condition actually restricts data heterogeneity as it characterizes not only the model properties but the local data distributions as well.\n\n#### Typos\n\nEnd of page 4: nodesâĂŹ\n\nPage 6, line 2: “le” -> \\leq\n\n___\n\nNesterov, Y. (2018). Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Appli-\ncations. Springer, Cham.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the area of distributed stochastic optimization, specifically examining the effectiveness of Local SGD. It merges $L$-smoothness and over-parametrization with data similarity conditions, addressing both (strongly-)convex and non-convex scenarios. Theoretical results presented here advance beyond previous studies and are supported with some lower-bound examples. The paper also includes numerical experiments to corroborate its mathematical assertions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**C1.** The paper should clarify how its analysis differs from prior works, elaborating on the technical novelties and what it is based upon.\n\n**C2.** Definition 1 appears non-standard in the context of distributed learning literature. A more comprehensive discussion on this, particularly if it acts as an additional assumption on local losses $f_i$, would strengthen the paper.", "broader_impact_concerns": "No for this work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main contributions are the effect of overparameterization in improving the convergence of local SGD. While the effect of overparameterization has been known for SGD, its power in accelerating the convergence has not been studied for local SGD. For both convex and nonconvex problems, the paper shows that local SGD in overparameterization setting achieves the rate $O(K/T)$, which are faster than the existing rate $O(1/\sqrt{nT})$ without overparameterization ($K$ is the number of local steps, $T$ is the total number of iterations and $n$ is the number of nodes). Furthermore, the paper derives rate $O(1/T)$ under a mild data similarity assumption. The paper also presents two problem instances, which show that the derived convergence rates are tight up to constant factors. These results are interesting to understand why local SGD achieves impressive performance to train overparameterized models. All the reviewers appreciate the theoretical contributions.

Minor comment:

Abstract ", These bounds improve" should be ". These bounds improve"
Decision: Accept (poster)