On the Choice of Learning Rate for Local SGD
Authors: Lukas Balles
Prabhu Teja S
Cedric Archambeau
Venue: Accepted by TMLR ()

Abstract: Distributed data-parallel optimization accelerates the training of neural networks, but requires constant synchronization of gradients between the workers, which can become a bottleneck. One way to reduce communication overhead is to use Local SGD, where each
worker asynchronously takes multiple local gradient steps, after which the model weights are averaged. In this work, we discuss the choice of learning rate for Local SGD, showing that it faces an intricate trade-off. Unlike in the synchronous case, its gradient estimate is
biased, with the bias dependent on the learning rate itself. Thus using learning rate scaling techniques designed for faster convergence in the synchronous case with Local SGD results in a performance degradation as previously observed. To analyze the manifestation of this bias, we study convergence behaviour of Local SGD and synchronous data-parallel SGD when using their optimal learning rates. Our experiments show that the optimal learning rate for Local SGD differs substantially from that of SGD, and when using it the performance of Local SGD matches that of SGD. However, this performance comes at the cost of added training iterations, rendering Local SGD faster than SGD only when communication is much more time-consuming than computation. This suggests that Local SGD may be of limited practical utility.

Published in Transactions on Machine Learning Research (01/2024)
On the Choice of Learning Rate for Local SGD
Lukas Balles*
lukas. Sabsssballees@llehh-llh......
Aleph Alpha, Heidelbery, Germany. Work done at AWS.
Prabhu Teja S
prbutejjo@lmazzn.dee
Amazon Web Services, Berlin, Germany.
Cédric Archambeau
cedric. Sadric.rcchambeav@@hhllsiin ai
Helsing, Berlin, Germany. Work done at AWS.
Reviewed on OpenReview: https: openrevew.. net/ pormfo id- DPuur
Abstract
Distributed data-parallel optimization accelerates the training of neural networks, but re- quires constant synchronization of gradients between the workers, which can become a bot- tleneck. One way to reduce communication overhead is to use Local SGD, where each worker asynchronously takes multiple local gradient steps, after which the model weights are averaged. In this work, we discuss the choice of learning rate for Local SGD, showing that faces an intricate trade-off. Unlike in the synchronous case, its gradient estimate biased, with the bias dependent the learning rate itself. Thus using learning rate scaling techniques designed for faster convergence in the synchronous case with Local SGD results in a performance degradation as previously observed. To analyze the manifestation of this bias, we study convergence behaviour of Local SGD and synchronous data-parallel SGD when using their optimal learning rates. Our experiments show that the optimal learning rate for Local SGD differs substantially from that of SGD, and when using it the perfor- mance of Local SGD matches that of SGD. However, this performance comes the cost of added training iterations, rendering Local SGD faster than SGD only when communication is much more time-consuming than computation. This suggests that Local SGD may be of limited practical utility.
1 Introduction
Gradient-based optimization techniques like Stochastic Gradient Descent (SGD) (Robbins Monro, 1951) and its variants (Qian, 1999; Sutskever et al., 2013; Kingma Ba, 2015) have contributed enormously to the success of deep learning models in the past decade. With increasing scale of both models and datasets, distributed training has become commonplace. The predominant distributed training paradigm is dala- parallel training, where each of K workers computes gradient using an independently drawn minibatch of data in parallel. These individual gradients are then averaged across all workers before an optimizer update is applied, effectively increasing the batch size by a factor of K.
The use of larger batch sizes results in an improved gradient estimate, its variance being inversely proportional to the total batch size (Bottou et al., 2018). However, fully capitalizing on this reduced variance requires higher learning rates, Goyal et al. (2018) propose to increase the learning rate linearly with the number of workers. The goal is to achieve what called perfect linear sealing, i.e., to converge in K times fewer iterations when using K workers. This has been shown to succeed for moderate number of workers,
Equul Contribution.

---

Published in Transactions on Machine Learning Research (01/2024)
K 24, H
K 8, =
K = 16, H =
2
K
Mothod
Autoscaled Accum SGD
16
Autowcaled
K = 16, H
Local SGD
[
2¹
50
63
29
K= 21, H
27
2"
K 24, 32
Ratio of Communication time to Computation time
K = 8, 1I = 32
K 16, 11 = 32
Figure 2: When is Local SGD useful in practice? With adaptive learning rate scaling methods mod- ulating the number of training iterations, we exam- ine when Local SGD (LOCAL-ADA) faster than SGD (Acc-ADA). We see that Local SGD is faster than the synchronous case only when communication costs much more than computation (m 2), thus making Local SGD of utility only in scenarios of extreme com- munication costs. We show on x-axis the communi- cation to computation costs of a hypothetical system, and pseudo-wall clock time on y-axis (see $6.2). The plots in shades correspond to various H, and the dark lines to the minimum skyline for each cost factor and K across all values of H. The cross-over from SGD to Local SGD happens only for high costs (m).
LOCAL-ADA
LOCAL-LIN
Why is Local SGD's performance lower than SGD? Existing experimental works on Local SGD (Lin et al., 2020) use linear scaling that was designed for synchronous SGD and thus result in poorer performance when number of local steps H is large (LOcAI--LIN). When using automatic learning rate scaling method (LOCAL-ADA) based on optimal learning rates, we find that Local SGD performs sim- ilarly for a large range of K and H. These results are for Wide ResNet-28 being trained on ImageNet32. Each line represents K, H configuration and accu- racy increases moving away from the center.
Figure 1:
but performance deteriorates for large K. In general, using larger K roquires a learning rate increase by factor smaller than K and, consequently, training for more than 1/K times the number of iterations. AdaScale (Johnson et al., 2020) uses estimates of gradient variance and magnitude to compute a local scaling factor for each update step, which is used to modulate the learning rate, as well as to stretch the number of training itcrations.
While data-parallel training can significantly speed up model training, it necessitates synchronization among workers at each iteration. As the number of workers increases, the communication time required to syn- chronize begins to dominate the computation time (see Ortiz et al., 2021, Figure 1). This is exacerbated by compute infrastructure with low bandwidth and/or high-latency connections between workers. A straight- forward remedy for communication overhead is gradient accumulation, where each worker averages gradients from 11 > 1 minibatches locally before synchronization. However, this increases the effective batch size by factor of K x H, which quickly enters regime of diminishing returns. It has been shown to deteriorate performance, even for moderate values of H, when using linear learning rate scaling (Lin et al., 2020).
An alternative approach to reduce communication overhead is Local SGD (Stich, 2019; Yun et al., 2022). which performs H > 1 gradiont steps locally on each worker, after which the model weights are averaged and syuchronized across K workers. While theoretical work has shown that Local SGD converges al. the same rate as synchronous data-parallel SGD, empírical studies (Lin et al., 2020; Ortiz et al., 2021) have observed deteriorating model performance when using Local SGD.
In this paper, we study this apparent discrepancy between the theory and empirical findings on Local SGD. We, specifically, answer the following three questions:
2

---

Published in Transactions on Machine Learning Research (01/2024)
1. Why does Local SGD's performance lag that of SGD? Empirical works that study the performance of Local SGD use learning rate scaling methods borrowed from SGD literature (see $2). We surface that this is problematic for Local SGD. As in the synchronous case, increasing the number of workers reduces the variance of the virtual gradient estimate used by Local SGD, which warrants a learning rate increase. As we show, Local SGD's gradient estimate is biased, and the bias depends on the learning rale itself. Thus, a naive application of known learning rate scaling techniques may adversely affect the quality of Local SGD's gradient estimate and, thus, its convergence behavior; this explains the results by Lin et al. (2020); Ortiz et al. (2021) who use linear learning rate scaling and show that Local SGD performs worse than standard SGD (see $4).
2. Can the performance gap between Local SGD and SGD be bridged? We examine the optimal learning rates for Local SGD and SGD, and devise automatic learning rate scaling methods that scale the learning rate based on gradient statistics. In this process, we recover the well-known technique for SGD called AdaScale (Johnson et al., 2020) that was previously proposed as a heuristic (see $5). We show that using our proposed scaling technique, Local SGD reliably maintains the target accuracy across a wide range of values for K and H as shown in Figure 1 in blue. This is in contrast to previous works that observe deteriorating performance when using Local SGD with linear learning rate scaling as shown in the green curve in Figure 1 (see $6.1).
3. When is Local SGD empirically preferable to SGD! When using automatic learning rate scaling mothods, we show that Local SGD converges faster than large batch SGD realized through gradient accumulation for large H. However, this does not trivially translate into wall-clock speedups, as these automatic learning rate scaling methods also modulate the number of training iterations. In Figure 2, we show that Local SGD improves wall-clock time convergence compared to synchronous data-parallel SGD, when comparing under optimal learning rate scaling, only in extreme scenarios of communication being substantially more time-consuming than computation. This finding casts fundamental aspersions on the practicality of Local SGD especially when scaling only the learning rate, one find missing in prior works (sce $6.2).
2 Related Work
The literature on distributed optimization is vast, so we focus on the most closely related works. For instance, we do not discuss fully asynchronous methods like HogWild (Recht et al., 2011) or approaches to compress gradients for communication (e.g., Alistarh et al., 2017; Basu et al., 2019). Cao et al. (2023) present a survey of such methods.
Learning rate scaling To our knowledge, the first practical recommendation for learning rate modulation in distributed optimization was proposed by Krizhevsky (2014), who introduced linear scaling rule in terms of the number of workers. They found it to work well for small numbers of workers but observed performance drops for larger numbers. Goyal et al. (2018) showed that lincar scaling could be made to work at larger scales with the use of a warmup phase that gradually increases the learning rale towards the target value. They found the duration of the warm-up to be critical to the performance. As an alternative to linear scaling, Krizhevsky (2014) as well as Hoffer et al. (2017) experimented with a less aggressive square-root heuristic, which ultimately did not prove successful. Going beyond simple scaling factors, AdaScale (Johnson et al., 2020) adaptively scales the learning rate based on estimates of the gradient, variance and magnitude and has been shown to retain performance for a much higher number of workers. We will discuss this method in detail in $5. Methods for improved generalization, like cyclical learning rate (Smith, 2017), can be seen orthogonal to our work, as we investigate optimal scaling factors for the learning rates.
Large-batch optimizers Optimizers like LARS (You et al., 2017) and LAMB (You et al., 2020) have been proposed with the explicit goal of handling large batch sizes, but their utility has been questioned. Nado et al. (2021) find that, with suitable hyperparameters, both SGD and Adam match the performance of LARS and LAMB. Basod on the assumption that small batch training generalizes botter, Adasum (Maleki et al., 2021) tries to mimic small batch training while using larger batch sizes using a more complex operation fuse the gradients instead of summation. Refuting the claims that the stochastic nature of SGD is important
3

---

Published in Transactions on Machine Learning Research (01/2024)
for its performance, Geiping et al. (2022) show that with explicit regularization, even full-batch gradient descent can attain the performance of small batch SGD.
Local SGD The method now known LocalSGD has been studied both empirically (Povey et al., 2014; Zhang et al., 2016; Lin et al., 2020; Gu et al., 2023), and theoretically (Dekel et al., 2012; Zhou & Cong, 2018; Stich, 2019; Haddadpour et al., 2019; Khaled et al., 2020; Woodworth et al., 2020; Deng et al., 2022; Yun et al., 2022). Deep learning models trained using Local SGD have been shown to achieve lower performance than using fully synchronous training. Lin et al. (2020) remedy this by post-Local SGD, where they switch to Local SGD after training the network with synchronous SGD for certain number of iterations. Ortiz et al. (2021) show that the point of the switch is a sensitive hyperparameter. They change the global averaging step to moving average in Wang et al. (2020) and find it partially alleviates that sensitivily. Note that both Lin et al. (2020) and Ortiz et al. (2021) attempt to achieve perfect linear scaling (d.e., reducing the number of iterations by a factor of K) and apply the linear learning rate scaling rule of Goyal et al. (2018) to Local SGD. A closely related work by Wang & Joshi (2019) shows that the number of local steps H needs to be decreased as model reaches closer to convergence. They consider a fixed known learning rate, and optimize H, whereas we do the opposite. Thus, the two approaches are flip-sides of the same coin. Recently, Gu et al. (2023) find that Local SGD performs like SGD when using small learning rate and training long enough. Hence, this scenario while useful for analysis, is of limited utility, as in practice we are interested in getting a high enough performance in the shortest time possible.
Federated learning A plethora of Local SGD variants have been used and studied in federated learn- ing (Wang et al., 2021), where workers access fixed subsets of data, which are not necessarily iid. Under these conditions of data heterogeneity, Murata & Suzuki (2021) remark that the gradient estimate of Local SGD is biased but do not quantify it. Works in federated learning that examine learning rate scaling have focussed on heuristics like linear and square-root scaling presented above (e.g., Charles et al., 2021). Data heterogencity poses additional challenges compared to our setting and is not considered here.
3 Preliminaries
In this section, we introduce some preliminary material and define notation.
3.1
Problem Setup
Training a neural network requires solving an empirical risk minimization problem with an objective of the following form:
1 N Σ f(w;x;);
f(w)
(1)
where are the model weights and f(;x;; denotes the loss of the i-th training example. Throughout this paper, we assume Í to be I-smooth, i.e., its gradient is Lipschitz: (VV[(w)-V//// V/(w]] < T.lww' - w for all
w, w' in the domain of f. This implies the well-known local quadratic bound f(w') & f(w) (Ww"TW""
w) + L w' w|?, which we will use in our analysis.
Gradient descent iteratively minimizes the objective with updates of the form W = w. - W ((w,), tt is the learning rate at iteration t. For large datasets, it is inefficient to compute the gradient over all data points in each iteration. Instead, we resort to Stochastic Gradient Descent (SGD), where we approximate the gradient using a stochastic gradient
where
1 Σ v((wx))),
(2)
B
IEB
computed a randomly-sample minibatch B C (1,2... ... N} of size B B & N.
4

---

Published in Transactions on Machine Learning Research (01/2024)
In synchronous data-parallel SGD, each worker computes stochastic gradient g using independent minibatch. These are then averaged, g: = Σ gi before an optimization step is applied. Each gi is k==
an unbiased estimate of the gradient, [g V = V[(w:) with variance that we denote as of :- Var,(g/]. Consequently, the averaged gradient g. unbiasedly estimates V with variance of oi/k. Here and throughout this paper, E, denotes the conditional expectation given w Ak E (1,2... K}.
3.2 Local SGD
Synchronous data-parallel SGD is equivalent to each worker taking local gradient step, followed by an eraging of the model weights. This requires synchronization of the weights after every iteration, which may cause a large communication overhead, depending on the number of workers and the compute infrastructure.
In Local SGD, each worker takes H 1 local gradient steps before the weights averaged:
Ek (w. mgt), H 1
k 2+1
R w
k=
ng.
otherwisc.
This reduces the communication frequency without affecting the rate convergence (Stich, 2019). practice, each of those H iterations can be replaced by more complex update step, such as using momentum even adaplive gradient methods like Adam (Singh al., 2021; Wang et al., 2020).
4 Local SGD's Learning Rate Conundrum
The analysis of Local SGD is based on the virtual sequences
K W
W. ==
k g
(4)
K
K
k=1
which are the averages of the per-worker itcrates and gradients at each iteration. These sequences tools for the mathematical analysis and are not computed by Local SGD at every ileration. They evolve W = w. - T... resembling an SGD trajectory with an "implicit" gradient estimate g..
Theoretical works on Local SGD show that this sequence behaves almost like synchronous data-parallel SGD under certain restrictions on the learning rate. This indicates that the implicit gradient estimate gi approximates the gradient V)(w:)) just as well as a hypothelical standard stochastic gradient. gr with E, [: = fw:)) and a variance of
E. [S(W,)]]] of K
(5)
The meaning of "just as well" is relatively opaque in existing works on Local SGD. Here, we make it explicit. As we will see, the quality of gr is influenced by the preceding steps taken since the most recent synchronization point. We, therefore, consider single constant step size y across H consecutive steps, starting from synchronization point, and assume local bound on the gradient variance. This is formalized as follows.
Assumption 4.1. Assume run H consecutive steps of Local SGD using constant step size 7, starting from synchronization point t: H t. Assume the gradient variance across these H steps is bounded, i.e., for all & E [K] and i' E t H), we have Var ig* < की for some ōt
With that, we can derive bound on the mcan-squared error (MSE) of Local SGD's implicit gradient estimate g. The proof is given in Appendix C.1.

---

Published in Transactions on Machine Learning Research (01/2024)
Proposition 4.2. Under Assumption 4.1, the MSE of Local SGD's implicit gradient estimate (Eg. 4) sat- isfies
- o K (H-1)L?
Ex gr - vf(ww))ll
(6)
for all t' E tt
Varionce
Bias
The bias originates from the fact that the per-worker gradients, g in Equation (4), are computed at slightly different locations in the parameter space duc to differences in the local trajectorics. The extent of this diffusion depends on the number of local steps and, crucially, the learning rale y used in preceding steps.
The published convergence theory for Local SGD assumes restrictions to the learning rate y which control the bias term such that the error dominated by the variance term and its l/K behavior. Therefore, those results have to be understood in the following way: For given value of H, there small enough lcarning rale y at which Local SGD converges at the same speed as synchronous data-parallel SGD. However, this learning rate will not be optimal, neither for synchronous data-parallel SGD nor for Local SGD.
Equation (6) shows that Local SGD faces fundamentally different trade-off when setting the learning rate compared to synchronous data-parallel SGD. Increasing K decreases the variance, which warrants a learning rate increase. However, larger learning rate increases the bias term
Empirical studies (Lin et al., 2020; Ortiz et al., 2021) observing the poor practical performance of Local SGD for large values of H could in part be explained by this. Since they adopt the linear scaling rule for Local SGD, for large values of K and H, the bias term will dominate the total error in Equation (6). The same argument explains the observations of Wang & Joshi (2019); when the learning rate fixed, the only way of reducing the gradient error (and therefore facilitating convergence) to reduce the commuiccation interval H, leading to their heuristic. In the next section, we propose learning rale scaling rule for Local SGD that directly tackles the trade-off surfaced in Equation (6).
5 Adaptive Learning Rate Scaling for Synchronous and Local SGD
To gauge the real potential of Local SGD, we need to be able to scale its learning rate appropriately. We have seen in the previous section that Local SGD faces fundamentally different trade-off with respect the learning rate, compared to synchronous SGD. In this section, first derive optimal learning rate scaling technique for SGD. We then carry-over the ideas to derive an optimal learning rate scaling technique for Local SGD.
5.1 Optimal learning rate scaling for SGD AdaScale
From the assumption of Lipschitz gradients $3.1, satisfies
L 7. E
Bis(we+1)] S f(w.) - 74 f Elg.
El
(7)
for two consecutive iterates W., We+1 with an SGD step. The optimal learning rate that maximizes the expected decrease over one step is given by
1
2
|| +
(8)
The optimal learning rate requires L which is difficult to estimate in practice, and thus not used in practice. Consequently, when the variance of our gradient estimate is reduced by factor of 1/K due to an increase in number of workers to K, the optimal learning rate changes by the following factor:
|
2 + o?
Tt
E {).
(9)
|

---

Published in Transactions on Machine Learning Research (01/2024)
This is the gain ratio proposed by Johnson et al. (2020). Thus, we reinterpret the AdaScale gain ratio the ratio of optimal learning rates for the case of K workers to 1 worker. We present detailed derivation in Appendix B.
For fil < of we recover the linear scaling rule of Goyal et al. (2018) with a gain ratio of = K. In practice, however, the gain ratio will be smaller than K. When 12 > of the gradient estimate is already very accurate, and the gain ratio is close to 1, implying that using a higher number of workers has no benefit. This is related to the concept of a critical batch size (McCandlish et al., 2018), which is the point after which further increase in batch size has diminishing returns in terms of convergence speed.
In addition to using r as a scaling factor for the learning rate, Johnson et al. (2020) propose the concept of scale-invoriant iterations. When using the standard linear scaling rule (Goyal et al., 2018), the iteration pass. However, AdaScale interprets the gain
counter is incremented by factor of K for ratio to be the effective number of workers used at iteration l. Incorporating this into the training process, they maintain an accumulator 5 Er= Tr, which replaces the standard iteration counter. Since re < K, the use of scale-invariant iterations increases the total number of passes over the training set (true epochs) and "stretches" " the learning rate schedule accordingly; see Lines and 7 of Algorithm 2 in the Appendix. Thus, scaling to a larger number of workers may necessitate more true epochs but will typically still result in substantial wall-clock time speedup, as shown by Johnson et al. (2020).
AdaScale estimates fill and of from the K iid per-worker gradients. We adopt their estimation procedure for our scaling method for Local SGD.
5.2 Optimal learning rate scaling for Local SGD- LocalAdaScale
We now derive a learning rate scaling method similar to AdaScale for Local SGD, named LocalAdaScale using the same principle underlying our derivation of AdaScale. We first derive an optimal step size for Local SGD, depending on the number of workers K and local steps H. gain ratio obtained by dividing by the optimal step size for the base case (K Hl = 1) and will be used exactly as in AdaScale, both as scaling factor for the learning rate, as well as the basis for a scale-invariant iteration counter.
Optimal step size for Local SGD Finding the optimal step size for Local SGD is more complicated than for synchronous data-parallel SGD since the step size used in previous steps influences the quality of the (implicit) gradient estimate used in the current step. To simplify this, we adopt Assumption 4.1 from 64 and consider H consecutive steps using a constant step size. As we show in Appendix C.2, these steps lead to an expected decrease in function value, which is bounded as follows:
7L
2L
7
E. < f(w,) - H [ +
2A 2
A,
(H (H-1)0? 1)02)
(10)
2
2
K
4
where
G. H
1
Σ E. Vf
13,
A=
1
Σ
E. V Vf
(11)
This expected function decrease bound features the cumbersome terms G. and A., which are expected squared gradient magnitudes along the trajectories of the virtual averaged iterates, and the per-worker iterates, respectively. These quantities are, in principle, dependent on n, since the choice of step size influences the gradient magnitude along that trajectory. We ignore this secondary effect by assuming A, z ||V /W:(()))l' G, independent of 17. This is fulfilled if the gradient magnitude stays approximately constant over the subsequent steps. We verify this experimentally in Figure 7 in the Appendix. Using this assumption gives approrimate upper bound:
B.[[(W(HH]] 5 S(W.) - H -
2
22 (H - 1)
G.
(12)
2
2
K
4
7

---

Published in Transactions on Machine Learning Research (01/2024)
In the expected decrease bound in Equation (10), the bias discussed in $4 manifests the 7 term. To illustrate that, Appendix D provides a similar H-step bound for synchronous data-parallel SGD, where this term is absent.
We derive an approximately optimal step size for Local SGD by maximizing the term x in Equation (12) leading to
1
2G.
7t
(13)
Get
52 + (Gi+
52) x +H(H-1)
See Appendix C.3 for derivation.
Gain ratio Analogous to our derivation of AdaScale, we can now define a gain ratio by dividing the optimal step size in Equation (13) by the base case (Hl K 1):
2 (G: + +
P: =
(14)
o² G + +V (0++ +3(1-1)G,ot
When 1, this gain ratio recovers AdaScale. To illustrate the difference in behaviors between AdaScale and LocalAdaScale, we plot the gain ratio p in Figure for increasing values of ///G. The larger the H, the smaller the gain ratio any given value for a 8²/a. This is explained by the fact that the gradient estimates get worse with H as in Proposition 4.2. Looking at the inset plot: for deterministic case, i.e., when there is no variance (ō² + 0) and thus no advantage to using multiple workers, see that, AdaScale and LocalAdaScale. For a large variance x² > G, the gain ratio approaches K for all values of H, rocovering the lincar scaling rulc. However, for larger H, it takes substantially higher values of /a/G for that regime to be reached.
1 for
H
AucalAdascale goin
Algorithm Automatic learning rate scaling for Local
16
64
SGD- LocalAdaScale.
2
Input: Initialization Wo, step-size Nt: #workers K, #local steps H, scale-inv budget S, t = = 0, 0, grad cache=I], p
10
1: while < S do
& Scale inv budget not exhansted. On each worker Compute g using batch of data. Gradient at t. if H then
2:
for E [K] do
Figure 3: LocalAdaScale gain ratio from Equation (14) with K = 8. We plot o²/G / on the x-axis and the gain ratio on the y-axis. In the inset, we show the plot for very small val- ues of the ratio o² ///G. We see that synchronous SGD (AdaScale with LocalAdaaSale H 1) have different scal- ing behaviour. AdaScale reaches its maximum gain factor for much lower values of o² than LocalAdaScale. In practice, this translates to Local SGD needing a lower learning rate, and more iterations than SGD. When this is vio- lated, Local SGD exhibits poorer convergence behaviour, further evidencing the arguments in $4
One step after model sync. gradient.
grad cache/k] = gf
6:
if H (++ then
> Average every H steps
w - 1 E
1) and Local SGD
Gf + grad stats(grad uund_sttasgra__aachho Compute p as Equation (14). wh+ w p7/.g.
Eq.15 Local update.
10:
11:
8 ststp
12:
1+t+1
13: return the last iterate w..

---

Published in Transactions on Machine Learning Research (01/2024)
Implementing LocalAdaScale To implement LocalAdaScale, we need to estimate G2 and o We take the approach of estimating these quantities only at synchronization points, and then using the resulting gain throughout the following H local steps. This is in line with our assumption that gradient magnitude and variance are approximately constant over H steps. At a synchronization point t, we have access to per-worker gradients computed al. the same location. This allows us to estimate gradient variance and mean exactly as in AdaScale:
K K - B
1 K :
0
| k=1
G. R
B
(15)
K
K
Following AdaScale, these estimates are smoothed using an exponential moving average for additional sta- bility. The algorithms LocalAdaScale and AdaScale are summarized in Algorithm 1, as LocalAdaScale is equivalent to AdaScale when H 1.
When using Local SGD, computing the estimates in Equation (15) requires the synchronization of gradients in addition to the weights, doubling the amount of data communicated. We partially alleviate this issue as follows. We cache the gradients computed right after synchronization and delay their communication (and thereby the computation of the gain ratio) until the next synchronization step. This way, we can synchronize weights and gradients simultaneously and only incur the lalency overhead once. Of course, this does not alleviate communication time incurred due to bandwidth limitations. Note, however, that we devisod AdaScale primarily as a tool for the analysis of Local SGD and did not further optimize our implementation. In future work, one could devise approximate versions of LdcalAdaSeale that avoid additional communication.
6 Experiments
Our experiments compare Local SGD to the gradient accumulation bascline under two scaling approaches, amounting to a total of four different methods. We compare these methods under identical numbers of intervals H:
workers (K) and commuiccationn/yyccnonnaa
1. Gradient accumulation of steps with linear scaling (ACC-LIN).
2. Gradient accumulation of steps with AdaScale (ACo-ADA).
3. Local SGD with H local steps with linear scaling (LocAi-L.IN). Local SGD with H local steps adaptive scaling (LOCAL-ADA), the method derived in $5.
4.
These four methods process the same number of samples between two consecutive synchronizations. ear scaling variants perform exactly n true epochs, where n is set based on prior work for each The lin- combination (see Appendix H.1). The adaptive scaling variants are allocated a budget of scale-invoriant epochs. Recall from $5.1 that this results in a variable number of true epochs.
For linear scaling, we follow prior work and perform linear warmup from h to the final value of Kahhase for 5% of the total iteration budget. For AdaScale, we use the implementation from FairScale (FairScale authors, 2021) which supports gradient accumulation. We compare these methods at different values for the number of workers K, as well the communication interval H. The latter used the number of local steps or accumulation steps, respectively.
We train a ResNet-18 (He et al., 2016) on CIFAR-10 (Krizhevsky, 2009), WideResnet-255 2aaeatt--222-(aouaaaaa Komodakis, 2016) on ImageNet--32 (Chrabaszez et al., 2017), and ResNet-50 on ImageNet (Deng et al., 2009; Russakovsky et al., 2015). We use a base learning rate schedules from previously published works, which are well-tuned to the respective architecture and dataset, which we take to be the optimal learning rates for the base case i.e., K = 1,H, = 1. Note that we are comparing learning rate scaling techniques and not specific learning rate schedules. Additional details of our experimental setup can be found in Appendix H.1.
(Zagoruyko &
In Appendix perform an ablation study showing that this delayed communication of gradients does alter the behavior of the methor significantly.
9

---

Published in Transactions on Machine Learning Research (01/2024)
6.1 Local SGD with automatic learning rate scaling LocalAdaScale maintains Target Accuracy
In Figure we show the test accuracy reached by the four methods. The target performance for cach experiment is the performance we get when training on one worker (K 1) with the standard hyperparameter settings (in Appendix H). For CIFAR-10 it is top-1 1 accuracy of 93%, for ImageNet32 it is top-5 accuracy of 69%, and for ImageNet it is top-5 accuracy of 93%. See Appendix H.1 for attributions.
We see that ACC-LIN breaks down very quickly for all datasets. Performance starts dropping when the total scaling (K x H) exceeds 32, in line with the findings by Goyal et al. (2018). This is overcome by using AdaScale (ACC-ADA), which maintains the target accuracy even for large H across all our experiments. In the Local SGD family, LOCAL-LIN performs considerably better but we still see notable drops in test accuracy around H 2 Finally, adaptive learning rate scaling for Local SGD) maintains the target performance across all and H considered. Thus, we have demonstrated that appropriate learning rate scaling can fix the performance gap of Local SGD observed in previous works using LOCAL-LIN (Lin al., 2020; Ortiz et al., 2021).
6.2 Should Use Local SGD?
We have established with the results in Figure 4 that. both Local SGD and gradient accumulation can maintain high accuracy in the presence of appropriate learning rate scaling, As described in $5, ACc-ADA and LOCAL-ADA not only modulate the learning rate but also increase the number of iterations by using scale-invariant epochs. Therefore the question of whether the reduced commuiccation time makes up for the increased number of iterations arises.
Our experiments help answer this question. In Figure 5, we compare the number of iterations required by each method. We see that increasing H, both adaptive scaling methods increase the number of iterations quite drastically. For H < 8, ACC-ADA converges in slightly fewer iterations than LOCAL-ADA,, whereas LOCAL-ADA is more itcration efficient for more infrequent communication (larger H). See also the tabulatod results in Appendix H. for details.
But which H should we choose in practice? Answering this question requires us to make assumptions about the relative cost of communication and computation. We let m denote the relative communication overhead, i.e., the ratio of time taken for one communication round to the time taken for one minibatch gradient computation without any synchronization. This is determined by the hardware and, therefore, beyond our control on the algorithmic side. Given the total number of epochs (K.H) observed in our experiments for LOCAL-ADA and ACc-ADA (Figure 5), we compute a pscudo-wall-clock training time as follows:
Communication
(K.H) meethod
(K.H) method
=
72
x
1
+
m H
(16)
K
Iterations
Computation
In Equation (16), we do not show dependence on per-device batch size B and dataset size explicitly in the term for number iterations as they are constant scalars across methods. We plot this wall-clock time in Figure 6 for CIFAR-10 and ImageNet32 at K = 24 and H E (1,2,8); additional results may be found in Appendix H.3. For CIFAR-10, we see that SGD is faster than Local SGD for all Il when Local SGD otherwise. However, different picture emerges for ImageNet-32; small values of H (say 2) for both gradient accumulation and Local SGD result in faster convergence than SGD. This is possibly because the overall batch size (B 24) is smaller than the critical batch size and thus gradient accumulation results in faster convergence. Local SGD is faster than SGD (for some H) when the dotted lines are below the solid ones in Figure 6, and we see that Local SGD is faster than SGD (with gradient accumulation) only when m 2 4. Additional plots may be found in Figure 11 the Appendix. Such large values of m are atypical in most training set-ups. Ortiz et al. (2021) show that even when using 256, m stays around 3. A substantially larger communication overhead is plausible for some setups, e.g., crowd-sourced
3, and
10

---

Published in Transactions on Machine Learning Research (01/2024)
ACC-ADA
LOCAL-ADA
LOCAL-LIN
24
Top-1 Accuracy
100
CIFAR 10
80
Top-3 Accuracy
ImageNNet32
60
Top-5 Accuracy
ImageNet
80
80
H
H
Figure 4: Test accuracies achieved for different numbers of workers (K) and communication intervals (H). Lincar scaling with gradient accumulation deteriorates quickly. Lincar scaling with Local SGD more robust but suffers for large values of H. Using adaptive scaling, both gradient accumulation and Local SGD maintain the target performance across large range of values for K and H.
K=16
K=24
True Epochs
6000
CIFAR 10
2000
7500
5000
1000
2000
2500
0
ImagoNNet32
Tirue Epochs
100
200
400
200
100
27
29
27
2a
22
21
Image-Vtt Vel.
True Epochs
300
100
200
400
200
200
100
2'
21
2
2
H
H
H
Figure Number of epochs used by each method. While linear scaling operates under a fixed budget, the adaptive scaling methods stretch the learning rate schedule, which increases the total number of epochs. For values of HI < 8, ACc-ADA uses slightly fewer epochs than LOCAL-ADAL For large values of H, LOCAL-ADA is drastically more eteration-effcieent.
11

---

Published in Transactions on Machine Learning Research (01/2024)
volunteer computing (Ryabinin & Gusev, 2020). However, such scenarios come with host of other issues like stragglers, lault tolerance that have propelled their own lines of research (Learning@home team, 2020; Borzunov et al., 2022a;b; Ryabinin et al., 2021; Blanchard et al., 2017). Therefore, our findings cast doubts on the practical utility of Local SGD in commonplace distributed training environments.
7 Conclusion
Summary of Findings The previously published literature on Local SGD suffers from certain dis- crepancy between theory and practice. Previous theoretical results have been interpreted as: "Lo- cal SGD behaves just like syuchronous data-parallel SGD". In contrast to that, empirical studies have reported performance degradation when using Lo- cal SGD compared to synchronous SGD.
CIFARIO
Training time T
210
2"
22
27
26
2
ImageNNt332
We show that this discrepancy may be attributed to the choice of learning rate. Theoretical results have assumed restrictive upper bounds on the learn- ing rate. This recovers the behavior of synchronous SGD at the same learning rate, but that lcarning rate is clearly non-optimal. Empirical works have used learning rate scaling techniques tailored to syn- chronous SGD. We show that this is likewise non- optimal, since Local SGD faces fundamentally dif- ferent trade-off than synchronous data- data-parallel SGD where the error of its gradient estimate depends on the learning rate itself.
'Training time T
Method
2"
ACC-ADA
2"
LOCAL-ADA
2
2"
2a
2"
Relative cost m
Figure 6: Which method is faster? We plot pscudo- wall-clock time T on the y-axis for different assumed values of the relative communication overhead m, see (16)). We see that LocalAdaScale (using large val- ues of H) converges faster for high communication overheads. For lower m, synchronous SGD with few gradient accumulation steps is preferable.
To further study the behavior of Local SGD, we de- vise an optimal learning rate scaling method, called LocalAdaScale, mirroring the AdaScale method for synchronous SGD. Our experiments demonstrate that LdcalAdaScale bridges the gap in performance between Local SGD and synchronous SGD and that Local SGD converges in fewer iterations than gradient accumulation for large communication intervals. However, in wall-clock time, we find that Local SGD is faster than synchronous data- hatallarallel SGD only for very high communication overheads, shedding new light on the practicality of Local SGD.
Limitations and Future Work The optimality of learning rale in this work is based on the training loss and not the test loss. Thus, the claims of optimality have to be seen in the limited context of training perfor- mance and optimization, not generalization. Several techniques that target improved generalization (Orvieto et al., 2022) have been investigated, and studying them for Local SGD is beyond the scope of the current work.
Our paper is limited to analyzing the effect of the learning rate while keeping other hyperparameters fixed. Tuning other hyperparameters, such as momentum, may be useful to improve convergence or genoralization. We also performed our comparison at a fixed communication interval H. A comparison of Local SGD vs. gradient accumulation under varying H (e.g., such as post-local SGD (Lin al., 2020)) may be interesting.
The optimal step size for Local SGD in Equation (13) involves multiple approximations. Firstly, like AdaS- cale, it is based on Lipschitz bound which may be loose for some objective functions. Secondly, we assume the gradient magnitude along H consecutive Local SGD steps to be approximately constant. Finally, we
12

---

Published in Transactions on Machine Learning Research (01/2024)
estimate gradient magnitude using imperfect empirical estimates, rendering our learning rate scaling only approximately optimal.
We have restricted our analysis to the case of homogeneous data distribution each worker. An extension of our learning rate scaling technique to the federated learning scenario with heterogeneous data would be interesting future work. Our experiments are limited to computer vision tasks and for models based on convolutional nets. Thus, our findings on the value Local SGD might be limited to those conditions. Broader generalizations require further experimentation.
As discussed $5, our implementation of Ldaale syuchronizes both the model weights and gradients, which adds communication compared to plain Local SGD. We did not attempt to alleviate this, since we devised LocalAdaScale primarily as a tool for the analysis of Local SGD. In future work, one could devise approximate versions of LocalAdaScale that avoid additional communication. A possible avenue would be to approximate gradient magnilude and variance from the pseudo-grudient (Reddi et al., 2021) given by the displacement Wi+H Wt
Beyond that, our work can be extended in several ways. While we have compared gradient accumulation and local steps as alternatives, one may realize a desired communication interval H using a combination of both. (For example, local steps, each using 4 gradient accumulations, achieves a communication interval of 32.) Relatedly, one may alter the communication interval for different phases of the optimization process. Both decisions will influence learning rate scaling and may, in turn, be informed by gradient statistics.
References
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding, Advances in Neural Information Processing Systems, 30:1709-1722 17200 2017. 3
Lukas Balles, Javier Romero, and Philipp Hennig. Coupling adaptive batch sizes with learning rates. Gal Elidan, Kristian Kersting, and Alexander T. Ihler (eds.), Proceedings of the Thirty- Third Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017. AUAI Press, httpp//pppss/////ee /111 pdf. 19
wwtgg/aii2111 2017. URL http://aual wtt.://///.....//orreeeeeeaa
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qpparse-local-SGDD: Distributed SGD with Quantization, Sparsification, and Local Computations. arXiv:1906. 020007002677700 fes, math, stat), November 2019.
3
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advonces in neural information processing systems, 30, 2017. 12
Alexander Borzunov, Dmitry Baranchuk, Tim Dettmers, Max Ryabinin, Younes Belkada, Artem Chu- machenko, Pavel Samygin, and Colin Raffel. Petals: Collaborative inference and fine-tuning of large models. arXiv preprint arxi::2009.00 01 188, 2022a. URL https: http:///axxvvvor//////// org/abs httg//bb/2209.000//
12
Alexander Borzunov, Max Ryabinin, Tim Dettmers, Quentin Lhoest, Lucile Saulnier, Michael Diskin, Yacine Jernite, and Thomas Wolf. Training transformers together. In NewrIPS 2021 Competitions and Demon- strations Track; pp. 335 342. PMLR, 2022b. 12
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learn- ing. SIAM Review, 60(2):223-31) 2018. doi: 10.1137/16M11080178.. URL http://00...0//011111.////////// 16M1080173.
Xuanyu Cao, Tamer Bagar, Suhas Diggavi, Yonina C. Eldar, Khaled B. Letaief H. Vincent Poor, and Junshan Zhang. commuieattion-fffcieett distributed learning: An overview. IEEE Journal on Selected Areas in Commemications, 41 41(4):851-88 -57883, 2023. doi: 2.1109/15AC.22023324227
13

---

Published in Transactions on Machine Learning Research (01/2024)
Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulliia, and Virginia Smith. On large-cohort training for federated learning. In A. Beygekzimer Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.); Advances in Neural Information Processing Systems, 2021. URL http:///ppenreveeeeeeeeeeeeee 2026p7chwhht. 4
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In 2016 seee international confer- ence acoustics, speech and signal processing (icassp), pp. 5880 -0-88484. IEEE, 2016. 24
Patryk Chrabaszez, Nya Loshchilov, and Frank Hutter. A downsampled variant of ImageNet as an alternative to the CIFAR datasets. arXiv preprint or arviv: 707.08819, 2017. 9, 28
Ofer Dokel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012. 4
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Local SGD optimizes overparameterized neural networks in polynomial time. In Gustau Camps-Varl Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.). Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 6840-6861 6861. PMLR, 28-30 Mar 2022. URL https: // //proceedings.ntt www.eeeddiinm............m.e...e mlr. pttps//eie/deeeegeeeeeeeee h.mm..
FairScale authors. Fairscale: A general purpose modular pytorch library for high performance and large scale training. https://githut wom////ceboorrrearrr/aaaaaa
2021. 9
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. In International Conference on Learning Representations, 2022. URL
https://openrevieet new seer/foruumid==2BseeBBsS 4
Priya. Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour.
arXiv:1 026670277 [es), April 2018. 1, 3, 4, 7, 10, 28
Xinran Gu, Kaifeng Lyu, Longbo Huang, and Saujeev Arora. Why (and when) does local SGD generalize better than SGD? In The Fleventh International Conference on Learning Representations, 2023. URL
https://openreviery http://pporrrreeeeeeeeerorrnmmn http://ormmiissveeiiiiiiii 1Drl. 4
Farzin Haddadpour, Mohammad Mahdi Kamani, Mchrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 11080-11092, 2019. 4
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognation, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770 778. IEEE Computer Society, 2016. doi: 10.1109/CVPR.2016.990 URL https://dof orw/ooo///// 10. 1109/CVPR. 2016.02222022222 90. 9, 23
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: Closing the generalization gap in large batch training of neural networks. In Proceedings of the 91st International Conference on Neurul Information Processing Systems, NIPS17, pp. 1729 1739, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Tyler Johnson, Pulkit Agrawal, Haijie Gu, and Carlos Guestrin. AdaScale SGD: A user-friendly algorithm for distributed training. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4911- 4920. PMLR, 13-18 Jul 2020. URL https: httpss//proceeedings. mlr, wtt..pprss/vv///e/ee jow.sooo0a......aa..m html. 2, 3, 7, 19, 24
14

---

Published in Transactions on Machine Learning Research (01/2024)
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local SGD on identical and heterogeneous data. In Silvia Chiappa and Roberto Calandra (ods.), Proceedings of the Twenly Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4519-4529. PMLR, 26-28 Aug 2020. URL https: https://proceedings. mlr press/ v108/bayoumi 20a. 20m.mmml. 4, 20,
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (ods.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://aaxxiv.oggbbb/////ss 6980.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. 9, 23
Alex Krizhevsky. One weird trick for parallelizing convolutional neural networks. arXiv preprint
arXiv:1404.5997, 2014.
Learning@home team. Hivemind: Library for Decentralized Deep Learning. https://github.cem com/
aaarning-at-hooe/hiieeett 2020. 12
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. In International Conference on Learning Represenlations, 2020. URL https://openreviecn .etereeeeieeeeeeeee/eeee forum?id-B1eyO1BFPr 2, 3, 4, 6, 10, 12, 24
Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Olli Saarikivi, Tianju Xu, Vadim E'ksaressky, Jaliya Ekanayake, and Emad Barsoun. Scaling distributed training with adaptive summation. Proceedings of Machine Learning and Systems, 3, 2021. 3
Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAl Dota Team. An empirical model of large-batch training. ar Xiv: 18162111221122 fes, statf, December 2018. 7
David E Muller. A method for solving algebraic equations using an automatic computer. Mathemalicul tables and other aids to computation, 10(56):208 215, 1956. 23
Tomoya Murata and Taiji Suzuki. Bias-variance reduced local SGD for less heterogeneous federated learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Leorning Research, pp. 7872-7881. PMLR, 18-24 Jul 2021. URL https://procee//e/ http://oooeeeen..... mlr, wtt.:i/s.ll....ss/s/eeeeee ppess/vv333 v133///ratt2111aaam//// html. 4
Zachary Nado, Justin M. Gilmer, Christopher J. Shallue, Rohan Anil, and George E. Dahl. A large batch optimizer reality check: Traditional, generic optimizers suffice across batch sizes. arXiv:2102.06:0 fes, stat/, June 2021. 3
Jose Javier Gonzalez Ortiz, Jonathan Frankle, Mike Rabbat, Ari Morcos, and Nicolas Ballas. Trade-offs of local sgd at scale: An empirical study. arXio preprint 3rXio:2110.0810 2021. 2, 3, 4, 6, 10
Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorrelated noise injection for improved generalization. In International Conference on Machine Learning, pp. 17094-17116.
PMLR, 2022. 12
Daniel Povey, Xisohui Zhang, and Sanjeev Khudanpur. Parallel training of dans with natural gradient and parameter averaging. arXiv preprint arXim:1410. 7455, 2014. 4
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12(1):145-11) 1999.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to paral-
lelizing stochastic gradient descent. Advances in neural information processing systems, 24, 2011. 3
15

---

Published in Transactions on Machine Learning Research (01/2024)
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021. URL
13
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemalical statisfics, pp. 400-407, 1951.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. ImageNet large scale visual recognition challenge. International journal of computer vision, 115(3):211-25) 2015. 9
Max Ryabinin and Anton Gusev, Towards crowdsourced training of large neural networks using decentralized mixture-of-experts. Advances in Newral Information Processing Systems, 33:3659 3672, 2020. 12
Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Moshpit sgd: Communication-effiienn decentralized training heterogeneous unreliable devices. Advances in Neu- ral Information Processing Systems, 34:18195-18211, 2021. 12
Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-SGD: Commmicattion-fficeen momentum SGD for decentralized optimization. IEEE Journal on Selected Areas in Information Theory, 2(3):954-969, 2021. 5
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference applications of computer vision (WACV), pp. 464-472. TERE, 2017. 3
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on 2, 4, 5, 27
Learning Representations, 2019. URL https:// wwwp:eeetoooomddinnnnieoemm
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in doep learning. In International conference machine learning, pp. 1139 1147. PMLR, 2013.
Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtim, trade-off in local-update sgd. Proceedings of Machine Learning and Systems, 1:212-229, 2019. 4, 6
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communcationn- efficient distributed SGD with slow momentum. 2020. URL https::/oppnreevie: wttp:arrrrreeeeeeeoutnuuiiiiiii net/forum?id=
SkxJEREYPH. 4, 5, 24
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Peter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtarik, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. Field Guide Federated Optimization. arXio:2107.0691 [cs]. July 2021. 4
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Ts local SGD better than minibatch SGD? In Proceedings of the 37th International Conference on Machine Learning, pp. 10334 10343. PMLR, November 2020. 4
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. Xr preprint arXiv:1708 038888 2017. 3
16

---

Published in Transactions on Machine Learning Research (01/2024)
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In International Conference on Learning Representations, 2020. URL https: //openreview. syy/: 3
Chulhce Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Leurning Represenlations, 2022. URL https://
2, 4
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Jian Zhang, Christopher De Sa, Toannis Milliagkas, and Christopher Ré. Parallel SGD: When does averaging help? XiXiv prepriat arXiv:1606.00 07366, 2016. 4
Fan Zhou and Guojing Cong. On the convergence properties of K-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 3219 3227, 2018.
17

---

Published in Transactions on Machine Learning Research (01/2024)
Contents
Introduction
1
2 Related Work
3
3 Preliminaries
4
3.1 Problem Setup
4
3.2
Local SGD
5
Local SGD's Learning Rate Conundrum
5
5 Adaptive Learning Rate Scaling for Synchronous and Local SGD
6
5.1 Optimal learning rate scaling for SGD AdaScale
6
5.2 Optimal learning rate scaling for Local SGD- AdcalAd
6 Experiments
9
6.1 Local SGD with automatic learning rate scaling LocalAdaScale maintains Target Accuracy
10
6.2 Should Use Local SGD?
7 Conclusion
12
A Glossary of Symbols
19
B Derivation of AdaScale
19
C Details on Local SGD
20
C.1 MSF of Local SGD's Gradient Estimate (Equation 6)
C.2 Expected Decrease (Equation 10)
21
C.3 Optimal Step Size (Equation 13)
23
D Expected Decrease for H Steps of Synchronous SGD
24
E Avoiding Stale Gradients in Computing the Gain Ratio
24
F How accurate are our approximations in Equation (14)?
26
G Need to Modulate Step Size for Larger Batch Sizes
27
G.1 With Constant Learning Rate
27
G.2 Using AdaScale
H Details of Experiments
28
H.1
Experimental Setup
28
................................
H.2 Tabulated Results
H.3 Additional Results for Pseudo-Wai Clock Time
30
H.4 Behavior of the Gain Ratio
30
18

---

Published in Transactions on Machine Learning Research (01/2024)
A
Glossary of Symbols
Symbol
Meaning
K
Number of workers
Number local steps
? base
Unscaled learning rate for K
B
Batch size per worker/Base Base batch size Quantity (+) at time
(+)
ft
Gradient of function at w,
of gr
Variance of gradient estimation at time t
Gradient estimate on worker k at time t
G T2
Virtual Gradient magnitude and variance estimate for Local SGD
w
Model weights on worker k at time t
Table Glossary of symbols used
B Derivation of AdaScale
In this section, we derive the AdaScale rule of (Johnson et al., 2020) using ideas from Balles et al. (2017). This view of AdaScale being the learning rate scaling that maximizes the function decrease is novel to the best of our knowledge. Pseudo-code for AdaScale is shown in Algorithm 2.
By definition, f satisfies the following property.
I
f(v) - f()) + Vf(x) x)+
2 11 20|
(17)
for z,y E dom(f). Plugging in z wt and W w. 7gg, and computing the expected value of I (W++1) given Wt where ge is the stochastic gradient at 1, we get
L E ge 3
Elf(w(41) < f(w,) - TO V Egg +
(18)
2
The optimal learning rate is the one that minimizes the right-hand side, thereby maximizing the expected decrease of the function value.
Differentiating the right side of Equation (18) and sctting it to zero gives the optimal lcarning rate as
v Egg.
G.
7t L. g 1
L (o G
(19)
where [g St, || G. and [lgl
G. + of.
When increase the batch size by factor of K, the variance is reduced by factor of K. Thus, the optimal learning rate becomes
G
K
(20)
L
0 + G.
Thus, the relative change in the learning rate when the batch size increased times
Tt of Ge
(21)
K G.
and is termed the gain ratio. As it is evident, it takes maximum value of K when & & o².
19

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 2 AdaScale for synchronous gradient descent
Input: Initialization w, 0, learning rate function Yh. # workers K, scale-invariant iteration budget
S, 00 0.
1: while S do
D Scale invariant budgel not exhausted P On each worker D Compute local gradients.
2:
for k [K] do
3:
Compute g using a batch of data. Compute r2 [] as given in Equation (21).
Update W++1 Wt 7[a] rage
6:
t+
Iteration counter increment. Budget is computed from the scaling obtained.
7: 8 8
return Last iterate
C Details on Local SGD
This section contains details regarding Local SGD which have been omitted from the main text, in particular the derivation of the MSE of its implicit gradient estimate (Appendix C.1) well as the optimal step size (Appendix C.3).
Local SGD was introduced in $3, in particular Equation (3)- In practice, Local SGD is often used with local steps other than vanilla SGD step, e.g., momentum variants. Algorithm provides pscudocode; Line 5 calls an update function, which may apply any gradient-based optimization step, like SGD momentum SGD or adaptive gradient methods like Adam.
Algorithm Local SGD
Input: Initialization Wo, step-size ",, #workers K, #local steps H, budget ++0
1:
while < do for [K] do Compute g² using batch of data.
Training budget not exhausted. On each worker
5:
w < Update(w"; g.).).
Local update Average every H steps
6:
if t 1 +1|H H then
w + & Ik= w
t+
return Averaged iterate R ΣK w/.
C.1 MSE of Local SGD's Gradient Estimate (Equation 6)
We derive the error in estimating the gradient for Local SGD, stated in Proposition 4.2. We first give the following Lemma, variant of Lemma in Khaled et al. (2020) using our local variance bound.
[t, + H). Define Vy 2 ER w worll Then Lemma C.1. Let Assumption 4.1 hold and let t'
Ex[Ve] & (H 2
(22)
Proof. See Lemma 1 of Khaled et al. (2020).
We ready to prove Proposition 4.2.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Proof of Proposition 4.2. Using the definition of ge (Equation (4)), for every t' E [t, t H), have
1
Ey ||Be
vf(We)]l? Ev
gi
vf(we)
(23)
K
1
E.
(g.
vs(w
(VS((w) -VS(w>))
(24)
K
K
1
Ey
- v((wt))
+
Vf(w)) -(llw))--((w))) vf(we)))
(25)
K
K
k=1
k=1
Term 2
(26)
For Term 1, the variance bound in Assumption 4.1 gives us
[[]
Ev
ge
k
V((WE))
(gg
f((w))))
vf(w()))
5f
(27)
K
K2
K
For Term 2, we use Jensen's inequality and T-smoothness to get
K
K
(V(W)) - vf(we))
$ K
(V
(f(w)))
1
Σ
w
wo/l?
K
K
(28)
k=1
=:V,
Plugging that back in and taking the expectation E,, we find
o? +
o² K
Ey I vf(w>))
E =
+ +(H 1)D33722
(29)
K
C.2 Expected Decrease (Equation 10)
We derive upper bound on the expected decrease achieved by Hl consecutive steps of Local SGD. This result was stated in Equation (10). The following Proposition states the bound, where we factorize the learning rate as = f: this is solely for the readability of the proof.
Proposition C.2. Let f be L-smooth. We consider H conseculive sleps of Local SGD (Fquation (3)) starting from a synchronization point H tt. We assume a fixed step size = n/ across these H steps. Then
Be[s(wr+H)] S s(w.) H
17 G. +
11 A.
1/2 A.
112 o
n (H 11) -
(30)
2T.
2T.
2T.
2T.
4T.
where
1 H---1
++--1
G =
H (lll
A
Σ
E. f
(31)
K
_
H
P't
Proof. From T-smoothness, have for any t
1/2
Ey [[(W++]]] S S(we) " V(((:)) Tey [Br]
Er ||| [12]
2I.
(32)
1
= =((we) - - \
+
E.
I gr 11
K
2L
21

---

Published in Transactions on Machine Learning Research (01/2024)
Regarding the linear term, we have
vs(we)²
1 R
2
1
E [V((W)) V
K
k
1
Σ
1,2 1
|w - wr /12
2
K
A:A.
(33)
Furthermore, we have
Ey Br [2] =
[g
[B]]]]
Var [B s
vs(wF)
K
K
(34)
SAp
Plugging Equations (33) and (34) back into Equation (32), we get
& - " IVS(we)]
7
Av +
La
Vp
+
Av + o o.
(35)
2L
2L
2
2L
2L K
Tterating this bound backward from 1' = L - while taking the expectation E, yields
[ E, F1 -I
Et ((W(-H-1)- 2L
17
7
1 +
Ln
V V44H-1 + A
n
172 oî 2T
2L
2L
s...
s f((w))
"
Σ
E, [[(w))]]
"
1+H-1
Σ N=t
Eg
[Ay
+
"
Σ
E((Av]
+ q/2
H
+
Lm
t H H-1
Σ t'=t
[e]
2L
2L
2L
2L
K
2
d'=
P'=t
-HG.
=H
= =AA
(*)
(36)
It remains to bound the term (+). From Lemma C.1 know that V, obeys the recursion
E, [1]] s 11 y= L
(37)
Since V = 0, we get E,[Vo] & (t' - t v
I and
##-1
VV < /: 1 ++--1
(H 1)H
Σ
(t- o3
(38)
L
212
M=t
Plugging that back in gives
s B)
"1 HG,
H +
1
HA +
1 22
H +
(H 1)H
(39)
2L
2L
2L
2L
K
4L
22

---

Published in Transactions on Machine Learning Research (01/2024)
10a
10
Std (19
10-2
Mean
11
2
10-3
500
1000
1500
2000
Training step
Figure 7: Examining the assumption in Equation (40)- We plot the standard deviation of the full-gradient magnitude over H steps for ResNet-9 (He et al., 2016) trained CIFAR-10 (Krizhevsky, 2009). It is evident that the gradient magnilude changes very little over the course of training and thus the assumpliio over small number of H gradient steps the magnitude remains constant is reasonable approximation.
This expected function decrease bound features terms G, and A,, which are expected squared gradient magniludes along the Irajectories of the virtual averaged iterates, and the per-worker ilerates, respectively. These quantities are not computed in practice, and in principle, dependent on 77, since the choice of step size influences the gradient magnitude along that trajectory. We make simplifying assumption that
A, ~ (w:)l x G.
(40)
Equation (40) significs that between two synchronizations the average virtual gradient magnitude and the local gradient magnitudes computed on each worker do not change too much and can be approxinated by the gradient magnitude computed at the point of synchronization (w,). We study the validity of this assumption in Figure 7. We train small ResNet-9 on CIFAR-10 using SGD. We are interested in how the gradient magnitude (not stochastic gradient magnitude) evolves over a short horizon of H steps, and thus we plot the ratio standard deviation the gradient magnitude over H steps to the average gradient magnitude over those steps, commonly termed coefficient of variation. It is apparent from Figure 7 that the coefficient of variation well below is almost < 1 except at the start of the training. This provides evidence that we can reuse the gradient magnitude for H steps due to its relative constancy.
Substituting Equation (40) into Equation (39) gives
[) < s(w.) - H 111,, 72L G.
22
(H (H1
(41)
K
C.3 Optimal Step Size (Equation 13)
We now find the learning rate y that minimizes our bound on E[f(w++H) in Equation (41). Setting the derivative of the right-hand side w.r.l. to zero reads
G. GL - 7 5Z
4
=0
(42)
This quadratic equation in can be solved by the standard quadratic formula. We instead use Muller's method (Muller, 1956) which gives the rools of a quadratic of form ax? + ba + 0 as
2c
I bb V
(43)
4ac
23

---

Published in Transactions on Machine Learning Research (01/2024)
Ignoring the negative root, get
2Gr
(44)
L G. G V(r -
In our experiments, following Johnson al. (2020), SGD with momentum. Momentum buffers are maintained locally on each machine and not synchronized. We leave the investigation of different approaches to momentum buffers (Lin et al., 2020; Wang et al., 2020; Chen & Huo, 2016) to future work.
D Expected Decrease for H Steps of Synchronous SGD
To elucidate the expected decrease bound for Local SGD in Equation (41), we contrast with similar bound for H consccutive steps of synchronous data-parallel SGD using a constant learning rate 7. Analogously to our analysis for Local SGD, assume gradient variance and magnitude to be bounded across these H steps,
Ee Lo S of [VV]( 2 G. (t, H).
(45)
For the averaged gradient across K workers, this results in Vary Br) S
K
By smoothness, get
IT2
Eg [f(+++)) S f(w.)) - V.(we)) ( TE [Sr1 +
Ey,
||
2
</|V - In"
= =[(w))
[I+e )11 + Vary [gr]]
(46)
2
(7G, - I
))
S((w)
G, +
2
K
Using this recursively for steps from to + while taking the expectation E,, we get
[e]((w++H) & f(w)) - G 7 o
21
2 K
(47)
Expected decrease for SGD
Contrast this with Equation (30), restated here:
[[[((++))] < f(w)) - H. (16.-2
PL 2
L912
G.
4 --
-H-1)0
(48)
2
K
We see that Local SGD has an additional cubic term that results from the biased estimation of gradients.
E
Avoiding Stale Gradients in Computing the Gain Ratio
To implement LocalAdaScale,, we need to estimate G, and o.. In Algorithm 1, we proposed method that synchronizes once every H steps average the weights and the cached stale gradients simultancously. As ablation study, compare this against alternative stralegy where synchronize the gradients one step after weight synchronization in Algorithm 4. While this incurs latency overhead twice, the resulting gain ratio computed with more recent gradient ovaluations and should therefore be more accurate.
In Figure 9, we compare the two variants LOCAL-ADA, and LOCAL-ADA-NOSTALL we find that there are very small differences between the two variants in the final accuracy obtained or the number of epochs convergence. The difference in the number of epochs for LOCAL-ADA and LOCAL-ADA- NoSTALE explained by the fact that underestimating the gain ratio p due using stale gradients results in longer training durations.
Across all datasets,
24

---

Published in Transactions on Machine Learning Research (01/2024)
ROCAL-ADA-NOSTAN
LOCAL-ADA
K =
1=
K=24
Top-1 Accuracy
CIFAR 10
95
94
2a
24
Top-5 Accuracy
ImageNNec22
69
2
23
2 2 2"
23
Top-5 Accurayy
ImageNet
91
92
90
2
H
H
H
Figure 8: Comparison test accuracies achieved for different numbers workers (K) and communication intervals (H) by the two implementation variants of LdcalAdaScale, Accuracy stays nearly identical between the two implementations, and the minor variations within random seed variations.
K=8
K=24
2000
CIFAR 10 True Epochs
1000
1500
1000
1000
2.
02
ImageNet.32 True Epochs
200
125
150
75
22
2
2
26
2
24
2
22
2
21
2
ImageNet True ippochs
200
300
400
150
200
200
24
2
2
HI
HI
Figure 9: Number of epochs used by each method. When K 8, both variants converge in nearly identical number of epochs. LOCAL-ADA trains for marginally more iterations, underestimates the gain ratio due to the utilization of cached gradients
25

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 4 LacalAdaScale with two synchronizations LOCAL-ADA-NOSTAUE
Input: Initializatinn wo, step-size Yts #workers K, #local steps H, Scale inv budget S, t 0, s 0. while S do for k E [K] do
Scale inv budget not cxhausted. b On each worker Gradient at t. b Onc step after model sync. Equation (15)
4:
Compute gž using batch of data.
5:
if H t then
6:
Gr. & grad grradstatt(g?)
Compute p as Equation (14).
if H 1) then
Average model every H steps
w f Σ w
Vj.
10:
W f w p7/
b Local update. Average every steps
11:
H (t + 1) then
12:
w <- 2j=1 w! Vj.
13:
8 Pt 1+t+1
14:
15:
return the last iterate W.-
F
How accurate are our approximations in Equation (14)?
We study the tightness of our assumptions by studying generalized version of Equation (14) as
2 2Ge + +
(49)
02 2) G. + K + V(G.+
02
+30 (H -H
Here when (0) reduces to AdaScale and (1( is LocaLAdaScale, and thus Pc(c) for c E [0,1] interpolates AdaScale and Modulating e scales the learning rate as well as the number of training iterations.
ImageNet-32
Top-5 Accuracy
68
66
64
ImageNee
16
True Epochs
200
mm x
x
32
150
100
50
0.0
0.5
1.0
1.5
Figure 10: Ablation over e Equation (49). We plot us Top-5 Accuracy and Number of epochs ImageNet32
for K 16 for 16, 32. We see that c 2 0.6 results recovering the Target Accuracy.
26

---

Published in Transactions on Machine Learning Research (01/2024)
We show in Figure 10 the effect of the performance. Using AdaScale's gain formula (c= 0) for Local the learning rate used is
SGD is has the ad advataage of fastest convergence albeit with poorer generalization likely too aggressive, and consequently training iterations too few. As c is increased from 0, we see improved performance and the performance shows diminishing returns when c 2 0.6. This threshold can vary with the dataset and network archilecture addition the number of workers, and cannot be interpreted as a universal threshold. We see that our proposed method scales the learning rate conservatively and our threshold works well for very high communication gap of H 32. This figure is further evidence that scaling methods that were designed for synchronous data-parallel SGD do not perform well for Local SGD and the delayed communccation (H 2 2) has to be accounted for, as we seen in the case of c = 0 where there is a substantial performance difference between the two cases H = 16 and H = 32.
G
Need to Modulate Step Size for Larger Batch Sizes
G.1 With Constant Learning Rate
Khaled et al. (2020); Stich (2019) analyze the convergence of Local SGD under a different condition for learning rate: either constant, or decreasing with time, but not the optimal learning rate. We can analyze this choice by mapping that idea SGD in Equation (18). Let y be the learning rate that small enough (additional upper bounds exist). We can see that with that learning rate the loss function decreases by
[[f(w w.l S f(w,) (11VV fel + of Ln²
(50)
2
By keeping the learning rate the same value and when the number of workers goes up K fold, the variance reduces by the same factor, we get
| + R LA2
[[[(w++)))w) S f(we)-
(51)
2
Comparing Equations (50) and (51), it is apparent that merely increasing the batch size results in an update that results in a larger reduction of the function value without having to tinker with the learning rate at all. However, this is suboptimal as a practitioncr would be interested in tuning the learning rate that results the largest reduction (implying faster training). Here lies the difference between prior works and our results.
G.2 Using AdaScale
In Appendix B, we derived the optimal learning rate, which results in the largest decrease in the function value. Thus, when the number of workers is increased from 1 to K, any learning rate smaller than the optimal, will also result the decrease of the function value in Equation (18), however, will be lesser than optimal. We make this more formal here.
Substituting Equation (19) into Equation (18), we get.
(o) +
[[V/P))
|V (o) + |V
[[ w:] E f(w:)
oo
V
ft (2)
L
2L
V
= -((w)
(OptRednSGD-I Worker)
2T. C0) +
VMP))
Reduction factor
27

---

Published in Transactions on Machine Learning Research (01/2024)
Similarly, can show that the optimal reduction in the function value when K workers are used as
| fell
Bl/(we+))\wl) S S(we))
(OptRednSGD-K Worker)
2L
ffll?
Reduction factor
The reduction factor in Equation (OptRednSGI-K Worker) 2 Equation (OptRednSGD-1 Worker), as the denominator in Equation (OpIRednSGD-K Worker) is smaller than Equation (OpIRednSGDD1 Worker) and all other terms are identical. A learning rate adaptation is required to capitalize on the availability workers.
H Details of Experiments
H.1
Experimental Setup
CIFAR-10 We used ResNet model code and training hyperparameters from the GitHub repository https:
//github. gonuangluuppytoon cifar. They report test accuracy of 93.02% for ResNet-18 in the single-worker base setting.
ImageNet32 We used Wide ResNet pytorch- cifar100 and training hyperparameters from the paper proposing ImageNet32 (Chrabaszez al., 2017). They report top-5 test accuracy of 69.08% for WRN-28-2 in the single-worker base setting.
model code from https://github. com/weiaicunzal
ImageNet We used ResNet model from the torchvision library and training hyperparameters from Goyal et al. (2018). The torchvision library reports a top-5 test accuracy of 92.86%.
Training hyperparameters are listed in the following table:
Dataset
Tbasc
Momentum
Weight decay
LR schedule
Epochs
CIFAR-10
0.1
0.9
5 10-4
Cosino-decay
200
ImageNel32
0.01
0.9
5 x 10-4
Step (x0.5 every 10 epochs)
40
ImageNet
0.1
0.9
5 x 10
Step (x0.1 every 30 epochs)
90
H.2 Tabulated Results
Tabulated results of experiments may be found in Tables 2 to 4.
28

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: Accuracy 1%
and number of epochs for CIFAR-10.
Accuracy
Epochs
K
H
ACC-ADA
ACC-LIN
LOCAL-ADA
LOCAL-LIN
ACc-ADA
ACC-LIN
LOCAL-ADA LOCAL-LIn
95.12
94.73
95.07
95.16
291
200
338
200
95.11
93.92
94.94
95.26
353
200
405
200
8
94.81
88.06
95.77
95.22
496
200
469
200
16
94.70
53.09
96.02
94.98
791
200
604
200
32
94.28
13.19
95.85
94.25
1450
200
813
200
64
94.53
10.70
95.71
93.61
2260
201
1056
200
95.35
94.13
95.11
95.24
360
200
422
200
95.15
87.36
95.55
94.69
502
200
525
200
94.65
36.52
95.71
93.82
812
200
666
200
16
94.43
14.18
95.74
93.35
1330
200
890
200
32
94.64
14.12
94.74
91.95
2499
201
1735
200
64
93.24
10.12
95.47
90.83
6157
202
1846
200
94.52
90.02
95.24
94.21
443
200
515
200
94.79
79.58
95.72
93.63
617
200
634
200
94.55
13.87
95.72
92.99
1006
200
813
200
24
93.65
10.76
95.39
91.68
1634
200
1132
200
32
93.96
11.08
95.92
86.69
3688
201
200
92.73
11.48
95.28
66.22
8542
203
2535
200
Table 3: Accuracy 1%]
and mumber of epochs for ImageNet32.
Accuracy
Epochs
K
H
Acc- ADA
Acc-Lan
ADA
LOCAL-LIN
ACc-ADA
ACo-LIN
LOCAL-ADA LOCAL-LIN
69.01
68.00
69.41
68.32
69.15
67.84
69.51
68.13
40
65
40
8
69.48
62.59
69.06
67.31
40
75
40
16
69.50
51.15
68.86
66.19
104
40
89
40
32
69.91
41.72
68.89
64.76
161
40
113
40
64
69.94
28.45
68.87
63.96
283
40
142
40
68.88
67.35
69.24
68.27
69.16
61.09
69.42
67.22
8
69.66
53.42
68.91
65.80
104
40
101
40
16
16
70.01
48.60
68, 08.61
63.44
162
40
123
40
32
70.02
29.78
68, 41
60.93
286
40
163
40
64
69.54
6,30
68.44
59.27
518
40
219
40
68.99
66.51
69.51
67.02
69.45 8
45.41
69.36
65.81
103
69.71
47.79
68.60
64.05
133
121
24
16
69.58
32.45
68.27
60.80
218
40
154
40
32
69.77
7.91
67.91
56.53
409
40
209
40
64
68.97
4.84
67.89
54.18
744
40
279
40
Table 4: Accuracy %
and number of epochs for ImageNet.
Accuracy
Epochs
K
H
ACc-ADA
ACC-LIN
LOCAL-ADA
LOCAL-LIN
ACc-ADA
ACC-LIN
LOCAL-ADA LOCAL-LIN
2
92.32
92.66
92.93
92.31
108
90
122
90
8
92.54
90.70
92.89
92.30
157
90
156
90
32
92.14
59.23
92.98
90.72
328
90
240
90
92.15
92.37
92.66
92.54
127
149
92.54
85.40
92.85
91.64
213
217
32
91.74
92.89
88.40
568
377
2
92.84
91.81
92.83
92.49
141
177
90
92.35
77.93
92.72
90.83
260
272
91.12
0.62
92.24
84.08
761
536
29

---

Published in Transactions on Machine Learning Research (01/2024)
H.3
Additional Results for #seudo-Wall Clock Time
In Figure 11, we plot the full communication tradeoffs for all the datasets, and workers (K) considered.
K
= 16
K 24
241
2
2
Training time T Training time T
2
2
21
20
20
CIFARIO
2a
27
27
27
26
26
24
21
2'
29
29
28
28
29
27
26
2
22
32
24
23
23
23
Method
2a
22
ACc-ADA
LOCAL-ADA
2
2.
210
Training time T
29
2
2"
2"
ImageNot
27
27
27
2
2
28
28
28
2
24
23
23
23
20
21
22
23
24
24
2
27
29
2
2
23
25
26
2
29
24
22
24
25
20
27
Relative cost m
Relative cost m
Relative cost m
Figure 11: When LocalAdaScale preferable to ACC-ADA? On the x-axis, we plot the relative cost m of communication to computation, and on the y-axis, we plot pseudo-walled wallclock time T. We see that LocalAdaS- cale converges faster than gradient accumulation for highor H, and also for a higher cost of communication. For lower m, gradient accumulation with fewer steps is preferable to LocalAdaScale.
H.4 Behavior of the Gain Ratio
Figures 12 and 13 show the gain ratios used by AdaScale and LocalAdaScale We plot (Eq. 14) for LOCAL- ADA and the "effective gain" # (Eq. 9) for ACc-ADA, accounting for the different scales of and r. Since different methods take different numbers iterations, we adjust the r-axis to correspond to scale-invariant epochs. We see that both methods approach the maximum gain ratio average gain ratio achieved by ACc-ADA slightly higher for small H, resulting fewer iterations as observed before. For large H, this is reversed, and LOCAL-ADA achieves higher average gains. all settings and for both methods, the gain ratio generally increases smoothly over time, reflecting diminishing gradient magnitude.
for small values of H. The
30

---

Published in Transactions on Machine Learning Research (01/2024)
K
16
K 24
16
24
20
Gain
16
12
16
24
20
16
Gain
Method
ACc-ADA LOUM-ADA
2
24
12
Gain
2-
Epochs
Epochs
Epochs
Figure 12: Gain ratios for CIFAR-10 on ResNet-18. Each corresponds to communication interval H and each column to the number of workers K. ACc-ADA reaches higher gain ratios for small H and thus is more iteration efficient than AOCAL-ADA. This trend reverses for large H, where we see that ACC-ADA reaches higher scaling only towards the end training. The x-axis has boen lincar downsampled to fit into 200 epochs for risuaiization.
K
K
K 24
16
24
20
Gain
16
12
2-
6
12
Gain
Method
Acc-ADA
LO0AL-ADA
244
20
12
Gain
1.6
12
Epochs
Epochs
Epochs
Figure 13: Gain ratios for ImageNet-32 on WRN-28-2, Each row corresponds to a communication interval and each column to the number of workers K. ACC-ADA reaches higher gain ratios for small and thus is more iteration efficient than LOCAL-ADA. This trend reverses for large H, where we see that ACc-ADA reaches higher scaling only towards the end training. The x-axis has been linear downsampled to fit into 40 epochs for visualization. The step structure of the gain is due the step learning rate decay schedule and does not align across plots because LocalAdaScale uses scale invariant epochs, which corresponds to different number of epochs in each K, H setting.
31


Reviews:
[{"review_id": "68CC2IDF0l", "reviewer": "Reviewer_25QM", "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:\n1. This paper studies a well-motivated problem: how do we reduce communication overhead while maintaining the convergence speed? The authors tackle this problem by looking into the learning rates of Local SGD, one of the most popular communication-efficient optimizers.\n1. This paper is well-written. The experiment and proof details are written very clearly.\n2. The proposed method LocalAdaScale is grounded by theory and has been validated via thorough experiments on different datasets, numbers of local steps, and numbers of workers.\n\nWeaknesses:\n1. My main concern is about the main claim of the paper, \"Local SGD is of limited practical utility\". In my understanding, what the authors indeed did is to design learning rate schedules with their best efforts (via LocalAdaScale), and found that Local SGD is not faster than SGD if the communication cost is not strikingly large. I believe a more fair summary of their efforts could be \"tuning learning rates of Local SGD alone may not be able to gain much over SGD\" because other hyperparameters may also be very important, but this paper doesn't include any empirical study on them. For example, although this paper mainly views Lin et al. (2020) as a paper showing negative results of Local SGD, what they actually do in the paper is to propose a method, called \"Post-local SGD\", which is Local SGD with a special schedule of $H$: it starts with 1 and then increases to a larger constant halfway through training. In fact, Lin et al. (2020) found that this method can even beat SGD with the same number of training steps. So tuning the schedule of H, instead of tuning the schedule of learning rates, may improve the practical utility of Local SGD, but this paper doesn't have any related experiments. I would recommend the authors restrict their claim to tuning the learning rates alone.\n2. Another issue of this paper is that it doesn't make a clear distinction between the previous efforts studying optimization and generalization.\n    * Many tricks on learning rates, such as learning rate decay and warmup, are not only aiming for faster optimization. A folklore observation in deep learning is that starting training with a small learning rate can be much faster than that with a large learning rate, but in the end, the test accuracy is worse. The theory part of this paper only studies the learning rate from the optimization aspect, but in the experiments, the test accuracy is always reported. It is thus unclear whether the learning rates found by AdaScale are indeed \"optimal\" for test accuracy.\n    * Previous works such as Lin et al. (2020) and Gu et al. (2023) are studying the generalization aspect of Local SGD. Their claim is that Local SGD (with LR and H set properly) can achieve better test accuracy, although the training loss could be a bit worse than SGD. All their experiments are conducted in standard setups with CIFAR-10 and ImageNet, so it is unfair to ignore the results and claim the scenarios being studied are \"impractical\" (Page 4). I would recommend the authors write more clearly that the current paper only studies Local SGD in terms of the convergence speed of training loss, and report the training loss in all their figures.", "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 standard distributed data-parallel training of neural nets requires constant synchronization of the gradients between workers. Using Local SGD is one way to reduce the communication overhead, but its gradient estimate is biased. This paper borrows the idea of AdaScale to study how the learning rate should be set automatically for Local SGD. More specifically, their method adjusts the learning rates according to the gradient statistics and may automatically add more training steps until loss converges.\n\nBy comparing the empirical performances of SGD and Local SGD, the authors claim that Local SGD is empirically preferable to SGD only in extreme scenarios of communication being substantially more time-consuming than computation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is of high quality overall and I would like to vote for acceptance. However, I encourage the authors to rephrase their main claim on the practical utility of Local SGD and make a clearer distinction between optimization and generalization.\n\nTypos:\n* Page 3, Contribution 3: \"Local SGD convergences faster\" -> converges\n* Page 12, \"our findings on the value of Local SGD might limited to those conditions.\" -> might be", "broader_impact_concerns": "This work studies the optimization methods in deep learning and raises no ethical issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "A24ofWx3YG", "reviewer": "Reviewer_yXqE", "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* This work is very well written and easy to follow; indeed, it was a pleasure to read this paper.\n* The theory is also quite straightforward and provides a clear motivation for the proposed adaptive learning rate scaling.\n* Numerical experiments provide compelling evidence for the advantage of the proposed adaptive learning rate scaling method compared to the linear scaling heuristic.\n* The paper is also quite honest in taking a critical look at when one would expect Local SGD to be advantageous in practice, and the authors are not afraid to point out that extreme communication imbalance is required in practice to realize a speedup with Local SGD.\n\n### Weaknesses\n* All arguments in the paper follow by minimizing an upper bound on the expected loss function after $H$ local iterations. However, the practical quantity of interest is the validation accuracy. Given the non-convexity of the considered problem, decreasing the training loss as quickly as possible often leads to suboptimal solutions, especially in the case of supervised image classification. How do we reconcile the theory derived with respect to the training loss, and the practical quantity of interest, generalization and validation accuracy?\n* Proposed adaptation strategy requires double the communication overhead of Synchronous SGD with gradient accumulation, however the authors are explicit about this limitation in the work.\n* Numerical experiments are only conducted for supervised image classification with convolutional networks, however the authors are also explicit about this limitation in the work.\n* According to details in the appendix, momentum is used in all numerical experiments, however it is not clear to me how this is incorporated in practice, especially in the case of Local SGD. I am concerned that local momentum buffers quickly fall out of synch, and this will exacerbate performance of the Local SGD baseline with heuristic linear or square-root scaling of the learning rate. Are there both global and local momentum buffers? If so, how do they interact? If not, how do you synchronize momentum buffers? Would properly handling momentum buffers change the conclusions or decrease the performance gap? For instance, there is Slow-Momentum [1] or BMUF [2], which take special care in handling the momentum buffers in distributed optimization.\n* Based on the training loss curves in the appendix, it appears to me that all methods are still trained with a step-wise learning-rate decay. Is this indeed the case, that all numerical experiments are conducted with a step-wise learning rate decay? How does such a learning-rate schedule interact with the proposed Local AdaScale learning-rate scaling rule, and how do you reconcile this gap between theory and practice?\n* Why specifically focus on an AdaScale type derivation of the scaling rule, especially since the choice to minimize an upper bound on the training loss in each iteration is somewhat arbitrary given that the relevant quantity at the focus of this work is generalization/validation accuracy? For instance, why not consider Adagrad or Adam style updates?\n\n\n[1] Wang et al., Slowmo: Improving communication-efficient distributed sgd with slow momentum, ICLR 2020.\n\n[2] Chen et al., Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering, ICASSP 2016.", "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": "This work studies the convergence of Local SGD. In particular, the authors focus on ERM problems and derive an upper bounded on the expected decrease in the loss function in each iteration as a function of the number of workers $K$ and the number of local iterations $H$, when assuming L-smooth functions. They then derive a heuristic learning rate adaptation strategy that minimizes their upper bound on the expected training loss after $H$ local iterations. When $H=1$, they recover the AdaScale method, and thus they term their proposed strategy Local AdaScale. Following the AdaScale paper, the \"effective\" number of training iterations is tracked based on a specified \"gain scale,\" which depends on the online gradient norms, an upper bound on the stochastic gradient variance, and the learning rate... coarsely speaking using a smaller learning rate can to a first order result in a slower iteration counter, and thus require more physical iterations to train for a given \"effective\" number of iterations. As a result, the proposed method not only adapts the Local SGD learning rate, but also the total number of Local SGD training iterations.\n\nNumerical experiments are provided on supervised image classification with convolutional networks. The primary baselines are a) linear learning rate scaling with Synchronous SGD with $K$ workers and $H$ gradient accumulation steps, b) AdaScale learning rate scaling with Synchronous SGD with $K$ workers and $H$ gradient accumulation steps, c) linear learning rate scaling with Local SGD with $K$ workers and $H$ local gradient steps, d) Local AdaScale learning rate scaling with Local SGD with $K$ workers and $H$ local gradient steps.\n\nEmpirically, the proposed Local AdaScale strategy results in better generalization on the validation set than linear learning rate scaling with Local SGD. However, the authors also find that Local SGD requires a significant imbalance between communication and computation time (at least 3x in many cases) to provide any wall-clock speedups compared to large mini-batch SGD, since Local AdaScale can require many more training iterations to reach a certain level of performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Please include a discussion and clarify how to reconcile the theory derived with respect to the training loss, and the practical quantity of interest, generalization and validation accuracy.\n* Please clarify and make it clear in the main paper how momentum is used in the numerical experiments. Are there both global and local momentum buffers? If so, how do they interact? If not, how do you synchronize momentum buffers? Would properly handling momentum buffers change the conclusions or decrease the performance gap? How would the results change if one incorporated existing techniques for correctly tracking the momentum buffers, as in SloMo?\n* Please clarify whether the numerical experiments are conducted with a pre-specified step-wise learning rate decay rule on top of the proposed Local AdaScale rule. If so, please discuss how you reconcile this gap between theory and practice?\n* Please include a broader discussion on learning rate adaptation methods and their use in the literature.\n\nMy main concern with this work is the large gap between theory (motivation and derivation of an adaptive learning rate), and practice (unsynchronized momentum buffers, step-wise decay, validation accuracy vs training loss, etc.). I am concerned that the simple and well written exposition may provide a misleading picture for researchers, students, or practitioners trying to understand the behaviour of Local SGD.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IyKND8e8Uc", "reviewer": "Reviewer_3XYf", "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": "The article gives a good literature review over the topic. The presentation is quite clear and easy to read. The idea of using adaptive learning rate as in AdaScale to reduce the bias in eq 6 seems to be new to the local SGD literature. It is nevertheless unclear how much bias is reduced in the proposed algorithm 1. Further clarifications are needed for me to understand the numerical results.", "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 article studies the importance of the learning rate choice in the local SGD method for distributed optimization. Compared to the data-parallel SGD method, there is a bias in the update direction of this method, which makes the method fail to converge when the learning rate is not suitably chosen. An adaptive method is proposed, based on existing works for data-parallel SGD. Extensive numerical results to show the advantage of using local SGD relative to the data-parallel SGD, when the commutation between workers is costly.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-\tIn the numerical results in section 6, what is the definition of each iteration (in order to count n^{K,H} in eq 16) for the gradient accumulation methods? Is it the same k as the local SGD method? It is important to be precise on this. \n-\tAs mentioned in the beginning of section 6.1, one seeks to achieve a quite high test accuracy in each of the 3 dataset. Did you use this accuracy to decide the value of n^{K,H}? If so, how? Also why in Fig 5, the local-lin method with K=24 can still achieve such an accuracy (with a quite small number of epochs)? Is it contradictory to the result in Fig 4 ? Is the number of epochs  = n^{K,H} / training data size ? \n-\tThere is still a lack of understanding why the local SGD with the proposed learning rate scheduling can achieve a good accuracy. Is it due to the reduced bias as mentioned in section 4? Some further discussions on this would be good. \n-\tIn the abstract, the cost of added training iterations of local SGD is with respect to which method? Unlike in the synchronous case, which case are you referring to? In the introduction, when is local SGD empirically preferable to SGD, you mentioned local SGD converges faster than large batch SGD. What is the measurement of the speed here (to be faster)?", "broader_impact_concerns": "The main result of the article remains still empirical, but the topic is interesting so it may open up new research directions in the future.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers also recommend this be accepted, in particular after a slight adjustment in the claims. I agree with them.
Decision: Accept (poster)