Proximal and Federated Random Reshuffling
Authors: Konstantin Mishchenko
Ahmed Khaled
Peter Richtárik
Venue: NeurIPS 2021 Submitted (2021)
Keywords: random reshuffling
proximal methods
ProxRR
FedRR
Local SGD

Abstract: Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD) without replacement, is a popular and theoretically grounded method for finite-sum minimization. We propose two new algorithms: Proximal and Federated Random Reshuffling (ProxRR and FedRR). The first algorithm, ProxRR, solves composite convex finite-sum minimization problems in which the objective is the sum of a (potentially non-smooth) convex regularizer and an average of $n$ smooth objectives. ProxRR evaluates the proximal operator once per epoch only. When the proximal operator is expensive to compute, this small difference makes ProxRR up to $n$ times faster than algorithms that evaluate the proximal operator in every iteration, such as proximal (stochastic) gradient descent. We give examples of practical optimization tasks where the proximal operator is difficult to compute and ProxRR has a clear advantage. One such task is federated or distributed optimization, where the evaluation of the proximal operator corresponds to communication across the network. We obtain our second algorithm, FedRR, as a special case of ProxRR applied to federated optimization, and prove it has a smaller communication footprint than either distributed gradient descent or Local SGD. Our theory covers both constant and decreasing stepsizes, and allows for importance resampling schemes that can improve conditioning, which may be of independent interest. Our theory covers both convex and nonconvex regimes. Finally, we corroborate our results with experiments on real data sets.

Proximal and Federated Random Reshuffling
Anonymous Author(s) Affiliation Address
email
Abstract
Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD) without replacement, is popular and theoretically grounded method for finite-sum minimization. We propose two new algorithms: Proximal and Federated Random Reshuffling (ProxRR and FedRR). The first algorithm, ProxRR, solves composite finite-sum minimization problems in which the objective is the sum a (potentially non-smooth) convex regularizer and average of n smooth objectives. ProxRR evaluates the proximal operator once per epoch only. When the proximal operator is expensive compute, this small difference makes ProxRR up times faster than algorithms that evaluate the proximal operator in every iteration, such as proximal (stochastic) gradient descent. We give examples of practical optimization tasks where the proximal operator is difficult to compute and ProxRR has a clear advantage. One such task is federated or distributed optimization, where the evalu- ation of the proximal operator corresponds to communication across the network. We obtain our second algorithm. FedRR, as a special case of ProxRR applied federated optimization, and prove it has smaller communication footprint than either distributed gradient descent Local SGD, Our theory covers both constant and decreasing stepsizes, and allows for importance resampling schemes that can improve conditioning, which may be of independent interest. Our theory covers both convex and nonconvex regimes. Finally, corroborate our results with experiments on real data sets.
3
5
10
11
12
13
14
15
16
17
18
20
Introduction
21
Modern theory and practice of training supervised machine learning models is based the paradigm of regularized empirical risk minimization (ERM) SSalev-Shwarte and Ben- Ben-David, 2014]. While the ultimate goal of supervised learning is to train models that generalize well unseen data, in practice
23
25 only finite data set is available during training. Settling for model merely minimizing the average loss this training set-the empirical risk-is insufficient, this often leads over-fitting and poor 27 generalization performance in practice. Due to this reason, empirical risk is virtually always amended with suitably chosen regularizer whose role is to encode prior knowledge about the learning task hand, thus biasing the training algorithm towards better performing models.
29
The regularization framework is quite general and perhaps surprisingly it also allows us to consider 31 methods for federated learning (FL)-a paradigm which we aim at training model for a number of clients that do not want to reveal their data [Konečný et al., 2016, McMahan et al., 2017, Kairouz
33 et al., 2019]. The training in FL usually happens on devices with only a small number of model updates being shared with global host. To this end, Federated Averaging algorithm has emerged
35 that performs Local SGD updates on the clients' devices and periodically aggregates their average. Its analysis usually requires special techniques and deliberately constructed sequences hindering the
37 research this direction. We shall see, however, that the convergence of our FedRR follows from merely applying algorithm for regularized problems carefully chosen reformulation.
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

39 Formally, regularized ERM problems are optimization problems of the form
P((x) == Ei + #ER
min
(x)];
where Ji: R2 + I is the loss of model parameterized by vector x E I&d on the i-th training data point, and sh: Rd - IR U [+x} is a regularizer. Let [r] == (1.2.....,) We shall make the following assumption throughout the paper without explicitly mentioning it:
40
41
42
43
Assumption 1. The functions Si are L,-smotth, and the regularizer vb is proper, closed and convex.
44
Let Lmax == m Li
45
In some results we will additionally assume that either the individual functions fs. or their average f = 1 E, fe, or the regularizer vb are μ-strongly convex. Whenever we need such additional will make this explicitly clear. While all these concepts are standard, we review them briefly in Section A.
46
assumptions,
48
49
When the number of training data points is huge, as is increasingly common 50 in practice, the most efficient algorithms for solving (1) are stochastic first-order methods, such
Proximal SGD.
51 as stochastic gradient descent (SGD) [Bordes et al., 2009], in one or another of its many variants proposed in the last decade [Shang et al., 2018, Pham et al., 2020]. These method almost invariably rely on alternating stochastic gradient steps with the evaluation of the proximal operator
52
53
prox yr (2) == argmin,es* (rb(2) + åll== - ==13]
54
The simplest of these has the form
SGD 'k+1 prox ( SGD 7k V (xx ))
(2)
55
where i is an index from 21. n chosen uniformly at random, and Y > 0 is properly chosen learning rate. Our understanding of (2) is quite mature; see [Gorbunov al., 2020] for a general treatment which considers methods of this form in conjunction with more advanced stochastic gradient estimators in place of Vii.
56
58
59
Applications such as training sparse linear models [Tibshirani, 1996), nonnegative matrix factoriza- 80 tion [Lee and Seung, 1999]. image deblurring [Rudin et al., 1992 Bredies et al., 2010], and training with group selection [Yuan and Lin, 2006] all rely on the use of hand-crafted regularizes. For most of them, the proximal operator can be evaluated efficiently, and SGD is near or at the top of the list of efficient training algorithms.
81
62
63
Random reshuffling. A particularly successful variant of SGD is based on the idea of random shuffling (permutation) of the training data followed by n iterations of the form (2), with the index i following the pre-selected permutation [Bottou, 2012]. This process is repeated several times, each time using a new freshly sampled random permutation of the data, and the resulting method is known under the name Random Reshuffling (RR). When the same permutation is used throughout, the technique is known under the name Shuffle-Once (SO).
65
66
57
68
69
One of the main advantages of this approach is rooted in its intrinsic ability to avoid cache misses when reading the data from memory, which enables a significantly faster implementation. Furthermore, RR is often observed to converge in fewer iterations than SGD in practice. This can intuitively be
71
73 ascribed to the fact that while due to its sampling-war waing-wwthhppppee with-replacemmnt approach SGD can miss to learn from some data points in any given epoch, RR will learn from each data point in each epoch.
74
75 Understanding the random reshuffling trick, and why it works, has been a non-trivial open problem for a long time [Bottou, 2009, Recht and Ré, 2012, Gürbüzbalaban et al., 2019, Haochen and Sra, 2019]. Until recent development which lead to a significant simplification of the convergence analysis technique and proofs [Mishchenko et al., 2020], prior state of the art relied on long and claborate proofs requiring sophisticated arguments and tools, such as analysis via the Wasserstein distance [Nagaraj et al., 2019], and relied on a significant number of strong assumptions about
76
77
79
81 the objective [Shamir, 2016, Haochen and Sra, 2019]. In alternative recent development, Ahn et al. [2020] also develop tools for analyzing the convergence of random reshuffling, in particular using decreasing stepsizes and for objectives satisfying the Lojjsiwwii condition, a generalization
83
84 of strong convexity [Polyak, 1963, Lojasiewicz, 1963].
85 The difficulty of analyzing RR has been the main obstacle in the development of even some of the most seemingly benign extensions of the method. Indeed, while all these are well understood in

---

Algorithm Proximal Random Reshufiling (ProxRR) and Shuffle-Once (ProxSO)
Require: Stepsizes "i > O, initial vector zu E IR" number of epochs
1: Sample permutation (To.. ....... 1n of [rd] (Do step I only for ProxSO)
2: for epochs t 0, ..... , 1 do
3: Sample permulation (To. NI. : In-1) of [n] (Do step 3 only for ProxRR)
24 21
5: for 0.l,...,. do
6: Tt = 22
fx, (x)) 7: 2++1 = prox (x!²)
combination with its much simpler-to-analyee cousin SGD, to the best of our knowledge, there exists no theoretical analysis of proximal, parallel, and importance sampling variants of RR with both constant and decreasing stepsizes, and in most cases it is not even clear how should such methods be constructed. Empowered by and building on the recent advances of Mishchenko et al. [2020], in this paper address all these challenges.
88
90
91
Contributions
92
93
In this section we outline the key contributions of our work, and also offer few intuitive explanations motivating some of the development.
94
Despite rich literature on Proximal SGD [Gorbunov et al., 2020], it is not obvious how one should extend RR to solve problem (1) when a regularizer şi is present. Indeed, the standard practice for SGD is to apply the proximal operator after each stochastic step [Duchi and Singer, 2009], i.e., in analogy with (2). On the other hand, RR is motivated by the fact that a data pass better approximates the full gradient step. If applied the proximal operator after each step of RR, we would no longer approximate the full gradient after an epoch, as we illustrate next.
New algorithm: ProxRR.
96
88
100
Example 1. Let n = 2, vxxx)= = 1 ||= (x = (c1, 2), f2(x) = (c2, x) with some C1, C2 E Rd. >V fi (zn). 22 = have 27 (22) proX2 (zo- (zoo). However, if #1 prox. (To fV))) and
101
102
C1 A C2. Let To E IR,, > 0 and define Tj
[2(()) Then, we
103
104
22 = prox, (I1 V fa)))) then 32 * prox2 (2o 2 (zoo).
105
Motivated by this observation, we propose ProxRR (Algorithm 1), in which the proximal operator is applied at the end of each epoch of RR, i.c. after each pass through all randomly reshuffled data. A notable property of Algorithm I is that only single proximal operator evaluation is needed during each data pass. This is sharp contrast with the way Proximal SGD works, and offers significant advantages in regimes where the evaluation of the proximal mapping is expensive (e.g., comparable to the evaluation of n gradients fi,..., fn))
106
108
110
Convergence of ProxRR (for strongly convex functions or regularizer). We establish several convergence results for ProxRR, which we highlight two here. Both offer a linear convergence rate 113 with fixed stepsize to a neighborhood of the solution. In both we reply on Assumption 1. Firstly, in
112
114 the case when addition, each fa is p-strongly convex, we prove the rate (see Theorem 2)
E
||T
=1] < (1 744 nT 11:00 xx.12+ 20
115 where 7: 7 S. 1/trmax is the stepsize, and o is shuffling radius constant (for precise definition,
116 see (4)). In Theorem we bound the shuffling radius in terms [[v]((==)] n, Lmax and the more
117 common quantity o2 = 1 Σn [[x,) - V (f..)) Secondly, if af is j-strongly convex, and
118 we choose the stepsize "/ = 7 S 2/Lmass we prove the rate (see Theorem 3)
| - x.ll |1
< (1+ 27um) -T ||lu - x=1 + ?2
119 Both mentioned rates show exponential (linear in logarithmic scale) convergence to a neighborhood whose size is proportional to 2 Since can choose to be arbitrarily small or periodically
3

---

121
decrease it, this implies that the iterates converge to a, in the limit. Moreover, we show in Section 4 that when 7 = 0(7) the error O(tz), which is superior to the o(+) error of SGD.
122
123
Results for SO. All of our results apply to the Shuffle-One algorithm as well. For simplicity, we center the discussion around RR, whose current theoretical guarantees in the nonconvex case are better than that of SO. Nevertheless, the other results are the same for both methods, and ProxRR is identical ProxSO in terms of our theory too. A study of the empirical differences between RR and
124
125
128
127 SO can be found in [Mishchenko et al., 2020J.
Application to Federated Learning. In Section 6 we describe an application of our results to federated learning [Konečný et al., 2016, McMahan et al., 2017, Kairouz et al., 2019]. In this way we obtain the FedRR method, which is similar to Local SGD, except the local solver is single pass of RR over the local data. Empirically, FedRR can be vastly superior to Local SGD (see Figure 2). also show that the rate of FedRR beats the best known lower bound for Local SGD due to [Woodworth et al., 2020] (we needed to adapt it from the original online to the finite-sum setting we consider in this paper) for large enough n. See Section F for more details.
129
131
132
Remarkably,
133
134
135
Nonconvex analysis. In the nonconvex regime, and under suitable assumptions, we establish (see Theorems 5 and 8) an O (GT) ) rate up to a neighborhood of size ( For a certain stepsize it yields
137
an O convergence rate.
138
Besides the above results, we describe several extensions in the appendix, which we now outline.
139
Extension I: Decreasing stepsizes. The convergence of RR is not always exact and depends on the parameters of the objective. Similarly, if the shuffling radius of is positive, and we wish to find an e-approximate solution, the optimal choice of a fixed stepsize for ProxRR will depend on This deficiency can be fixed by using decreasing stepsizes in both vanilla RR [Ahn et al., 2020] and in SGD [Stich, 2019]. We adopt the same technique our setting, However, we depart from [Ahn et al., 2020] by only adjusting the stepsize once per epoch rather than at every iteration, similarly to the concurrent work of Tran et al. [2020] on RR with momentum. For details, see Section I.
140
141
142
143
144
145
146
Extension 2: Importance resampling for Proximal RR. While importance sampling is a well
147
established technique for speeding up the convergence of SGD [Zhao and Zhang, 2015, Khaled and
148
Richtárik, 2020], no importance sampling variant of RR has been proposed nor analyzed. This is not surprising since the key property of importance sampling in SGD--unbiasedness--ae
149
not hold for RR. Our approach to equip ProxRR with importance sampling is via a reformulation of problem (1) into a similar problem with a larger number of summands. In particular, for each E [rx] we include n, copies of the function J. ft. and then take average of all N = Σ, n. functions constructed this way. The value of n, depends on the "importance" of fi. described below. We then apply ProxRR to this reformulation. If f. is L,-smooth for all E [n] and we let L := Σ, Li, then we choose n, [../E]. It is easy to show that N < 2n, and hence our reformulation leads to at most a doubling of the number of functions forming the finite sum. However, the overall complexity of ProxRR applied to this reformulation will depend on T. instead of max; L, (see Theorem 10), which can lead to significant improvement. For details of the construction and our complexity results, see Section J.
150
151
152
153
154
155
156
157
158
3
Preliminaries
159
160
In our analysis, we build upon the notions of limit points and shuffling variance introduced by Mishchenko et al. [2020] for vanilla (i.e., non-proximal) RR. Given a stepsize >> 0 (held constant during each epoch) and a permutation π of {1,2,... .., n1. the inner loop iterates of RR/SO converge
161
182
183
to neighborhood of intermediate limit points x! x ..... x. defined by
x = V V (z.), i i=
(3)
164
The intuition behind this definition is fairly simple: if we performed i steps starting at F., we would end up close to x². To quantify the closeness, we define the shuffling radius.
185
186
Definition (Shuffling radius). Given a stepsize 7 > 0 and a random permutation π of {1, 2.......7. n} used in Algorithm 1, define x;; = =1, x) as in (3). Then, the shuffling radius is defined by
(aa(7) = max
1 + [ (xi, x.)) sm.1]]
(4)

---

168
where the expectation is taken with respect to the randomness in the permutation л. If there are multiple stepsizes 71: 72.... used in Algorithm 1, we take the maximum of all of them as the shuffling radius, i.e., ofad == max of (7t).
189
170
171
The shuffling radius is related by multiplicative factor in the stepsize the shuffling variance introduced by Mishchenko et al. [2020]. When the stepsize is held fixed, the difference between the two notions is minimal. When the stepsize is decreasing. however, the shuffling radius easier to work with, since it can be upper bounded by problem constants independent of the stepsizes.
172
173
174
Armed with special lemma for sampling without replacement, can upper bound the shuffling radius using the smoothness constant Lmax. size of the vector fx.)), and the variance of of the gradient vectors (z.)),..... fn
176
178
Theorem (Bounding the shuffling radius), For any stepsize y > 0 and any random permutation I of {1, 2,..., n) we have L'ad I Euges n (ap ( =0?), where z, is a solution of Problem (1)
179
180
and o is the population variance at the optimum
-==
- (xxx))1?
(5)
All proofs are relegated to the supplementary material. In order to better understand the bound given by Theorem 1, note that if there is no proximal operator (i.e., v = 0) then V (x.)) = 0 and
182
get that Fad I Lo This recovers the existing upper bound on the shuffligg variance of Mishchenko et al. [2020] for vanilla RR. On the other hand, if (I.)) A 0 then we get an additive term of size proportional the squared norm of (x.)).
183
184
185
4
Theory for strongly convex losses f1,..., fn
186
187
Our first theorem establishes a convergence rate for Algorithm I applied with a constant stepsize to Problem (I) when each objective fi is strongly convex. This assumption is commonly satisfied in machine learning applications where each fi represents a regularized loss on some data points, as in lg regularized linear regression and Eg regularized logistic regression.
189
190
191
Theorem 2.
Let Assumption be satisfied. Further, assume that each fi is ju-strongly convex. If Algorithm is run with constant stepsize "t = 7 S 1/Emax, then its iterates satisfy
192
[lrr- =..1 s (1 7/4)"² "d I1.0 x. 11 2y
E
193
We can convert the guarantee of Theorem 2 to a convergence rate by properly tuning the stepsize and using the upper bound of Theorem on the shuffling radius. In particular, if we choose the
194
195
stepsize as 7 = min Limax
/20rnd
JER
and let k = fmx// and ro == ||50 - x.112. then we obtain
IT - x. [1 = O (s) provided that the total number of iterations KRR = nf at least
196
KRR 2 [(s +
v [V
+ (2m))
(6)
Vep
197
Comparison with vanilla RR. If there no proximal operator, then [+x)))) = and we recover the earlier result of Mishchenko et al. [2020] on the convergence of RR without proximal, which is optimal in up to logarithmic factors. On the other hand, when the proximal operator is nonzero, we get an extra term in the complexity proportional to // fz. Il: thus, even when all the functions are the same (i.e., a= = 0), we do not recover the linear convergence of Proximal Gradient Descent Karimi et al.. 2016, Beck, 2017]. This can be easily explained by the fact that Algorithm performs
199
201
203 n gradient steps per one proximal step. Hence, even if f1 = = fn. Algorithm does not reduce to Proximal Gradient Descent. We note that other algorithms for composite optimization which may not take a proximal step at every iteration (for example, using stochastic projection steps) also suffer from the same dependence [Patrascu and Irofti, 2021].
205
206
207
Comparison with proximal SGD. In order to compare (6) against the complexity of Proximal SGD
(Algorithm 2). recall that Proximal SGD achieves E | xx111 113
O (c) either f or &b is
209
j-strongly convex and
KSGD 2 (N+
o² log 2no ey²²
5

---

Algorithm 2 Proximal SGD
Require: Stepsizes T > initial vector xo RR, number of steps K
I: for steps k = 0, 1.l..... ., K do
2: Sample ig uniformly at random from [n]]
3: 2x+1 p (2t V4 (xx))
210 This result is standard [Needell et al., 2016, Gower et al., 2019], with the exception that we do not know any proof in the literature for the case when v is strongly convex. For completeness, we prove in Appendix C, but since our proof is a minor modification of that in [Gower al., 2019], we do not provide it here.
212
By comparing KSGD (given by (7)) and KRR (given by (6)), see that ProxRR has milder dependence on e than Proximal SGD. In particular, ProxRR converges faster whenever the target
215
216
((e]())))++ Furthermore, ProxRR much better when we consider proximal iteration complexity of proximal operator access), in which case the complexity of ProxRR (6) is reduced by a factor of n (because we take one proximal step every n iterations). while the proximal iteration complexity of Proximal SGD remains the same (7). In this
accuracy & is small enough to satisfy e S Temaserii
218
220
case, ProxRR is better whenever the accuracy satisfies
fx.)) +
or
71
+
We can see that if the target accuracy is large enough or small enough, and if the cost of proximal operators dominates the computation, ProxRR is much quicker to converge than Proximal SGD.
223
5
Theory for strongly convex regularizer
In Theorem 2, assume that each is p-strongly convex. This is motivated by the common practice of using f2 regularization in machine learning. However, applying & regularization in every step of Algorithm can be expensive when the data are sparse and the iterates æi are dense, because requires accessing each coordinate of æt which can be much more expensive than computing sparse gradients V (z)). Alternatively, we may instead choose to put the lg regularization inside y and
225
226
227
228
229
only ask that & be strongly convex-the way, we can save lot of time as we need to access each coordinate of the dense iterates 2; only once per epoch rather than every iteration. Theorem 3 gives
230
convergence guarantee in this setting.
232
Theorem 3. Let Assumption hold and Vi....,Ja In be convex. Further, assume that yb is je-stroggly
233
convex. If Algorithm is run with constant stepsize " 7 S 1/Lmax, where Lmax max, Li, then
234
its iterates satisfy
E | - x..13]] S (1+ 27/m)
- 11:00- - x.1l 112 2002
235
Using Theorem 3 and choosing the stepsize as
min
VEP
(8)
get E ||rr- 2.11²] =0 (E) provided that the total number of iterations satisfies
K2 k draa/p VER
+ +n) log (2ro)
This can be converted to bound similar (6) by using Theorem I, in which case the only difference between the two cases is an extra n log (!) term when only the regularizer is ju-strongly convex.
238
239
Since for small enough accuracies the 1/va term dominates, this difference is minimal.
FedRR: application of ProxRR to federated learning
240
Let us consider now the problem of minimizing the average of EM Nm functions that are stored on M devices, which have Nı...., .,,...,NN NN samples correspondingly.
241
min F(I) + R(x), F(x) = (m) (m)x) = Emnffms())) zE
(10)

---

Algorithm 3 Federated Random Reshuffting (FedRR)
Require: Stepsize 7. > O, initial vector zo = z8 E IRd, number of epochs T
I:
for epochs t = 0, .....777 1 do
2:
for = ..... MM locally in parallel do
3:
Fi.m 34 Sample permutation To.m, N1, .... NN 1, of (1, .... Nm
2..,.....
5:
for i 0, 0,I,... Nm
do 21,m = Ttm VV Te (2),m)
6:
++1
7:
Nm
2141
M D== F.
243
For example, [m) can be the loss associated with a single sample (Xmj; Umj), where pairs (X my. Mmj) follow a distribution Dm that is specific to device m. An important instance of such for- mulation is federated learning, where A devices train a shared model by communicating periodically with server. We normalize the objective in (10) by N this is the total number of functions after we expand each Fm into sum. We denote the solution of (10) by T...
245
247
Extending the space. To rewrite the problem as an instance of (1), we are going to consider a bigger product space, which sometimes used distributed optimization [Bianchi al., 2015]. Let us define n == max (N1, .....,.......................... Nm and introduce dec, the consensus constraint, defined via
249
0,
J.M
vc 2M) (000 otherwise
251
;.....,MM.. By introducing dummy variables ; aM and adding the constraint 21 = ... IM we arrive at the intermediate problem
min 31 ER
ΣM F.. (2m) + (R + (e)(
where R + the is defined, with slight abuse of notation, as (R + (c)( R(x1) if
254
1
TM. and (R + (c)(F,,..., =M) = +oo otherwise.
Since have replaced R with more complicated regularizer R + th. need to understand how to compute the proximal operator of the latter. We show (Lemma in the supplementary) that the proximal operator of (R vbc) is merely the projection onto {(I)....,IM) x1
256
Z. }
258
followed by the proximal operator of R with a smaller stepsize.
259
Reformulation. To have functions in every Fm. we write Fm, as a sum with extra n - Nm, zero EE=n Nn fmy (Fm)
functions, Fmg (x) = for any j > Nm. so that (Im) Σド= fmy(Tm)
N== O. We can now stick the vectors together into æ (Z1..... E RMd and multiply the objective by N which gives the following reformulation:
281
min 1 fi + w(x)
(1I)
WERM d
where (xx) (R #/c) and
M
f(x)= = f((1I, xM) )= = Σ fmi (mm).
264
In other words, function f((x) includes i-th data sample from each device and contains at most one loss from every device, while (x) combines all data losses device m. Note that the solution of (11) is I, = (x. ).) and the gradient of the extended function fz) is given (T)) Therefore, a stochastic gradient step that uses V (x)) corresponds to updating all local models with the gradient of i-th data sample, without any communication.
286
by [xx) = (Vx((a)))
287
268
289
Algorithm 1 for this specific problem can be written in terms of Ti...., EM. which results in Algorithm 3. Note that since (m,) depends only on 2;, computing its gradient does not require communication. Only once the local epochs are finished, the vectors averaged the result of xM).
271
projecting onto the set ((x),..., .ar) 2
273
Reformulation properties. To analyze FedRR, the only thing that we need to do is understand the properties the reformulation (1 I) and then apply Theorem or Theorem The following lemma gives us the smoothness and strong convexity properties of (11).
275
7

---

277
Lemma 1. Let function fms be smoshh and y-stroogly convex for every m. Then, fo from reformulation (1 is smoohh and p-strongly convex.
278
The previous lemma shows that the conditioning of the reformulation is K Lmax just as we would expect. Moreover, it implies that the requirement on the stepsize remains exactly the same: Lmmas. What remains unknown is the value of d'dd. which plays a key role in the convergence bounds for ProxRR and ProxSO. To find an upper bound on rad let us define
281
<
282
m, := N.. Σ
V
283
which is the variance of local gradients on device m. This quantity characterizes the convergence rate of local SGD [Yuan et al., 2020], so we should expect it to appear in our bounds too. The next lemma explains how use upper bound ornd.
284
285
Lemma 2. The shufiling radius ofad of the reformulation (11) is upper bounded by
of S Lmax
(IVF
_o m
4
The lemma shows that the upper bound on ofdd depends the sum of local variances Σ o as well as on the local gradient norms > mil || Fm.())))) (I² Both of these sums appear in the existing literature on convergence of Local GD/SGD [Khaled et al., 2019, Woodworth et al., 2020. Yuan et al., 2020]. We are now ready to present formal convergence results. For simplicity, we will consider heterogeneous and homogeneous cases separately and assume that N1
288
289
290
281
Nas n. To further illustrate generality of our results, we will present the heterogeneous assuming strong convexity R and the homogeneous under strong convexity of functions fmai
292
293
294
Heterogeneous data. In the case when the data are heterogeneous, we provide the first local RR method. We apply either Theorem 2 or Theorem 3, but for brevity, we give only the corollary obtained from Theorem 3.
296
Theorem 4. Assume that functions fmi are convex and L.-smooth for each and i. If R is j--ttrongly convex and 7 S 1/Imar, then we have for the iterates produced by Algorithm 3
298
E
| =.]]]]] s (1 + 2y/m) |1:00 x.11
22 My
> >dS mm=
(IV (m.))I
+ 4M 0 m,
299
For nonconvex analysis, we consider R = 0 and require the following standard assumption.
300
Assumption 2 (Bounded variance and dissimilarity). There exist constants Ç > 0 such that for
any x Rd and
301
E Fimi
1 [F) 0²
and
Σ I VF(=)|1 s 5
Note that above (z) N.. V is the gradient of local dataset and VF(x)
302
a
M (i(( is the full gradient on all data.
303
304
Theorem (Nonconvex convergence). Let Assumptions 1 and 2 be satisfied, and R = 0 (no prox).
Then, the communication complexity achieve | [ ||] s =²
305
T ( -i= + + (F(xx) - F.)) (f()))-F)))
306
Notice that by replicating the data locally on each device and thereby increasing the value of without changing the objective, we can improve the second term in the communication complexity. In particular, if the data are not too dissimilar (a >>> () and E is small (1) >> 1.), the second term in
307
308
309
the complexity dominates, and it helps to have more local steps. However, if the data are less similar,
310
the nodes have to communicate more frequently to get more information about other objectives.
311
Homogeneous data. For simplicity, in the homogeneous (i.e., i.i.d.) data case we provide guarantees without the proximal operator. Since then we have (z:)
312
Fas (z), for any m it holds V (x.) = 0, and thus o² = E/=1 fIV (Ix) )|2. The full variance is then given by
313
Em m., 1 Dm 1 I [VSm( No =
M
MM
where of = N Σn EM | V [x.) 2 is the variance of the gradients over all data.
8

---

50D
SGD
Averaage
101
Mic-- sto--i pront
tepach prost
104
HR Etoration pro4)
tepoch prac)
PICYSS shufth srruffi
200
104
0.003
104
0.0003
10a
104
200
420
020
3000 2300
20000
00000 00000
2.0
2.0
Figure 1: Experimental results for problem (12). The first two plots show with average and confidence intervals estimated 20 random seeds and clearly demonstrate that can save lot of proximal operator computations with our method. The right plot shows the best/worst convergence ProxSO over 20,000 sampled permutations.
Loca 5CD
40
S2D
201
Scaffiee Pechil
Scartal
107
10a
Scatfold
Local 5GD
10
20a
10a
600
2002
20000
20000
30002
40200
30000
25000
30000
42000
Communication
Communicater rounds
Communscation rouncs
Figure 2: FedRR vs Local-SGD and Scaffold: i..d. data (left) and heterogeneous data (middle and right). We
set A1= 0 and estimate the averages and standard deviations by running 10 random seeds for each method.
315 Theorem 6. Let R(x)= = 0 (no prox) and the data be i.i.d., that is (x.) = O for any m, where
318 I, is the solution of (10). Let o² := N Σ Em= fmr (Ix))l? If each fms is Lmax-smooth and p-strongly convex, then the iterates of Algorithm satisfy
1
317
E ||æT x. 11 S (1 - mu)" n2 1120 x. 112 + 2 N
Mp
318
The most important part of this result is that the last term in Theorem has factor of M in the denominator, meaning that the convergence bound improves with the number of devices involved.
319
320
7
Experiments
ProxRR vs SGD. In Figure 1, we look at the logistic regression loss with the elastic net regularization,
322
E Ma(x) A + du |
(12)
where each fi Rdd R is defined as fx( == - (b. log (M(a x)) + (1 b.) log (1 h1 x)) x))). and where (a,, b,) E Rd x (0.1). 10 N N are the data samples, h: t + 1/(1+ + e- is the sigmoid function, and λι, Ag 2 0 are parameters. We set minibatch sizes to 32 for all methods and use theoretical stepsizes, without any tuning. We denote the heuristic version of RR that performs proximal operator step after each iteration 'RR (iteration prox)'. From the experiments,
323
324
326
328
that all methods behave more or less the same way. However, the algorithm that we propose needs only small fraction of proximal operator evaluations, which gives it huge advantage whenever the operator takes more time to compute than stochastic gradients.
330
FeRRR vs Local SGD and Scaffold. We also compare the performance of FedRR, Local SGD and Scaffold Karimireddy et al. [2020] on homogeneous (i.e., i..d.) and heterogeneous data. Since Local SGD and Scaffold require smaller stepsizes to converge, they are significantly slower in the i.i.d. regime, as can be seen in Figure 2. FedRR, however, does not need small initial stepsize and very quickly converges to noisy neighborhood of the solution. We obtain heterogeneous regime by sorting data with respect to the labels and mixing the sorted dataset with the unsorted one. In this scenario, we also the same small stepsize for every method to address the data heterogeneity. Clearly, Scaffold is the best in terms of functional values because it does variance reduction with
332
334
336
338
339
respect the data. Extending FedRR in the same way might be useful too, but this goes beyond the scope of our paper and we leave it for future work. We also note that in terms of distances from the optimum, FedRR still performs much better than Local SGD and Scaffold.
340
341
Our code is provided in the supplementary. More experimental details are in the appendix.

---

References
342
343
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. arXiv preprint arXiv:2006.0694 Neural Information Processing Systems (NeurIPS) 2020, 2020. (Cited on pages 2, 4, and 31)
345
Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. doi: 10.1137/1.7781611199999 (Cited on page 5)
347
348
Pascal Bianchi, Walid Hachem, and Franck Iutzeler. A coordinate descent primal-dual algorithm and application distributed asynchronous optimization. IEEE Transactions on Automatic Control, 61 (10)2994-29553 2015. (Cited on page 7)
319
350
Antoine Bordes, Léon Bottou, and Patrick Gallinari. SGD-QN: Careful quasi-Newton stochastic gradient descent. 2009. (Cited on page 2)
352
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. Unpublished open problem offered to the attendance of the SLDS 2009 conference, 2009. URL http://leon bottou. wwggpapppe/bbotttooooooooooeoeee
354
slds-open -pree-oooeepp------eeee- prwppem- 2009. (Cited on page
356
Léon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade, pages 421 436. Springer, 2012. (Cited on page 2)
357
358
Kristian Bredies, Karl Kunisch, and Thomas Pock. Total generalized variation. SIAM Journal on Imaging Sciences, 3()):422-526, 2010. (Cited on page 2)
359
Gong Chen and Marc Teboulle. Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions. SIAM Journal on Optimization, 3(3):538-544 1993. doi: 10.1137/ 0803026. (Cited page 19)
381
363
John Duchi and Yoram Singer. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research, 10(Dec):2899-2933 2009. (Cited on page 3)
385
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. volume 108 of Proceedings of Machine Learning Research, pages 680-690, Online, 26-28 Aug 2020. PMLR. (Cited on pages 2,3, 3, 18, and 34)
366
367
368
Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General Analysis and Improved Rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5200-5209, Long Beach, California, USA, 09-15 Jun 2019. PMLR. (Cited on page 6)
370
372
373
Robert M. Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: variance
374
reduction via Jacobian sketching. Mathematical Programming, pages 1-58, 2020. ISSN 0025-5610. doi: 10.1007/s10107-022 506-0. (Cited on page 34)
378
Mert Gürbüzbalaban, Asuman Özdaglar, and Pablo A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, Oct 2019. ISSN 1436-4646. doi: 10.10077/100077-019401440000 (Cited on page 2)
377
378
379
Jeff Haochen and Suvrit Sra. Random Shuffling Beats SGD after Finite Epochs. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2624-2633, Long Beach, California, USA. 09-15 Jun 2019, PMLR. (Cited on page 2)
380
381
382
383
Peter Kairouz et al. Advances and open problems in federated learning. arXiv preprint arXi::1912.04977 2019. (Cited pages 1 and 4)
385
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear Convergence of Gradient and Proximal- Gradient Methods Under the Polyak-Lojasiewva Condition. In European Conference on Machine Learning and Knowledge Discovery in Databases Volume 9851, ECML, PKDD) 2016, page 795-811, Berlin, Heidelberg, 2016. Springer-Vetie (Cited on page
387
10

---

389
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning, In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020. (Cited pages 9 and 30)
390
382
395
Ahmed Khaled and Peter Richtárik. Better theory for SGD the nonconvex world. arXiv Preprini arXiv:2002.03322, 2020. (Cited pages 4 and 31)
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First Analysis of Local GD on Heterogeneous Data. arXiv preprint arXiv: 2019. (Cited on page 8)
396
387
A hmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for Local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages
399
PMLR, 2020. (Cited on page 29)
400
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016. (Cited on pages and 4)
401
402
403
Daniel D. Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755))788-791 1999. (Cited on page 2)
404
405
Stanislaw Lojasiewiez. A topologiaal property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117:87-89, 1963. (Cited page 2)
H. Brendan McMaaan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communicationn-eficcccnn learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. (Cited on pages and 4)
408
410
411 Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random Reshuffling: Simple Analysis 05988. Neural Information Processing Systems (NeurIPS) 2020, 2020. (Cited on pages 2, 3, 4, 5, 16, 19, 20, 25, and 26)
with Vast Improvements. arXiv preprint arXiv:2006.0590
413
414
Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. SGD without Replacement: Sharper Rates for General Smooth Convex Functions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4703-4711, Long Beach, California, USA, 09-15 Jun 2019. PMLR. (Cited on page 2)
415
416
417
418
Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Mathematical Programming. 155(1):549-555 573, Jan 2016. ISSN 1436-4646. doi: 10. 1011077/110007-005--66447 (Cited on pages 6 and 34)
420
Neal Parikh and Stephen Boyd. Proximal Algorithms. Foundations and Trends in Optimization, 1(3): 127-239, January 2014. ISSN 2167-3888. doi: 10.1561/24000000003, (Cited on pages 16 and 30)
423
424
Andrei Patrascu and Paul Irofti. Stochastic proximal splitting algorithm for composite minimization. Optimization Letters, pages 1-19, 2021. (Cited on page 5)
Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoe Tran-Dinh. ProXSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110): 2020. (Cited on page 2)
427
428
429
Boris T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki i Matematicheskoi Fiziki, 3(4):643-653, 1963. (Cited on page 2)
430
431
Benjamin Recht and Christopher Ré. Toward a noncommutative cithmetii--eomettie mean in- equality: Conjectures, case-studies, and consequences. S. Mannor, N. Srebro, and R. C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23,
432
433
434
page 11.1-11.24, 2012. Edinburgh, Scotland. (Cited on page 2)
435
Leonid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, (0(1-4):259-268 1992. (Cited page 2)
11

---

437
Shai Shalev-Shwaid and Shai Ben-David. Understanding machine learning: from theory to algo- rithms. Cambridge University Press, 2014. (Cited on page 1)
438
439
Ohad Shamir. Without-replacement sampling for stochastic gradient methods. In Advances in neural information processing systems, pages 46-54, 2016. (Cited page 2)
Fanhua Shang, Licheng Jiao, Kaiwen Zhou, James Cheng, Yan Ren, and Yufei Jin. ASVRG: Accelerated Proximal SVRG. In Jun Zhu and lchiro Takeuchi, editors, Proceedings of Machine Learning Research, volume 95, pages 815-830. PMLR, 14-16 Nov 2018. (Cited on page
442
444
Sebastian U. Stich. Unified Optimal Analysis of the (Stochastic) Gradient Method. arXiv preprint arXiv:1907.042333 2019. (Cited on pages 4 and 31)
445
448
Ruo- Yu Sun. Optimization for Deep Learning: An Overview. Journal of the Operations Research
447
Society of China, 8(2):249-2944 294, Jun 2020. ISSN 2194-6698. doi: 10.10077/4003550000000000
(Cited on page 31)
Junqi Tang, Karen Egiazarian, Mohammad Golbabace, and Mike Davies. The practicality of stochastic optimization in imaging inverse problems. IEEE Transactions on Computational Imaging, 6:1471- 1485, 2020. (Cited page 34)
450
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society: Series B (Methodologicul), 58(1):267 1996. (Cited on page 2)
453
454
Trang H. Tran, Lam M. Nguyen, and Quoc Tran-Dinh. Shuffling gradient-based methods with momentum. arXiv preprint arXiv:201 1884, 2020. (Cited on pages and 31)
455
456
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs Local SGD for Hetero- geneous Distributed Learning. arXiv preprint arXi::2006.0473. Neural Information Processing Systems (NeurIPS) 2020, 2020. (Cited on pages 4, 8, and 24)
457
458
459
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. arXiv preprint arXiv:2011.08474 2020. (Cited page 8)
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statitical Methodology), 68(1):49-67, 2006. (Cited on page? 2)
462
464
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Proceedings of the 32nd International Conference on Machine Learning, PMLR, volume 37, pages 1-9, 2015. (Cited on page 4)
485
486
12

---

Checklist
487
468
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
470
contributions and scope? [Yes]
471
(b) Did you descrihe the limitations of your work? [Yes]
472
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
474
475
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
477
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
480
481
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
482
483
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
484
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
486
487
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
488
(a) If your work uses existing assets, did you cite the creators? [Yes]
489
(b) Did you mention the license of the assets? [N/A]
490
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
482
(d) Did you discuss whether and how consent was obtained from people whose data you're ro using/curating? [N/A]
483
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
485
496
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
498
489
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
500
501
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "cdDuSmDTn_", "reviewer": "Reviewer_SKrH", "summary": "This paper studies a proximal extension of random reshuffling algorithm, namely ProxRR for finite-sum composite optimization. ProxRR requires only one proximal steps per round, which reduces the complexities incurred by costly proximal operators. This paper also studies a federated version of ProxRR, namely FedRR, and proved theoretical advantages over Local SGD.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I would like to express my appreciation for your submission to NeurIPS 2021. The paper is overall well-written and I enjoyed reading it. My concerns are as follows.\n\n1. The ProxRR presented in this paper applies only one proximal step per epoch. This reduces the number of calls to proximal operators, but at the same time incurs additional complexities (say, in eq (6)). It is hard to calibrate the significance of ProxRR bound (6) with [1] or Proximal SGD (7) since there are two factors mixed in --- reshuffling and reduced proximal calls. Have you considered doing ablation study to separate these two factors? For example, how does “ProxRR with proximal at every step” work? Will it eliminate the additional term in (6)?\n\n2. This work compares  FedRR with other smooth federated optimization algorithm such as FedAvg and SCAFFOLD. How does FedRR compare with other federated composite algorithms such as [2] (theoretically or empirically)? For example, for experiments presented in Fig. 2, how does FedRR compare with FedDualAvg [2] if $\\lambda_1 \\neq 0$?\n\n[1] Random Reshufﬂing: Simple Analysis with Vast Improvements, NeurIPS 2020.\n[2] Federated Composite Optimization, ICML 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review for limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Mg8Jj7jPNW4", "reviewer": "Reviewer_Ak2z", "summary": "This paper first proposes a proximal variant of the gradient method with shuffling strategy for a class of composite finite-sum minimization problems, and then specifies it for an optimization problem in federated learning (FL). In fact, the proposed algorithm performs n gradient descent updates per epoch and then applies the proximal operator at the end of each epoch. Both single shuffling and randomized reshuffling strategies can be used. The authors analyze the convergence rates of this algorithm under the strong convexity of the losses and the strong convexity of the regularizer. Next, they apply the proposed algorithm to FL, with and without regularizer. This variant is similar to FedAvg, but it replaces SGD by a shuffling gradient scheme for local updates. They establish the convergence of this variant for both the strongly convex case (where the regularizer is strongly convex) and the non-convex case in both heterogeneity and homogeneity settings, respectively. Numerical experiments are conducted to illustrate the algorithm and compare it with two existing methods: local SGD and SCAFFOLD. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Originality: The first part of this paper extends the results in [Mishchenko et al, 2020] to the composite setting. The convergence results are very similar to those in this work. The use of proximal operator at the end of each epoch makes sense since the convergence guarantee will be in epoch, and it is independent of the shuffling strategy. This is perhaps one of the main contributions. Algorithm 3 is very similar to FedAvg by replacing a classical SGD update with a shuffling gradient scheme. In this algorithm, I do not see where the proximal operator of R comes in. I believe that it should be placed after line 8. Overall, the originality of this paper is moderate. Except for adding a new proximal step, the results are very similar to [Mishchenko et al, 2020]. In fact, [Mishchenko et al, 2020] essentially extends and improves [Nguyen et al 2020] to randomized reshuffling variants.\n\nQuality/clarity: The paper is well written and well-motivated in general. The extension to composite form is nontrivial as they have discussed. However, I have a feeling that the analysis for the strongly convex case is not much different from [Mishchenko et al, 2020]. Therefore, the quality of the paper is moderate. \n \nSignificance: Overall, the paper has considerable contributions in terms of new algorithms, especially Algorithm 1, and the theoretical results associated with both Algorithms 1 and 3. But as mentioned above, due to the similarity of this paper and [Mishchenko et al, 2020], its significance is weak. \n\nBelow are some additional comments:\n\n-- The authors only consider the strongly convex case for Algorithm 1, but not the convex and nonconvex cases. Why are the two latter cases not considered? Is the latter case a special case of Theorem 5?\n\n-- In Theorem 2, how can one estimate or upper bound sigma_rad to form a learning rate? In Theorem 1, its upper bound depends on x*? I believe that this is for theoretical guarantee, but it seems to be very small since it depends on both sigma_rad and epsilon (a desired accuracy). Could you please comment on this aspect?\n\n-- Is there any difference in terms of convergence if either the regularizer is strongly convex or at least one loss is strongly convex?\n\n-- Is Theorem 4 a special case of Theorem 3?\n\n-- In terms of analysis, what is the essential difference between [Mishchenko et al, 2020] and this paper when a regularizer is added?\nWithout a regularizer, does this analysis reduce to [Mishchenko et al, 2020] or other previous works?\n\n-- The proof of Lemma 7 is unclear to me, making me unable to verify Algorithm 3. Could you please add more details to clarify its proof?\n\n-- In Supp. Doc. the authors present the convergence for diminishing learning rates, when t > t_0 ~=T/2. Can you use diminishing learning rate from t=1? If so, then how does the convergence rate in Theorem 9 change?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed. \n\n--- I would suggest the authors to compare also single shuffling (like incremental) and randomized reshuffling in Supp. Doc.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Aep2PCIaCyb", "reviewer": "Reviewer_X7ht", "summary": "This paper proposed two shuffling based stochastic optimization methods, ProxRR and FedRR. ProxRR is the proximal version of SGD with shuffling, and they prove that ProxRR achieves better convergence rate than vanilla proximal SGD on strongly convex function, similar to its counterpart SGD with shuffling. Another advantage of this paper is that their convergence results do not need bounded gradient assumption, which was needed in the several prior shuffling SGD papers. In FedRR algorithm, each client uses SGD without replacement to optimize the local model, instead of vanilla SGD employed in local SGD. They also have analysis of FedRR for convex and nonconvex functions under both homogeneous and heterogeneous settings, and the convergence rates are faster than local SGD. The experiments also show the faster convergence of shuffling based algorithms.\n", "questions": "", "limitations": "", "rating": 6, "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": "As far as I know, this paper is the first to analyze the convergence of proximal SGD without replacement, and it is also the first to introduce shuffling ideas into federated optimization. The theoretical analysis is sound to me. The experiments also support their theory. The paper is well-written and both experimental and theoretical results are clearly presented. This paper introduces shuffled local updates in local SGD, which is a well-known idea to speedup SGD in the traditional optimization community. As the authors showed in the paper, this idea does improve the convergence rate of vanilla local SGD, and the experiments also support that. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. For ProxRR, I am curious about the comparison with the literature of shuffling SGD. Particularly, [1] gives a lower bound $O(n/T^2)$, so can we choose the learning rate carefully such that we can match with this lower bound? \n\n2.  It is a decent algorithm and it does provably improve local SGD. My minor concern is that FedRR is a simple combination of local SGD and SGD without replacement. It would be great if we can apply the shuffling idea on client level as well, e.g., for model averaging stage, server does not randomly sample a subset of clients to do the average, instead it shuffles the clients and selects subsets without replacement. It makes the algorithm look more tailored for federated learning. \n\n[1] Rajput, Shashank, Anant Gupta, and Dimitris Papailiopoulos. \"Closing the convergence gap of SGD without replacement.\" International Conference on Machine Learning. PMLR, 2020.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6yEkAkZxkpT", "reviewer": "Reviewer_Gcuo", "summary": "In this paper, the authors propose two new algorithms for finite sum minimization: Proximal Random Reshuffling (ProxRR) and Federated Random Reshuffling (FedRR). ProxRR is used to solve composite functions, while FedRR is a special case of ProxRR as used in the context of federated optimization. They provide convergence rates under various convexity assumptions, and they also show convergence to small gradient norm (in expectation) for smooth non-convex objectives.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "In extending random reshuffling methods to composite optimization, the authors observe the importance of only applying the proximal operator once every epoch of random reshuffling, rather than at the end of each step. Thus, their algorithm only evaluates the proximal operator a single time during each pass of the data. They go on to show that their results apply to the setting of Shuffle-Once, which was also considered (alongside random reshuffling) in Mishchenko et al. (2020). The authors also provide promising experiments in the federated setting. \n\nThat said, the results of this paper, particularly in handling the random reshuffling difficulties, are somewhat of an incremental extension when compared to Mishchenko et al. (2020). It would be recommended that the authors better elaborate in what ways their results go beyond simply combining Mishchenko et al. (2020) with the standard prox analysis.\n\n\n==== Minor comments ====\n\nThe authors should refer to, and compare with, the method FedAc [1].\n\nLine 263: The equation is overlapping the text.\n\nThe authors note there is no tuning for the ProxRR vs SGD experiments (though tuning here would be *strongly* recommended), but what about for the federated optimization experiments? Please elaborate.\n\n\n[1] Honglin Yuan, and Tengyu Ma. \"Federated Accelerated Stochastic Gradient Descent.\" In NeurIPS. 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After all reviews, responses, and discussions, there is general agreement that the paper is clear and well motivated on its own, but that its main contributions in relation to previous work appear limited as currently presented. The concerns about improvements on prior work took several forms, with the most common being that the extension above Mishchenko et al. (2020) seemed incremental. The discussion clarified a few finer details about this, but in the end did not address the basic concerns of multiple expert reviewers, even considering the nonconvex analysis.

There was discussion on a minor point between Reviewer Gcuo and the authors about tuning step-sizes in experiments. I understand that step-sizes from analysis are used on purpose in order to simulate the theory. Although tuning these would be a different experiment, it could be a related interesting one. Regardless, I did not read this as the main point of that review and would not consider it a serious issue affecting the overall recommendation. It is clear that this paper focuses on theory.
Decision: Reject