Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
Authors: Chulhee Yun
Shashank Rajput
Suvrit Sra
Venue: ICLR 2022 Oral (2022)
Keywords: Local SGD
Minibatch SGD
Shuffling
Without-replacement
Convex Optimization
Stochastic Optimization
Federated Learning
Large Scale Learning
Distributed Learning

Abstract: In distributed learning, local SGD (also known as federated averaging) and its simple baseline minibatch SGD are widely studied optimization methods. Most existing analyses of these methods assume independent and unbiased gradient estimates obtained via with-replacement sampling. In contrast, we study shuffling-based variants: minibatch and local Random Reshuffling, which draw stochastic gradients without replacement and are thus closer to practice. For smooth functions satisfying the Polyak-Łojasiewicz condition, we obtain convergence bounds (in the large epoch regime) which show that these shuffling-based variants converge faster than their with-replacement counterparts. Moreover, we prove matching lower bounds showing that our convergence analysis is tight. Finally, we propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.

Published as a conference paper at ICLR 2022
MINIBATCH VS LOCAL SGD WITH SHUFFLING: TIGHT CONVERGENCE BOUNDS AND BEYOND
Chulhee Yun KAIST AI
Shashank Rajput Univ. of Wisconsin-Madison CS ra jput.3@wi www.wwwww..o...o.....o.........e edu
Suvrit Sra MIT EECS suvritêmit
chulhee, www.eeyynnkkkseccmmm.m
ABSTRACT
In distributed learning, local SGD (also known as federated averaging) and its simple baseline minibatch SGD are widely studied optimization methods. Most existing analyses of these methods assume independent and unbiased gradient es- timates obtained via with-replacement sampling. In contrast, we study shuffling- based variants: minibatch and local Random Reshufiling, which draw stochastic gradients without replacement and are thus closer to practice. For smooth func- tions satisfying the Volyak-Lojasiewite condition, we obtain convergence bounds (in the large epoch regime) which show that these suuffling-based variants con- verge faster than their with-replacement counterparts. Moreover, we prove match- ing lower bounds showing that our convergence analysis tight. Finally, we propose algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homen seur-homogeneuus settings.
INTRODUCTION
Distributed learning within the framework of federated learning (Konečný et al., 2016; McMahan et al., 2017) has witnessed increasing interest recently. A key property of this framework is that models are trained locally using only private data on devices/machines distributed across a network, while parameter updates are aggregated and synchronized at a server. Communication is often the key bottleneck for federated learning, which drives the search for algorithms that can train fast while requiring less communication-sse Li al. (2020a); Kairouz al. (2021) for recent surveys.
A basic algorithm for federated learning is local stochastic gradient descent (SGD), also known as federated averaging. The goal is to minimize the global objective that is an average of the local objectives. In local SGD, we have M machines and a server. After each round of communication, each of the M machines locally runs B steps of SGD on its local objective. Every B iterations, the server aggregates the updated local iterates from the machines, averages them, and then synchronizes the machines with the average. Convergence analysis of local SGD and its variants has drawn great interest recently (Dieuleveut & Patel, 2019; Haddadpour et al., 2019; Haddadpour & Mahdavi, 2019; Stich, 2019; Yu et al., 2019; Li et al., 2020b;e; Koloskova et al., 2020; Khaled et al., 2020; Spiridonoff et al., 2020; Karimireddy et al., 2020; Stich & Karimireddy, 2020; Qu et al., 2020).
Of the many, the biggest motivation for our paper comes from the line work by Woodworth et al. (2020a;b; 2021). In (Woodworth et al., 2020a;b), minibatch SGD is studied yet powerful baseline for this intermittent communication setting. Instead of locally updating the iterates B times, minibatch SGD aggregates B gradients (evaluated at the last synced iterate) from each the M machines, forms a minibatch of size M,, and then updates the shared iterate. Given the same M and B, local SGD and minibatch SGD have the same number of gradient computations per round of communication, so it is worthwhile to understand which converges faster. Woodworth al. (2020a;b) point out that many existing analyses on local SGD show inferior convergence rate compared to minibatch SGD. Through their new upper and lower bounds, they identify regimes where local SGD can be faster than minibatch SGD.
simple
While the theory of local and minibatch SGD has seen recent progress, there is still gap between what is analyzed versus what actually used. Most theoretical results assume independent and
A distinctive feature of federated learning is that not all devices necessarily participate in the updates; however, focus on the full participation setting in this paper.

---

Published as a conference paper at ICLR 2022
unbiased gradient estimates obtained via withh-replacmmen sampling of stochastic gradients (i.e., choosing training data indices uniformly at random). In contrast, most practitioners use without- replacement sampling, where they shuffle indices randomly and access them sequentially.
Convergence analysis of wethouttreplaeemmnt methods is challenging because gradients sampled within an epoch lack independence. As a result, the standard theory based on independent gradient estimates does not apply to bhuffling-based methods. While shuffling-base based methods are believed to be faster in practice (Bottou, 2009), broad theoretical understanding of such methods remains elu- sive, except for noteworthy recent progress mainly focusing on the analysis of SGD (Gürbüzbalaban al., 2019; Haochen & Sra. 2019; Nagaraj et al., 2019; Nguyen et al., 2020; Safran & Shamir, 2020: 2021; Rajput et al., 2020; 2021: Ahn et al., 2020; Mishchenko et al., 2020; 2021: Tran et al., 2021). These results indicate that the large-epoch regime (where the number of epochs greater than some threshold), without-replacement SGD converges faster than with-replacement SGD.
1.1 OUR CONTRIBUTIONS
We analyze convergence rates of without-replacemmet versions of local and minibatch SGD, where local component functions are reshuffled at every epoch. We call the respective algorithms local RR (Algorithm !) and minibatch RR (Algorithm 2), and their with-replacement counterparts local SGD and minibatch SGD. Our key contributions are as follows:
In Section 3, we present convergence bounds on minibatch and local RR for L-smooth func- tions satisfying the y--Polyak Soollykk-Ljasiewiiee condition (Theorems & 2). Our theorems give high- probability bounds, departure from the common in-expectation bounds in the literature. We show that minibatch and local RR converge faxter than minibatch and local SGD when the num- ber of epochs is sufficiently large. We also identify regime where local RR converges fast as minibatch RR: when synchronization happens frequently enough and local objectives are not too heterogencous. See also Appendix A for a detailed comparison with existing upper bounds.
Section 4, we prove that the upper bounds obtained in Section 3 are light, in all factors except L and μ.. We present Theorems 3 & 4 and Proposition 5 which show lower bounds that match the upper bound up to a factor of T,2 1/2p². Our lower bound on local RR indicates that the synchronization interval B is too large, then local RR has no gain from parallel computation.
In Section 5, we propose a simple modification called synchronized shuffling that allows to bypass the lower bounds in Section 4, at the cost of a slight increase in communication. By having the server broadcast random permutations to local machines, we show that in heagehooogessuus settings, the modified algorithms converge faster than the lower bounds (Theorems 6 & 7). In Appendix C, we present numerical experiments that corroborate our theoretical findings.
PROBLEM SETUP
Notation. For a natural number a N, let [a] := (1,2,...,,a) Let S, be the set of all permutations of [a]. Since our indices start from 1, we redefine the modulo operation between E Z and b e N as a mod = a - e-1 1b, to make a mod E [b].
Optimization task. Consider M machines, each with its objective Fz) for m E [M]. The m-th machine has access only to the gradients of its own N local components S (x), (=)),..... J (ar). In this setting, we wish to minimize the global objective function which is an average the local objectives:
ΣN fT'
F(x)= := 37
>M
(x) = MN ΣM EN" (w)
Further, we assume that each individual component function 1! is L-smooth, so that
(v) < ft (x) + (z) y - x) + l =||2 =|| for all x, E Rd,
(1)
and that the global objective F satisfies the j.Polyyk-t.ojaiieviin Lojsieewezz (PL) condition. |V=())] 2 (F(())) F*) for all Rdd where μ 0.
Algorithms. Under the above setting, we analyze local RR (Algorithm 1) and minibatch RR (Algo- rithm 2) and characterize their worst-case convergence rates. The algorithms are run over K epochs,
PP.. functions can he thought as a nonconvex generalization of strongly convex functions. In Algorithms and 2, consider SYNCSHUF as FALSE for now. We will discuss SYNcSHUF in Section 5.
2

---

Published as a conference paper at ICLR 2022
Algorithm Local RR (with and without SYNCSHUFF
Input: Initialization yo, step-size # machines M, components N, epochs K, syne interval B. 1: Initialize æi. := Yo for all m E [M].
2: for E [K] do
SYNCSHUF TRUE then
Local RR with SYNCSHUF
Sample d ~ Unif(Sw) x - Uni.(SM).
5:
Set of (i) a(i M m(m)) mod N) for all [M], [M].
N
6: else
Local RR
Sample of (Sw) independently and locally, for all m E [M].
8:
end if
9:
for E [N] do
10:
for m E [M] do locally Update #i,. = whi-1 V Sog 2 (1)
12:
end for
13:
B divides then
14:
Aggregate and average Vk. = 37 Em= a
B Synchronize vh.. == ys. # for all m E [M). end end for
15:
16:
17:
18: #1+1,00 Vk. x. for all [M].
19:
end for
20:
return the iterate UK -
Algorithm Minibatch RR (with and without SYNCSHUF)
Input: Initialization æo. step-size machines M, components N, epochs K, syne interval B.
1: Initialize 21,0 = æ0.
2: for E [K] do
3: if SYNCSHUF = TRUE then (Sw), ). Unif(Sas).
>
Minibatch RR with SYNCSHUF
4: Sample
N 5: Set of (1) == o(ti + Mf (m)) mod N) for all m E [M], E [N].
6: else
> Minibatch RR
7:
Sample of Unif(Sw) independently and locally, for all [M].
end if
9:
E 1
Update T2ts == #x,i-1
Σ mm1
Σ
11:
end for
2x+1.0 2x
avenging done locally
13:
end for
14: return the last iterate x K
i... K passes over the entire component functions. At the beginning epoch k. each machine m shuffles its local component functions {f. Ti=1 using random permutation of Unif(Sx) ). In local RR, each machine makes B local RR updates to its iterate by sequentially accessing its shuffled component functions, before the server aggregates iterates from all the machines and then synchronizes the machines with the average iterate. In minibatch RR, instead making B local updates, each machine collects B gradients evaluated at the last iterate, and the server aggregates them to make an update using these M B gradients. Since these two algorithms use the same amount of communication and local gradients, minibatch RR is simple yet powerful baseline for local RR.
Below, we collect our assumptions on the algorithm parameters used throughout the paper.
Assumption (Algorithm parameters). We assume M 1, > 2, and K 2 Also, assume that B divides N. We restrict < B < N for minibatch RR because B N makes the algorithm equal to GD. We also assume 2 < B < N for local RR because B = 1 makes the two algorithms the same. We choose constant step stze-size scheme, i.e., is kept constant over all updates.
We next state assumptions on intra- and inter-machine deviations used in this paper.*
Assumptions 2,3 & require that they hold for the whole Rd We discuss ways avoid it in Appendix D.7.
3

---

Published as a conference paper at ICLR 2022
Assumption 2 (Intra-machine deviation). There exists
such that for all m [M] and E [N],
|| I v, for all a R
Assumption 2 requires that the difference between the gradient of each local component function (x) and its corresponding local objective function F=)(x) is uniformly bounded. It models the variance of local components f:" within each machine. While the uniform boundedness requirement may look strong, we use this assumption to prove high-probabbilty upper bounds, which are stronger than the common in-expectation bounds. See Appendix A for comparisons with other assumptions, and also Appendix D.7 for ways to avoid uniform boundedness over the entire R
The next two assumptions capture the deviation across different machines, i.c., the degree of hetero- geneity, in two different levels of granularity: objective-wise and component-wise. Assumption (Objective-wiis inter-machine deviation). There exist T 2 0 and p 2 1 such that
M ||VF"(())) (a))l S t [VF(()) for all æ E BR
Assumption 3 models the heterogeneity by bounding the mean of |V by a constant plus a multiplicative factor times FFI. The assumption includes the homogeneous case (i.e., Fl FM = F) by J = 0 and p = 1. Assumption is weaker than many other heterogeneity assumptions in the literature (e.g., Karimireddy al. (2020)); see Appendix for detailed comparisons.
Assumption 3 measures heterogeneity by only considering the local objectives 1T not the local
components f." We consider more fine-grained notion of heterogeneity in Assumption 4:
Assumption (Component-wiy) wise inter-maching deviation). For all E [N], let ft = 1 There exist À 2 0 such that for all E [M] and i [N].
M Σm= STh
V S (x)
V f=(())] S X, for all x E Rd.
Assumption states that the gradients of the i-th components of local machines are "close" to each other. The assumption subsumes the component-we homogeneous setting, i.c., f = f f.M. by À 0. In distributed learning, this choice corresponds to the setting where each machine has the same training dataset. Assumption 4 with > also relevant to the case where each device has slightly perturhed (e.g., by data augmentation techniques) version of certain dataset. is straightforward to check that Assumption 4 implies Assumption 3 with T = and =
We conclude this section by defining the function classes study in this paper. Definition (Function classes). We consider two classes of global objective functions funcctinn F, also taking into account their local objectives 1mm and local components f. We assume throughout that f are differentiable and F is bounded from below.
Fobj H4, (L, T. == [ F is p-PL; fthh are L-smooth; F, FTh, fth satisfy Assumptions 2 & 3 Fomp(L, A) (F i- f:h are L-smooth; F, FT f:h satisfy Assumptions 2 & 4
Notice that Fobsi L, μr, V2 P, 3 Femp(L, T) for any 2 1. We only make the Pt. assumption on the global objective F, not on the local objectives pmm
the local components f?" Using
L and μ. we define the condition number K == 1/p 2 1.
3 CONVERGENCE ANALYSIS OF MINIBATCH AND LOCAL RR
3.1 UPPER BOUND FOR MINIBATCH RR
We first begin with the convergence result for minibatch RR on (L, which exhibits a faster large-epoch rate compared to the single-machine setting. For upper bounds, we use Ö(-) to hide universal constants and logarithmic factors of J. M, N, K, and B.
Theorem 1 (Upper bound for minibatch RR). Suppose that minibatch RR has parameters satisfying Assumption 1. For any F E Faby L, ,1 V, T. P). consider running the algorithm using step-size
B MoogMMMa NK3) for epochs K 2 6x log log K2). Then, with probability at least 1- 6,
7
HNK
F( x) F* F(wo) F
MNK² + + (12 v2
(3)
MNK?
4

---

Published as a conference paper at ICLR 2022
Proof. The proof is in Appendix D.2. The key challenge in the convergence analysis of our shuffling- based method stems from the indices sampled within an epoch being dependent on each other. For example, if fi" is accessed already, then the index i 1 will not be used in later iterations of the epoch; this dependence significantly complicates the analysis. Our approach starts with real- izing that for any permutation o, E Fo(n) NF We decompose gradients V (
(2) (Zx..-1)
( (i) (IXg.0) plus noise, then aggregate all updates over an epoch get "one big step of GID plus noise": 21++100 F4,0 F) + n We bound the noise ryK using Lemma 8 (Appendix D.6), which is our extension of the Sheffding-Serfiing in- equality to the mean of M independent without-replacemmntt sums of vectors; the lemma might be of independent interest too. Lemma 8 shows that averaging accumulated gradients over M machines reduces variance by M, which leads to the reduction by factor of M in the bound (3).
(see Line 10 of Algorithm 2) into V V
O
Theorem shows that for large enough epochs K W K, minibatch RR converges at rate of 12'22
O 1 MNRR) with high probability. Compared the large-epoch rate Ö مري machine RR (e.g.. Ahn et al. (2020)), we see an additional factor M in the denominator, which highlights the advantage of multiple machines. If we compare against the with-replacement coun- terpart, it is known that for strongly convex and smooth F, the optimal convergence rate of minibatch SGD is O <MNRR) )²² which is worse than our bound (3) if K Z x². Also notable is that the con- vergence rate does not depend on the heterogeneity constants (i.c., and p from Assumption 3) of the local objective functions. This observation that minibatch RR is "immune" to heterogeneity consistent with minibatch SGD in the with-replacement setting (Woodworth et al., 2020b).
(>NN? of single-
Epoch vs communication complexity. One might wonder why (3) does not have the batch size B. In (3), we wrote convergence rates in terms of epochs K, which captures the gradient computation complexity because the same number gradients are evaluated in single epoch regardless of B. we are interested in communication complexity instead, we can write (3) in terms of the number of L.,2N
communication rounds R == NK and get a rate of Ö (( RH ). From these, we can also discuss the overall cost of the algorithm. If the cost of communication round is ces and the cost of local gradient computations over an epoch is co. then the total cost to obtain an e-accurate solution is
Cminibatch (c) = = (CNNN
CCV
(
(4)
BVMe
VMN
omitting T. and for simplicity. The total cost shows that there is essentially no harm increasing the batch size B in minibatch R.,, as we can get more accurate estimates of true gradients as B becomes larger. In the next subsection, we will see that this is not the case in local RR.
What about K S A:? We remark that all upper bounds in this paper hold only for the "large-epoch" regime, where K Z K. Such requirements are common in the literature of without-replacemeet SGD (Haochen & Sra, 2019; Nagaraj et al., 2019; Rajput et al., 2020; Ahn et al., 2020), and there is recent result (Safran & Shamir, 2021) suggesting that faster convergence of wethouttrrelaccmment SGD may not be possible in the K S regime. We defer a more detailed discussion on this regime to Section 4, after Theorem 3.
3.2 UPPER BOUND FOR LOCAL RR
Next, we are interested in how fast local RR can converge, what is the optimal batch size B, and whether local RR can be as fast as minibatch RR.
Theorem 2 (Upper bound for local RR). Suppose that local RR has parameters satisfying As- sumption I. For any F Fobj(L, M, p).). consider running the algorithm using step-size
l for epochs K 7pm log( Mogg(MM (M Then, with probability at least 1 - 8, PNK
FlyK, F* F(yo)- - F*
+0(1"
T.2
(
122 MNKK +
LBB
N²K3 ))
r²B²
MNK² + +6
(5)
N²K²
'The optimal rate for (with-replacement) SGD after R iterations O 22 With-replacement minibatching reduces the variance v²2 to MB. and R NK B
(see e.g., Rakhlin al. (2012)).
However, achieving the optimal rate for last iterates typically requires carefully designed step-size schemes (Jain al., 2019).
5

---

Published as a conference paper at ICLR 2022
Proof. The proof is in Appendix D.3. We take the same "big GD step plus noise" approach as in Theorem I; however, due to local updates, bounding the noise is much more involved. In the proof, we obtain the epoch update Uk+1.0 ys,0 ny.V (o + +j and T4.3 contain errors introduced by local updates. Noise from local updates accumulates over B iterations, which cannot be remedied by averaging over M machines. They result in two additional terms in the rate (5), one from intra- maraine variance and the other from heterogeneity.
+ 7frx, ry where 1k.1
3.2.1 DISCUSSION OF THEOREM 2
Let us compare our high--robabbiltyy bound (5) with existing in-expectation bounds. For strongly L2y²B n NNMK + Hº N= + L g² ) N=
convex F, the corresponding last-iteran bound of local SGD is Ö (Khaled et al., 2020; Spiridonoff' et al., 2020; Qu et al., 2020). Notice that (5) better than this with-replacement bound when K Z K. For average iterates, there are known bounds Ō ( u²
Lu²
"MNN +
L + -." ==N= (Koloskova et al., 2020; Woodworth et al., 2020b) which are smaller than the u=N=K=
last-iterate bound by factor of k. It is unclear if averaging iterates could improve our rate, because most such analyses exploit Jensen's s inequality, which we cannot use for nonconvex F.
Dependence on and p. Out of the two heterogeneity constants and p (Assumption 3), P does not appear in (5), and it only affects the epoch requirement Z pk. Consider the case T = 0 and 1, which is heterogeneous but in the "interpolation regime," because (x) 0 whenever VF(x) = 0. In such a case, the rate (5) is equal to the homogencous case.
Using B (NN) is no better than single-machine A close look at Theorem 2 reveals rather surprising fact. Even in the homogeneous case (T = 0), if we choose B = O(N), then local RR converges at the rate of Ó ((k=)): ): the same rate as the single-machine RR! In Section 4, we show that this observation is not due to suboptimal analysis; the rate Ö( ( is tight for B ((N).
Trade-off' in the choice of B. As done for Theorem 1, we can compute from (5) that the total cost of local RR for e-accuracy is (omitting L and μ for simplicity)
Clocalle) = =Ō(ce Cc
PVN
" DVB TB (MNN NVEE ATa
+
++ Ve)
+
(6)
BVMe
VBe
Note that for local RR, there exists a trade-off between communication and epoch complexity in the choice of B. If B is too small, this reduces the number of epochs required but increases communi- cation costs. On the other hand, if B is too large, this reduces communication rounds but errors that accumulate in local updates get severer, resulting in the need for more epochs. Hence, the optimal choice of B must balance the two complexity measures. The existence of this trade-off is indeed different from minibatch RR where larger B always reduces the total cost Cminibatch (e).
When can local RR match minibatch RR? Comparing the convergence rates (3) and (5), we can identify some regimes in which local RR converges as fast as minibatch RR. In a nutshell, if machines are not too heterogeneous and communication happens frequently, then local RR can have the same upper bound as minibatch RR. For example, if B is chosen to be constant, M S N, and T S //N/M, then the Õ matches (3). Another example of such regime is when B S N and S //M/N. Note that this 37 comparison assumees that the same values of B are chosen for both algorithms. Also, such "frequent communication" regimes are favorable if the communication cost ce is small.
Ft (NNKK term in (5) becomes the dominating factor and hence
5,2u²
Can local RR ever beat minibatch RR? The upper bounds (3) and (5) indicate that local RR is always no better than minibatch RR, least for the function class Fabj (L, μ. p). This in fact consistent with Woodworth et al. (2020a:b), because the authors identify regime where local SGD performs better than minibatch SGD for convex objective functions, but fail to do so for strongly convex functions. However, as was also pointed out in Woodworth et al. (2020a), there is simple extreme scenario in which local RR can be faster: when v R T Re 0 and p R 1. In this case, we have fm ~ F for all m and i, so local RR corresponds to NK steps of GD, whereas minibatch RR corresponds to NK B steps of GD. Clearly, local RR will converge faster, exploiting the advantage of more updates. Finding out other such regimes is an important future direction.
'Due differences in assumptions, many existing rates cannot be compared directly. These rates are the ones we consider "comparable" to our hound. See Appendix for more detailed comparisons.

---

Published as a conference paper at ICLR 2022
4 MATCHING LOWER BOUNDS
In Section 3, we presented large-epoch upper bounds (i.c., for K 2 x) for constant step-size mini- batch and local RR. In this section, we prove matching lower bounds to show that the upper bounds tight, in all factors except L and ja. We use S2(-) to hide universal constants in lower bounds.
4.1 LOWER BOUND FOR MINIRATCH RR
Theorem 3 (Lower bound for minibatch RR). Suppose that minibatch RR has parameters satisfying Assumption 1. Additionally, assume that N is a multiple of 2. Then, there exist large enough constants C12 c2 such that the following holds: For L and μ satisfying 4 2 Ct there exists a function F E Femp (L, H4, v, 0) such that for any constant step-size n,.
52
V² PMNK D²
if < o2K,
E
F F(
if 2 C2K.
JMNNK
Proof. We prove Theorem 3 in Appendix E. The proof is an extension of Rajput et al. (2020); Safran & Shamir (2020; 2021) to minibatch RR. We will sketch some key intuitions after Theorem 4. N
First notice that the function is from (T, 14, v, 0), where all the machines are component-wise homogeneous. As seen in Definition 1, Femp (L, fr, 2/ 0) C. Fobs (L, M,V, v, T, p) for any 7 0 and p 2 I, so Theorem 3 provides a lower bound for Femp() (.) and Fobj(-), with arbitrary heterogeneity constants. We assume that N is even because we construct functions ςa and O2 such that f. == Ii N. if S 2. and f. := 92 if i > 2 One can remove this assumption by using a zero function when N is odd (see e.g., Safran & Shamir (2020)). It is rather unsatisfactory that our theorem requires large enough constants e₁ and (2; we believe tighter analysis can relax this restriction.
Theorem 3 proves lower bounds for two different regimes: K 2 K. and K S k. In the large-epoch regime (K Z x),, we can observe that the lower bound Q2 (ANK*) matches the upper bound (3) in Theorem 1, modulo a factor of x². Tightening the x² gap between upper and lower bounds is left for future work. In the small-epoch regime (K S k), we observe that the lower bound 2 u² exactly matches the convergence rate of (with-replacemmett) minibatch SGD; hence, the lower bound implies that minibatch RR has no hope for faster convergence than minibatch SGD, at least in the constant siep-size and small-epoch regime. This observation is in line with Safran & Shamir (2021).
HMNK
Upper bounds for K S k?? Even for single-machine RR (M 1), proving an upper bound that matches the small-epoch lower bound Q
_2 still remains a challenge. Nagaraj et al. (2019, The- 2²
WNK
orem 2) prove an upper bound for non-quadratic strongly convex functions that matches 2 #NK if NK Z x²?; however, they use suffix averaging, so it is not directly comparable to Theorem 3 which considers last iterates. Safran & Shamir (2021) prove upper bounds for quadratic strongly convex functions, but assume that their Hessian matrices commute. For noncommutative cases, proving a small-epoch upper bound seems to require some form of matrix AM-GM inequalities, whose avail- ability an open problem (Recht Ré, 2012; Lai & Lim, 2020; De Sa, 2020; Yun et al., 2021).
Remark 1 (Strong convexity in construction). We note that all lower bounds in this paper are structed with strongly convex functions, a stronger assumption than Pt. functions (2). Thus, our lower bounds are also applicable strong convexity counterparts of Fobs(-) and F-mp(-)-
4.2 LOWER BOUNDS FOR LOCAL RR
In this subsection, we present lower bounds for local RR. We prove two bounds that correspond to homogeneous and heterogeneous cases. By combining the two bounds, we get lower bound that matches our upper bound (5) in Theorem 2 up to a factor of x²²
Theorem 4 (Lower bound for local RR: homogeneous case). Suppose that local RR has parameters satisfying Assumption 1. Additionally, assume that B is a mudtiple of 4. Then, there exist large enough constants C3, C4 > 0 such that the following holds: For L and μ satisfying k. > c3. there exists a function F E Femp p, 0) such that for any constant step-size 17.
22 WMNK D2
if < max (CAN,
MB
E [(UK -F*
N
(8)
Ω
[uMNK=
+
BBB WN2K2)
MB 1 if K max (cnk,
N J.
7

---

Published as a conference paper at ICLR 2022
Proof. The proof is in Appendix G. For the large-epoch lower bounds in Theorems 3 and 4, use "skewed" quadratics f."(() (x) (Llrgo + plr>0) 2 2,1/ where 2; = if < N and 2
2; = -1 otherwise. For x ~ 0, the imbalance results in a "drift" towards positive x. whose strength approximately proportional to the absolute value of partial sums of random permutations over NN -_ - By averaging the sums over M machines (minibatch RR), their absolute values shrink by v in contrast, if each machine makes local updates (local RR), the magnitude of the drift cannot be reduced with M, because we average after local iterates already have taken B "big" steps. The proof uses techniques from Rajput et al. (2020).
+ +I's and A
1
Proposition 5 (Lower bound for local RR: heterogeneous case). Suppose that local RR has param- elers satisfying Assumption 1. Additionally, assume that B is multiple of and K. = #22 2 2. Then, there exists function F E Fobi (L, nr 0, 7, 1) such that for any constant step-size 1,
B²B²
E F(yx - -
(9)
PNNK2
Proof. We note that Proposition 5 is almost identical to Theorem II of Karimireddy et al. (2020);
however, we provide a proof specific to our algorithm in Appendix I.
Theorem 4 constructs a component- wise homogeneous function from Famp H4, 0) and Propo- sition 5 constructs a heterogeneous function from Fobj M,, O, 1). Since Famp (L, μt 14, 0) U LL, (4, T, C Fobj (L, μt, T, for any p 2 1, combining (8) and (9) for the 2 2²
v²B =²B² }) that matches the max(cax, MB case gives lower bound Mmmax pMNK? WN-K* (N=RE)) N
large-epoch upper bound (5) in Theorem 2, up to a factor of x?? When KN 2 MB, CдK becomes the dominating term in the max, in which case the threshold in (8) is (k)). Tightening the X² gap as well as removing additional requirements such as k 2 C3 and xN Z MB are left for future work.
Using B ((N) does not help, indeed. In Section 3.2.1, observed that if B ( then even in the homogeneous case (T = 0), local RR converges the rate of Ō <k==), ). This is the same rate as single-machine RR, meaning the efforts by M - 1 machines become meaningless. Our lower bound (8) shows that Ō( wk=) ) is in fact the best we can hope for (treating T. and ju as constants). In order make the best use of M machines, B should be smaller than O as suggested in Section 3.2.1. In an existing work, Mishchenko et al. (2021) consider local RR with B = N as a special case of a proximal algorithm. In Theorem of Mishchenko et al. (2021), the authors claim "the convergence bound improves with the number of devices involved" because the bound has a factor of M in the denominator. However, at least under our assumption, this is not the case; if we apply our Assumption 3 to upper-bound their a., the term "No?" 2n in the numerator grows linearly with M. Hence, our bounds do not contradict Mishchenko et al. (2021); see Appendix A for details.
Remark 2 (Small-epoch bound is likely loose). We note that while we focused on deriving a match- ing large-epoch lower bound, we did not try hard to tighten the small-epoch lower bound. Our =²B small-epoch lower bound in (8) misses term (such pNTK*) that corresponds to the error from local updates. We leave investigations on small-epoch lower and upper bounds for future work.
SYNCHRONIZED SHUFFLING: HOW TO BYPASS LOWER BOUNDS
Recall from the total complexity of minibatch RR (4) that the total cost shrinks with a factor of VM'
Using M machines, we are only getting v M-factor speedup. Ideally, we hope to see a linear speedup, i.e., cost inverse proportional to M. Hence, Theorem 1 falls short of achieving this goal, and our lower bound in Theorem confirms that linear speedup is indeed impossible.
In this section, show that the desired linear speedup is possible, at least in some special cases. We consider the component-wise wear-homogeneour case (i.e., Assumption with small A) and discuss how simple modification minibatch and local RR can let us "break" the lower bounds and achieve linear speedup. This comes at a cost of broadcasting permutations: at the beginning Unif(Srr), and broadcasts them
of the k-th epoch, the server samples a Uni and to the machines. Then, local machines choose their permutations of to be shifted versions of o,² i.c., of (i) == a ((i+ N (m)) mod N). We call this trick synchronized shuffling, denoted as Wee assume for simplicity that M divides N.
8

---

Published as a conference paper at ICLR 2022
SYNCSHUF. Please revisit Algorithms and 2 for the precise descriptions of the modified algo- rithms local RR with SYNCSHUF and minibatch RR with SYNCSHUF, respectively.
The intuition why this should help is simple. In the proof of RR, aggregate the component gra- dients over an epoch (i.c., N iterations) to write it as a full gradient plus noise. If we are in the component- -wise homogeneous setting and permutations gating N component gradients on a single machine, we can aggregate गł component gradients on M machines to get a full gradient. This allows us reduce the "noise" from without-replacement sampling. We emphasize here that we do not necessarily set B M to get full gradient every time; our analysis works for arbitrary B and M, as long both divide N. See Appendix B for detailed illustration of SYNCSHUF; also, see Appendix C for experiments showing its effectiveness.
synchronized, then instead of aggre- N
The idea of synchronized shuffling is similar to approaches in distributed learning that shuffle and partition datasets and distribute them to local machines (see e.g., Lee et al. (2017); Meng et al. (2017)). In contrast, we do not communicate data, but communicate how to permute datasets stored in local machines. Meng et al. (2017, Theorem 3.3) provide analysis for distributed method similar to minibatch RR, but fail to show convergence to global minima in strongly convex cases. We also note that an independent concurrent result (Szlendak et al., 2021) uses the same idea as SYNCSHUF to build compressors for communication -fffccinnnn distributed optimization.
5.1 UPPER BOUNDS FOR MINIBATCH AND LOCAL RR WITH SYNCSHUF
With SYNCSHUF, we can show that the M's appearing in the convergence rates ((3) and (5)) in Theorems 1 and can be replaced with M for more stringent function class Femp() that requires bounded component-wise inter-machine deviation (Assumption 4).
Theorem 6 (Upper bound for minibatch RR with SYNCSHUF). Suppose that minibatch RR with SYNCSHUF has parameters satisfying Assumption 1. Additionally assume that M divides N. For any F E Femp(1. (L, j4, v, X), consider running the algorithm using step-size 1j B loggM NK*) for
H K
epochs K 2 GK log( K2) Then, with probability at least - -5,
F( - F 10 (
v2
X
F( F=
M2NK2 + Ö
M2NK2 + 1
(10)
MK2
The proof of Theorem 6 is presented in Appendix D.4. One can check that if the component- wise deviation constant satisfies X S VMN (i.e., near- seaa-homogeneous) then the rate (10) becomes
Ō >
). It is then easy to confirm that M machines reduce total costs by M linear speedup.
A similar speedup can be shown for local RR. In Appendix D.5, we prove that Theorem (Upper bound for local RR with SYNCSHIFF), Suppose that local RR with SYNCSHIF
has parameters satisfying Assumption 1. Additionally assume that M divides N. For any F
log(MP2 for epochs K 2 aNK
Femp [L, J,, v, A), consider running the algorithm with step-size 1 7k log( N22 Then, with probability at least
- 5,
F(yo) F M2NK2 + +
L2
1²
BBB
B N2K2
X² MK²) )) (1I)
yK ( 26
1B
MENK2 N²K2
We can similarly check that if B M
N
and A VMN i.e., frequent communication and near-
homogeneity, then the Ö MZNK>) term dominates in (11), and hence gives a linear speedup that matches the best rate of minibatch RR with SYNCSHUF (10). Nevertheless, we note again that for local RR, such small B is favorable only when the communication cost c. is small (recall (6)).
CONCLUSION
We studied convergence bounds for local RR and minibatch RR, which are the practical without- replacement versions of local and minibatch SGD studied in the theory literature. For smooth func- tions satisfying the Polyak-Lojasiewicz condition, we showed large-epoch convergence bounds for minibatch and local RR that are faster than their with-replacement counterparts. We also proved matching lower bounds showing that our convergence analysis is tight. We also proposed a sim- ple modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-howd har-hhomgeeneuss settings. Immediate future research directions include extension to small-epoch regimes, as well as general convex and nonconvex functions.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
This paper develops theoretical guarantees for popular distributed stochastic optimization algo- rithms. Therefore, the authors do not any particular concerns related to its ethical aspects or future societal consequences.
REPRODUCIBILITY STATEMENT
This paper is a theoretical work, without any experimental results. Definitions and assumptions are provided in Section 2. Our theoretical contributions well some additionally required assump- tions are clearly stated in Sections 3, 4, and 5. Complete proofs of all the theorems are provided in the appendix.
REFERENCES
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. In Advances in Neural Information Processing Systems, 2020.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Pro- ceedings of the symposium learning and data science, Puris, 2009.
Christopher M De Sa. Random reshuffling is not always better. Advances in Neural Information Processing Systems, 33, 2020.
Aymeric Diculeveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32:13601-13612, 2019.
Mert Gürbüzbalaban. Asu Ozdaglar, and Pablo Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, pp. 1-36, 2019.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in feder- ated learning. arXiv preprini arXiv: /4425, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32:1 11094, 2019.
Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In International Conference on Machine Learning, pp. 2624-2633, 2019.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pp. 1752-1755. PMLR, 2019.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjum Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. I.. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Ja- vidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Pra- neeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-110, 2021. ISSN 1935-8237. doi: 10.1561/22000000833 URL http://dxx doi o 10 15611116611 1tw.11....1111101101110 220002000000....
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the chine Learning and Knowledge Discovery in Databases, pp. 795-811, Springer, 2016.
condition. Joint European Conference on Ma-
10

---

Published as a conference paper at ICLR 2022
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143, PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- on Machine Learning, pp. 5381-5393. PMLR, 2020.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 1xXiv:6610005492 2016.
Zehua Lai and Lek-Heng Lim. Recht-Ré noncommutative arithmetii--eomeerii mean conjecture is false. In International Conference on Machine Learning, 2020.
Kangwook Lee. Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ram- chandran. Speeding up distributed machine learning using codes. IEEE Transactions on Infor- mation Theory, 64(3):1514-1529, 2017.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and futuree directions. IEEE Signal Processing Magazine, 37(3):00-60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Dhillon, D. Papailiopou- los, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume 2, pp- 429 450, 2020b. URL https: httt:s::/proceeedingg wtw.eddinnssmsss...........m.m.. org. http:/appe//22//////g2 201/2/000/eeee//////////e/ 38af8613
TEEE86134b65dl 4b6500 11110e3333dd7744444 Paw.:ed7766ee--eap...ppp.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. In International Conference on Learning Representations, 2020c.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-fficientt learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Qi Meng. Wei Chen, Yue Wang, Zhi-Ming Ma, and Tie- Yan Liu. Convergence analysis of distributed stochastic gradient descent with shuffling. arXiv preprint arXiv: 10432, 2017.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. arXiv preprint arXiv:2006.05400 059888 2020.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. arXiv preprint 1xiv:2102.06704, 2021.
Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pp- 4703 47 11, 2019.
Lam M. Nguyen, Quoe Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten van Dijk. uni- fied convergence analysis for shufffing-type type gradient methods. arXiv preprint arX1v:2002.08246, 2020.
Iosif Pinelis. An approach incqualities for the distributions of -ineess-dimmeniinalll martingales. In Probability Banach Spaces, 8: Proceedings of the Eighth International Conference, pp- 128-134. Springer, 1992.
Iosif Pinelis. Optimum bounds for the distributions of martingales in banach spaces. The Annals of Probability, pp. 1679-1706, 1994.
11

---

Published as a conference paper at ICLR 2022
Zhaonan Qu, Kaixiang Lin, Jayant Kalagnanam, Zhaojian Li, Jiayu Zhou, and Zhengyuan Zhou. Federated learning's blessing: Fedavg has linear speedup. arXiv preprint arXiv:2007.05690, 2020.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, 2020.
Shashank Rajput, Kangwook Lee, and Dimitris Papailiopoulos. Permutation-basee sgd: Is random optimal? arXiv preprint arXiv:2102.097/5 2021.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference International Conference on Machine Learning, pp. 1571-1578, 2012.
Benjamin Recht and Christopher Ré. Toward a noncommutative arithmetic- geoeetri mean inequal- ity: conjectures, case-studies, and consequences. In Conference on Learning Theory, pp. 11-1, 2012.
Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pp. 3250-3284. PMLR, 2020.
Itay Safran and Ohad Shamir. Random shuffling beats SGD only after many epochs on ill- conditioned problems. arXiv preprint arXiv:2106.06880, 2021.
Markus Sehneider. Probability inequalities for kernel embeddings in sampling without replacement. In Artificial Intelligence and Statistics, pp. 66-74, 2016.
Robert J Serfing. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pp. 39-48, 1974.
Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch Paschalidis. Local sgd with a communication overhead depending only the number of workers. arXiv preprint arXiv:2006.02582 2020.
Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2019.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 21: 1-36, 2020.
Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.033000, 2021.
Trang H Tran, Lam M Nguyen, and Quoc Tran-Dinhe Dinh. Smg: A shuffling gradient-based method with momentum. In International Conference on Machine Learning, pp. 10379-10389. PMLR, 2021.
Blake Woodworth, Kumar Kshitij Patel, Sehastian Stich, Zhen Dai, Brian Bullins, Brendan Mema- han, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020a.
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. arXiv preprint arXiv:2102.01588 2021.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6292. 2020b.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693- 2019.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, pp. 4653-4658, PMLR, 2021.
12

---

Published as a conference paper at ICLR 2022
CONTENTS
1 Introduction
1.1 Our contributions
2 Problem setup
3 Convergence analysis of minibatch and local RR
3.1 Upper bound for minibatch RR
3.2 Upper bound for local RR
Matching lower bounds
4.1
Lower bound for minibatch RR.
4.2
Lower bounds for local RR
5
Synchronized shuffling: how to bypass lower bounds
5.1
Upper bounds for minibatch and local RR with SYNCSHUF
6
Conclusion
Comparisons with assumptions and rates in existing results
14
B More detailed illustration of synchronized shuffling
18
C Experimental results
19
C.I SYNCSHUF improves convergence of minibatch/local RR
20
C.2 Local RR becomes closer to single-machine RR B + N
21
C,3 With- vs. without-replacemmnt sampling
22
Proofs of upper bounds
23
D.I Proof outline
24
D.2 Proof of upper bound for minibatch RR (Theorem 1)
24
D.3 Proof of upper bound for local RR (Theorem 2)
29
D.4 Proof of upper bound for minibatch RR with SYNCSHUF (Theorem 6)
35
D.5 Proof of upper bound for local RR with SYNCSHUF (Theorem
39
D.6 A generalized vector-valued Doeffding-Serfling inequality
42
D.7 How can we avoid uniform bounds over d in our assumptions?
44
Proof of lower bound for minibatch RR (Theorem 3)
46
E.1 Lower bound for 1 < #NK
47
E.2 Lower bound for 1 2 RNK and r S 513LN
47
E.3 Lower bound for 7 2 ZNK and 1) > B
50
13

---

Published as a conference paper at ICLR 2022
F
Proofs of helper lemmas for Appendix E
52
F.1
Proof of Lemma
52
F2 Proof of Lemma 12
55
E3 Proof of Lemma
55
F4 Proof of Lemma 14
57
F55 Proof of Lemma
G Proof of lower bound for local RR: homogeneous (Theorem 4)
59
G.1 Lower bound for 1 Σ RNK
60
G.2 Lower bound for 7) 2 μNK and r) 10251.N
60
G.3 Lower bound for 1 2 nNK and rj 2 1025I.N
64
H Proofs of helper lemmas for Appendix G
66
H.l Proof of Lemma 16
66
H.2 Proof of Lemma 17
70
H.3 Proof of Lemma 18
70
H.4 Proof of Lemma 19
72
I Proof of lower bound for local RR: heterogeneous case (Proposition 5)
73
L1 Lower bound for SpNK S 8uB and
<
73
I.2 Lower bound for 7 S 8μNK and n
75
A COMPARISONS WITH ASSUMPTIONS AND RATES IN EXISTING RESULTS
In this section, we compare our assumptions and convergence bounds against other existing results mentioned in the main text. Most existing results that study independent and unbiased gradient estimates state their assumptions in terms of the expectation over the randomness the estimate; for such assumptions, we adapt them to our finite sum setting in order to make for easier comparison.
Heterogeneity assumptions. start by discussing our definition objective-wise heterogeneity (Assumption 3), namely that there exist + 2 0 and p 2 1 such that
M (VF*(
Σ
<
(+)) for all a E Rd.
(12)
M
Perhaps the most relevant to this assumption the (G, B)BGG assumption that appears in Karim- ireddy al. (2020): For all Rdd
1
Σ
[V) G + D /F(x))]
(13)
M
Note that thanks Jensen's inequality and a² 1/ (a b)2 for a, 0, (13) implies
M
M
1
V (2)))
|
[z) < G² + B² VV < (G + B BI
M
M
m=1
1=
and hence (12) with 7 and p B. Therefore, our Assumption weaker than the (G, B) BGD assumption. Several papers (Haddadpour & Mahdavi, 2019; Li et al., 2020b) the same
14

---

Published as a conference paper at ICLR 2022
assumption (13), with G = 0; therefore, Assumption 3 also subsumes the heterogeneity assumption posed in these papers. Note that G = 0 implies that, the minima for F are also the minima for F"", for every m, and hence G 0 results in weak form of heterogeneity.
Some papers (Yu et al., 2019; Li et al., 2020c; Qu et al., 2020) assume bounded local gradients: for all m [M] and IRd
(14)
and this in fact implies the (G,0)-BGD assumption (13). To see why, from Jensen's inequality
N
N
| [x))]
=
V
(z)
VV (x)) G².
N
N
Therefore, (14) is stronger assumption for objective-wise heterogeneity than Assumption 3.
In Theorem 3 of Woodworth et al. (2020b), the authors use the following assumption on heterogene- ity: for all x E R4,
M
Vf(x)|| C
(15)
M
Noting that N EM VVF (x)
[[V]( 1 Σm= | (x) - - M
we can see
that (15) implies (13) and hence Assumption 2 (12), with and 1.
Indeed, there are also some results that make weaker heterogeneity assumptions than ours (12), by requiring bounded deviation only at the global optimum x.. Given the global optimum xx of F, Koloskova et al. (2020) define
M Σ m=
VF (x') [F""("")1 11
(16)
M
and use this constant in their bounds. Khaled et al. (2020) also define similar quantity that can capture heterogeneity, but does not provide a result on strongly convex functions in the heteroge- neous setting. While assuming bounded ? (16) is weaker than Assumption in the sense that only a bound at x is required, we note that these assumptions cannot be applied easily in nonconvex settings; in fact, for nonconvex (but not necessarily PE) functions, Koloskova al. (2020) also use (13) as their heterogeneity assumption.
Intra-machine variance assumptions. (Assumption 2), namely that there exists > such that for all m E [M] and E [N].
We next consider our notion of
deviation
(z) Fm (x)l SM for all Rd.
(17)
In many existing results using independent and unbiased gradient estimates (Karimireddy et al., 2020: Yu et al., 2019; Li et al., 2020c; Qu et al., 2020; Woodworth et al., 2020a;b; 2021), the bounded variance assumption adopted: For all m [M] and æ E Rdd
[x) (x) o².
(18)
We note that the bounded local gradients assumption (14) also implies (18), by
N
1 [T) (v)
(x)
(x)
1
c
(19)
N
15

---

Published as a conference paper at ICLR 2022
Some other papers (Haddadpour et al., 2019; Haddadpour & Mahdavi, 2019; Spiridonoff et al., 2020) consider a generalized version of (18), namely that for all m E [M] and a E R
N (x) v FT (x)]l & cllVF" +
(20)
N
for C, 2 0. There are other papers (Koloskova el al., 2020; Khaled et al., 2020) that use intra- machine variance at the global minimum x" in their bounds. Koloskova et al. (2020) define
M
N
MΣ
V (x="(())]]
(21)
MN
for the global minimum x", and use in their strong convexity and convexity bounds. Khaled al. (2020) define
N M
M
2
V. (x (x")
(22)
MN m== i=1
which is used in their bound on strongly convex functions in homogeneous cases. Note that for F (x*) = 0, so o² = cop
homogeneous cases, V VF"(x"" V
We note that in contrast to our discussion on inter-machine deviation (Assumption 3), the intra- machine variance assumptions in the existing literature are weaker than our Assumption 2. However, utilize our stronger assumption to prove our high-probability upper bounds, which is departure from in- in-expectation bounds in the literature.
Existing upper bounds on local SGD. In the discussion after Theorem 2, we mentioned some recent upper bounds on (with-replacemmnn) local SGD. We make more detailed comparisons here. restate our theorem local RR below.
For the reader's is convenience,
Theorem 2 (Upper bound for local RR). Suppose that local RR has parameters satisfying As- sumption 1. For any F H,, T.P). consider running the algorithm using step-size [o for epochs K 2 7 log(MNK2), Then, with probability at least 1 5, PNK
F F(yK -
F(yo)- - F
MNK² +
+
+
(1²
I.2
MNK + N2K² + N2K²
v²B
B²B²
(5)
We start with last-iterate bounds in homogeneous cases. Theorem 3 and Corollary 3 of Khaled et al. (2020) consider local SGD μ-strongly convex and L-smooth F. Khaled et al. (2020) allow variable synchronization intervals, where the maximum interval is upper-bounded by B. In this setting, Corollary 3 of Khaled al. (2020) shows that local SGD after T total local update steps yield
PT x. =
[ -
I. T
Spt
Lo (B 1-11 1) ope 1TT2
(23)
HºMT
where E; is the average over all M machines' i-th local iterates, and Jppt is from (22). Noting that T corresponds to NK in local SGD and Oope corresponds to in Assumption 2, (23) is comparable to upper bound
L
L2D2B N
E F - FM = =
(24)
Here, we do not compare
F(yo)-F+ Fx and Liigg MNKE
T2 because Thcorem the term F(yn)-Fss F'
MNKE can
be made arbitrarily "small" (e.g.. F(ye)- Fo for any I E N) by changing the log factor in r). [MNK]]
similar homogeneous, strongly convex, and smooth setting considered in Spiridonoff et al. (2020), under intra-machine variance assumption defined in (20). Theorem 1 of Spiridonoff et al. (2020) proves general theorem statement for arbitrary synchronization intervals. If we specialize to constant interval B, Corollary 1 of Spiridonoff al. (2020) gives Lo²
E F( - δ 1
F*)
1B02(B-1)
(25)
T
MT
3
Note that additional factor is due conversion from squared distance function value.
16

---

Published as a conference paper at ICLR 2022
where 3 2 2k² is constant defined to choose algorithm parameters such as the step-size. Noting again that T corresponds to NK and a in (20) is comparable to y in Assumption 2, (25) also translates to (24).
The next last-iterate bound we compare against is Qu et al. (2020). Theorem of Qu et al. (2020)
uses bounded intra-machine variance assumption (18) and bounded gradient assumption (14). Spe-
cializing Theorem of Qu et al. (2020) to full device participation and uniform weight (p) =
PN n) case, their bound reads
- - = ( Lo²
(PMT (PPM +
(26)
1TT
Recalling that corresponds NK, a to v/ in Assumption 2, and G to the heterogeneity constant in Assumption 3 and also (due to (19)), (26) translates to
LV²
++)
E F( - FM] Ô
NRMNK +
(27)
N2NK2
Comparing the local SGD last-iterate bounds (24) and (27) against our local RR bound (5) Theo- rem 2, see that the last iterate of local RR satisfies a smaller upper bound as soon K 2 к. Admittedly, this is not a fully rigorous comparison given the differences in assumptions and types of bounds; nevertheless, we believe that the comparison least provides some degree of evidence for faster convergence local RR than local SGD. It is also interesting to see that the "error from local updates" terms match in with- and without-replacent
bounds.
Next, we review existing average-iterate bounds mentioned in the main text, which are better than the last-iterate bounds. Koloskova et al. (2020) present unifying framework for analyzing distributed optimization algorithms over networks, which can specialize to local SGD. For j-strongly convex and L-smooth F. Theorem 2 of Koloskova al. (2020) shows that
E ([F = Ô [B [BBl x'112 exp (-
KL LB
O2 HMT
LoEB H2T2
LE 12T2
(28)
where é is some weighted average of iterates and ?? and of are defined in (16) and (21), respectively. Noting that 7 corresponds to NK, Ç. to T in Assumption 3, and o. to in Assumption 2 (although our assumptions are stronger), we can see that the bound (28) for large enough can translated into
U² WMNK
L N2N2K22
L N2N2K2
E (
(29)
Notice that (29) is smaller than the last-iterate bounds (24) and (27) by factor of k. Similarly, Theorem of Woodworth et al. (2020b) proves that for j-strongly convex and L-smooth F.
L3 1x0 x01
T2 MMT
Lo
LEB N²T2
E [[F -1
(30)
LT + NT2
P2T2
for some weighted average of iterates ã. Here, σ2 o2, and (2 are as defined in (21), (18), and (15), respectively. Substituting to its comparable constants ã. and and T to Ç. we can similarly check that (30) can be converted to (29).
Comparison to Mishchenko et al. (2021). In Mishchenko al. (2021), the authors study a prox- imal algorithm referred to as Proximal Random Reshuffling (ProxRR), and obtain a distributed op- special case. If we set R = 0 in FedRR, the algorithm then is equal to local RR with B = N, i.c., the one that synchronizes only after one entire epoch.
timization algorithm called FedRR
Assuming that all component functions f!"(x) are μ-strroglyy convex² and L-smooth, and objective- wise homogeneity 1 which states that
pm = F; the authors obtain Theorem 8 (Mishchenko et al., 2021),
LL opt
E
lluk
x= 11]] < (1
NK 1 -0-1-111-- + NN)
11
(31)
J.M
This is in fact quite strong compared to this paper, hecause we only assume F to be Pf., not T nor ft
17

---

Published as a conference paper at ICLR 2022
where yo and yk are the initialization and last iterate of the algorithm, and & was defined above in (22). The term M MN in (31) corresponds the term "No," as per the notation in Mishchenko al. (2021). If apply our Assumption 3 to bound opt we get cpt I v², which reduces the last term (31) to L² If we substitute logí M 1
to the bound (31), we get
RNK
x x²1
LU²
E
|lxx x"
201²
+ Ô
(32)
MNK2
|
which translates to the same convergence rate F(yk)= - F single-machine RR. For the heterogeneous setting, applying Lemma of Mishchenko et al. (2021) to Theorem 2, we can obtain
E yk - x= x1]1 S (1 mulu NK
1yy0
1
2 L
(x))]² (x*))"""""1 1
N
N2 V
[V
VF VF
)1
μM m=l
4
i=1
1o x=Il 112 2n7² 2N2
Lo?
(1 np) NK
NK
Σ
IV FM (x*)("")"" )1²
(33)
n.M
2/1
where o² was defined in (21). Note that in Lemma (Mishchenko et al., 2021). the function "Fi." " in the authors' notation is equal to N in our notation. Recall that the (G. B)-BGD as- sumption (13) is "comparable" to Assumption 3 (12). If we apply (13) to the bound (33), we get 1 Em= V (x*)) (I*) < G². Similarly, if we apply Assumption 3, we get o < xv. Substituting
M
these upper bounds and log( (NK*)
to (33) gives
pNK
180
1 MNK2
LG 1
L p
E
yK
x=
+
(34)
and after translating this into bound on function value, we get an upper bound Ö 12v2 which in fact matches our upper bound (5) in Theorem when we set B N.
1.2G² k²
NNNK"
The two upper bounds obtained for homogencous (32) and heterogeneous (34) settings indicate that, least under assumptions on intra- and inter- machine deviation such as ours, the claimed advantage that "the convergence bound improves with the number of devices involved" (Mishchenko et al., 2021) is not achievable. As our lower bound shows, one needs to choose B smaller than N in order to get the most out of parallelism. That being said, since Mishchenko et al. (2021) is free of uniform intra- and inter-machine deviation assumptions, there may still exist certain scenarios where multiple machines speed up performance even with B N.
B MORE DETAILED ILLUSTRATION OF SYNCHRONIZED SHUFFLING
In this section, we provide a more detailed explanation on synchronized shuffling that we intro- duced in Section 5. For the illustration, let consider the component-wise homogeneous case. Component-wise homogeneity means that all the machines have the same set of components: f.d fr for [N]. Hence, we have F -n for all m [M] and our
f f goal is to minimize F= f.
In the proof of Theorem (presented in Appendix D.2; see Appendix D.1 for a sketch), we add the component gradients over an epoch and then use the following key identity: for any permutation o,
N
Voa = Σ
(35)
1=1
We use this identity (35) to represent the per-epoch progress as "one big GD step plus noise." For the rest of the proof we bound the "noise" term, and the key to bounding to upper bound the norm of summations of the following form, for i [N/B 1] (see (41) and (43)):
1 M
ΣΣ
(36)
18

---

Published as a conference paper at ICLR 2022
To bound the norm, decompose it into two terms using the triangle inequality
M B
M
i
MΣΣ
-BVF +iB [VF(2)))]]
M
M m=
and we use concentration bounds (44) on the first term of the RHS, which gives a high-probability upper bound on the RHS of the form Ô
(VV M
+iB] (45).
The key to proving fast convergence is to make the upper bound above as small as possible. To make the bound (45) even smaller, we wish to be able to apply the identity (35) to the summation (36). However, under the standard way of choosing permutations o% independently over machines, one cannot apply the identity because we do not sum over all = 1,...., This limitation motivates our proposed technique synchromized shuffling, manipulation the choices of o that lets us prove even faster convergence.
Recall the definition of synchronized shuffling. At the beginning of the k-th epoch, the server sam- ples a ~ Unif(Sx) and ~ Unif(SM) ), and broadcasts them to the machines. Then, local machines choose their permutations 0% to be shifted versions of a: o (i) = ((i + X2 =m)) mod N).
Now set N and M 3. Assume for simplicity that the permutation S3 of machines satisfies π (m) = m for m E [3]. 10 Suppose the server samples a = broadcasts it. Under synchronized shuffling, the local machines choose
((4), (5), (6)) and
o = ((t)
0 (()))).)()))(())))2))))))) oF (2)))
One can see that each permutation is a shifted version of with an offset that is a multiple of X 2.
Now consider adding fag over m 1,2,3 and j = 1, (in fact, any two consecutive j's will do). By synchronized shuffling, we get summation over all 6 component functions, which
by (35) gives the full gradient:
VV Σ
Vf. = 6VF.
m=1j=1
The point here is that the permutation identity (35) can be applied to the summations (36) to further reduce their norm bounds. This is in contrast sampling independent of where one cannot apply (35). For this reason, synchronized shuffling significantly reduces the noise that comes from without-replacemmnt sampling, thus resulting in faster convergence rates in momooe)homognncous cases.
C EXPERIMENTAL RESULTS
In this section, we present some simple numerical experiments that support our theoretical analy- sis. We evaluate the performance of the algorithms considered in this paper the "hard instance" constructed in our lower bounds (Theorems 3 and 4).
Our hard instance F E Femp (L, μ4, v, 0) is function in the component wise homogeneous setting, where all the machines have the same set of local component functions: f f? In the proofs of Theorems 3 and 4, we construct the global objective F(z) N ΣN f((x) as the following:
f:M fi-
+1
if i N/2, i < Ni
f((z) := (Ll.g0 + plo>o) 2UVZ, 2
(-1
In fact, permuting the machines by is not required in the component-wise homogeneous setting (i.c.,
when À 0 Assumption
19

---

Published as a conference paper at ICLR 2022
With this set of component functions, the global objective F(x) + convex and L-smooth with a unique global minimizer at x = 0.
2² is p-strongly
We compare the performance of the algorithms this problem instance, with I, 100, / 1, V = 1, N = 768, and M = 16, while varying the choice of E {1.4, 4, 16, 64, 256) and K (1,3, 5, 7, 10, 30, 50, 70, 100, 300, 500, 700, 1000). For each value of B and K, we the algorithms for K epochs (K N/B communication rounds for with-replacement algorithms) starting zi and return the values of F evaluated the last iterates. Note that the algorithms are not deterministic, because the sampling/shuffing schemes are random. In order to account for random- ness, for each combination of (algorithm, B, K) we execute 20 independent runs of the algorithm and plot the mean, first quartile, and third quartile of the final objective values.
In the subsequent subsections, we compare the following seven algorithms with constant step-sizes.
B Ing( log(NNKK MNK"),
Minibatch RR, 7)
ANK
Local RR, 17 log 3
log(MNKK
Minibatch RR with SYNCSHUF, 1j
ANK
Local RR with SYNCSHUF, 7 lNg(
PNK
Single-machine RR with minibatch size B, (=
uNK
With-replacement minibatch SGD, 7)
B (M
WNK
With-replacement local SGD, 1) log( l
HNK
C.I SYNCSHUF IMPROVES CONVERGENCE OF MINIBATCH/LLOAA RR
In Figure 1, we compare minibatch RR and local RR, with and without SYNCSHUF. Each plot in Figure shows how the methods' performance changes with K, for a fixed value B. Each point on the curve is the mean of the final objective function values over 20 independent runs of the corresponding algorithm with the specific B and K, and its error bar indicates the first and third quartiles.
Recall from our Theorems 2, and that the four methods satisfy the following convergence bounds, in homogeneous settings (i.e., = X 0):
Minibatch RR: Ô MNK*)
L2 2
Local RR: δ L
2 MNKE
2²B ==)=) NER=
+
Minibatch RR with SYNCSHUF: δ
L2 MANK'
Local RR with SYNCSHUF: Ö 0
2BB N=K
MANKS
In fact, if B local RR is identical to minibatch RR. Figure I(a) confirms that this is indeed true, and also that the versions with SYNCSIUFF outperforms the ones without SYNCSHUF. This corroborates the additional M factor speedup in our bounds. In Figure 1(b) and I(c), we can see that as B increases, the performance of local RR with SYNCSHUF degrades and becomes closer to
local RR without SYNCSHUF. This shows that the δ (22 >BB ua NIK2 term starts to dominate. Also, that local RR (without SYNCSHUF) also starts to degrade and its gap between minibatch RR becomes larger. Again, this means that the
(6
as we increase B further, in Figure 1(c) and (d)
Ö L? BB n N=K? term becomes the dominant factor in the local RR bound. The performance of mini-
batch RR, with and without SYNC stays relatively independent of B. One thing note is that for large values of B, the small-epoch behavior of minibatch RR looks rather unstable. The choice
B (MNKk)
of step-size n
seems cause overshooting when B is large and K is small. We
BNK
20

---

Published as a conference paper at ICLR 2022
10
LocalRR
Loca
107
NinkatzhRR Syynchhu
LocaIRR +SyncShuf
LocaRR-55ynsiu
10
324
10
224
10
10
329
(a) B
(b) B
101
NinisathiRR
MinisnchRR
LocaIRR
Locu
10
+yyncchuu
MinianccRR -Synchh
Localfi dyynchhl
10
353
107
107
224
107
107
207
16/
(c) B 16
(d) B = 64
NinibachhRR Localt
<SyncShuf
30'
10
307
30"
(e) B 256
Comparison between minibatch RR and local RR, with and without SYNCSHUF. Best viewed in color. The algorithm versions with SYNCSHUF converge faster. Also note the perfor- mance degradation as increases, as expected by our theory.
Figure 1:
note that this does not contradict our convergence analysis because theorems only characterize the large-epoch behavior (K above certain thresholds) of the algorithms. Perhaps in the small- regime, our choice of 1) is not necessarily optimal and smaller 1) is needed prevent overshooting.
C.2 LOCAL RR BECOMES CLOSER TO
RR AS B + N
Our next set of plots presented in Figure 2 provides a comparison of minibatch RR, local RR, and single-machine RR (i.e.. minibatch RR with M = 1). In Theorems 2 and 4, we showed that when B ((N), then the convergence of local RR becomes just fast the single-machine RR.
21

---

Published as a conference paper at ICLR 2022
101
32
LocalRR
LocaiRa
107
SingishachinRRR
357
10
324
10
324
10
10
329
(a) B =1
(b) B
107
NH-ESKAAR LocaIRR SingstlschncRR
Minibanh
LocaIRR
10
324
107
32-
10
10
204
107
307
207
16
(c) B 16
(d) B = 64
MinbaRchRRR
LocaRR SingaMMadinuRR
30'
10
307
30"
10
(e) B 256
Figure 2: Comparison of minibatch RR, local RR, and sangle-machine RR. Best viewed in color. The large-epoch performance of local RR becomes similar to that of single-shuffle RR as B be- comes closer to N.
Indeed, we can observe from Figure 2 that this is really the case. As B increases, the curve of local RR moves closer and closer to that of single-machin RR, especially in the large-epoch regime.
C.3 WITH- VS. WITHOUT-REPLACEMENT SAMPLING
Lastly, in Figure 3 we compare the with-replacement and without-reelaccmmen versions of mini- batch/local SGD. In all plots, we can that the withoutt-rpllucmment versions outperform with- replacement ones, at least for our problem instance. is also intriguing to note that the two versions perform very similarly in the small-epoch regime (for K up to 10), but without--epllacemet starts
22

---

Published as a conference paper at ICLR 2022
10
LocaiRR
LacalRR MinibathhGD Loca/GDD
107
NiniatchGG LocalSGD
10
324
10
10
10
329
(a) B
(b) B
107
Ni-EaRnRRR LocaIRR
MiribachRR
Loca
10
NinkathsGo LoCa5GD
MinbanchSGD LoGa8GD
10
107
107
224
107
307
207
10
(c) B = 16
(d) B = 64
MiibakhhR
Localiit
MiD
LoC
30'
10
307
30"
(e) B 256
Comparison of with-replacement (SGD) and without-replacemmet (RR) versions. Best viewed in color. Without-replacement versions converge faster than with-replacement versions, at least in our problem instance. Also note that the two versions perform similarly in the small-epoch regime, which supports our theoretical findings.
Figure 3:
to outperform for larger K's. This observation supports theoretical prediction from Theorem that in the small-epoch regime, minibatch RR can at best perform as fast as minibatch SGD.
D PROOFS OF UPPER BOUNDS
In this section, we provide proofs of our upper bounds stated in Sections 3 and 5. We start by describ- ing a high-level proof outline that we use for all the proofs presented in this section (Appendix D. In the subsequent subsections, we prove Theorems 1, 2. 6, and 7, in the order they appeared in the main text. The next subsection (Appendix D.6) states and proves key lemma that gives concen-
23

---

Published as a conference paper at ICLR 2022
tration bounds for the mean of multiple without-replacemant sums of vectors. This general-purpose lemma can be of independent interest and can prove useful in various other settings. Lastly, in modify the theorem statements remove the requirement in Assumptions 2, 3, and that they must hold for the entire IR.
Appendix D.7 discuss how
Notation. Throughout this section, we use the product notation II in a slightly unconventional manner. For indices S j and square matrices A,, the matrix product A, A,, If j. then IT A I.
Ay, we use II A to denote
D.1 PROOF OUTLINE
The proofs of upper bounds follow a common structure, consisting of the following three steps:
1. writing one epoch one step of GD plus noise;
2. getting high-probability upper bound on the noise term using concentration inequalities;
3. obtaining the convergence rate using the bounds on the noise term.
We first unroll the update equations over an epoch, and write an epoch of the algorithms as one step of gradient descent plus noise:!
1,0 2k,0 (NVF)) + rr
Substituting the above to the definition of L-smoothness of and arranging terms, we obtain
F( F(xx.0)
L
(FF( - 2x +
| - o2.oll
2
|xll + T²L ILVFF(ZL)) mrxll
S ~ (VF (VF
I <-nn + + (VF + (FF VV ||mlll + + ||xl1
(37)
The next step is to get high-prrobbbility upper bounds on the term ||w/]]. This done by applying concentration inequality lemma (Lemma 8) to partial without-replacement sums of component gradients. As result, will get upper bounds on ||r]]| and ||r for i: ....., K, which hold with probability at least
In the last part, substitute the high- probability bounds (37) and invoke the definition of PL functions to get a per-epoch progress bound. We then unroll the per-epoch inequality for all epochs k == 1,...., K. Arranging the terms in the resulting inequality gives desired convergence bound that holds with probability at least 1 8.
D.2 PROOF OF UPPER BOUND FOR MINIBATCH RR (THEOREM 1)
One epoch as one step of GD plus noise. To simplify the notation throughout the proof, we will prove the same convergence rate for rescaled update rule and step-size:
Lk It
Σ
(38)
M
j=(f 1)B+1
for E [] and k [K]. and m
pNK Note that the gradient term is scaled up by B and
the step-size is scaled down by B. We will prove the convergence rate for this equivalent algorithm.
We start the proof by unrolling the update equations over an epoch and expressing the progress as
# æk n, FF + n
i.c., step of full gradient descent plus some noise.
In of local RR, replace æ5.0 with yı.0-
24

---

Published as a conference paper at ICLR 2022
To this end, we decompose the gradient V () (Tk,5-1) into the signal V fog (Ix,,) and noise:
v on (
V Vorrol (T + (TH.i-1) Voo (322,0)
un + V V2 (oro (TI.D + (ar F1:0))dt ( Fk,0):
where f(x) denotes the Hessian of f æ, whenever it exists. We remark that the integral exists, due to the following reason. Since we assumed that each fa0 is differentiable and smooth, its gradient V () is Lipschitz continuous, and hence absolutely continuous. This means that V is differentiable almost everywhere (i.e., for (z) exists a.e.), and the fundamental theorem of calculus for Lebesgue integral holds; hence the integral exists.
To simplify notation, we define the following for E [N/B]:
M
iB
1
Σ
V Too
()
M
m
1)8+1
M
iB
1
H.
Σ
Σ
V f Jo (f + - rx,0))dl,
M
m=1
j=(i- 1)B+1
so that we can write (38) as
Thg = Fk 79 1 ( -
(39)
From L-smoothness of f!"'s, it is straightforward to check that || S LB. Unrolling (39) for i l,..., N/B, it turns out that we can write
N/B
i+1
EK+1.0 = Ig.0
1
Σ
II
(I - HHH ( 9:.
1=1
j=N/B
Due to summation by parts, the following identity holds:
N/B
N/B
N/B-1
Σ
- aN/B
Σ
b
(a++1 a.) Σ by.
We apply this to the last term, by substituting a;
i+1 Nj=
(I n)HH) and = g:
N/B
Σ
II (I - (I-)H,,)
7
gi
1=1
j=N/B
N/B
N/B-1
i+2
(+1
9
Σ
II -I--A HH) - II
(I nHi)
Σ9, 9j
1=1
Aml
(=N/B
L=N/B
jml
N/B-1
14-2
NNF((ELO)) - 7
Σ
II N=//B
(
Hi+1
Σ gi
j=l
With the "noise" T& defined as above, we can write #k+1,0 = 2k.0 - V + 1 as desired. Next, it follows from L-smoothness of F that F(x++1.0) F(zx.0)
x (VF(2zo)) 2K41, - Ik.o) + |04+1,0- - xx,oll
2
72L IN J.VFF(I..l + 7
- M |V |
S (- + 1²= |
2 /
(VF mall + *
(40)
where the last inequality used |a + 612² < ||||||| + 1ba2
25

---

Published as a conference paper at ICLR 2022
Bounding noise term using concentration.
is left to bound ||x||| l|. We have
N/B-1
6+2
||x
Σ
II N=N/B
(I
Hi)
H
gj
5=1
N/B-1
Σ
II
(I
HH)
H
9j
==1
I=N/B
==1
N/B-1
S LB +T.BBBBB N/B
Σ
9j
(41)
where the last step used || |
Recall from the theorem statement that log(MN This means that uNK
S LB for E [N/B].
K 2 6xlog(MNK3) and
[1+
KB (.Blog(MNK3)
N/B
B
N/B
(1 (L+ =
S
11
I
1/6
(42)
NK
6N
Now, we use Lemma 8 to bound the norm of
M
1B
E9
v Sor (5) (#R.0).
(43)
M
Note that for any epoch k, the permutations of .k...., ok of the epoch, and hence independent of ff Therefore, we can apply Lemma 8 the partial sum (43), with D.th + (FF,,)) n +- iB, and + B5 By Lemma with probability NK
M are independent of the first iterate æ3.0
at least 1
B6
we have
NK
M
B
8 8log 2NK
pm Vo (zR,0) VF((x))))
SuV
(44)
iBM
iBM
Using this concentration bound, with probability at least
B38 NK
we have
8 log 2NK
BiB log 2NK
Σ 9j
iBV
+iB [V = u
M + iB [F( (45)
iBM
We can now substitute (42) and (45) to (41) to get
N/B-1
BiB log
2NK
rrlll LB
Σ
Ba
+ iB |
M
1=1
1/6
/8L
N/BB
2NK
N/B-1
VEdt V log
+ 1/6 L (F(
Σ
M1/2
Bd
(N3/2 B3/2)
2NK
log
+ LN B) [F(2
(46)
2M1/2
B8
which holds with probability least K. due to the union bound over i 1,..., N/B 1.
if we apply the union bound over k 1,..., K. Next, by + b)2 < 2a² + 26²,, we have
The bound (46) holds for all ls E [K] with probability
| < 2 B3/2
2NK
log
+ +2L - (VF(( (47)
2M
which also holds for all ls [K] with probability least 1 8.
26

---

Published as a conference paper at ICLR 2022
Getting high-probability convergence rate. we can substitute them to (40) and get
Given our high-probability bounds (46) and (47),
F( F(
(r S <(-nN + L V FF( 77 [IF Imxell ||rx||
I (- + 7 LN + 11 LN -B) + 20y N (N
- -B)) (IV
5 Lu - )
2NK
log
|FF(2)0))
1/
B8
25 L322 (NV/2 B8/2y²
2NK
log
(48)
2M
The second term in the RHS of (48) can be bounded using ab 2 +
0² b2. 2
5n Lv( B²/2)
2NK
log
B8 |F((xx)))
2M
17 N2/2
" - B3/2)
2NK
IVF(
log Bd
M1/2N1/2
NN
25n' L'33 B2/2y2
2NK
|VF
log B3
2MN
Putting this inequality to (48) and noting N - B S N gives
(- (-3 nN + 217 LN L* /F(
F(xx-10) F(xx,0) S
8
25n L (1 NLN) BB//33
2NK
log
(49)
2MN
B8
Recall from K 2 6x log(M and log(MNK3
that MLN S 3/4 Since the inequality
aNK
2 + 22 + 2 < 12 holds on 2 E [0, 21. we have
7
8 N 2n LN2 + 2 N
Applying this bound to (49) results in
N
15r/" L2 (N3322 B3/222
2N
F( - F(xx00) -
VF(
log
2
MN
B8
We now recall that F is J-Pt., /F 2 2
FF)):
(N3/2 - B3/222 2NK
F( F s (F F*)
log B8
(50)
MN
Recall that (50) holds for all l: E [K]. with probability 1 - 6. Therefore, by unrolling the inequality, F ) - F* < muN)* K (F(zo) - F*)
15 22 B3/2y² log
2NK K-1
Σ (1
MN
Bd
k=
15n² 22 122 (N332 - B3/222
2NK
< < (1 DuN (F(()))FFF)))))))))))))))( -F F+)+
log
(51)
μMN2
Bd
[o](MNK3 PNK
Lastly, substituting
gives
F(ZD) - F²
15 B3/2 log B8
2NK
log (MNK3)
F F
MNK2
MM
F(xo) -F'
(B222
+ Ô
(52)
M
11 MNK?
27

---

Published as a conference paper at ICLR 2022
Getting in-expectation bound from the high-probability bound. We conclude this subsec- tion by briefly describing how we can obtain an in-expectation bound from the high-probability bound we just proved. Recall that the bound we proved above holds under the event E that all the concentration bounds used throughout the proof hold. The key to proving an in-expectation bound obtain an upper bound under its complement F", i.e., conditioned the event that at least one of our concentration bounds does not hold. We do so by repeating the same proof without ever using the Sheeffding-Serfinng bounds (Lemma 8). Of course, this leads a much looser bound, but can L222
choose å to be small enough that the desired bound Ö
1 MNK3)
holds in expectation.
For the version without concentration bounds, the proof proceeds in the same way until starts diverge at (44). Instead of applying concentration inequalities, we loosely bound the quantity as the following:
M
Σ
V
- (F(..)))
iBM
M
Σ
( (Ik,00) (o)
pm
M Σ Fr (Ik
1
iBM
o (02,00)
SV.
M
B
With this bound, the RHS of the upper bound (45) on وー=1رز becomes iB + iB F This results the bounds on ||rx|] and ||r=ll (corresponding to (46) and (47)) that read
|| S LoN(N B) LN(N B) [VF |ral|| - 22 - B)² + 2 2 B)² [|FF(
The rest is substituting the bounds above to (40), and going through the same steps to obtain the final bound. The resulting bound that corresponds to (51) is
L22 B)²
F( F (1 nuNN ().N))((((x)))) F*)
3/1
log( log(MNK3 yields aNK
which, by substituting 17
F(æo) - F
(0(011)) L22v2 n13 K2
F(ØK,g)- F
MNK2 +
(53)
To finish the proof of in-expectation bound, choose MN. Recall that the probabilistic event E occurs when all our concentration bounds hold. Conditioned on E, which occurs with probability least MN. the tighter bound (52) holds, with log å replaced by log(MNN. The complement event E occurs with probability at most MN- under which the looser bound (53) true. Thus, in expectation,
B (((K,)) F.] = -P(F)R F(ZK - FM
E
P(EE) [(
F' F.
1
F(I N - F
F(Zx,g)
-F - F E
MN
3(F(zo) - -F))
I22 1
2M +
MNK3
For the remaining bighbbbbbability upper bounds proved in the paper, we can similarly follow this process to obtain matching (up to log factors) in-expectation upper bounds.
28

---

Published as a conference paper at ICLR 2022
D.3 PROOF OF UPPER BOUND FOR LOCAL RR (THEOREM 2)
One epoch as one step of GD plus noise. The update rule of local RR can be written as the following. For & [K], i E [N], and m [M].
- V/ (1) ( Σ -== 1 17 V ( =: yk.iBB if B divides i.
if B does not divide i,
(54)
Recall that k,0 's are the initial points of an epoch and they all the same regardless of the machine We define yk,o 2k For any i in the range of (L- 1)
IB for some E [M], will use y as the "pivot" and decompose the gradients into the ones evaluated at yk,1-1 plus noise terms.
Vo (0 Fo (#
of (y
-V (31,1-1) +
V f (yk,1-1 + t( yk.1-1))dt (2 Vk,1-1),
=
where the integral H exists due to the reason discussed in Appendix D.2. Also note from L- smoothness fr that ||","|| I L. Using the decomposition, one can unroll the updates (54) and write yku in terms of yk,t-1 in the following way:
IB Σ
yk -k.11
Σ
(
V V (o
(55)
M (1-1))++1
j=
for 1 = 1,...,,,N N/B. Next, we again decompose the gradient V (1) the pivot:
(1k,1-1), this time using yk.o
( (3k.11) = V fo (3 + (0).-))) V ( (BE..)
V Oz (1) (3k.0) + 1//0 v2 f0 (yK,0 t(yh.11 - -t (Hk.1-1 - yk.0).
This decomposition allows rewrite (55) in the following form
ykul = Vt.1-1 ntt1 1) yk,o),
(56)
where
M
1B
i+1
t; =
Σ
Σ
II (I ))
V VS oo
(57)
M
m=
i[(1-1]++
f=1B
M
IB
i+1 II - (I- Hy
S
Σ
Σ
Å.
(58)
M
11+1)
f=lB
Unrolling (56) for 1 1,.... N/B then gives the progress over epoch:
N/B
H+1
Vk-1,0 yk.u
Σ
II (I n/s,) t,.
(59)
J=N/B
As done in the proof of Theorem (Appendix D.2), we will express (59) as one step of GD on F plus some noise. Of course, the noise terms here will be more complicated to handle than they were in Theorem Due to summation by parts, the following identity holds:
N/B Σ
N/B
N/B-1
aN/B
Σ bj
Σ
(a-11
a1)
Σ by.
29

---

Published as a conference paper at ICLR 2022
We apply this to the last term of (59), by substituting a,
[+1 [[j=N/B (I n)5,)) and bj ty:
N/B
N/B
N/B-1
L+2
" Σ
II (I
(I-nS))) n)
t, 1 Σ t カー 7
Σ
II (I n/Ss))
S Σ tj. (60)
J-N/B
j=N/B
We also apply the summation by parts the inner summation of tt's (57):
M
IB
++1
t =
Σ
Σ
II
nH
(0
M
(1-1)((11)B+
jmtB
M
IB
Σ
Σ
f (1) (3+.0)
M i=
M
IB-1
H22
[I HHH)
H
(61)
M
m=1
11-11)
MElB
j=(1-1)8+1
Substituting (61) to (60) gives
yk+1,0 k NVF 7/ + r/ rT
where Tk.1 Tk22, and Tk.3 are noise terms defined
N/B
IB-1
2+2
Fk = M
Σ
Σ
Σ
H
Σ
1=1 M=
l)B+1
\=IB
(1-1)
N/B-1
L42
M
1
Tk22 =
Σ
II J=N/B
(I (I-n)s))
S Σ
(1).))
pm
M
1 N/B-1
L42
TK33
Σ
II
(I (I-))s))
S
M
J/N/B
JB-1
(+2
ΣΣ
Σ
II
(I-NHT
H
Σ
(o
j=1 (01-1)
{=jB
(=
Defining Fh Pk Tk22 k,3, it follows from L-smoothness of F that F())+1.0) F(y).o)
L
< (VF(g).)) vk+10 ykoo)
2 1,0 y1,oll
(yk .0)l |ell + T/L
S N IVF(GE)
VF
-2 (INVF(y8,0) + 17rx11
S {- + LN? VV + [VF(()))) ||r]|| 1/ T. ||r=1
(62)
Bounding noise terms using concentration. We next bound |||=|| by bounding each ||rk,2ll, and ||r,,s||- From this point on, we write 9.º = S (t) (Bk.,) to simplify notation. ||ral]l
1 N/B M
|raall
Σ
Σ
II (n-nHT))
Σ
g
M
[=1 m=1 (1+11)
\t=BB
1(++1))+1
1 N/B IB-1
i42
3Σ Σ
H 1+1 II (H-)
< M 1=1
g
(1-1)8+1
V=1
(1(11))++
L(1 + nL) B N/B M
IB-1
ΣΣ
Σ
Σ (1111)
m
(63)
M
B+1
30

---

Published as a conference paper at ICLR 2022
where used
H L. Recall from the theorem statement that K 2 Tpklog(MNN3) and
log(MNK") PNK
This means that
<log(MNK3) B NK
B
1
B
(1 + (1+
1+
Sel17.
(64)
TpN
7B
Also note from the definition of St (58) that |||||| - LB(1 + 7L) similar bounds for the next two terms 2 and T,
S e/7 2 LB, which use get
N/B-1
1-2
M 18
| =
Σ
I (I (I- ns,)) (I-nS,) j-N/B
S Σ
TR
M
1=1
YIL
Am
LB1 + LLB
N/B-1
Σ
ΣΣ
9i
(65)
M
and bound
(1 (1+e LLB) (1+
1 B log (MN23)
N/B
NK
1+ e
N/B
c//7
I exp
(66)
PpN
We similarly bound the norm of the last noise term Tk.3:
e LBLL
e/ (L
N/B
|rx,3|| 5
X
M
N/B-1
i
M
i22
Σ
Σ
Σ
II
(I nH;")
H
Σ
gi'
m
B+1+1
t= BB
eT + 1 LBB
+ nL
B N/B-1
M
jB-1
Σ
Σ
Σ
9r
M
1=1
i= 1- l)B+1
1= B+1
11L'B
N/B-1 1
M
jB-1
Σ ΣE
Σ
Σ g
(67)
7M
|=
1= B+1
where the last inequality used (64), (66), and 2277 exT(et/TT7) S 11/7.
Given the bounds (63), (65), and (67), now Lemma 8 to get high- probbbbibbbbiiity bounds for the partial sums of g!" that appear in the bounds. For any i satisfying (j - 1) + 1 i j.jBBB.. 1. where j E [N/B] and for any m E [M], the following bound holds with probability at least 1 - 2MNK
1
gr
9,
(j 1)B
(((-1))B+1
1=1
8 log 1MNK 8
Σ
V (o ( (Ur.o)
VF (3)1,0)
S
(j
1)B
(j 1)B
1)8+1
From this, with probability at least
2MNR have
Σ
g:th < u 8(i (j 1)B) log
4MNK 8 + (i- -j-1)B) V (yr.)))
(68)
Similarly, for I [N/B B - 1), the following bound holds with probability least 1
B8
2N
M
IB
M
N
1
Σ
9h
m
g
m
IBM
MN
m=
31

---

Published as a conference paper at ICLR 2022
M
IB
8 log 1NK 13
Σ
v
(U VF(Uk.)) S Sv
IBM
IBM
m=
which gives us
M
IB
Σ m==1
9t m
SUV 81BM log 138 + 1BM [|V
4NK
(69)
[=1
By applying the union bound, with probability at least R. the bound (68) holds for all m E [M]
and E U B)B :: 1], and the bound (69) holds for all I E [N/B - 1].
We now substitute the bounds (68) and (69) (63), (65), and (67) to get upper bounds for || || and ||*,,]||, respectively. First,
||r
IB-1 e L N/B M
ΣΣ Σ
(1- 1)B) (1- log 4MNK à
+ (i- (1 - 1)B)
V Fm
(H.,))))
M
M=
(1(11))+1
e/ /BLUN
B-1
4MNK
LN
B-1
M
Σ
log 8
Σ i
|F VV
(U1,)))
B
B
M
m=1
2ALuN(B3/22
4MNK log
3LN(B 1)
+
(T + p V F ol))
(70)
11B
5
5
where the last inequality used DD1 Vi <
S1 /zdz = (B8822 1) and Assumption For the
B
next noise term, we have e e//7 1/7 BL)) N/B $ 7/5, so
N/B-1
7LB
||r,221 s
Σ
U
UVBIBB log
4NK BB
+ IBM I VV (F(UE.))))
5M
7//LvB3/2
N//B1
4NK
TLB2
N/B-1
Σ
Vi
log
+
Σ 1
|FF(M)))
5M1/2
B5
5
8Lv(N3/2 B3/2)
4NK
7LN(N-
B)
log
(71)
3M1/2
B5
10
Lastly,
|k,
1
N/B-1 1
Σ
ΣΣ Σ
BB-1
(WVB(E (j 1)B)
- log 1MNK
7M
j=l m= 11)+1))++1
+ (1-1) ( (BK.D)) (F
11VBLPUB
N/B-1
B-1
4MNK
Σ
1
Σ
Vi
log
7
8
1=1
I1LBB
N/B-1 Σ
BB-1
M
Σ
1
Σ
(yRO))
7
M
m=l
(N BB32222 1)
4MNK 8
log
2B
(N - -B)B 1)
(T + VF
(72)
5
32

---

Published as a conference paper at ICLR 2022
Recalling the definition FA Fk,1 + Fk.2 1)r,,3, get upper bound for |rx| from (70), (71), and (72):
| 1 Mk |1 + ||x l + F 11rk
4MNK
2AN(B8/22 8(N3/2- B8/2)
39LN(N BBBLNN
B)
S Lu log
6
11B
3M1/2
2B
(N
1) +
2n - BB )
B))
Lr
5
5
3p - 1)
7N B)
2nLoN BBB
(F
+
(73)
5
10
5
Recall again that we have K 2 pp log( MNK3) and 17
(og(M ANK
So NLN & 1/7. Using this
and N - B S N, we can further simplify (73).
4MNK
12N B3/2 1)
8(N3/2 B3/2)
2L 1)
|| < L log 8
5B
3M1/2
3
2p -1)
7N(N B)
10
4MNK S /
2L 1)
7LpN2 5
[V
(74)
5
3
which holds with probability at least 1 K.
The bound (74) holds for all k E [K] with probability
1 - 8 if we apply the union bound over 1,..., K. Next, by (a + b c) 3a 3b2 + 3c we have
4MNK
4L2,2N2(B +
14712
|r 3 log
(75)
3
25
which also holds for all k E [K] with probability at least 1 - 5.
Getting high-probabiin convergence rate. can substitute them to (62) and get
Given our high-probability bounds (74) and (75),
F( F(y,,o) $ {- - L2 | (F +n² (VFIFFF(oool |[x]] + + |rxll
LpN2 p
NN + 1 +
5
25
4MNK
4MNK
+ L2 log
(F + +3n 1 2 log
5
8
2 LL 1)
L - 1)²
|VF(
(76)
3
3
The following terms the RHS of (76) can be bounded using < 2 + :
4MNK
n² LUD
V log
[VF(Ho))
8
N1/2222/2
/ Lu
4MNK
|F
llog
V8
N1/2
NN
4MNK 8
log
(77)
N
2n² LT
L
|VF((y))))
3
33

---

Published as a conference paper at ICLR 2022
1)) /11//21/2
LT
|VF(yR.0)]
V8
nN
16 1 - 1)2
(VF(y+))]
(78)
16
9
Substituting (77) and (78) to (76) results in
Fly++100) - Fy),o)
$ (-3 7
n nN + =2= + Lp?2
1.
+
/FF()))))
25
log 8 2
4MNK
4n L2 2 (n - 1)2
(79)
N
Again, we have K 2 7p log (M and log(MNK*)
so nLPN S 4. Since the inequality
MNK
2² +
147
24
< 2 holds on [0, #], we have
25
Trp2
147
8 N LN
5
25
Lp
1.7
N +
1 2 n.N.
5
25
Substituting this inequality to (79), together with 4+ 3+3
S
31
< Q
2 yields
F F(yx+1.0) Fly.oo) S |VF(E.)) + 22v222
TN
4MNK
log
+ 2nn
NB -B-1)² 1)).
2
2N
8
We now recall that F P-PL, [VF('))))) 2 (2((F))),)) - F*):
F(y++10) - F S (1
mi 1222p22 4MNK
- -F*)
+
log
+ 2ny N 1)?
(80)
2N
Recall that (80) holds for all ls E [K]. with probability 6. Therefore, by unrolling the inequality, F(yK, x) F (1 n/N)** " (F(y0) F²)
9n79 22
2N log 8
4MNK
+ LB - 1)3
K-1
Σ
(1
NNN
k=
< (1 qNNNK (PNN)((((g))))
(H)) F*)
22
4MNK 2B 1)2
log
(81)
N
12N(B 1)
8(N3/2 B2/2) hence
Recall that +-
5B
3M/17
288
AASN2(B3/2 (B3/2
1)2
128(N3/2 B3/222
25
9M
Substituting this inequality and also 17
log(MNK3)
gives
uNK
F(yK,N)
< F(yo) F"
2B2 1)2
log (MNK3)
MNK2 +
N2
9I202
4MNK
2B8/2 1)2
128(N3/2 B3/252
log
log (MNK3
2μ 2
8
25
9M
F(yo) F
L2T2 B²
L2
B
L2D²
1
MNK2 + δ
+
+0
133
N2K3
n3
N2K
113
MNK2
with probability at least
- 8. This finishes the proof.
34

---

Published as a conference paper at ICLR 2022
D.4 PROOF OF UPPER BOUND FOR MINIBATCH RR WITH SYNCSHUF (THEOREM 6)
The first part ("One epoch as one step of GD plus noise") of the proof is identical to that of Theo- rem We start from the second part.
Bounding noise term using concentration.
It is left to bound ||x |l. As seen in (41), we have
N/B-1
||x/|| < nLB
93
(82)
Recall from the theorem statement that K 2 6n log M MNKK K2) and log(MNK3)
This means that
pNK
(1 + LLB)N/BB = (1+
& BBglog (Blog(MNK))
N/B
B
N/B
1+
I
e//
(83)
NK
6N
Next, we bound the norm of
18
1 - M
Σ9
Σ
of ()
(84)
j=1
exploiting our modification SYNCSHUF as well as Lemma 8. For each V () (2x,0), we first add and subtract its corresponding (Z1.o) where f. N > f defined in Assump- tion 4. This way, (84) can be decomposed into two sums Σj= 9j = To (p: + q:), where
M iB
p: = Σ
(o
m= j=1
L =
V Sa
Fa (2 - Vor
Using this decomposition, we will derive high-probabiliy bounds for ||p:|| and ||q/|]-
To simplify expressions follow, we decompose iBM (i.e., the total number of component gradi- ents that are summed up) into a multiple of N and the remainder. Let
iBM N
(1) =
3(1 = iBM - Na(ii,
so that iBM is decomposed into Na(i) and the remainder < (())) < N. Using this new notation, we can write p; as
M No(S)
M
iB Σ
p.
(O +
Σ
V F)
(85)
m=
m=
Noce
Here, recall that with SYNCSHUF, we defined (j) = o ((i+ N (m)) mod N). With this choice
of "shifted" permutations, one can notice that { (j) M. m=1.j=1 [N], meaning that adding Sog () for E [M] and [N/M] results in the sum of all N fi'. In fact, this happens if we sum over m E [M] and any N/M consecutive j's. From this observation and = + EN Fr, (85) can be written
M
iB
P: = Na()) +
Σ
Σ
Vacli Ne) mod NY (o)
(86)
Noto
+1
Assume for now that 3(1) > i.e., Na(i) < iBM. The summation in the second of RHS
in (86) is without-replacement sum (note that the indices Nm do not overlap) of (() terms.
"
35

---

Published as a conference paper at ICLR 2022
Hence, it is equal in distribution to checked that for any i [M]
((
V ( Also, from Assumption 2, it can be easily
(f - VF(= S
These observations mean that we can apply Lemma to get concentration bound, with M 1, t/ + (.,,,)))) n < B(i), and 5 +- 2NK
By Lemma 8, with probability at least 2NK
Bá
(over
the randomness in σ), we have
8 log 4NK
Voa (p) mod NY (x (20.0))
S suV
BB
(87)
3(1)
3(1)
Combining (86) and (87), we get the following upper bound on ||pell, which holds with probability least 1
B8
2NK
M
iB
| < || +
Σ
Voc(ii 3 mad NY) (2x..)) - B(1)
4NK
S 1BM [VF VV 18(()) / log
B5
4NK
S <iBM N 8log
(88)
B5
where the last inequality used ((1) < N. Also recall that we assumed 3(1) > O in order to use Lemma 8 and derive (88). However, note that even with 3(i) = 0, the bound (88) trivially holds.
We next bound ||::|-- This time, we will apply Lemma 8 to the permutation over the local ma- chines. To do this, we will condition on fixed instantiation of the permutation a and derive high-probabilics bound that holds with conditional probability at least 2NK The conditional probability is least 1 ditional) probability that our bound holds also least 1
BB
2NK irrespective of the choice of a, so
Rs
conclude that the (uncon-
2NK*
Without loss of generality, choose the instantiation (I) | for all / E [N]. With this we have of (i)
(j + M7
N π (m)) mod N, so the vector q. reads
M iB
q
V (i+ N (m)) mod N (xx,0) V fot =(m)) mod N (0
(89)
m=1
j=1
Let us consider rewriting this summation the over 7 [N], where appears in the subseript of the component functions. One can check that
=
j
M (m)) mod N <>
N
N (l- and (m)) = (1 - j) N mod M,
M
where a b denotes "a divides b." From this, we can rewrite (89) as
((--)) mod Mf)
(2xx,0) V f((
(90)
((1-))
=:
By the same reasoning above and below (86), the cardinality of the set Ji := tj [iB] we notice that each q. is a without-replacemmen sum of (i) or a(1) + terms. For now, suppose
from (90) that for a given index / E [N]. 37 (1 (1- is either a(i) a<i) + From this,
N
aii) O. For each q, can apply Lemma 8 to it, and show that with probability (conditioned B8 2N'K have
on the instantiation a (1) 1) at least 1
\ 8(a(i)) log
INZK BM
if a(i), if
d 8(a(1) + log 4N2K
if a(i) +
36

---

Published as a conference paper at ICLR 2022
Note that cases in the RHS are all bounded from above by Av
AV16at 16a(i) log 4N2K Applying union
bound on all / E [N], we get that with probability at least
B6
we have
2NK
4
16:BM
4N2K
4N2K
q & AN 16o(1) log
S SAN
log
1 iBMN log
(91)
B6
N
B6
Now consider the case a<ii) 0. Recall from the definition a<i) = ARM
N that ai)) = 0 implies
iBM < N. In this case, q = 0 for N -iBM indices / satisfying [T]] 0. and ||q < A for the remaining iBM ('s satisfying [i| is in fact less than the upper bound in (91). Therefore, the bound (91) holds even for a(i) 0.
Summing up. || is bounded from above by AiBM. which
Recall that goal was to find bound the norm of E 9, MJ (P. + q.). From the high- B6
probability bounds obtained in (88) and (91), with probability at least NK
VVN V
4NK B6
iBN 4N M
Σ 9
S iB VF xxD0
8log
+ AAV
log
(92)
We can now substitute (83) and (92) to (82) to get
N/B-1
V/N
4NK
iBN
4N²
||xl]| S LB
Σ
iB
( +
8log
4X
log
M
B5
M
B
2/
/8LON B)
4NK
LB2
Σ
log
M
B5
22/
/NBB
4N2K
Vidty Vlog
log
M1/2
B5
LN(N- - B) (V + 7LuN1/2 - B)
4NK
log
2M
B5
(LA32/2(N3/22 B3/2)
4N2K
log
(93)
2M1/2
B8
which holds with probability least K
5 due to the union bound over i 1,..., N/B 1.
The bound (93) holds for all k e [K] with probability 1- 8 if apply the union bound over
L...., K. Next, by (a + b c)² S 3a² + 36 3c we have
14 B)²
4NK
|| 3 3) (F
log
4M2
B8
I4732 2
4
log
(94)
4M
which also holds for all E [K] with probability at least
Getting high-probability convergence rate.
Given high-probability bounds (93) and (94),
we can substitute them to (40) and get
F(x++1.0) F(
S(nNN- + 1 I.22 (VF( + + $ (-nN + +1² 2 2 + 1 LN B) + N - -B)
[I 1|
/ (N- (I
7np LuN/2 BB)
4NK
L2N B)²
4N
log
log B8
2M
Bd
4M2
12 B3/2)
4N2K
log
2M1/2
B8
1477 N
B3/2
4N2K
log
(95)
4M
B8
37

---

Published as a conference paper at ICLR 2022
Two terms in the RHS of (95) can be bounded using ab o² +
b²
Tnf L - B)
1og
4NK
V
|VF(<x.)))
2M
B3
1) 1///2
7v2np212
Lv(NN 13)
4NK
|VF(
log
2/2
M
B8
nN
L2 MON--B -B)²
4NK
[VF +
log
(96)
16
M
BB
Tnf
LAN
-33/2)
4N2K
log
2M1/2
B5
1 1/2
7v2n
LA(N3/2 B3/2)
4N2K
|
log
2/2
11/2
B8
N
49ry L2X2 2²
4N
[F(
log
(97)
16
M
Putting inequalities (96) and (97) to (95) and noting N - B < N gives
-( - F(xx,o) v
Nn + 21/ LN + 3x L3 [
1/ 31,LN) -B2
4NK
log
4M
B8
4. LN) - B3/2)2
4N2K
log
(98)
4M
B5
Recall from K 2 6x Nog and 1 = lo3( MNK
that nTN & 1- Since the inequality
z 2z 3=a < 2 holds
[0, 1. we have
1 7 N + 2n/ LN2 + L3
-
8
Applying this bound to (98) results in
F F(xx,))) < |F( 56 36nr3L2 L2v2 -B)
nN
4NK
log
2
M2
B8
56n
- 12X2(N3/2-B""
4N2K
log
M
Bd
We now recall that F is μ-Pt., so |V 2 (F(F
F*):
F( - F* < (FNN) F*) + 56 L6 (2 (N B)²
L²
4NK
log
M2
B8
(N2 B3/2)2
4N²K
log
(99)
M
Recall that (99) holds for all l: E [K]. with probability 6. Therefore, by unrolling the inequality, and using ΣK- 1unNN < Npn, we get
F( x) F* < (1 - MuN)* K (F(x)) FF) + 56n - -B)
4NK
log
nM2N
B8
56n 1222( B3/222
4N²K
log
(100)
HMN
B8
1= RNK
Lastly, substituting
to (100) gives
F( F F(æo) F + M2NK3
56L - 2)) log Bd
1NK
log (M2N33)
N3
38

---

Published as a conference paper at ICLR 2022
56L X2 B3/ log
4N*K Bó
log logo (M
F(zo) F MRNK2 1
(T
T2
U2
+ M
X?
+O
MRNK2
D.5 PROOF OF UPPER BOUND FOR LOCAL RR WITH SYNCSHUF (THEOREM 7)
The first part ("One epoch as step of GD plus noise") of the proof is identical to that of Theo- rem 2. The first part defines our "noise" 7h as the sum of three terms Th == Tk,1 + Tk.2 1JTR.3. We start from the second part.
Bounding noise terms using concentration. ||r,,2|| and ||r We have already seen from (63), (64), (65), (66), and (67) in Appendix D.3 that
We next bound ||r]|| by bounding each |r
L
N/B
M
IB
|rx,1ll <
ΣΣ
Σ
Σ
Σ
(101)
M
[=1
m=
(1-1)8-11111
1=(1- I)B+1
N/B-1
iB
7LB
||
Σ
Σ
fog (e) (BA.o)
(102)
5M
11LAB
N/B-1
M
BB-1
||r S
ΣΣΣ
Σ
E
(o
(103)
7M
1=1 j=1 m= (--jj118B
As in the previous subsections, the key is bound the norm of the partial sums of V Vo (o using Lemma 8. For the summations appearing in (101) and (103), we apply Lemma 8 in the same way as (68). For any satísfying (j - 1) 1 < jB 1, where j [N/B], and for any
[M], the following bound holds with probability at least 3MNK
Σ
V (e) (Bk.o)
S Sv 8(i (j - 1) 6MNK
1=0--1)+ 1)++1
(i (j 1)B) ( (yk,))l-
(104)
For the summation that appear in (102), we use the techniques from Appendix D.4. For each E [N/B 1), we can similarly decompose ΣM ΣIB V Vf (3k.0) into pt qi where
M
(o
Pt
M
1B
q: = Σ
(o)
v
(e) (31.o). (c
(2k.o)
m=1
As done in Appendix D.4, we can follow the same steps and show high highh-probability bound, which is a slightly different version of (88): with probability at least 1
B8
3VK
6N
P < IBM (( + + 8 8log
(105)
B8
Similarly, for ||qل|| we can show a slight modification of (91):
6N2K
||li|| ll S 4x LBMN log
(106)
B8
which holds with probability at least 1
B8 3NK
Combining (105) and (106), with probability at least
1
2B8
we have
3.V
M
A
6N
Σ
(1) (yR.))
IBM [I + log
B8
39

---

Published as a conference paper at ICLR 2022
6N
+ + IBMN log
(107)
B3
By applying the union bound, with probability at least 1 R the bound (104) holds for all m E [M]]
and E U
[0 B) 1 : 1], and the bound (107) holds for all E [N/B 1 1].
We now substitute the bounds (104) and (107) to (101), (102), and (103) to get upper bounds for
|| Il. || and || respectively. For ||rx,1| l| and ||r we can apply the same caleulations as in (70) and (72), modulo the fact that Assumption 3 now implied by Assumption 4, with constants X and p 1. We obtain
2 1)
6MNK
3LN(B (A+ VF(yxo))))
log
(108)
11B
3L - B) 1)
6MNK log
||r.all
S
2B
N B)
VV+ ykoo)1l)-
(109)
For ||r
we have
N/B-1
7LB
6NK
BBMNlog 6N
||r <
IBM (VF(),))) + DVN 8 8log
+ 4x
5M
Bd
B5
N/B-1
7LB²
(FF(E))) + 7/ - B)
6NK
Σ
log
5M
B6
1=1
28LXB3/2
N/B-1
6N²K
Σ vi
V log B8
5M1/2
7LN(N- B)
1/2
B)
6NK
/VF()))))
log
10
M
B5
15LAN 1/2
12 23/2)
6N2K
log
(110)
4M1/2
Recalling the definition (109), and (110):
T3,1 + Pk.2
7/4,3, get an upper bound for |ra]] from (108),
|aall < [[ +
|| + 11T33
6MNK
2AN(2B322 1)
4N B)
+ 3nLN(N B) -1)
< L
log
8
11B
M
2B
3N B 1)
1233/2(N3/22
B3/2)
log 6N2K
+ 2nLN(N - B) 1)
+ LA
5
4M
B8
5
3N - 1)
7N(N B)
2N B)(B -11)
+ L o))
(111)
5
10
5
Recall again that we have K 2 7x (Mg M/NK3 and Nx3
SO MLN S 1/7. Using this
aNK
and N - B < N, we can further simplify (111).
6MNK
12N 3//2
4N B)
||ra|| S L
5B
M
6N
2N - 1)
(2 B3/2)
+ LA log
+
B5
3
4M1/2
40

---

Published as a conference paper at ICLR 2022
22 -1)
(N -B)
V (3k.o)l
3
10
6MNK
6N²K
7LN2
S log
L
+ LX log
(y,,))l
(112)
B3
5
which holds with probability at least
R. The bound (112) holds for all h [K] with probability
1 - 8 if we apply the union bound over 1....,,.. K. Next, by (a (a+b + c)² 3a² 3b² + +
we have
6MNK
6N2K
1
|rall S 3T? log
+ 31,2 log B5
/V (113)
8
25
which also holds for all l E [K] with probability at least 1 - 8.
Getting a high-probability convergence rate. Given our high-probabillty bounds (112) and (113), we can substitute them (62) and get
F F(UR+1,0) F(yn,o)
$ s- + L IV FF
+1² (VF IVVF
|rx|| +1 7 |rall
L
1.7
$ n. + + LN2
|VF(
25
6MNK
6MNK
17² Lv V
log
(V + + 23 log
8
6
6N²K
+1 =
log
[V 1,> log
(114)
B5
B5
The following terms in the RHS of (114) can be bounded using ab 1 a² +
b²
2
2
6MNK
112 Lo
log
VF(Y),))
8
N1//2
6MNK
log
V8
N1/2
< NN
6MNK
[F +
log
(115)
16
N
5
6N2K
1p
log
||F
1/22/1/2
/817 LADx
6.2
IVF(WEO))
log
V8
N1/2
B8
N
2
6N
|F +
log
(116)
16
N
18
Substituting (115) and (116) to (114) results in
F(y4410) F(y
LN
N +
|[FF()))))
5
25
11 22 (4 + L
6MNK
I2 + 3nLN)
6N
log 8
log
(117)
N
N
B8
Again, we have
K > 7x log 2 and 17 (g
MLN < 4. Since the inequality
PNK
7 2
12
2
+
147 4
< 22 holds on E [0, 71. we have
8
25
N + 12n Lp
L3
5
25
41

---

Published as a conference paper at ICLR 2022
Substituting this inequality to (117), together with 4 3rLN -
2/2
yields
F(U++100) - F(yk,o) - nn
6MNK
log 8
2
2N
1,
6N²K
log
2N
We now recall that is μ-PL,
=|1 2 (y(F(yk,o)) P)
911 "
6MNK
F(y++1.0) F* & (1 - (I(V) +*)+
log
2N
6
9 1
6N
log
(118)
2N
B5
Recall that (118) holds for all E [K], with probability - Therefore, by unrolling the inequality, and using > 11 (1 *uNn} < MNN. we get
F(yK,)) F (1 MuN) K (F(y)) - -F*) + 91²² 2
6MNNK
2μ log
9r9
log 6N
(119)
N
Recall that 4,
12N(B8/2
B)
and @x ==
2N(
1 ///2))
hence
5B
M
3
4M1/2
288N2 1)²
32 - -B)²
Φ6 <
25B²
M
8.N (B 1)?
225N2NN312 BB/222
$ 5
9
2M
Substituting these inequalities and also 17
gives
WNK
F(yK, x F
F(yo)= - F 2 log 8
6MNK
log N
(B8/ 1)² +
32N - -B)²
M2NK2
24 K2
25B2
M2
9I2X2 136
6 log
2 2M2MMMN
(8N 1)²
225N(N3/22 B3/282
N4R
2M
F(yo) F
1.2
BB
U2
B²
)) MK²
X²
+
2
31
N2K²
M N2K²
with probability at least
8. This finishes the proof.
D.6 A GENERALIZED 'ECTOR-VALUED HOEFFDING-SERFLAN INEQUALITY
We extend the vector-valued Hoeffding-Serfling inequality proved in Schneider (2016) to account for the mean of multiple independent withouttreplacemmet sums.
Lemma Suppose there are MN vectors {0 J mmmlimm E Rdd that satisfy -| - 6 S
M.N
for m E MM, where TTh = N permutations o1..... OM Unif (SN). For any n I N 1, with probability at least 1 1-8, 8, we have
N v." Consider M independently and uniformly sampled
.MM
1 Mn
R
M
8(1 n-1 log a
m
(120)
mm (6)
Mn
Proof. The proof is extension of Theorem 2 of Schneider (2016) which proves the M = 1 case for vectors in smooth separable Banach spaces. We prove our extended concentration inequality for Rdd but note that the proof technique be applied directly general smooth separable Banach spaces, as done in Schneider (2016). Below, we state a special case of Theorem 3 of Pinelis (1992) and Theorem 3.5 of Pinelis (1994), because this Rd case serves our purpose.
42

---

Published as a conference paper at ICLR 2022
Lemma 9 (Pinelis (1992; 1994)). Suppose that sequence of random variables {x 122 is mar- tingale taking values Rd, and Σ j= ess sup |X x--1 A
S c² for some c Then, for
X
p(sup[| : 2
0} 2 A)
- 2 exp
2c
The proof of Lemma proceeds by defining a sequence of random variables {x,) showing that is martingale, and applying Lemma 9 to prove concentration bound. For m [M.] define index functions km U (0) - [O: n] in the following way:
0
if j S (m 1)n, (m 1)n + S S mm,
km (i) = ma jnn - (m - 1)n}} = j
(m 1)m
n
if 2 mn +1.
Using these index functions, we introduce the following sequence of random variables (xy):
M 1
Kim (i)
Xj
(von (1)
;²)),
N
kim (j)
1=1
and show that this a martingale, i.e..
E[x, XI...., x,-1] X;-1
(121)
for all j 2 1. Notice first that by definition of km 's we have XMd XMa+1 = XM*+2 so (121) trivially satisfied for jll > Mn. Next, for any satisfying (1 - 1) + S S In where
1 E [M]. we have
Xy Σ N E(o (0)()) 6Th) +
1
Σ
10' (1) -0')
N kz(1)
k(t)
Xj-1 +
(0 (wa - 4')
N - -uj)) N k()) +1
N - ki) (v' (oo((k(0)) - 6²)
(122)
Now note that for any h E [N - 1]. we have
N
Elu! - o' [I((),,... an 1)] =
Σ
(o - 44)
N h:
1=k
-t²),
N
where the last equality used Σi (e)² (1) - 84) Using applying this fact (122) and noting
N-
N-RUD)+
(N -N-K(())NN-N)))-+-
k1 -1
E[xy X1....
x +
(v (u)(() x6)
k()+ (N -N -k)) +1)
E (oottinn - o' xI....,,,_11
x,-1|
N kn)
X
hence proving that {x, 120 is martingale, We now apply Lemma 9 to our fx,}. }. For j such that 1)n j S In, notice from (122) that
k=
(N - (x)xxxx - x,-1)= = - -k(()))
Σ 1=1
(0' (a(()) - -0)
+ (o'(a,00)) - 5')
43

---

Published as a conference paper at ICLR 2022
N
(oo110) - - + (0' (vo(()()))) - 6²),
(N ki) + 1)
kz(
which leads to
(N -N- 1 xy-1l1 - ku()) + +13 N kz) +1
+ 2v,
by the triangle inequality. From this, we get the bound c² in the statement of Lemma 9:
4v2
sup |X, x--1
Σ
ess ess sup |x, - x S Σ
1=1
4v M (N n)² + 4 M
N-1
Σ
1
4 (N n)3 +
42 1)
4v2
1 -
12
(N n)N
(N n)
N
km N=N-n
where the second inequality used the inequality that Σk=a+ x²2 S
b-a
(Serfling, 1974,
a(b+1)
Lemma 2.1). Now, applying Lemma 9 to {xy) with c² 4: Mn (N-n)²
(1
" gives
X² - nn)
P([ 2 >) s ||spp[[[ : 03 2 A) s 2cxp
(T882Mn (1 mx1)
(123)
Recall from the definition of {xy} that
1
XMn
(0) - 0.))
N n
Substituting x Mnc
to (123) gives
N-n
n
Mne2 88/2 (1
P
8Th)
Mn
(1)
N
which finishes the proof.
D.7 How CAN WE AVOID UNIFORM BOUNDS OVER R IN OUR ASSUMPTIONS?
In Section 2, we introduced Assumptions 2, 3, and 4 on the intra- and inter-machine deviation. The assumptions required that inequalities such as V (x= V (ær) S hold for all E Rd. In
this subsection, we discuss more this strong requirement "entire Rd
In fact, the entire-R. requirement is posed in our assumptions to simplify the exposition of the main results, and is not strietly necessary. One easily check from our proofs that the assumptions only applied to the beginning iterates Fg (for minibatch RR) or уıoo (for local RR) of epochs. Hence, if these iterates lie in a bounded set, then the constants v, T, p. and À may become much smaller, depending on problem instances. Actually, if we explicitly assume that the iterates lie in compact set S, 12 then Assumptions 2-4 are even guaranteed hold for some constants; e.g., for Assumption 2, we can choose
max ME[MM,NENNI.ES
[V F (x)]l.
since the maximum always exists.
However, assuming that the iterates lie in a specific set S can be problematic because the distance that the iterates travel depend on the objective functions. One cannot know priori if all iterates will stay in fixed set S; hence, explicitly assuming bounded iterates should be avoided.
Then, a natural question is whether we can prove bounded iterates under some reasonable conditions, instead of assuming it. We point out that this can be done by applying the technique developed in Ahn et al. (2020, Theorem to our upper bound theorems. Using the technique, modified version of our Theorem 1 can be written as follows:
12is bounded iterates assumption is indeed used in some existing results such as Haochen & Sra (2019); Nagaraj (2019); Rajput al. (2020); Ahn al. (2020).
44

---

Published as a conference paper at ICLR 2022
Theorem 10 (Best-iterate version of Theorem 1). Suppose that minibatch RR has parameters sat- isfying Assumption 1. Assume that all local component functions f:"h are L-smooth, the global
objective function F is H-PL, and the set of global minima of F is nonempty and compact. Consider running the algorithm using step-size 11
Blog Blog(MN (M) and initialization 11, = 2o, for epochs PNK
K 6olog(MNK)) Then, with probability at least -
F( - -F* MNK2 + (L 1. MNK?
L2 v²
min F( - F' kE[K+1]
where the constant oc is defined as
max max #: (()))((( ME mE(M)
sup
(v) (x))l
(124)
In the theorem, we used #1+100 to denote the last iterate of the algorithm kK, Theorem 10 differs from Theorem in three aspects: 1) it considers the best-iterate, not the last-iterate; 2) it additionally assumes that the set global minima of F is nonempty and compact, which always holds if F' is strongly convex; and 3) does rely on Assumption 2, but instead "proves" it for the F( -subleve set of F (124). Note that the constant v (124) can be much smaller than the uniform bound required to make Assumption 2 hold for the entire IR For Theorems 2, 6, and we can also apply similar techniques to prove best-iterate bounds with smaller intra- and inter-machin deviation constants v, T, P, and X; we omit the precise statements.
We conclude this subsection with the proof of Theorem 10.
Proof. The proof follows that of Ahn et al. (2020, Theorem 1).
Existence of We first show the existence of < co (124). The global objective function F is μu-PL. If we denote the set of global minima of F as X", the set X' is nonempty and compact by assumption. Then, by Karimi et al. (2016, Theorem 2) p-Pt. functions satisfy quadratic growth, i.e.. denoting by x" the closest global minimum in X* to the point œ.
F(x) - F" 2 2p I - x11
Define the sublevel set = {x F(x:) S F(xo)) ) Due to the quadratic growth property, have F(zo) F 2 F(x)
F 2μ | 1²1 for all S. This implies that
F( F
: fx E Rdd F(x)= < ((wo))
x E I ||
x²1
2p
Since we assumed that X is compact, is also bounded, and hence compact. Now, for any m E [M] and i E [N]. [V (x) / [x)]] is continuous function on compact set Se so there must exist a constant 1nth < ao such that | 1 (x) - F (x)ll < v for all æ E S. Taking the maximum of
1/th over m and gives v.
Proving the best-iterate bound. With the constant v (124), if all the iterates (I stay within the sublevel set $ : {x F(w)= < F(zo)), one can consider Assumption 2 to be true with constant v. From this observation, we consider two cases:
1. All the iterates [0.,0) stay in the sublevel set S.
2. There exists an iterate 03,0 & S.
In fact, the first case can be proven by exactly the same steps as Theorem 1, described in Ap- pendix D.2.
For the second case, suppose that there exists an iterate æg.u that escapes the sublevel set S. Let R' f2....,K K + 1} be the first such A. Then, since - o is still in S. it follows from (50) in Appendix D.2 that we have
15n (N33 B3/232
2NK
F( (F))((F((
log B8
(125)
MN
45

---

Published as a conference paper at ICLR 2022
However, the fact that 2v.00 & S and 2ş/-1,0 E S implies
F(mE .0) > F(xo) 2 1(0)-110))
(126)
Combining the two bounds (125) and (126), we get
0 < -IL F*) + 15n 1 2 B3/3)2 2N
log
MN
Bd
which implies
15n 2 2
2NK
min F( - F F(2w-110) F AE KE|++]]
log B6
MM
log(MNK2) 13
Substituting
gives the desired bound and finishes the proof.
aNK
E PROOF OF LOWER BOUND FOR MINIBATCH RR (THEOREM 3)
For Theorem 3, we consider three stee-size ranges and do case analysis for each of them. We construct functions for each corresponding step-size regime such that the convergence of minibatch RR is "slow" for the functions on their corresponding step-size regime. The final lower bound is the minimum among the lower bounds obtained for the three regimes. More concretely, will construct three one-dimensional functions Fi (x), F2(z), and F2(z) satisfying L-smoothness (I), Ju-PE. condition (2), and Assumption 2 such that
Minibatch RR on F1 (1) with S
B μNK and initialization
results in
E
F ( K.
x)
52
Minibatch RR on (x( with 7 2
B and
S
B
and initialization zo 0 results
uNK
513LN
in
E[ x = WMNN3
Note that the step-size range requires K 2 513k, hence this lower bound occurs only in the "large-epoch" regime, i.e., K Z k.
Minibatch RR F2(x) with 1) 2 pNK and 2
B
B 513LN
and initialization zp 0 results
in
( (WMNK]
v2
[[Fa(*K, 52
Then, the three dimensional function F(1x, u, vergence in any step-size regime. Furthermore,
2] Fi(x) + F2(1) + Fs(2) will show bad con-
μI min V' V
that is, Fi, F2 and F3 are p-strongly convex and T-smooth, then so F. Moreover, since the component functions in each coordinate are designed to satisfy Assumption 2 with v, the resulting three dimensional function F' also satisfies Assumption 2 with V
Since the final lower bound is the minimum among the lower bounds obtained in the step-size ranges, if K > 513k, and Ω
the lower bound becomes ?
22
2² if K 513x (in which case jMNNK)
pMNK?
the second step-size range does not exist).
In the subsequent subsections, prove the lower bounds for F,, Fz, and F3 separately.
RNK Recall that this is different from y Blog MK in the theorem statement, because for the proofs, we
consider an equivalent "rescaled" version minibatch defined beginning Appendix D.2. "In fact, the functions constructed in this theorem are j-strongly convex, which is stronger than Jt-PI. required in Definition
46

---

Published as a conference paper at ICLR 2022
E.1 LOWER BOUND FOR
B
pNK
Consider the case where every function at every machine is the same: for all i [M] and m E [M], (x) سس² Hence, Fi
Let 2k,0 and Tk, 7 denote the iterates where the k-th epoch starts and ends respectively, Then,
2k+1,0 2k, x (1 mul) 28 2k.0-
Initializing 01, = y and unrolling this for K epochs, we get
NK
B
K (1 mp
NK
p
4u
since N 2 2, K 1, and B divides N. Hence, Fi (I # S2(2)
E.2 LOWER BOUND FOR 2
B PNK K AND 513LN
B
For most part of this subsection, consider iterates within a single epoch, and hence we will omit the subscripts denoting epochs. Let zo denote the iterate at the beginning of the epoch, and z; denote the iterate after the i-th communication round in that epoch. In construction, each machine will have the same set of component functions, that is, there will be no inter-machine deviation. We therefore omit the superscript from the local component functions f The function we construct for the lower bound and its component functions are as follows:
1 Fxxx)= == N
Σ f+) +
Σ f-1(0))
where
i=
x²
[41(2) = (I. al100 + jul x1200)
vx, and
x²
f-1(x) = (Lleç0 + pl230)
V/T
2
Note that the function (2(x) = (T1s50 + 11 x1)=)) 2/2 is p-strongly convex and I-smooot with minimizer at O, and also satisfies Assumption 2.
N -lss. Then, machine computes gradients on Let Tt be random permutation of N +1's and 7 f-1 and f41 in the order given by o nD Let o"" denote the j-th ordered element a" Then,
fo (x) (Ll=go ulz>o)æ + vog".
Hence, the last iterate an epoch, x ng. is given by
M
(++1)B
7
Σ
Σ
v Foy (z:)
MB
m= i+
M (+11)
Σ
Σ
((L,,, + mln + voj))
MB m= B+1
M (x+1)B
MB Σ
Σ
(Ll,, + ulm;20)
(Since Σi 03 0)
i=0
m= j=iB+1
(Ll + 111,,00
(127)
1=0
47

---

Published as a conference paper at ICLR 2022
-ーー E. [[(( 20 + [lz,,0))a.) We want to prove that E(ry keeps epoch, that is E[æ x zul when zo is close enough to the minimizer 0.
Thus, F[ag - zo] = -1
increasing
For this, first consider the where the first iterate 2o of the epoch satisfies zo 2 0. The To < O case will be considered later. For the case To 2 0, we will show that whenever do is small, the expected amount of update made in the (i 1)-th iteration, E[(L1>,50 + u1a, is negative in the first half of the epoch and not too big in the second half.
We the following lemmas, proven in Appendices F.1 and F.2, respectively.
Lemma 11. For 2 0, 0 < S
2B
N
S
B and f > 7695, 513LN
6
E El 0; + z
Lao
1536 V MB
Lemma 12. For To
N - 1, and 1/ S
B 513LN
B
513inL
513m
5 + plm,00) S 1
1+
2o +
512
512
MB
The key intuition that, for big enough, we can use the lemmas above in (127) to get
E vol 11
(L ulz,00);
N BB"
N/B
Ω
nL
MB
whenever |zal is small. Multiplying the above by K (for K epochs) will give the required lower bound (up to factors of 4)) We will make this approximate calculation precise in the rest of the proof.
Using the two lemmas above in (127), we get that
Bix zu]
--
B[(Laa,s + plm
B[[LIa, so + p1o;00)
Σ
B[(LI2,50 + pla;30)
t=0
++++11
6 Lao
nLv
V MB
1536
1=0
513ngL
513mpw
11
Zo +
(128)
512
512
MB
N
Since inL < nLN
B
<
513 / S
7695
and N/B 2 2, the following bound holds:
#
513
L
Σ
14
1
512
1=0
t= NY
H+1
6T.
N
N
+
+
[+
2B
B
2B
7695
512
6.N
LN
7LN
<
(129)
7B
7680B
8B
48

---

Published as a conference paper at ICLR 2022
Also, note that
NN
N
whenever N/B 2. We have
22
Vi
N
Vidl
2
N
3/2
2
N
3/2
2N3/2
(130)
3
2B
3B
9/3B3/2
i=U
2
N
3/2
N
3/2
Vi <
Vidl
+1
N H+1
B
2B
J+1
2
N
3/2
N
3/27
(2v2 1)N3/2
N3/2
(131)
3
B
2B
3V2B3/2
2B3/2
Substituting the bounds (129), (130), and (131) into (128), and using μ S
L
7695
TnLN
172 LuN3/22
pu
E
rul
2
8B
Tu
+
6912/3M//2BB
1024M1/2B"
TnLN
LuN
8B
To
5/2
(132)
For the other case 2o < 0, we have the following Lemma, which we prove in Appendix F3:
Lemma 13. !fn S 5I3NL
B and an epoch starts at 0, then
7nLN
E
Ery
Tu < 0
8B
Further, if the first epoch of the algorithm is initialized at O, then for any starting iterate 3o of any following epoch, we have P(ro 2 0) 2 1 2
Using (132) and Lemma we get
B I x = P(zo 2 0)E[2 # xo 2
0]
+ Pizo < <0)E[ N ID < 0]
NnLN
1/ L3
P(10 < <0) (1
7nLN
Px0 2 20
8B
To
56000M1/2B'"
8B
20
7nLN
17 LLN3122
+
SB
112000M1/3B2
Thus far, we have characterized the expected per-epoch update, starting from the initial iterate zg and iterating until the last iterate zy of the epoch. Now recall that we run the algorithm for K epochs. Using 2k,s to denote the i-th iterate of the k-th epoch, we get a lower bound on the expectation of the last iterate , x if we initialize F1,0 0:
11 7nLN 8B
L3
K-1
7nLN
E 1
F1,0 +
112000
8B
k=0
TNLN
17² LL
8B
112000 B
inLN &B
N1/2
7uLN K
98000M122BB
8B
N1/1
7I. K
(Since 1j 2 -B
98000M122B
8uK
pNK
Note that since L 7695 and K
>
5131
(which is implied by
< 1) S 513LN
aNK
K
1
7L
2
1
Ih. BW
2
1
6733
1.
8pK
49

---

Published as a conference paper at ICLR 2022
Hence, we get from
B pNK that
NUN1//2 M
L K. x S2
and by Jensen's 's inequality, finally have
22
[[
Blpx K. 12(uBlxx x=1)= = HMNN3
E.3 LOWER BOUND FOR
B PNK AND
B 513LN
Similar to earlier parts of the proof, here as well, each machine will have the same component functions, that is, there will be no inter- machime deviation. The proof uses a similar construction as Safran & Shamir (2020; 2021):
Fx(x) = Etn())+ +
Σ f-1(0))
where
N
i= +
Lx + vx, and f-1 =
Lx²
f41(2) = 2
2 12.
Hence, Fa(x) = Lxa and has its minimizer at 0.
2
We first compute the expected "progress" over given epoch. For simplicity, let omit the subscript for epochs for now. Let vn denote the iterate at the beginning of the epoch and x; denote the iterate after the i-th communication round in that epoch. For a given epoch, let 6t be the permutation of -I's, sampled by machine m. Then,
N +1's and N 2
2
N
F NN =
Σ
Σ
(Lxr v + vo
MB
j=
1)B-1
N
11-nb)ag-1 MB
Σ
oj
1)B+1
8
(1 nL) nL) x mo
TJV
nL
MB
(1-1))++1
For the rest of this proof, xद refers to the square of the i-th iterate. Then,
201e1 snI.) NN
M
E
2
=
22 nL)
To
E
Σ
(1
nL)
Σ
B
MB
m=
1-11)411
11202 M B
M
iB
Σ
nL)
Σ
Σ
oj
m=1
)
?222
(1 -1-mL)
00
E
1b)
Σ
Σ
(133)
M2 B
m=1j=((-
B+1
where we used the fact that E| = O. Further, because nt and m² are independent and identi- cally distributed for different m and m', we get that
B Σ
E
> (1- 1=1
Σ
m= j=(f- B+++1
50

---

Published as a conference paper at ICLR 2022
27
M
Σ
Σ
(1-nt))-
nL)
Σ
()++1)
iB
Σ
E
Σ
1
TT)
Σ
1=(1-1)B+1
B
Σ E
Σ
(1- nL) nL)
Σ
E
Σ
nL)
LL
Σ
o
mşm!
j=(t- (i
1)B+1
j= (i- 1) B+1
# -E
iB
(1-
Σ
(=
where the last equality used the fact that B|oj"| - for all m E [M] and i E [N], and that o are identically distributed. Since we only consider the permutation a (i.e., the one for machine 1) from now on, we henceforth omit the superscript. Substituting this to (133) gives
21²12 M 1
#
iB Σ
El 1= (1-
mL)
2 + 20
E
Σ (1
LL)
(134)
B+1
From (134), we have calculated the per-epoch expected update. Recall that we run the algorithm for K epochs. Using Thi to denote the i-th iterate of the k-th epoch, we get lower bound on the expectation of the last iterate &R squared:
17²22
K-1
1j T12
B B
k. v = (1 1L) 2NK
110
+
MB
Σ
(1-
2N B
2
MB² 4
(135)
k=
where the inequality used F1.0 and Σ k- (1 the expectation term, i.e., Φ defined in (134).
L.)
2%k
2 (1
TT)
Next, we analyze
27
iB
E
Σ (1 - カーー
Σ
B=
N
Σ (1 1L)
2
1) 03 + (1 - nL
B[ooo,y
j=1
Noting that of and E[o,oyy] N-I. we get
① = B Σ
(1
N 1 22
1=
jzj
B -11
B Σ
(1 2)
Σ nL)
-
1
Σ (1 (1-
N
f=0
5=1
1 Σ (1
B
Σ
21
1
B
n-
nD
B
(1 23
N -
j=0
NN -1 Σ (1 nL
B²
N
Σ
(1 - (1-7L)21
N -1
B 0=
1=0
51

---

Published as a conference paper at ICLR 2022
(
-1 (1 (1-n nz
1
# -- Σ 1=0
Σ j=0
n.
(136)
-1
N -11
Note that the term in the parenthesis is exactly the right hand side of Equation (23) in Safran & Shamir (2020) modulo n and a replaced with B and n,,, respectively. Hence, by Lemma of Safran & Shamir (2020), we have
m - (1
[+ 1 N
L2 B
Σ 1=0
(1-mi
(1-
DD)
nLD2
2 c min
N B
-1
B
(137)
for some universal constant > 0. Using the fact that 1/ 2
513LN it is easy to check that the RHS of (137) lower-bounded by nT. where d > 0 is a universal constant. Combining (135), (136), and
B
(137) gives
n2v2
B² B
-1 d
d'pp² N-B
E B
M B2
N
7
LMB N -
Since 2B divides N, we have B S N/2. Since N 2 2, we have and the fact that 1) 2 pNK- - we get
N-B
2 N-1
2(N-13
N
2 1 Using this 2.
L
dvz 4
R[ k.
2
F PROOFS OF HELPER LEMMAS FOR APPENDIX E
F.1 PROOF OF LEMMA 11
First, if = 0 then the lemma trivially holds, because so 2 0 gives
6
[[(12000 + plzo>a)zol = pao S Loo.
The inequality holds because 4 2 7695.
For the rest of the proof, we consider the case 1 sis 2B
By the law of total expectation we have
M
iB
M
iB
[[(112,g0 + (11 [11,,0)mm1
=P
m
0
(L1,, + ulz,s0)a
Σ
m=
m-
j=1
M
B
M
iB
+P
m2
<0
(Lla, 5o + plos50)
Σ
50
3
m== 1=1
m=1
j=1
iB
sB
< P
0 >
LE
Σ
m== j=1
m=
j=1
iB
M
+
Σ
Σ
JF 50
ulE
ΣΣ
<0
(138)
m=1j=1
m=1j=1
where the last inequality used the fact that (L1,gu plexo)t S Lt and (Lligu + pl jut for any E R.
Define E = Σ m=
Σ/E
o. We handle each of the two expectations in (138) separately. We first
bound E [2: E > 0].
1-1
M
(1+1)
[
3
> 0 = E
x0
Σ
Σ
(Vo m + (L + (lle,00 E > 0
MB
==
m=1
k
52

---

Published as a conference paper at ICLR 2022
G+1)B
E
30
Σ
Σ
(vo + (blz,50 + p 20)) 8>
MB
j=0
k=j
M
(+1)B
+
Σ
E
(Ll,, + plo,20)00 & &
1=
k=1
1 Σ
(Mxy500 + 1 (15500) E>
T
R 0)
MB
1)
IE (Ll,
0
< Fn
1- 1
L1 L1 + 1>0000))
TT MB
E > 0)
+ 1L
El zol | 3 > 0].
(139)
Next, we use the following lemma to bound the conditional expectations that arise in (139). This lemma is proven in Appendix E44 and it may be of independent interest to readers.
Lemma 14. For m E [M), let nm be a random permutation of N +1 's and N B
2 -'ss. Then, for any
T
i < N and ls S 2' we have
(VM
M
Vk SE
64
M
m=1j=1
-=i+1
Furthermore, for any 0 < i < N and 0 S k S N satisfying i + k: S N. we have
M
i+
E
1
+
M
S SVM VM + Vh.
M
m=
j=i+1
Lastly, for any 0 s and 0 <
k <
B
satisfying i + k: 2 1, we have
2
M
i
i#
M Σ
i+-k
P
Σ
M
Σ
of
>0
F
M
<0 2
5
j=it1
m=1j=1
j=it1
Lemma 14 implies that 1 83 > 0, this, we get
R M
and P > 0) P(g < <) 1/6. From
E 3131 > 0] T/ i MB
my
(140)
64 MB'
E| zoll
Bli, vol 33 0] <
< 6E
rol]- I-
(141)
3( 0)
Also, since S
B LN
we have
1TL.N
1 1 inp 2 1 -
(L1 (L aygo + (1lzyo0)
2
2 0.
B
1=0
which implies that
i-1
B
1 -
(1 2, <0 + p1 plo
E 8 0
< (1 -imp))oo
(142)
1=0
53

---

Published as a conference paper at ICLR 2022
Substituting (140), (141), and (142) (139), we obtain
[-1
E c E 0] S (1
imp
64
V
MB
+ +nnL _
Bliary - zoll-
(143)
j=0
Next, we have the following lemma that we can apply to El[ found in Appendix F.5. Lemma 15. For Do 2
- rol..
Proof of Lemma 15 can be
0,
0
i
N - 1 and 1j S
B
513LN
B
513
513
Blix
mol]= S
nu
Lno
512
MB
512
Applying this lemma to (143), we get
E E > 0J (1 00
T
i
1539n) 2 Lv
Vj +
1539m
i-1
64
MB
256 MB j=0
256
2=0
i
1/3/3/212210 Lv
15391221212
(1 imp)
370
64
MB
128v 128vMB
MB
512
1539:2
17 L
513inL
1 inp +
TU
512
64
128
MB
LinL
1/V
i
1 inpa
512
300
128
V MB
(144)
where we got the last inequality by using the fact that inL S 1LN
1 513 which follows from
B
7 S BIaLN So far, we have obtained an upper bound for E [2,|8 > 0].
B
Recall that there is another conditional expectation in (138) that we want to bound, namely [x:|E 2 0]. We bound it below, using the tools developed so far. For i x 2B
N
E [2,18 < 0]
zo + E [x; vi & 0]
S xo + E || xol
E < 0]
[|x; xo ||
S 000 + PPEE < 0)
S zr + 6E [|x; - xol I]
(Using Lemma 14)
1539nv i
1539in
20 + 256
V MB
(Using Lemma 15)
256
1539imL
1539mp
i
1
xo +
(145)
256
256
MB
Using (144) and (145) in (138), we get that for i 1 7B:
E + =0)=)
< PP (8: > 0) LE [x:|E 0] + P (8 S 0)
μl [x { S 0]
<P(E> > 100 (1-imp -imp
3inI.
n2
512
30
128 V
MB
+ +P 50p (1+ 1539inL
1539mP
i
20
+
V
(146)
256
256
MB
From Lemma 14, note that
1/2 < P (E > 0) < and < (E < 0)
< -.
We use these inequalities,
along with in <
nn
513 and L 2 7695, to bound the terms appearing in (146).
B
P 3E > 0) I. 1 inp + L
1539inL
To + P
(8
< 0) p
1+
512
256
54

---

Published as a conference paper at ICLR 2022
5
5
L
3
6
6
20 +
z0 S
Lao.
(147)
87552
6
7695
256
We also have
7LV
1539m
PE > 0)
128 V MB
+ +P 50)
256
MB
TL
i
2565muv
768
MB
512
MB
nLV
V
(148)
1536
MB
where we used the assumption
4 2 7695. Substituting (147) and (148) to (146), we get
6 nLv
EL + #l2,))a,11 s Loo
1536 V MB
desired.
F.2
PROOF OF LEMMA 12
[[(1,, + [12,)0));
S [1[((x)]
p.000
[1; Øal
S pao + |B - xoll
513
513
< pzo +
L +
nuv
(Using Lemma 15)
512
512
MB
F.3 PROOF OF LEMMA 13
We consider iterates within a single epoch, and hence we will omit the subscripts denoting epochs. In our construction, each machine has the same set of component functions, that is, there will be inter-maching deviation. We therefore omit the superscript m from the local component functions. Consider the function
N
G2(2):= =
(+) +
Σ g-1(x)
where
N
i= #1
L 9+1 (x) = 2 + uz, and g g-1 (x)
Lx²
=
2 VZ.
Hence, (z(z)= = نا" We will prove the lemma by coupling iterates corresponding to F& and G2- In particular, we will perform minibatch RR on F2 and G2 such that both start the given epoch at zo and all the corresponding machines use the same random permutations. Let I;,F' be the iterate after the i-th round of communication for F2 and F; be the iterate after the i-th round communication for G2. We use mathematical induction to prove that F4,F 2 FGGG for all i == O...., B- After that, we will use this to prove our desired statement E[r x F
0 > (1
TrLN
8B Jao. Let n be
random permutation of N +1's and
N T -1's.
Base case. Fo.F 2 TO.G since both start the epoch at the same point ø0-
Inductive case.
There can be three cases:
Case 1: FiFF 2 Fi.G 2 0. Then,
(++1)B
Σ Σ
(Viop(s1,)) Vooy (x,,G)
F1+1F 1, FFFF Fg MB
1=1
55

---

Published as a conference paper at ICLR 2022
M (++1)B
F1F FGGG MB Σ Σ
(LELF + voJ" LL vo)")
m= j=iB+1
= - G - 1] (F - Lt
21,F(1 - mT/1) - Ii 7L)
2 0.
Case 2: F&FF 2 LGG.- Then,
M
(++1)
F1+1FF Ii+1,
Ii,F
21,
"
Σ
Σ
(o - Voggi (2i,))
MB
m=1 j=i++1
M
(++1)
Ii, 3GG MB
1
Σ
Σ
(Laif vo - LL voT))
m= 1 j=i++1
Fr 2G 1) ( LI
1i - L - 21, n
2
Case Fi,F 2 22 Fg Then,
M
(++1)B
F141FF Ii+1, = -iiF F2.G
7
Σ Σ
(Vaap(EiF) - Vgoy (1i,c)
MB
m= 1++
M
(++1)B
ZiF IGG MB
7
Σ
Σ
(
+ LIg,G vo!")
m= j=i
Fi,F Fi - 1) (MT.,F F L
=I;, [1 - mT1) - I -nL).
Note that since 1 S LN Ft (1 mpu 2 and x2, 1L) I 0, which proves that Fi+1,F Zi+1.G 2 0.
Thus, that T411, T+11G- Further, by linearity of expectation and gradient, it is easy to check that
E Syy ny al = Bir -1, -VG -1,0)
=(1 -1- (11y/))(xgg-.cd
= ...
(1- n2) # xZ.
Using the result that FF 2 xx G which we proved above, we get E[x x. pl 2 (1 .1L)) T/H xo for
any initial iterate zy. Specifically for zo < 0, this implies E[r F 2o < 0 2 (1 - -n N/2 zy.
Further, since 7L - 513N. we have (1 - nL) N/ <
7TLN This is because 8B
T=N - (1 2) N 8B
is nonnegative on the interval 0, 1 - (7 N7B and (7/8) w/ 2
1 for all N
2 2. To
513N
B
see why, note that (1 513(n-1)
n 1 2 8
for all n 2, and this gives (7/8) +
513(n-1))
which then implies 1 - (7/8) N 513m for all n 2 2. Therefore, for xo < 0, we have E[x g.
Zo < 0 2 (1
TnLN )zo-
8B
For the last statement of the lemma, note that by symmetry of the function G2, if we initialize the Algorithm 2 at O, then for any starting iterate of an epoch we have P( 2 0) 2 1/2. This
combined with the fact that FF.F 2 3GG gives us that P( 2 0) 2 1/2.
56

---

Published as a conference paper at ICLR 2022
F.4 PROOF OF LEMMA 14
For m = 1,... M, let Tth be a random permutation of N that for any N/2 and B/2,
+1's and N 2
-1's. Then, we first show
2
M j=1
1 64
Vk
E
M
M
-=
To prove the lower bound, we will use Khintchine's inequality along with Lemma 12 from Rajput et al. (2020). Let define random variables am := | -j=10" Xm sign شز= )"), b
1 o.MM and Ya sign ميز=++ ). For Xm if the sum Σ oj O then Xm is +1 with probability 0.5 and -1 with probability 0.5. Ties occurring in yı are also broken similarly. We can note that Xm. 's and ym are i.i.d. Rademacher random variables, which allows us to apply Khintchine's s inequality, Then, by Khintchine's inequality,
M
E
+
M
E
Σ
amx + bMYM
M
m=1j=
j=it1
M
1/2
2
E
Σ
a + byg
2
By applying ||=||2
Vall
|=|1 for z E R2d twice, we get
M
1/27
M
1/2
M
E
am
+ bys
E
2
b
E
am + bas
2
2
Next, noticing that a. 's are ii.dd.
i+
1
1 VM
E
am + bM
E
VMaas + bM
M
+
M
2
m=1
i M
+ vk
(Lemma 12 from Rajput et al. (2020))
64
Note that Lemma 12 from Rajput et al. (2020) has the requirement that N > 256. However, that requirement is for the entire lemma to hold, whereas we need only the first inequality in the lemma. For that, the requirement is simply N 2 8. Further, note that for N = 2, 4, and 6 it can be manually verified that the required inequalities in Lemma 12 of Rajput et al. (2020) hold. Hence, this lemma holds for all even N.
The upper bound comes from Jensen's inequality:
M M
E
M
1
E
E
Σ
M
M
m=1j=1
j=i+1
j=1
27
27
1 M
M
i+
Σ
mm
+
M
m=1
f=1
1=
M
i+
1
Σ
m
+
M
M
j=it1
(Since Σ Σj= 07
for m 1, 2... are mean and independent.)
57

---

Published as a conference paper at ICLR 2022
21
i+k
E
Σ 2
+
E
Σ
off
M
1=
i+
Elogg offel
+
k +
Σ
Blog"0 01
M
B|0,g0 001 < 0 because oft' and of are negatively correlated. Hence, we get
1
E
M o
vk,
M
M
m=
j=i+1
as desired.
Next, is left to show that for 0 sis
N and
satisfying i i k 2 1, we have
M
i
i+
M ΣΣ OJ
i+
Σ
TH
+
= P
M
2
j=++1
j=i+1
By symmetry, proving the equality is straightforward, and hence it is sufficient prove that
i+k
P
ΣΣ oJ
+ M
Σ
=0
2
(149)
3
5=++1
For this, it in fact suffices to show that
2 for all 15
P
oo==0
(150)
3
because (149) can be derived from (150). We first explain why (150) implies (149), and then show (150). Suppose (150) is true. Then,
Case I: If = 0, then (149) becomes P(C; * j-1 of = 0) S 3. which is true due to (150).
Case 2: If M = 1, then (149) becomes P
E j= 0 = 0) S 3 which is true due to (150).
Case 3: if 2 1 and M 2 2, then we can consider two events that partition the probability
space:
1. E = 12 m Ej=1 oJ
+
M
itk 2j=it1
of = 0}. Conditioned on this event E,,
i
i+
i
P
M
Σ
=0
Fa = TP
Σ 0 =0 /=1
S
m=1j=1
#=++1
due to independence of machines and (150).
2. E2 = M m Ez=1 of + M E
itk vith
1 of + 0}. Conditioned on this event E2, let
c: Em 2j=1 o. + M
2j=1t1 of
M Then,
M
i+1
P
Σ
M Σ
GMM = Foz
=P
Σ 0 -
m=1
1=1
|=
/=1
However, by symmetry, IP = =
(Σ of = c 5
58

---

Published as a conference paper at ICLR 2022
From these two events, conclude that (149) must hold.
It is now left to prove (150). It is clear that P(E of = 0) 0 for all odd i, so we assume that i even. Also note that P(E)=1 oj = = P()) j oj = 0) = -({ of = 0), since af sum to zero. Therefore, for the rest of the proof,
N i's in the range 2 - 2 Note that P(E of = 0) is just the probability of having 1 +1's and -''s in the first spots in random shuffling of N/. +I's and NN -''s. This is equivalent choosing & indices (for +1) of the first and then choosing N-i indices out of the remaining N i. Thus,
focus
2
(12 (*-)
P
Σ o
(N/2)
N
Note that the term above is decreasing function of i for i s N/2. Hence, putting i to the RHS we get
P
Σ
oJ 0
N
2
2(N - 1)
3
N/2
where the incquality holds for 2 4.
F.5 PROOF OF LEMMA 15
i-1 M (i+1)B
E|a; roll =E
11
Σ
vo th + (Llz,<0 + 20,,2003
MB
j=0
B+1
n B
iiB
+ T
Σ (T [1 + p1 ul1520003
(By Lemma 14)
M
i MB
1=0
i MB
+ inLao + m
B1,,, zoll.
Let h(1) = nuv MB + in Lxo + 1L j=0 h(), starting with ((0) = 0. Then using induction, it can be seen that B[aa; xol] S h(()). Further, since h(i) is an increasing function of we get
TH
ME + in
M(1)= -
1 inL
Since i < N B and S B we get that
513LN.
I-
512
513
so E||2;
513 512
T
MB +
513 512
Lo
G PROOF OF LOWER BOUND FOR LOCAL RR: HOMOGENEOUS CASE (THEOREM 4)
Recall that Theorem 4 gives the bound for local RR in the homogeneous setting, where all machines have the same local objectives. Similar to Theorem 3, we consider three step-size ranges and do case analysis for each of them. We construct functions for each corresponding step-size regime such that the convergence of local RR is "slow" for the functions on their corresponding step-size regime. The final lower bound the minimum among the lower bounds obtained for the three regimes. More concretely, we will construct three one-diment mie-dimeniional functions F1 (x), F2(z), and Fz(x) satisfying L-smoothness (I), p-PE condition (2), and Assumption such that
Again, the functions constructed in this theorem are j-strongly convex, which is stronger than JiPl. re- quired in Definition 1. Also, our functions satisfy Assumption 3 with T 0, p
59

---

Published as a conference paper at ICLR 2022
Local RR on (z) with 1 S nNK and initialization yo j results in
E[FI ) =
Local RR on (2(x) with 1j NNK and 11 10257N and initialization yo results in
1
v²
vBB
B[ = PMNN2
PN
Note that the step-size range requires K 1025k, hence this lower bound occurs only in the "large-epoch" regime, i.e., K Z K.
Local RR on Fz(x)) with 1) Z PNK and 1) 1025L and initialization yo results in
DZ
R F[F x
{uMNK
Then, the three dimensional function F([x, v,
=,,²²)== Fi(x) + P2(1) + F2(z) will show bad con-
vergence in any step-size regime. Furthermore.
μI (
Max F V
that is, if Fi, F2 and F3 are p-strongly convex and L-smooth, then so is F. Moreover, since the component functions each coordinate are designed to satisfy Assumption with u, the resulting three dimensional function F also satisfies Assumption with v3v.
Since the final lower bound is the minimum among the lower bounds obtained in the step-size ranges, the lower bound becomes Ω
v²B K 2 1025k and K 2 MB (this inequality is NN"
PMNK +
#N*K2
required to make sure
B2B KNZK3
and Ω
otherwise.
ØMNK
BMNNK
In the subsequent subsections, we prove the lower bounds for F1, F2, and F3, separately.
G.1 LOWER BOUND FOR ?) S
PNK
Consider the case where every function at every machine is the same: for all i e [N] and m E [M], (x) = _
ج Hence, Fi (x) 2
Since all f! are the same, the local updates in all the machines are identical. Hence, for this subsection we omit the superscript for local machines. Let zk.0 and JA,N denote the local iterates at the beginning and end of the k-th epoch. Then,
Jk (1 mu) (u 5n.0-
Initializing 1,0 = and repeating this for K epochs, we get that after K epochs, the last iterate # KNN satisfies
NK
NK V #K, = KKNN = (1 (111) 2
V
1
2
11
NK
1
41
since N > 2, and K > 1. Hence, Fi vz 22 )
G.2 LOWER BOUND FOR 1) PNK AND S T025LN
For most part of this subsection, consider iterates within single epoch, and hence will omit the subscripts denoting epochs. Let Ty denote the iterate at the beginning of the epoch (which the same across all the machines), and xę- denote the i-th local iterate for machine m. After every B local iterates, the server aggregates the local iterates xm computes their average yi := M ΣM 2 and synchronizes all the machines - = yi-
60

---

Let yo denote the iterate the beginning of the epoch (which is the same across all the machines Fo = yo). and x denote the i-th local iterate at machine m. In our construction, each machine will have the same set of component functions, that is, there will be inter-machine deviation. We Published as a conference paper at ICLR 2022
therefore omit the superseript m from the local component functions f. The function we construct for the lower bound and its component functions as follows:
==(x)== N
Σ f+((2)
Σ
f-1(x)
where
i= i=
x²
f+1(2) = (Llaso + ulx50)
vx, and
x²
f-1(2) = (LU+50 + ulz20)
-V
2
Note that the function F2(x) = (Llsgu + xlx>0) x² minimizer O, and also satisfies Assumption 2.
is p-strongly convex and L-smooth with
2
Let Tt be a random permutation of N +1's and N. l's. Then, machine m computes gradients on 2
f-1 and f+1 in the order given by σ Let denote the j-th ordered element of om" Then,
Vl (x) (Llego ul=so)a + voj"
Hence, the last iterate of an epoch, V is given by
$
M B-1
y0
So Som (oiB+s)
B
M
B-1
7
(LL 1144 50 + 1
>0 :0)
vo vo(B+s+))
M
m=1
1=
# -1
M
B-1
7
Σ
50 + pl 30) (L
M
1=0
m=1
3=0
where, in the last line, used the fact that of=10 =0 Recall that in the construction, each machine has the same component functions. Hence,
M
B-1
Ely - vol = M
E
Ll 20 + , "00
m=
1=0
# B-1
ΣΣ A=0
E
(LI
S0 + # >0)
(151)
1=0
where the last equality holds because the iterates ribty are identically distributed across different
m [M]. Hence, we need bound E[(LIx) 2 ul
plggng #lu4,>0 >0ln [b)=+ As we did for Theorem 3, we want to prove that E[y B keeps increasing over an epoch, that is Elyg vol > when is close enough to the minimizer O.
For this, we first consider the case where the first iterate Yo of the epoch satisfies yo 2 0. The Yo < 0 case will be considered later. For the case yo 2 0, we will show that whenever yo is small, the expected amount of update made in the (iB+i++ 1) iteration, [[(Lla) s;,,, 50 + pulp >0)++,+)))++
negative if i < 1 and j < 2. and not too big otherwise.
We use the following lemmas, proven in Appendices H.l and H.2, respectively.
Lemma 16. For yo 2 0, 0 100is H < B. 1025L. and 1 P
15375
6 TL 1536
iB (V
B[(LL mi 50 + 1l = >o )
< $- L
+ Vi
M
61

---

Published as a conference paper at ICLR 2022
N. B Lemma 17. For yo 2 20.00
- 1,,0 B - 1, and 1j S 1025LN'
S p 1+ 1025(iB j)mT.
yo + 1025mu
iB + VJ
E[ SeI 50 5o + pl ا
1024
1024
Next, we apply the two lemmas above in (151). For now, we consider the case N/B 2 2. The case
B = N will be handled separately at the end of this subsection. For simplicity of notation, define Eib+j == [[(L1 so + p so)=) We will divide the summation in (151) into four
groups; for one of them we can apply Lemma 16, and for the other three we apply Lemma 17.
1-1
Elyg - y0] = 11
Eis+j
0=
i=0
18
128
B-1
-1
B-1
= 1)
Eis+j* +
Σ
Ea++j
Eab+j +
Eis+s
1=0
j=
j=
+-1
i=
|+1 j=0
L
1025(iB + jnnL
1025mpu
iB
+ V3 V3))
11 1(+
+
VM
1024
1024
- Lyo
nLv
iB (V
vi))
Σ
(V M
+
1536
L8
Σ
Σ
1 +
1025(iB + +.)mL
yo +
1025ma
VM + V3 )
iB
1024
1024
0 j= 2 +1
B-1 Σ
(1+
10B + 5)nL
1025mu
(V
iB
+V5) vi))
Σ
11
1024
you
+
1024
M
i=
+1
6
L
iB (
(V
v5)) V M
2
Σ
7
L
+
1536
20 セー
--18-1 " ΣΣ 1=
1025(iB + j)mL
1025mpM
LB (V MM
v3) vo))
p 1+
yo +
(152)
1024
1024
where the last inequality is true because the RHS of the inequality in Lemma 17 is nonnegative.
First consider the terms in (152) that involve yo- Since (i.B + jimL nLN V 1025 / S 15375 N/B 2 2, and B 2 4, we have the following loose bound:
1
21
--1B-1
1025(iB + +iyN
Σ
Σ
1
1 +
1024
2=
1=0
1=
N
B
6
N
2L
1
+
1
L
B
[+
2B
4
B
15375
1024
B
LN
7LN
+
(153)
B
2
7680
8
We next bound the terms in (152) that involve summation of square roots. From N/B 2 2, we have
28
N N
33
and
N 7B
+
1
>
28
N
so
N
g
ΣΣ
M
iB
+ VJ
=
4
B
++1
M
B
Σ
Vi
2B
N
+
fj
1
62

---

Published as a conference paper at ICLR 2022
B4/2
N
Vidi
+
Vidt.
4M
2B
B
B
N
3/2
N
B
3/2
B
3/2
+
6M
3B
3B
2
N3/2
(2V2
B
(154)
1
24
For the other sum, we have
Σ
B-
V3
B3/2
N
Σ
Vi+
N
Σ
B-1
Vi
M
M1/2
B
1=0 1=0
1=0
B3/2
N
Vidt
+
Vidt
1/
B
2B3/2
3/2
2N
B3/2
+
3M
B
3B
2/3/2
2/
(155)
1/2
Substituting the bounds (153), (154), and (155) into (152), and using μ S 40000
7nLN
Lu
N3/2
(2V2 - 1)N
Bly
yol 2
Yo +
8
1536
18/3M1/2
24
1025m² pv
2N3/2
2NB
1024
3M1/2
x)²
(N3/2
M1/2 + NB1/2)
90 +
(156)
8
240000
For the other case Yo < O, we have the following lemma, a local RR counterpart of Lemma 13. In Appendix H.3, we prove the following:
Lemma 18. Ifn S 1025LN and an epoch starts at yo < 0, then
7nLN
U yo
2
yo-
8
Further, if the first epoch of the algorithu is initialized at O, then for any starting iterate yo of any following epoch, we have P(yo 2 0) 1/2.
Using (156) and Lemma 18, we get
Ely y
Pyo 2 O)E N 130 2 0] + P(1o <
Yo < 0]
7nLN
2
/N3/2
NBB/2) )) + PP30 < (1- 7n (1-7)LN)
> P(yo 2 0)
9o
240000
M1/2
y0
7
LV
N3/2
M1/2 + NB1/2
>
Do
8
480000
Thus far, we have characterized the expected per-epoch update, starting from the initial iterate yo and iterating until the last iterate y of the epoch. Now recall that we run the algorithm for K epochs. Using yk.s to denote the i-th aggregated iterate of the k-th epoch, we get lower bound on the expectation of the last iterate Vv. x if we initialize at V1.0 O:
UU x1 2 (1-
TqI.N) K 8
vp2 LL NN3/2
K-1
7 &
2//2 + NB
Σ
V1.0 +
480000
8
k=
63

---

Published as a conference paper at ICLR 2022
K
ZULN 8
T
(N3/2
M1/2 + +NBI/2
480000
7yLN
[N1/2
7nLN
B!/2
1
420000
M/1/2
1/1
B1/2
7L
(Since 1/ 2 wNNK)
420000
M1/2
SpK
Note that since 4
40000 and K
>
1025L
(which is implied by pNK S 1l 1025
7L
K
21- - 35000 ~ 1.
8uK
Hence, we get from 2 pNK that
MVN1/2
V DB1/2
FluK, 1
1/ + nyuB1/3 =
WMM/INN/KK pNK
and by Jensen's 's inequality, we finally have
1 BIF x) 2 Blluy # 12pEE VK x1) =
D2
v²B
FMNN22
WN2K3
Recall that, from the paragraph below Lemmas 16 and 17 to this point, we have assumed N/B 2 2. We handle the case B = N now. In this case, notice that all the V iBB terms that appear in (152) disappear, because we always have 0. Therefore, the proof goes through in the same why, modulo the fact that we do not have the terms that originate from the / iB terms in (152). Therefore, we can show
(_
D2
E[
x]]
マ Eluy' x [yK = =Ω
1NN2
G.3 LOWER BOUND FOR 1) PNK AND 17 1025LN
Similar earlier parts of the proof, here as well, each machine will have the same component functions, that is, there will be no inter- mier-machine deviation. The proof uses similar construction as Safran & Shamir (2020; 2021):
Fs(x) =
Σ 1=1
(+)())
+
Σ f-1(0)) i=
where
N
2 + vx, and f=1
Lx²
f41(x)
V2.
2
2
Hence, Fs(x) 2 and has its minimizer at 0.
We first compute the expected "progress" over given epoch. For simplicity, let omit the subscript for epochs for now. Let yo denote the iterate at the beginning of the epoch (which is the same across all the machines z yo) and z!"" denote the i-th local iterate for machine m. After every B local
iterates, the server aggregates the local iterates x computes their average == 1/4 EM a and synchronizes all the machines = = yi-
For the epoch, let " be the permutation of N +1's and N -I's sampled by machine Upon receiving the aggregated iterate x = yi, each machine m performs B local updates. Unrolling the local update rules, the iterate after the B updates (and before synchronization) can be written as follows:
(++1)B [(+1)BB1 VV fo (z((+1)B-1)
64

---

Published as a conference paper at ICLR 2022
(++1)B-1 n( - vo
(1 --)))8811--11111100111-11 11oo
(++)
(1 + nu
BBB
Σ (1- nT.)
j=iB41
(++1)
(1 nL) y/1 TH
Σ
(1 (1-nL))+11B-1)
j=iB41
After synchronization, we get
M
M (++1)
(++1)B (1 nT)
T
Σ
Σ (1 (1-
Vi+1
m=1
m=1j=iB+1
Unrolling the equation above from yg (the starting iterate), we get
(the final iterate the epoch, after synchronization) to yo
N
y = (1-nL)
UN
TV
Σ
Σ
(1
(L-LL)N-1o
M
B+1
-...
M
iB
= (1 - --) yo
>
(1 - nL) (1-ML)N-
TV
Σ
Σ
(1-
M
i=1
m=
B+1
M
(1 nb) yo
TPU
-T.
M
1=
j=1
Then, by squaring both sides and taking expectations,
2mp(11
nII xo
M N
y 2 = (1
2N
yu
Σ
Σ i=1
- nL) N-i o
M
v22v2
M
N
+
Σ
Σ
(1
nL)
No am
M
m==
v222 yo +
M
N
= (1 - -1-nLL22
E
Σ E (1-
0,
(157)
M2
where we used the fact that Eoo,] = 0. Further, because 6t and gm' are independent and identi- cally distributed for different m and mí, we get that
M
N
27
TT
(1
-
M
m=
i=1
M
N
N
N
Σ
Σ 4==1
(1 11 NT
Σ mmm'm
E
Σ
(1
- nL
N-i
o,
Σ (1
nL) i m
m=1
1==1
N [ 1L--LL)N-O
)7
ME
where the last equality used the fact that B[o""] = 0 for all m [M] and i E [N], and that Th are identically distributed. Since we only consider the permutation o (i.e., the for machine 1) from
65

---

Published as a conference paper at ICLR 2022
on, henceforth omit the superseript. Substituting this to (157) gives
27
up2u2 M
E y == (1
yo
E
(158)
From (158), we have calculated the per-epoch expected update, because the final iterate yg is also the initial íterate of the next epoch. Recall that the algorithm for K epochs. We now yk, to denote the iterate after the i-th communication round in the k-th epoch. Using (158), we get a lower bound on the expectation of the last iterate yK, 7 squared:
72v2 M
K-1
172v2 M
B # = (1- [[1- 2N
vi.0 +
+
Σ k=0
(1
m2)
2NK
(159)
where the inequality used that we initialize at 01,0 0 and 2k
K Ck- (1 nL) > (1 nL) 1.
Next, we bound the expectation term, i.e., L, defined in (158). Using Lemma 1 from Safran & Shamir (2020) with and replaced with N and nL respectively, have
2 c. min { Tf. N.2
(160)
for some universal constant > Using the fact that ry 2 1025LN it easy to check that the RHS of (160) is lower-bounded by nT. where e' > 0s a universal constant. Combining (159) and (160) gives
o'
n2v2 d' énp2 M
E
2 K,
nL
LM
Also using the fact that 7) 2 PNK we gel
T.
duu 2μMNK
E[F x )
Elu
2
H PROOFS OF HELPER LEMMAS FOR APPENDIX G
H.1 PROOF OF LEMMA 16
The proof of Lemma 16 is similar to its minibatch RR counterpart, Lemma 11. From the given
0
1,0 S S B 1, define k iB + j. in order simplify notation. We also define
: M Σ of Ei
By the law of total expectation we have
EL + #llg)o)== = (E > D)E (LI [LI + 1l 1 & o]
+ (8
(L1 + يlا p < o|
< (E > 0) LE [ > 0) +P S 0) / jo < 0],
(161)
where the last inequality used the fact that (L1.g0 pl s Lt and (Llggo + pl μt for any / E R.
We handle each of the two expectations in (161) separately. We first bound E from the definition of algorithm iterates that
[ E > 0]. Recall
iB-1
k-1
# - yo r -0
1
Σ
Σ
Von (x1") - Σ Sot (xf)
(162)
M
1=1B
Expanding (162) using the definition of V fomm, 's, we obtain
E
0]
66

---

Published as a conference paper at ICLR 2022
M
iB-1
E
Vo
1
Σ
(vott + (Il + 1 2210))))0)))
M
m=1
1=0
(vot+ + (Ligt +
m + E =0 0
11
B
M
iB-1
E
Ma + plاy plap> - v0)
M
(LI a + p + x1) - 90) 3 > 0 - quB [E|E > 0]
E
7
Σ
(L + plom + 17
Σ
(L) + plo7>0)00 E E> 0
M
1=0
1=1B
M
BB-1
k-1 1
yoB
TJ
Σ
Σ
[L 50 + pl - "
Σ
(L) (Lu + =1 E> 0
M
M=
1=
B
E
1
(
+ plا (lo yyo)
M
m=1
t=
+1
(L1 st0 + 11 [0) 90) E E>3
nu n > 0]
I=
M B
k-1
EynE
7
L1 <o + 10lpppp00 - 17
Σ
(L1 2| + ml=) E > 0
M
m==1
t=
in
(
1)
iB
Σ
E [1a] yol
& 0] + n
Σ
E
[+t vol 3 18>0) 0]
M
M
1=0
A-1
Σ
[|
vol 1 - MyT
18 3 > 0],
iBB
where the last inequality used the fact that (Lleso + ul=so)) S Lt and (Llıso - plaso) S jul for any / E R; and that for different m = .,..., M, the local iterates xi"h are identically distributed conditioned on E >>0 O. Next, we use the fact that for any nonnegative random variable v and event A, we have that Elu|A| < (AA) Hence,
E [
E > 0]
i
S E
1
Σ
(Li <0 + ulop
17
Σ (LI + ulot20) &> 0
M
1=iB
Q - 1)
iB 1
E |
voll
n
B
E |xt voll
k-1 1
E [1x yo ||
+
+ 1
M
P( > 0)
M
P( > 0)
P(E > 0)
1=0
1=0
l=
m///EE 1 > 0]
M
BB-1
k-1
= E 1 M
17
Σ
Σ
(Llg -0 + plom>o) - 1) Σ
(LI 11 + mlotoo E> 0)
m=1
1=0
1=
E |ot vol
MILE [8]8:
0] + 1
(163)
P( > 0)
where the last equality used the fact that for different m E [M], the local iterates x;" are identically distributed when they are not conditioned.
67

---

Published as a conference paper at ICLR 2022
Next, use Lemma 14 again to bound the conditional expectations that arise in (163). We restate the lemma for the reader's convenience.
Lemma 14. For m [M], let Tth be a random permutation of N 2 i S 2
+1's 's' and 2 1ss. Then, for any
and l S 2'
B we have
M
1
+ Vk S E
Σ
t j
64
M
M
m=1j=1
1=+1
Furthermore, for any S i S and 0 S h S N satisfying + k S N, we have
E
S
vk.
M
M
Lastly, for any s and S S a satisfying i k 2 we have
2
M
i+
M
i+k
+ M
Σ
o >0
P
Σ
Σ
M <0 2 <
m=1j=1
-=
j=++1
Lemma 14 implies that E [E|E > 0]
E
04
1
v
18
M
B M
+
vJ
and
P( > 0) = 3(d <
0) 2 1/6. From this, we get
qv
iB
V3
T/E [8 > 0] N
V M
+
(164)
64
E | - yol]
< 6E
[
yo 1
(165)
IP > 0)
Also, since 17
1
we have
LN
M iB-1
1-1
1 -nn 2 1
" M m=1
Σ
Σ
[L + (lopso) - Σ
(LL + (lot20 1 7 2 0,
1=1B
which implies that
M
iB
k-1
E 0 1
Σ
(Lo
+ plapso) -
Σ
(LL (bla3 + plopzo)
S(1 --mp)yo
1=B
(166)
Substituting (164), (165), and (166) (163), we obatin
E c E
0] (1 kmp)yo
Tj
iB
vi)
1
Σ
E [
(167)
64
M
1=0
Next, we have the following lemma that we can apply to B[xa found in Appendix H.4. Lemma 19. For yo 2 0 5io
yol]. Proof of Lemma can be
N - B
L.OiiS 1, and < T025LN
(V
Bl vol] <
1024
1025
nM
(V
iB
M
+ Vi +
1024
1025
(iB + j)nLvo
Applying this lemma to (167) and arranging the bounds (recall that == iB + ÿ), we get
1024 k-1
[ yoll
1025
1=0
68

---

Published as a conference paper at ICLR 2022
1-1
BLUB
S TM
1 /1/BBI/B]
+ my Σ
M
100
1=
BL/BB]
TM
Σ
VVI
BLIBB
M
+B+j-1
(V
BL/B|
k-1
+ Tp
Σ
VI
B1/BB
+ 7L8
Σ
M
I=B
1=0
B
(-1
BB
i
+i
B-1
Σ
v[+
Σ
vi
+ nLy
Σ
1.
(168)
M
M
t-0
1=0
1=0
1=0
The terms in (168) can be bounded using Ei
Vl S So
Vtdt:
1024
k-1
2///2
12/2
////2
2iB3/2
2/²/2
k2a L
E [
=01]
S mp
1025
3M1/22
M1/2
3
3
2
1=0
(2iB + 3/)
iB
4rBj1/2 1/2
2/3/2
k2 Lyo
S Tp
3
M
3
3
2
(2iB + 3j)
iB
(4iB + 2j)
V3
1.2n Lyo
np
3
M
3
2
4kmv
iB
v3
k:2 k2
+
(169)
3
M
2
where the second last inequality used B < j (and hence B1/2 < 2/1/2), and the last inequality used
4
2iB 3j S 4(iB +) 4k and 4iB 2j I 4(B j) 4k. Substituting (169) to (167), we get
E [ > 0]
(170)
< (1 kmu)yo0
TV
V
iB M
+
Vi
+
1025km7 Lv
V
iB M
+ Vi
+
307 yo
64
128
1024
kmja
3075k21,2L3
1024
yo0
64
1
1025kyL
128
ny
iB V
M
+
Vi
1 knp +
IkTIL
yo
T1
iB
+ V3
(171)
1024
128
M
The last inequality here used LnyL < n < 1025 which follows from v/ < T025LN Thus far, we have obtained an upper bound for E
Recall that there is another conditional expectation in (161) that we want bound, namely E [cck] & < 0]. We bound it below, using the tools developed so far. For i S 2B 4
N and B
< j < B
E Tat|E < o]
yo + E
[
yo
E < 0] 3 0]
< Ub
E
[ vol
E ||=1 xul
K yo +
P(E < 0)
I yo
+ 6E [|
xol
(Using Lemma 14)
yo
+
3075MM
iB
+
Vi
+
3075knLyo
(Using Lemma 19)
512
M
512
1
3075kmL
+
3075MM
V
iB
vi
(172)
512
512
69

---

Published as a conference paper at ICLR 2022
Using (171) and (172) in (161), get that for i
NN 2B
and
S S 2
[ p. -0)=1
(P > 0) LE | > 0] + (E &
μB
2 & 0
< > 0) 1
1 + 3k7l.
yo 128
n
( M
iB
+
v3
1024
+ P 12 n (1+ 3
yo + 3075MP
(V
iB
(173)
512
512
M
From Lemma 14, note that
- P
> 0) S and S S S 0) S 8. We use these inequalities,
along with knL I nLN S 1025 and 2
15375 to bound the terms appearing in (173).
3kT
3075knL
PE > 0) L 1 - knp +
yo +
PP - 50)
1
yo
1024
512
5 r 1
3
5
2L
(1+
3
6
6
1049600
Do +
6
15375
512
y0
7
Lyo-
(174)
We also have
PE
> 0)
nLv
iB
vj
+
( S 0)
3075mμu
(v
iB
Vj
128
M
512
TLL
iB
+ Vj
+
5125muM
iB (V
WM
+ V3
768
M
1024
S
iB
+
Vi
(175)
1536
M
where we used the assumption
L
15375
Substituting (174) and (175) to (173), we get
2
[ + + -
nLv
iB
Vi
1536
V M
+
which finishes the proof.
H.2 PROOF OF LEMMA 17
E[(LI S0 + ul sto,, "o,,,, so)th S 1BBp
pyy + pBBa/Bt yo!
S pBJ + /Bll= æoll
1025(iB + +5mmL
1025muM
(V
iB M vj
pgo
yo +
1024
1024
where the last inequality used Lemma 19.
H.3 PROOF OF LEMMA 18
We consider iterates within single epoch, and hence we omit the subscripts denoting epochs. In our construction, each machine has the same set of component functions, that is, there will be no inter-machine deviation. We therefore omit the superscript m from the local component functions. Consider the function
N Σ
N Σ i=
G2(x) = N
(x)
+
g- (x))
(x)
where
+1
70

---

Published as a conference paper at ICLR 2022
Lx 9+1(2) = 2 + vx, and ga) =
Lx² 2
12.
Hence, G= = La We prove the lemma by coupling iterates corresponding to F2 and G2. In particular, we perform local RR F2 and G2 such that both start the given epoch at yo and all the corresponding machines use the same random permutations. Let x ii and aiB+j. denote the iterates (for (iB + j)-th iteration at machine m) for F2 and G2 respectively. We use mathematical induction to prove that a BF 2
2
N th *i for all = O..... π - 1 and j = 0,..., B and machines
m = I,..., M. After that, we will use this to prove our desired statement Elyx 30 < 0] =
E Σm= NN yo < 0J 2 (1
TaLN
8B Jyo-
Let TT be random permutation of N/ +1's and N -1's. First we consider i 0 and 0 S S B.
Base case. For the hase case, we know that 00 2 m +0,G since oF = F0 = Yo for all m.
Inductive case. There can be three cases:
Case
2hth BiB+j,F 2 Th BiB+j.G 2 O. Then,
2 11++++1FF
+1,+ m TB+4jFF j.G ( (V fo 1B (IiB+j,F) V No (1iB+j,G))
BBB+. FiB+i BB + 10 1B+++1
LBt vo (B+++1)
m =ii++ BiB+i,G 7 BB L+
=r]B+j,F(1 mH) B+ c(l nL) 2 0.
Case 2: 0 2 x :B+iFF 2 m. BB+.GG Then,
m 1iB+jt1.f - I m
B
=.i++j.F -
m - B, G VV (fBBtj.r) Vio 311 (I(B+j,G))
=..B+jF L.G 1) (Le + Vo LeiB+,. (+++++)
=s(B+j.r m L.B+j,G (Ia - La(B+5.))
= = L F + nlI,) 2 0.
Case 3: F.B+j,F 2 20 I.B+j.G. Then,
Bi F
F.B+j,F J.B+jiG j.G TI( V Ia (rin+j,F) m
Vo V (LI++jG))
m =1,B+j.F BiB+jiG j. - ( +0i
La vo vo.B+j+1)
-1,B+j,F I.B+j.G (br
L LoiB+j.G)
-1, mH) x BB nL).
Note that since 1) S LN. we get that T B f. mp) > and xm 2iB+j,o(l nL) s 0. which proves that BB4++11FF BBj++ 0.
n2 Bi 2 J -+B-++ for all the three cases, which proves by mathematical Thus, we see that
m
induction that F. I - for all 0 < j B and i = 0. Note that this implies that, the
aggregated averages F1,F := 1 EM 2h B. and V1,G = 1 MM BB satisfy y1.F 2 V1.G- Hence, after synchronization complete, we get that for M and j = O, mm B.B+j.F 2 1m 2. for all machines m. This proves the base case for i = 1. Now, we can repeat the Inductive cases for 15 < B and i = 1, and thereby prove that y/,F 2 92.G. Continuing on this process, we get that m BB+jjr 2 m BB for all 0 S j < B and S S B
M
and consequently, y .g.F 2 U . Further, by linearity of expectation and gradient, is easy to check that for any machine m,
E Elyx al = -1-10 (1-7L)* yo.
71

---

Published as a conference paper at ICLR 2022
Using the result that Vg.F Uy GG which proved above, get E E .l (1 - n yo for
any initial iterate yo- Specifically for yo < O, this implies Ely yo < 0] 2 (1 -n yoo-
Further, since nL I 1025N' we have (1 - nL) N -
Tn This is because 7=N (1 2) N 8
8
is nonnegative on the interval 0, 1 - (7/8)
and (7/8) 2 I025N for all N 2 2. To
see why, note that (1 1025(n
n-1 2 / for all n 2 and this gives (7/8) 1025(n 1)*
which then implies (7/8) n-1 1025n for all n 2 2. Therefore, for yo < O, we have Ely
Yo < 0 2 (1
TeL_N yoo- 8
For the last statement of the lemma, note that by symmetry of the function G2, if we initialize Algorithm at O, then for any starting iterate of an epoch we have P(y.,G 2 0) 2 1/2. This combined with the fact that y 2 Vi, gives that F 2 0) 1/2.
H.4 PROOF OF LEMMA 19
yoll
M
BB-1
iB+j-1
EE
17
voti + (Llzpee + +n
Σ
vol+1 + (LI,t<0 + #l2)20)a
M
#B+j-1
iB
AV
+ V3
+ n
Σ
(LI + + m202200z
(By Lemma 14)
M
1=0
iB+j-1
iB
SMV
+ VJ
+ 1
B B|+l
iB+j-1
iB
STV
+ Vj
+ (iB + Tyn + +nI
B[[a]
yol]
M
1=0
Now define
(V B BK M
/ BL/BB] + Lyjo + T k:
M(k) = Tp
Σ h())-
In terms of i and j. note that corresponds to k = iB + Then using induction, can be seen that Ell0 -ool= _ h(k). Further, since h(k) is increasing function of k. we get
B M
k-
k(k) np
V B[k/B]
+ Ln + nI
Σ h(1)
1=0
B Bk/BB B
S mp
/ B[k/B]
+ knLyo + km)
M
ny
B P
M
/ BLK/B]
+ knLyo
h(k) <
KnL
Since 1: 5 N and
1025L. we get that
1025
iB + Vi
1025
Bl - Holl <
1024 n/
v5)
(iB + +j)nLyo
1024
as desired.
72

---

Published as a conference paper at ICLR 2022
I PROOF OF LOWER BOUND FOR LOCAL RR: HETEROGENEOUS CASE (PROPOSITION 5)
Recall that Proposition gives the bound for local RR in the heterogeneous setting, where different machines have different local objectives. In this section, we construct examples where there is no intra-machine variation (i.e., f1 = _
JN for all m [M]) but there is certain level of
heterogeneity among different machines.
Similar to the other two lower bounds, consider four step-size ranges and do analysis for each of them. This time, we construct a single function F for these step-size regimes such that the convergence of local RR is "slow" for F. The final lower bound is the minimum among the lower bounds obtained for the four regimes. More concretely, we will construct a one-dimensional function F(r) satisfying L-smoothness (I), μ-PE condition (2), and Assumption 3 such that
I Local RR on ((r)) with S SONK and initialization
n results in
E[F(yK, $ Ω
Local RR on F(x) with SONK S "7 S
1 and initialization yo results BuB
E[F(UK, y = B²
Local RR on F(x)) with SuB S n S 1/2 and initialization yo results in
T"
[[F(UK, / = Ω
Local RR on F(x) with 1j 2 1. and initialization yo f. results in
B[F ( = T"
In the subsequent subsections, prove the lower bounds for F for the four step-size intervals.
1.1 LOWER BOUND FOR S S 17
S AND
S
We first consider the two intervals in the middle, because they are more interesting cases. The global objective function F and its local objective functions are as follows.
M
F(x) = M Σ f(())
+
Σ
f2(1))
where
+1
f1( = =- and fe(x) p + T.
In this construction, M/2 machines will have the function fi their N local component functions (and hence their local objective functions) and the other M/ machines will have the function fz-
Then, B local RR updates in each machine corresponds to updates using either fi or f2. If start from 2 = ys. the B local updates on machine m result in
-m + BT
if machine m has f1 if machine m has f2-
(
(1 2np) B x lT E 2np)
Taking the average of the M machines, we get that
B-1 (1 (1-2m))Bur y: 1pr Σ (1 2mp)s )
M (U: + BJ +
M
De+1 M
2
2
Again, the functions constructed in this theorem are j--ttrongyy convex, which is stronger than μiPl. re- quired in Definition 1. Also, our functions satisfy Assumption 2 with 0.
73

---

Published as a conference paper at ICLR 2022
B
Since there are total NK B Σ (1
(1+ - 27/))) yı + TT
j=0
such communication rounds over K epochs, at the end of the run we have
Ax
1 (1+ (1 -224)
VK.
2
30
B-1
NK
+
11T 2
B Σ (1 12211
(1+ 2211)
2
j= 0
1=0
11 + (1- () NK
TJT
B (1 2np 13
)
(176)
2
2fj
2 (1 + (1 2np))
where we used initialization 3/o = 0. Having defined the function and calculated its last iterate (176), let us now handle the two step-size regimes separately.
We first consider BPNK $ 7 S 8pB In this case, we exploit the fact that
1 2n + +1 2² B² S (1 2nj) 8 s 1 2npB3 + 4n722² B²
(177)
when 0 1) S 8 To see why, consider substituting z == 2np. Then (2(2)) == Bz 1 13²²
(1 =2) has (2) 2 0 on E [0, 1). M1 (0) 0, and h1 (0) = 0, implying that h1 2 0 on
2 E [0. 1]. On the other hand, let h2(2) = B 2² (1 - 2) R. If 2, then h2 0. If
B > 2, then it can be checked that (2) S 0 for small enough interval [0, d=1-
Using (177) on (176),
1 - g (1+ (1 2)) X/
1 - (1 2mp) B3
VK,
B
2111
1 1/2 (1+ (1 - 2//4) ()
1- ( (1 + 1 22 + x1²) x
1 (1 2mpBBB n2²1²² 12²
B
2
2114
1 1- (1 + 1 2n/B + 172
xx
nuB²
1 - (1 - nuB + 2n,² 21 12)
2
2
muBBB 112 B²
Nx
2 B
2
1- (1 nuB + 1)
4
npB
NK 3npB 4
BJBB
T/T
B
1
where we used mpB S $.
Now, substituting 1 2 8μNK to above, we obtain
KK
B)
3npB
VK.
1 -
1
4
4
NK
BB
3B
1
32
32N K
(1 (3332) )BB
32pNN K
Therefore, F(UK, x3 =
p² KN
Next, consider
8pB S 11 5
1.
We take a close look at the term that appears (176):
B-1
(1 2mp)² B 1 (1 2m1) B
B
Σ
20p1
74

---

Published as a conference paper at ICLR 2022
For this term, we would like to find lower bound which holds for all 1y 1uus g11 To this end,
consider substituting 2 2n/. Then, the function
B-1
ha(z) = B
Σ 21-
(178)
j=0
increasing on E [4B 1), and we have
h3 (4 B 4B 11 1n
(1- ))) - hy(2), for all E [1 1].
Using 2 2, h3 (B) can be lower-bounded as
B - 4B (1 - (1 - 5)) 16.
ha TB
Next, for 2 1, the derivative of hz(z) = B -
2)²
1-11=)) is h2(2)
1-(==))="((BB-1)=t)) Since B 2 2 is assumed to be even, it is easy to check that 1²(2)) 2 0 for conclude that
1 which means that hg keeps increasing on [1, 2]. Therefore,
B 16
ha ha (#)) S hz(2), for all E [+t 2].
and hence
B-1 B
Σ (1
2 2 16'
J=
for all 1
S n 1. Using VK # from (176), get
8pB
B-1
NK
VK, N
TTT
B - Σ (1
2n1
(1 (1 (1-101120)) 2m1h
2
2
1=0
1=0
B-1
2 T/
B -
Σ
(1 2mp1)
2
1/T
2 T
2
32
256μ
1=0
Here, we used the fact that Σ1
E
-1
( (1 (1 2m R))²
2 (1 (1+ (1 2211) = 1.
Hence, we obtain F(yK, 22(
finishing the proof.
1.2 LOWER BOUND FOR S SPNR AND 2
We now conclude with the "extreme" siep regimes. We consider the same function F as in the previous subsection, but with different initialization yo
For F, recall from (176) that
NK
1/2
1 (1 (1 -1- B)
MK. #
yo
B
NK
+
B
Σ
(1 2m1
2 (1 (1+(1 21j1) (1+(1))))))))
(179)
2
This time, we want to lower-bound the second term on the RHS of (179) with zero and focus on the first term. To this end, we revisit our discussion on hy (178). It is easy to check that hy is in fact
-B-1 increasing the entire [0, oo), and h2) 0. This shows B Σ5=o (1 2mp) > 0 for any
7 2 O. Next, since even, 1 (1 + (1 2m14) ") z 0 for any 77 2 0. This gives 2
UK 2 1 (1+(1 - 2n1))8)
1 (1 + 18-221 221))))
T
yo =
2/
(180)
75

---

Published as a conference paper at ICLR 2022
First, consider the interval 0 S I 1
8aNK- Recall from (177) that for this 7),
(1 2mp)) 1 2 1 2npB n²²2²B B² 2 1 2npB,
(181)
so
NK 8
NK
9K, N 2 2 (1+ (1- (1-100))))
1
2 (1 mdnBi Nx 2
B
9
7T
SNK
8pi
since
NK 2 1. Hence, F(UK, x 07( (1( )
Finally, if 2 1 then we have (1 - 2m/ra B 2 1, so
Nx
1 9K. v 2
(1+
I 2
T
As a result, F(UK
= ) =
76


Reviews:
[{"review_id": "Rhzlimq0JiW", "reviewer": "Reviewer_dmha", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The majority of the manuscript is well-written and easy to understand. This paper is solely theoretical with promising guarantees. The authors showed that if $K \\geq c_2\\kappa$ where $c_2>0$ and $\\kappa = \\dfrac{L}{\\mu}$, then their convergence rates are faster that the with-replacement counterpart. However, for the ill-conditioned case, the number of epochs (theoretically) will be huge to satisfy the mentioned assumptions. \n\nIt would be ideal if the authors could also provide some numerical results to demonstrate how well their proposed methods performs in practice.\n\n", "summary_of_the_paper": "This paper proposes two variants of stochastic gradient algorithms without replacement. For smooth functions satisfying the PŁ condition, the authors showed that the proposed shuffling-based variants converge faster than their with-replacement counterparts (for the case with large number of epochs). Moreover, the authors showed that their provided convergence analysis is tight for the case with not large number of epochs. ", "summary_of_the_review": "This paper provides some promising theoretical results for the variants of stochastic gradient algorithms without replacement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "JSnbouk3uZI", "reviewer": "Reviewer_9cRr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength. 1. The analyzed problems have significant importance in practice and lack a thorough theoretical understanding yet. 2. The technical contribution for analyzing gradient sampling with dependence is original, the technique for bounding gradient noise in local RR is involved and interesting. 3. The provided bounds are tight in some sense and variants with better performance (linear speedup) are analyzed. 4. The lower bound for mini batch RR in small-epoch regime is informative in that it concludes the weakness of mini batch RR for K \\lesssim \\kappa.\n\nSome other points. 1. There exists a gap of \\kappa^2 between upper bounds and lower bounds, which can be important given that \\kappa itself is relevant in the considered regime. It may help to explain more on parameter dependence when claiming tightness. 2. The lower bounds and upper bounds are in different notions of convergence, it may help understanding if there are some explanations there. 3. In theorem 3, it might be useful to explain on the connections among c_1, c_2 and \\kappa, does it affect the regime K \\ge c_2 \\kappa, if c_2 has dependence on \\kappa given that c_1 has dependence on \\kappa. 4. In theorem 4, it also assumes that K \\ge MB/N, does it has influence on the followed discussions on the choice of B. It seems to me the cutoff between parameter regimes is not very clear, could you explain more on it, like, similarly, does c_4 has relationship with \\kappa? 5. Although this is a theory paper, giving some experiments to validate the analysis especially for the discussions on different regimes would be appreciated. \n", "summary_of_the_paper": "This work analyzes the convergence rate of local and mini-batch Random Reshuffling. For \\mu-PL and smooth objectives, It provides high probability upper bounds, and matching expected lower bounds, and a special variant of the random reshuffling that outperforms the previous tight bounds with \\sqrt{M} speed up in some regimes. \n", "summary_of_the_review": "I think this is a good paper with solid theoretical analysis and contribution, the analyzed problem is of great importance and needs more thorough understanding like this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BJHL5E9-C6c", "reviewer": "Reviewer_6QN8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents a deep theoretical study of popular-in-practice methods that utilize shuffling of the data points. This paper has a good structure, all sections are well-written and fully described. All assumptions and statements of theorems are clear and understandable. \n\nHowever, assumption 2 is questionable:\n\nAssumption 2 (Intra-machine deviation). There exists $\\nu \\geq 0$ such that for all $m \\in[M]$ and $i \\in[N]$,\n$$\n\\left\\|\\nabla f_{i}^{m}(\\boldsymbol{x})-\\nabla F^{m}(\\boldsymbol{x})\\right\\| \\leq \\nu, \\text { for all } \\boldsymbol{x} \\in \\mathbb{R}^{d}\n$$ \n\nDoes this assumption hold in practice? Is it not too strict to have a uniform bound for this difference? \n\nThe theory is clear and it is easy to follow the proofs. The theoretical part is solid and the importance and novelty of obtained results are significant. Upper and lower bounds explain methods' behaviors in detail. These results should be interesting for the optimization community and the machine learning community in general. However, it might be useful to have a table with a comparison with rates of other methods for Federated Learning. Also, it is interesting to compare these results with results from https://arxiv.org/pdf/2102.06704.pdf. In this paper, local methods with shuffling are also considered. \n\nThis paper does not have any experimental results. I understand that this work is theoretical, but simple and small experiments on toy models are desirable. It can be useful for readers to have graphical illustrations of methods' behavior. \n\nThe synchronized shuffling method is not clearly described. The notation $\\sigma_{k}^{m}(i):=\\sigma\\left(\\left(i+\\frac{N}{M} \\pi(m)\\right) \\bmod N\\right)$ is quite confusing. Can you explain why you shift the permutation that way?  Despite the main idea of this approach being understandable, some technical details are not easy to get. It might be useful to add some clarifications in this part. \n\n\n\n", "summary_of_the_paper": "This paper studies two popular algorithms: local SGD and minibatch SGD using the data shuffling technique, which means sampling without replacement. Authors provide analysis under PL condition and show that in some cases these methods with shuffling outperform classical local SGD and minibatch SGD. Additionally, this paper provides lower bounds for minibatch RR and local RR in homogeneous and heterogeneous settings. At the end of the paper, a new technique of using synchronized permutations is proposed. In an almost homogeneous setting, this approach can improve rates.", "summary_of_the_review": "This paper introduces a deep and wide theoretical study of permutation-based variants of local SGD and minibatch SGD. Authors provide upper bounds, as well as lower bounds, which makes the contribution solid. The novelty and tightness of results are significant, so the paper should be accepted. My grade is \"accept, good paper\". ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes local SGD under the random reshuffling data selection setting. As is the case for standard random reshuffling, better rates are shown for local SGD when random reshuffling is used. This would already be a nice contribution to a line of work on random shuffling methods—but the paper goes beyond that by showing a matching lower bound and designing a (theoretically) better variant algorithm. The reviewers were all in agreement that this paper should be accepted (as a result not much further discussion happened after the original reviews), and I agree with this consensus. The modification seems to improve the paper, although I did not look through it in detail.
Decision: Accept (Oral)