Proximal and Federated Random Reshuffling
Year: 2021

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

text: Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD)1 without replacement, is a popular and theoretically grounded method for finite-sum2 minimization. We propose two new algorithms: Proximal and Federated Random3 Reshuffling (ProxRR and FedRR). The first algorithm, ProxRR, solves composite4 finite-sum minimization problems in which the objective is the sum of a (potentially5 non-smooth) convex regularizer and an average of n smooth objectives. ProxRR6 evaluates the proximal operator once per epoch only. When the proximal operator7 is expensive to compute, this small difference makes ProxRR up to n times faster8 than algorithms that evaluate the proximal operator in every iteration, such as9 proximal (stochastic) gradient descent. We give examples of practical optimization10 tasks where the proximal operator is difficult to compute and ProxRR has a clear11 advantage. One such task is federated or distributed optimization, where the evalu-12 ation of the proximal operator corresponds to communication across the network.13 We obtain our second algorithm, FedRR, as a special case of ProxRR applied to14 federated optimization, and prove it has a smaller communication footprint than15 either distributed gradient descent or Local SGD. Our theory covers both constant16 and decreasing stepsizes, and allows for importance resampling schemes that can17 improve conditioning, which may be of independent interest. Our theory covers18 both convex and nonconvex regimes. Finally, we corroborate our results with19 experiments on real data sets.20
1 Introduction21
Modern theory and practice of training supervised machine learning models is based on the paradigm22 of regularized empirical risk minimization (ERM) [Shalev-Shwartz and Ben-David, 2014]. While the23 ultimate goal of supervised learning is to train models that generalize well to unseen data, in practice24 only a finite data set is available during training. Settling for a model merely minimizing the average25 loss on this training set—the empirical risk—is insufficient, as this often leads to over-fitting and poor26 generalization performance in practice. Due to this reason, empirical risk is virtually always amended27 with a suitably chosen regularizer whose role is to encode prior knowledge about the learning task at28 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 consider30 methods for federated learning (FL)—a paradigm in which we aim at training model for a number of31 clients that do not want to reveal their data [Konečný et al., 2016, McMahan et al., 2017, Kairouz32 et al., 2019]. The training in FL usually happens on devices with only a small number of model33 updates being shared with a global host. To this end, Federated Averaging algorithm has emerged34 that performs Local SGD updates on the clients’ devices and periodically aggregates their average.35 Its analysis usually requires special techniques and deliberately constructed sequences hindering the36 research in this direction. We shall see, however, that the convergence of our FedRR follows from37 merely applying our algorithm for regularized problems to a carefully chosen reformulation.38
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Formally, regularized ERM problems are optimization problems of the form39
min x∈Rd
[ P (x) := 1n ∑n i=1 fi(x) + ψ(x) ] , (1)
where fi : Rd → R is the loss of model parameterized by vector x ∈ Rd on the i-th training data40 point, and ψ : Rd → R ∪ {+∞} is a regularizer. Let [n] := {1, 2, . . . , n}. We shall make the41 following assumption throughout the paper without explicitly mentioning it:42 Assumption 1. The functions fi are Li-smooth, and the regularizer ψ is proper, closed and convex.43 Let Lmax := maxi∈[n] Li.44
In some results we will additionally assume that either the individual functions fi, or their average45 f := 1n ∑ i fi, or the regularizer ψ are µ-strongly convex. Whenever we need such additional46 assumptions, we will make this explicitly clear. While all these concepts are standard, we review47 them briefly in Section A.48
Proximal SGD. When the number n of training data points is huge, as is increasingly common49 in practice, the most efficient algorithms for solving (1) are stochastic first-order methods, such50 as stochastic gradient descent (SGD) [Bordes et al., 2009], in one or another of its many variants51 proposed in the last decade [Shang et al., 2018, Pham et al., 2020]. These method almost invariably52 rely on alternating stochastic gradient steps with the evaluation of the proximal operator53
proxγψ(x) := argminz∈Rd { γψ(z) + 12‖z − x‖ 2 } .
The simplest of these has the form54
xSGDk+1 = proxγkψ(x SGD k − γk∇fik(xSGDk )), (2)
where ik is an index from {1, 2, . . . , n} chosen uniformly at random, and γk > 0 is a properly55 chosen learning rate. Our understanding of (2) is quite mature; see [Gorbunov et al., 2020] for a56 general treatment which considers methods of this form in conjunction with more advanced stochastic57 gradient estimators in place of∇fik .58 Applications such as training sparse linear models [Tibshirani, 1996], nonnegative matrix factoriza-59 tion [Lee and Seung, 1999], image deblurring [Rudin et al., 1992, Bredies et al., 2010], and training60 with group selection [Yuan and Lin, 2006] all rely on the use of hand-crafted regularizes. For most of61 them, the proximal operator can be evaluated efficiently, and SGD is near or at the top of the list of62 efficient training algorithms.63
Random reshuffling. A particularly successful variant of SGD is based on the idea of random64 shuffling (permutation) of the training data followed by n iterations of the form (2), with the index65 ik following the pre-selected permutation [Bottou, 2012]. This process is repeated several times,66 each time using a new freshly sampled random permutation of the data, and the resulting method is67 known under the name Random Reshuffling (RR). When the same permutation is used throughout,68 the technique is known under the name Shuffle-Once (SO).69
One of the main advantages of this approach is rooted in its intrinsic ability to avoid cache misses when70 reading the data from memory, which enables a significantly faster implementation. Furthermore,71 RR is often observed to converge in fewer iterations than SGD in practice. This can intuitively be72 ascribed to the fact that while due to its sampling-with-replacement approach SGD can miss to learn73 from some data points in any given epoch, RR will learn from each data point in each epoch.74
Understanding the random reshuffling trick, and why it works, has been a non-trivial open problem75 for a long time [Bottou, 2009, Recht and Ré, 2012, Gürbüzbalaban et al., 2019, Haochen and Sra,76 2019]. Until recent development which lead to a significant simplification of the convergence77 analysis technique and proofs [Mishchenko et al., 2020], prior state of the art relied on long and78 elaborate proofs requiring sophisticated arguments and tools, such as analysis via the Wasserstein79 distance [Nagaraj et al., 2019], and relied on a significant number of strong assumptions about80 the objective [Shamir, 2016, Haochen and Sra, 2019]. In alternative recent development, Ahn et al.81 [2020] also develop new tools for analyzing the convergence of random reshuffling, in particular using82 decreasing stepsizes and for objectives satisfying the Polyak-Łojasiewicz condition, a generalization83 of strong convexity [Polyak, 1963, Lojasiewicz, 1963].84
The difficulty of analyzing RR has been the main obstacle in the development of even some of the85 most seemingly benign extensions of the method. Indeed, while all these are well understood in86
Algorithm 1 Proximal Random Reshuffling (ProxRR) and Shuffle-Once (ProxSO)
Require: Stepsizes γt > 0, initial vector x0 ∈ Rd, number of epochs T 1: Sample a permutation π = (π0u, π1, . . . , πn−1) of [n] (Do step 1 only for ProxSO) 2: for epochs t = 0, 1, . . . , T − 1 do 3: Sample a permutation π = (π0, π1, . . . , πn−1) of [n] (Do step 3 only for ProxRR)
4: x0t = xt 5: for i = 0, 1, . . . , n− 1 do 6: xi+1t = x i t − γt∇fπi(xit) 7: xt+1 = proxγtnψ(x n t )
combination with its much simpler-to-analyze cousin SGD, to the best of our knowledge, there exists87 no theoretical analysis of proximal, parallel, and importance sampling variants of RR with both88 constant and decreasing stepsizes, and in most cases it is not even clear how should such methods be89 constructed. Empowered by and building on the recent advances of Mishchenko et al. [2020], in this90 paper we address all these challenges.91
2 Contributions92
In this section we outline the key contributions of our work, and also offer a few intuitive explanations93 motivating some of the development.94
• New algorithm: ProxRR. Despite rich literature on Proximal SGD [Gorbunov et al., 2020], it is95 not obvious how one should extend RR to solve problem (1) when a regularizer ψ is present. Indeed,96 the standard practice for SGD is to apply the proximal operator after each stochastic step [Duchi and97 Singer, 2009], i.e., in analogy with (2). On the other hand, RR is motivated by the fact that a data98 pass better approximates the full gradient step. If we applied the proximal operator after each step of99 RR, we would no longer approximate the full gradient after an epoch, as we illustrate next.100
Example 1. Let n = 2, ψ(x) = 12‖x‖ 2, f1(x) = 〈c1, x〉, f2(x) = 〈c2, x〉 with some c1, c2 ∈ Rd,101 c1 6= c2. Let x0 ∈ Rd, γ > 0 and define x1 = x0 − γ∇f1(x0), x2 = x1 − γ∇f2(x1). Then, we102 have prox2γψ(x2) = prox2γψ(x0 − 2γ∇f(x0)). However, if x̃1 = proxγψ(x0 − γ∇f1(x0)) and103 x̃2 = proxγψ(x1 − γ∇f2(x̃1)), then x̃2 6= prox2γψ(x0 − 2γ∇f(x0)).104
Motivated by this observation, we propose ProxRR (Algorithm 1), in which the proximal operator is105 applied at the end of each epoch of RR, i.e., after each pass through all randomly reshuffled data. A106 notable property of Algorithm 1 is that only a single proximal operator evaluation is needed during107 each data pass. This is in sharp contrast with the way Proximal SGD works, and offers significant108 advantages in regimes where the evaluation of the proximal mapping is expensive (e.g., comparable109 to the evaluation of n gradients∇f1, . . . ,∇fn).110 • Convergence of ProxRR (for strongly convex functions or regularizer). We establish several111 convergence results for ProxRR, of which we highlight two here. Both offer a linear convergence rate112 with a fixed stepsize to a neighborhood of the solution. In both we reply on Assumption 1. Firstly, in113 the case when in addition, each fi is µ-strongly convex, we prove the rate (see Theorem 2)114
E [ ‖xT − x∗‖2 ] ≤ (1− γµ)nT ‖x0 − x∗‖2 + 2γ 2σ2rad µ ,
where γt = γ ≤ 1/Lmax is the stepsize, and σ2rad is a shuffling radius constant (for precise definition,115 see (4)). In Theorem 1 we bound the shuffling radius in terms of ‖∇f(x∗)‖2, n, Lmax and the more116 common quantity σ2∗ := 1 n ∑n i=1 ‖∇fi(x∗)−∇f(x∗)‖
2. Secondly, if ψ is µ-strongly convex, and117 we choose the stepsize γt = γ ≤ 1/Lmax, we prove the rate (see Theorem 3)118
E [ ‖xT − x∗‖2 ] ≤ (1 + 2γµn)−T ‖x0 − x∗‖2 + γ 2σ2rad µ .
Both mentioned rates show exponential (linear in logarithmic scale) convergence to a neighborhood119 whose size is proportional to γ2σ2rad. Since we can choose γ to be arbitrarily small or periodically120
decrease it, this implies that the iterates converge to x∗ in the limit. Moreover, we show in Section 4121 that when γ = O( 1T ) the error is O( 1 T 2 ), which is superior to the O( 1 T ) error of SGD.122
• Results for SO. All of our results apply to the Shuffle-Once algorithm as well. For simplicity, we123 center the discussion around RR, whose current theoretical guarantees in the nonconvex case are124 better than that of SO. Nevertheless, the other results are the same for both methods, and ProxRR is125 identical to ProxSO in terms of our theory too. A study of the empirical differences between RR and126 SO can be found in [Mishchenko et al., 2020].127
• Application to Federated Learning. In Section 6 we describe an application of our results to128 federated learning [Konečný et al., 2016, McMahan et al., 2017, Kairouz et al., 2019]. In this way we129 obtain the FedRR method, which is similar to Local SGD, except the local solver is a single pass130 of RR over the local data. Empirically, FedRR can be vastly superior to Local SGD (see Figure 2).131 Remarkably, we also show that the rate of FedRR beats the best known lower bound for Local SGD132 due to [Woodworth et al., 2020] (we needed to adapt it from the original online to the finite-sum133 setting we consider in this paper) for large enough n. See Section F for more details.134
• Nonconvex analysis. In the nonconvex regime, and under suitable assumptions, we establish (see135 Theorems 5 and 8) anO( 1γT ) rate up to a neighborhood of sizeO(γ
2). For a certain stepsize it yields136 an O( 1ε3 ) convergence rate.137 Besides the above results, we describe several extensions in the appendix, which we now outline.138
• Extension 1: Decreasing stepsizes. The convergence of RR is not always exact and depends on139 the parameters of the objective. Similarly, if the shuffling radius σ2rad is positive, and we wish to find140 an ε-approximate solution, the optimal choice of a fixed stepsize for ProxRR will depend on ε. This141 deficiency can be fixed by using decreasing stepsizes in both vanilla RR [Ahn et al., 2020] and in142 SGD [Stich, 2019]. We adopt the same technique to our setting. However, we depart from [Ahn et al.,143 2020] by only adjusting the stepsize once per epoch rather than at every iteration, similarly to the144 concurrent work of Tran et al. [2020] on RR with momentum. For details, see Section I.145
• Extension 2: Importance resampling for Proximal RR. While importance sampling is a well146 established technique for speeding up the convergence of SGD [Zhao and Zhang, 2015, Khaled and147 Richtárik, 2020], no importance sampling variant of RR has been proposed nor analyzed. This is not148 surprising since the key property of importance sampling in SGD—unbiasedness—does not hold for149 RR. Our approach to equip ProxRR with importance sampling is via a reformulation of problem (1)150 into a similar problem with a larger number of summands. In particular, for each i ∈ [n] we include151 ni copies of the function 1ni fi, and then take average of all N = ∑ i ni functions constructed this152 way. The value of ni depends on the “importance” of fi, described below. We then apply ProxRR153 to this reformulation. If fi is Li-smooth for all i ∈ [n] and we let L̄ := 1n ∑ i Li, then we choose154 ni = dLi/L̄e. It is easy to show that N ≤ 2n, and hence our reformulation leads to at most a doubling155 of the number of functions forming the finite sum. However, the overall complexity of ProxRR156 applied to this reformulation will depend on L̄ instead of maxi Li (see Theorem 10), which can lead157 to a significant improvement. For details of the construction and our complexity results, see Section J.158
3 Preliminaries159
In our analysis, we build upon the notions of limit points and shuffling variance introduced by160 Mishchenko et al. [2020] for vanilla (i.e., non-proximal) RR. Given a stepsize γ > 0 (held constant161 during each epoch) and a permutation π of {1, 2, . . . , n}, the inner loop iterates of RR/SO converge162 to a neighborhood of intermediate limit points x1∗, x 2 ∗, . . . , x n ∗ defined by163
xi∗ := x∗ − γ ∑i−1 j=0∇fπj (x∗), i = 1, . . . , n. (3)
The intuition behind this definition is fairly simple: if we performed i steps starting at x∗, we would164 end up close to xi∗. To quantify the closeness, we define the shuffling radius.165
Definition 1 (Shuffling radius). Given a stepsize γ > 0 and a random permutation π of {1, 2, . . . , n}166 used in Algorithm 1, define xi∗ = x i ∗(γ, π) as in (3). Then, the shuffling radius is defined by167
σ2rad(γ) := maxi=0,...,n−1
[ 1 γ2Eπ [ Dfπi (x i ∗, x∗) ]] , (4)
where the expectation is taken with respect to the randomness in the permutation π. If there are168 multiple stepsizes γ1, γ2, . . . used in Algorithm 1, we take the maximum of all of them as the shuffling169 radius, i.e., σ2rad := maxt≥1 σ 2 rad(γt).170
The shuffling radius is related by a multiplicative factor in the stepsize to the shuffling variance171 introduced by Mishchenko et al. [2020]. When the stepsize is held fixed, the difference between the172 two notions is minimal. When the stepsize is decreasing, however, the shuffling radius is easier to173 work with, since it can be upper bounded by problem constants independent of the stepsizes.174
Armed with a special lemma for sampling without replacement, we can upper bound the shuffling175 radius using the smoothness constant Lmax, size of the vector ∇f(x∗), and the variance σ2∗ of the176 gradient vectors∇f1(x∗), . . . , ∇fn(x∗).177 Theorem 1 (Bounding the shuffling radius). For any stepsize γ > 0 and any random permutation π178 of {1, 2, . . . , n} we have σ2rad ≤ Lmax 2 n ( n‖∇f(x∗)‖2 + 12σ 2 ∗ ) , where x∗ is a solution of Problem (1)179 and σ2∗ is the population variance at the optimum180
σ2∗ := 1 n ∑n i=1‖∇fi(x∗)−∇f(x∗)‖ 2 . (5)
All proofs are relegated to the supplementary material. In order to better understand the bound181 given by Theorem 1, note that if there is no proximal operator (i.e., ψ = 0) then ∇f(x∗) = 0 and182 we get that σ2rad ≤ Lmaxnσ 2 ∗
4 . This recovers the existing upper bound on the shuffling variance of183 Mishchenko et al. [2020] for vanilla RR. On the other hand, if∇f(x∗) 6= 0 then we get an additive184 term of size proportional to the squared norm of∇f(x∗).185
4 Theory for strongly convex losses f1, . . . , fn186
Our first theorem establishes a convergence rate for Algorithm 1 applied with a constant stepsize to187 Problem (1) when each objective fi is strongly convex. This assumption is commonly satisfied in188 machine learning applications where each fi represents a regularized loss on some data points, as in189 `2 regularized linear regression and `2 regularized logistic regression.190 Theorem 2. Let Assumption 1 be satisfied. Further, assume that each fi is µ-strongly convex. If191 Algorithm 1 is run with constant stepsize γt = γ ≤ 1/Lmax, then its iterates satisfy192
E [ ‖xT − x∗‖2 ] ≤ (1− γµ)nT ‖x0 − x∗‖2 + 2γ 2σ2rad µ .
We can convert the guarantee of Theorem 2 to a convergence rate by properly tuning the stepsize193 and using the upper bound of Theorem 1 on the shuffling radius. In particular, if we choose the194 stepsize as γ = min { 1
Lmax , √ εµ√
2σrad
} , and let κ := Lmax/µ and r0 := ‖x0 − x∗‖2, then we obtain195
E [ ‖xT − x∗‖2 ] = O (ε) provided that the total number of iterations KRR = nT is at least196
KRR ≥ [(κ+ √ κn√ εµ ( √ n ‖∇f(x∗)‖+ σ∗)] log ( 2r0 ε ) . (6)
Comparison with vanilla RR. If there is no proximal operator, then ‖∇f(x∗)‖ = 0 and we recover197 the earlier result of Mishchenko et al. [2020] on the convergence of RR without proximal, which is198 optimal in ε up to logarithmic factors. On the other hand, when the proximal operator is nonzero,199 we get an extra term in the complexity proportional to ‖∇f(x∗)‖: thus, even when all the functions200 are the same (i.e., σ∗ = 0), we do not recover the linear convergence of Proximal Gradient Descent201 [Karimi et al., 2016, Beck, 2017]. This can be easily explained by the fact that Algorithm 1 performs202 n gradient steps per one proximal step. Hence, even if f1 = · · · = fn, Algorithm 1 does not reduce203 to Proximal Gradient Descent. We note that other algorithms for composite optimization which may204 not take a proximal step at every iteration (for example, using stochastic projection steps) also suffer205 from the same dependence [Patrascu and Irofti, 2021].206
Comparison with proximal SGD. In order to compare (6) against the complexity of Proximal SGD207 (Algorithm 2), we recall that Proximal SGD achieves E [ ‖xK − x∗‖2 ] = O (ε) if either f or ψ is208
µ-strongly convex and209 KSGD ≥ ( κ+ σ2∗ εµ2 ) log ( 2r0 ε ) . (7)
Algorithm 2 Proximal SGD Require: Stepsizes γk > 0, initial vector x0 ∈ Rd, number of steps K 1: for steps k = 0, 1, . . . ,K − 1 do 2: Sample ik uniformly at random from [n] 3: xk+1 = proxγkψ(xk − γk∇fik (xk))
This result is standard [Needell et al., 2016, Gower et al., 2019], with the exception that we do not210 know any proof in the literature for the case when ψ is strongly convex. For completeness, we prove211 it in Appendix C, but since our proof is a minor modification of that in [Gower et al., 2019], we do212 not provide it here.213
By comparing KSGD (given by (7)) and KRR (given by (6)), we see that ProxRR has milder214 dependence on ε than Proximal SGD. In particular, ProxRR converges faster whenever the target215 accuracy ε is small enough to satisfy ε ≤ 1Lmaxnµ ( σ4∗
n‖∇f(x∗)‖2+σ2∗
) . Furthermore, ProxRR is much216
better when we consider proximal iteration complexity (# of proximal operator access), in which case217 the complexity of ProxRR (6) is reduced by a factor of n (because we take one proximal step every n218 iterations), while the proximal iteration complexity of Proximal SGD remains the same as (7). In this219 case, ProxRR is better whenever the accuracy ε satisfies220
ε ≥ nLmaxµ [ n‖∇f(x∗)‖2 + σ2∗ ] or ε ≤ nLmaxµ [ σ4∗
n‖∇f(x∗)‖2+σ2∗
] .
We can see that if the target accuracy is large enough or small enough, and if the cost of proximal221 operators dominates the computation, ProxRR is much quicker to converge than Proximal SGD.222

heading: 5 Theory for strongly convex regularizer ψ223
text: In Theorem 2, we assume that each fi is µ-strongly convex. This is motivated by the common practice224 of using `2 regularization in machine learning. However, applying `2 regularization in every step225 of Algorithm 1 can be expensive when the data are sparse and the iterates xit are dense, because it226 requires accessing each coordinate of xit which can be much more expensive than computing sparse227 gradients ∇fi(xit). Alternatively, we may instead choose to put the `2 regularization inside ψ and228 only ask that ψ be strongly convex—this way, we can save a lot of time as we need to access each229 coordinate of the dense iterates xit only once per epoch rather than every iteration. Theorem 3 gives a230 convergence guarantee in this setting.231 Theorem 3. Let Assumption 1 hold and f1, . . . , fn be convex. Further, assume that ψ is µ-strongly232 convex. If Algorithm 1 is run with constant stepsize γt = γ ≤ 1/Lmax, where Lmax = maxi Li, then233 its iterates satisfy234
E [ ‖xT − x∗‖2 ] ≤ (1 + 2γµn)−T ‖x0 − x∗‖2 + γ 2σ2rad µ .
Using Theorem 3 and choosing the stepsize as235 γ = min {
1 Lmax
, √ εµ
σrad
} , (8)
we get E [ ‖xT − x∗‖2 ] = O (ε) provided that the total number of iterations satisfies236
K ≥ ( κ+ σrad/µ√εµ + n ) log ( 2r0 ε ) . (9)
This can be converted to a bound similar to (6) by using Theorem 1, in which case the only difference237 between the two cases is an extra n log ( 1 ε ) term when only the regularizer ψ is µ-strongly convex.238 Since for small enough accuracies the 1/√ε term dominates, this difference is minimal.239
6 FedRR: application of ProxRR to federated learning240
Let us consider now the problem of minimizing the average of N = ∑M m=1Nm functions that are241 stored on M devices, which have N1, . . . , NM samples correspondingly,242 min x∈Rd F (x) +R(x), F (x) = 1N ∑M m=1Fm(x), Fm(x) = ∑Nm j=1fmj(x). (10)
Algorithm 3 Federated Random Reshuffling (FedRR) Require: Stepsize γ > 0, initial vector x0 = x00 ∈ Rd, number of epochs T 1: for epochs t = 0, 1, . . . , T − 1 do 2: for m = 1, . . . ,M locally in parallel do 3: x0t,m = xt 4: Sample permutation π0,m, π1,m, . . . , πNm−1,m of {1, 2, . . . , Nm} 5: for i = 0, 1, . . . , Nm − 1 do 6: xi+1t,m = x i t,m − γ∇fπi,m(xit,m)
7: xnt,m = x Nm t,m 8: xt+1 = 1M ∑M m=1 x n t,m
For example, fmj(x) can be the loss associated with a single sample (Xmj , ymj), where pairs243 (Xmj , ymj) follow a distribution Dm that is specific to device m. An important instance of such for-244 mulation is federated learning, where M devices train a shared model by communicating periodically245 with a server. We normalize the objective in (10) by N as this is the total number of functions after246 we expand each Fm into a sum. We denote the solution of (10) by x∗.247
Extending the space. To rewrite the problem as an instance of (1), we are going to consider a bigger248 product space, which is sometimes used in distributed optimization [Bianchi et al., 2015]. Let us249 define n := max{N1, . . . , Nm} and introduce ψC , the consensus constraint, defined via250
ψC(x1, . . . , xM ) := { 0, x1 = · · · = xM +∞, otherwise .
By introducing dummy variables x1, . . . , xM and adding the constraint x1 = · · · = xM , we arrive at251 the intermediate problem252
min x1,...,xM∈Rp
1 N ∑M m=1 Fm(xm) + (R+ ψC)(x1, . . . , xM ),
where R + ψC is defined, with a slight abuse of notation, as (R + ψC)(x1, . . . , xM ) = R(x1) if253 x1 = · · · = xM , and (R+ ψC)(x1, . . . , xM ) = +∞ otherwise.254 Since we have replaced R with a more complicated regularizer R+ ψC , we need to understand how255 to compute the proximal operator of the latter. We show (Lemma 7 in the supplementary) that the256 proximal operator of (R + ψC) is merely the projection onto {(x1, . . . , xM ) | x1 = · · · = xM}257 followed by the proximal operator of R with a smaller stepsize.258
Reformulation. To have n functions in every Fm, we write Fm as a sum with extra n−Nm zero259 functions, fmj(x) ≡ 0 for any j > Nm, so that Fm(xm) = ∑n j=1 fmj(xm) = ∑Nm j=1 fmj(xm) +260 ∑n j=Nm+1 0. We can now stick the vectors together into x = (x1, . . . , xM ) ∈ RM ·d and multiply261 the objective by Nn , which gives the following reformulation:262 min
x∈RM·d 1 n
∑n i=1fi(x) + ψ(x), (11)
where ψ(x) := Nn (R+ ψC) and263 fi(x) = fi(x1, . . . , xM ) := M∑ m=1 fmi(xm). In other words, function fi(x) includes i-th data sample from each device and contains at most264 one loss from every device, while Fm(x) combines all data losses on device m. Note that the265 solution of (11) is x∗ := (x>∗ , . . . , x > ∗ ) > and the gradient of the extended function fi(x) is given266 by ∇fi(x) = (∇f1i(x1)>, · · · ,∇fMi(xM )>)>. Therefore, a stochastic gradient step that uses267 ∇fi(x) corresponds to updating all local models with the gradient of i-th data sample, without any268 communication.269
Algorithm 1 for this specific problem can be written in terms of x1, . . . , xM , which results in270 Algorithm 3. Note that since fmi(xi) depends only on xi, computing its gradient does not require271 communication. Only once the local epochs are finished, the vectors are averaged as the result of272 projecting onto the set {(x1, . . . , xM ) | x1 = · · · = xM}.273 Reformulation properties. To analyze FedRR, the only thing that we need to do is understand the274 properties of the reformulation (11) and then apply Theorem 2 or Theorem 3. The following lemma275 gives us the smoothness and strong convexity properties of (11).276
Lemma 1. Let function fmi be Li-smooth and µ-strongly convex for every m. Then, fi from277 reformulation (11) is Li-smooth and µ-strongly convex.278
The previous lemma shows that the conditioning of the reformulation is κ = Lmaxµ just as we279 would expect. Moreover, it implies that the requirement on the stepsize remains exactly the same:280 γ ≤ 1/Lmax. What remains unknown is the value of σ2rad, which plays a key role in the convergence281 bounds for ProxRR and ProxSO. To find an upper bound on σ2rad, let us define282
σ2m,∗ := 1 Nm ∑n j=1 ∥∥∇fmj(x∗)− 1Nm∇Fm(x∗)∥∥2, which is the variance of local gradients on device m. This quantity characterizes the convergence rate283 of local SGD [Yuan et al., 2020], so we should expect it to appear in our bounds too. The next lemma284 explains how to use it to upper bound σ2rad.285 Lemma 2. The shuffling radius σ2rad of the reformulation (11) is upper bounded by286
σ2rad ≤ Lmax · M∑ m=1 ( ‖∇Fm(x∗)‖2 + n 4 σ2m,∗ ) .
The lemma shows that the upper bound on σ2rad depends on the sum of local variances ∑M m=1 σ 2 m,∗ as287
well as on the local gradient norms ∑M m=1 ‖∇Fm(x∗)‖2. Both of these sums appear in the existing288 literature on convergence of Local GD/SGD [Khaled et al., 2019, Woodworth et al., 2020, Yuan et al.,289 2020]. We are now ready to present formal convergence results. For simplicity, we will consider290 heterogeneous and homogeneous cases separately and assume that N1 = · · · = NM = n. To further291 illustrate generality of our results, we will present the heterogeneous assuming strong convexity R292 and the homogeneous under strong convexity of functions fmi.293
Heterogeneous data. In the case when the data are heterogeneous, we provide the first local RR294 method. We can apply either Theorem 2 or Theorem 3, but for brevity, we give only the corollary295 obtained from Theorem 3.296 Theorem 4. Assume that functions fmi are convex and Li-smooth for each m and i. If R is297 µ-strongly convex and γ ≤ 1/Lmax, then we have for the iterates produced by Algorithm 3298
E [ ‖xT − x∗‖2 ] ≤ (1 + 2γµn)−T ‖x0 − x∗‖2 + γ 2Lmax Mµ ∑M m=1 ( ‖∇Fm(x∗)‖2 + N4M σ 2 m,∗ ) .
For nonconvex analysis, we consider R ≡ 0 and require the following standard assumption.299 Assumption 2 (Bounded variance and dissimilarity). There exist constants σ, ζ > 0 such that for300 any x ∈ Rd and301
1 n ∑n i=1 ∥∥∇fmi − 1n∇Fm(x)∥∥2 ≤ σ2 and 1M ∑Mm=1 ∥∥ 1n∇Fm(x)−∇F (x)∥∥2 ≤ ζ2. Note that above 1n∇Fm(x) = 1 Nm ∇Fm(x) is the gradient of a local dataset and ∇F (x) =302
1 N ∑M l=1∇Fl(x) is the full gradient on all data.303 Theorem 5 (Nonconvex convergence). Let Assumptions 1 and 2 be satisfied, and R ≡ 0 (no prox).304 Then, the communication complexity to achieve E [ ‖∇F (xT )‖2 ] ≤ ε2 is305
T = O ((
1 ε2 + σ√ nε3 + ζε3 ) (F (x0)− F∗) ) .
Notice that by replicating the data locally on each device and thereby increasing the value of n306 without changing the objective, we can improve the second term in the communication complexity.307 In particular, if the data are not too dissimilar (σ ζ) and ε is small ( 1ε3 1 ε2 ), the second term in308 the complexity dominates, and it helps to have more local steps. However, if the data are less similar,309 the nodes have to communicate more frequently to get more information about other objectives.310
Homogeneous data. For simplicity, in the homogeneous (i.e., i.i.d.) data case we provide guarantees311 without the proximal operator. Since then we have F1(x) = · · · = FM (x), for any m it holds312 ∇Fm(x∗) = 0, and thus σ2m,∗ = 1n ∑n j=1 ‖∇fmj(x∗)‖2. The full variance is then given by313 ∑M
m=1 σ 2 m,∗ = 1 n ∑M m=1 ∑n i=1 ‖∇fmi(x∗)‖2 = N n σ 2 ∗ = Mσ 2 ∗,
where σ2∗ := 1 N ∑n i=1 ∑M m=1 ‖∇fmi(x∗)‖2 is the variance of the gradients over all data.314
Theorem 6. Let R(x) ≡ 0 (no prox) and the data be i.i.d., that is ∇Fm(x∗) = 0 for any m, where315 x∗ is the solution of (10). Let σ2∗ := 1 N ∑n i=1 ∑M m=1 ‖∇fmi(x∗)‖2. If each fmj is Lmax-smooth316 and µ-strongly convex, then the iterates of Algorithm 3 satisfy317
E [ ‖xT − x∗‖2 ] ≤ (1− γµ)nT ‖x0 − x∗‖2 + γ 2LmaxNσ 2 ∗
Mµ .
The most important part of this result is that the last term in Theorem 6 has a factor of M in the318 denominator, meaning that the convergence bound improves with the number of devices involved.319
7 Experiments1320
ProxRR vs SGD. In Figure 1, we look at the logistic regression loss with the elastic net regularization,321 322
1 N ∑N i=1 fi(x) + λ1‖x‖1 + λ2 2 ‖x‖
2, (12) where each fi : Rd → R is defined as fi(x) := − ( bi log ( h(a>i x) ) + (1 − bi) log ( 1 − h(a>i x) )) ,323 and where (ai, bi) ∈ Rd × {0, 1}, i = 1, . . . , N are the data samples, h : t → 1/(1 + e−t) is the324 sigmoid function, and λ1, λ2 ≥ 0 are parameters. We set minibatch sizes to 32 for all methods and325 use theoretical stepsizes, without any tuning. We denote the heuristic version of RR that performs326 proximal operator step after each iteration as ‘RR (iteration prox)’. From the experiments, we can see327 that all methods behave more or less the same way. However, the algorithm that we propose needs328 only a small fraction of proximal operator evaluations, which gives it a huge advantage whenever the329 operator takes more time to compute than stochastic gradients.330
FedRR vs Local SGD and Scaffold. We also compare the performance of FedRR, Local SGD and331 Scaffold Karimireddy et al. [2020] on homogeneous (i.e., i.i.d.) and heterogeneous data. Since Local332 SGD and Scaffold require smaller stepsizes to converge, they are significantly slower in the i.i.d.333 regime, as can be seen in Figure 2. FedRR, however, does not need small initial stepsize and very334 quickly converges to a noisy neighborhood of the solution. We obtain heterogeneous regime by335 sorting data with respect to the labels and mixing the sorted dataset with the unsorted one. In this336 scenario, we also use the same small stepsize for every method to address the data heterogeneity.337 Clearly, Scaffold is the best in terms of functional values because it does variance reduction with338 respect to the data. Extending FedRR in the same way might be useful too, but this goes beyond the339 scope of our paper and we leave it for future work. We also note that in terms of distances from the340 optimum, FedRR still performs much better than Local SGD and Scaffold.341
1Our code is provided in the supplementary. More experimental details are in the appendix.
References342 Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component343 convexity and large epoch requirements. arXiv preprint arXiv:2006.06946. Neural Information344 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,346 Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997. (Cited on page 5)347
Pascal Bianchi, Walid Hachem, and Franck Iutzeler. A coordinate descent primal-dual algorithm and348 application to distributed asynchronous optimization. IEEE Transactions on Automatic Control, 61349 (10):2947–2957, 2015. (Cited on page 7)350
Antoine Bordes, Léon Bottou, and Patrick Gallinari. SGD-QN: Careful quasi-Newton stochastic351 gradient descent. 2009. (Cited on page 2)352
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. Unpublished353 open problem offered to the attendance of the SLDS 2009 conference, 2009. URL http://leon.354 bottou.org/papers/bottou-slds-open-problem-2009. (Cited on page 2)355
Léon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade, pages356 421–436. Springer, 2012. (Cited on page 2)357
Kristian Bredies, Karl Kunisch, and Thomas Pock. Total generalized variation. SIAM Journal on358 Imaging Sciences, 3(3):492–526, 2010. (Cited on page 2)359
Gong Chen and Marc Teboulle. Convergence Analysis of a Proximal-Like Minimization Algorithm360 Using Bregman Functions. SIAM Journal on Optimization, 3(3):538–543, 1993. doi: 10.1137/361 0803026. (Cited on page 19)362
John Duchi and Yoram Singer. Efficient online and batch learning using forward backward splitting.363 Journal of Machine Learning Research, 10(Dec):2899–2934, 2009. (Cited on page 3)364
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A Unified Theory of SGD: Variance Reduction,365 Sampling, Quantization and Coordinate Descent. volume 108 of Proceedings of Machine Learning366 Research, pages 680–690, Online, 26–28 Aug 2020. PMLR. (Cited on pages 2, 3, 18, and 34)367
Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik.368 SGD: General Analysis and Improved Rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov,369 editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of370 Proceedings of Machine Learning Research, pages 5200–5209, Long Beach, California, USA,371 09–15 Jun 2019. PMLR. (Cited on page 6)372
Robert M. Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: variance373 reduction via Jacobian sketching. Mathematical Programming, pages 1–58, 2020. ISSN 0025-5610.374 doi: 10.1007/s10107-020-01506-0. (Cited on page 34)375
Mert Gürbüzbalaban, Asuman Özdağlar, and Pablo A. Parrilo. Why random reshuffling beats376 stochastic gradient descent. Mathematical Programming, Oct 2019. ISSN 1436-4646. doi:377 10.1007/s10107-019-01440-w. (Cited on page 2)378
Jeff Haochen and Suvrit Sra. Random Shuffling Beats SGD after Finite Epochs. In Kamalika379 Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on380 Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2624–2633,381 Long Beach, California, USA, 09–15 Jun 2019. PMLR. (Cited on page 2)382
Peter Kairouz et al. Advances and open problems in federated learning. arXiv preprint383 arXiv:1912.04977, 2019. (Cited on pages 1 and 4)384
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear Convergence of Gradient and Proximal-385 Gradient Methods Under the Polyak-Łojasiewicz Condition. In European Conference on Machine386 Learning and Knowledge Discovery in Databases - Volume 9851, ECML PKDD 2016, page387 795–811, Berlin, Heidelberg, 2016. Springer-Verlag. (Cited on page 5)388
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U. Stich, and389 Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In390 International Conference on Machine Learning, pages 5132–5143. PMLR, 2020. (Cited on pages 9391 and 30)392
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv Preprint393 arXiv:2002.03329, 2020. (Cited on pages 4 and 31)394
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First Analysis of Local GD on395 Heterogeneous Data. arXiv preprint arXiv:1909.04715, 2019. (Cited on page 8)396
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for Local SGD on397 identical and heterogeneous data. In International Conference on Artificial Intelligence and398 Statistics, pages 4519–4529. PMLR, 2020. (Cited on page 29)399
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave400 Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private401 Multi-Party Machine Learning Workshop, 2016. (Cited on pages 1 and 4)402
Daniel D. Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix403 factorization. Nature, 401(6755):788–791, 1999. (Cited on page 2)404
Stanislaw Lojasiewicz. A topological property of real analytic subsets. Coll. du CNRS, Les équations405 aux dérivées partielles, 117:87–89, 1963. (Cited on page 2)406
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.407 Communication-efficient learning of deep networks from decentralized data. In Proceedings of the408 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. (Cited on409 pages 1 and 4)410
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random Reshuffling: Simple Analysis411 with Vast Improvements. arXiv preprint arXiv:2006.05988. Neural Information Processing Systems412 (NeurIPS) 2020, 2020. (Cited on pages 2, 3, 4, 5, 16, 19, 20, 25, and 26)413
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without Replacement: Sharper Rates414 for General Smooth Convex Functions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,415 Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings416 of Machine Learning Research, pages 4703–4711, Long Beach, California, USA, 09–15 Jun 2019.417 PMLR. (Cited on page 2)418
Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling,419 and the randomized Kaczmarz algorithm. Mathematical Programming, 155(1):549–573, Jan 2016.420 ISSN 1436-4646. doi: 10.1007/s10107-015-0864-7. (Cited on pages 6 and 34)421
Neal Parikh and Stephen Boyd. Proximal Algorithms. Foundations and Trends in Optimization, 1(3):422 127–239, January 2014. ISSN 2167-3888. doi: 10.1561/2400000003. (Cited on pages 16 and 30)423
Andrei Patrascu and Paul Irofti. Stochastic proximal splitting algorithm for composite minimization.424 Optimization Letters, pages 1–19, 2021. (Cited on page 5)425
Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoc Tran-Dinh. ProxSARAH: An efficient426 algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine427 Learning Research, 21(110):1–48, 2020. (Cited on page 2)428
Boris T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel’noi Matematiki i429 Matematicheskoi Fiziki, 3(4):643–653, 1963. (Cited on page 2)430
Benjamin Recht and Christopher Ré. Toward a noncommutative arithmetic-geometric mean in-431 equality: Conjectures, case-studies, and consequences. In S. Mannor, N. Srebro, and R. C.432 Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23,433 page 11.1–11.24, 2012. Edinburgh, Scotland. (Cited on page 2)434
Leonid I. Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal435 algorithms. Physica D: nonlinear phenomena, 60(1-4):259–268, 1992. (Cited on page 2)436
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: from theory to algo-437 rithms. Cambridge University Press, 2014. (Cited on page 1)438
Ohad Shamir. Without-replacement sampling for stochastic gradient methods. In Advances in neural439 information processing systems, pages 46–54, 2016. (Cited on page 2)440
Fanhua Shang, Licheng Jiao, Kaiwen Zhou, James Cheng, Yan Ren, and Yufei Jin. ASVRG:441 Accelerated Proximal SVRG. In Jun Zhu and Ichiro Takeuchi, editors, Proceedings of Machine442 Learning Research, volume 95, pages 815–830. PMLR, 14–16 Nov 2018. (Cited on page 2)443
Sebastian U. Stich. Unified Optimal Analysis of the (Stochastic) Gradient Method. arXiv preprint444 arXiv:1907.04232, 2019. (Cited on pages 4 and 31)445
Ruo-Yu Sun. Optimization for Deep Learning: An Overview. Journal of the Operations Research446 Society of China, 8(2):249–294, Jun 2020. ISSN 2194-6698. doi: 10.1007/s40305-020-00309-6.447 (Cited on page 31)448
Junqi Tang, Karen Egiazarian, Mohammad Golbabaee, and Mike Davies. The practicality of stochastic449 optimization in imaging inverse problems. IEEE Transactions on Computational Imaging, 6:1471–450 1485, 2020. (Cited on page 34)451
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical452 Society: Series B (Methodological), 58(1):267–288, 1996. (Cited on page 2)453
Trang H. Tran, Lam M. Nguyen, and Quoc Tran-Dinh. Shuffling gradient-based methods with454 momentum. arXiv preprint arXiv:2011.11884, 2020. (Cited on pages 4 and 31)455
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs Local SGD for Hetero-456 geneous Distributed Learning. arXiv preprint arXiv:2006.04735. Neural Information Processing457 Systems (NeurIPS) 2020, 2020. (Cited on pages 4, 8, and 24)458
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. arXiv preprint459 arXiv:2011.08474, 2020. (Cited on page 8)460
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal461 of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67, 2006. (Cited on462 page 2)463
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss464 minimization. In Proceedings of the 32nd International Conference on Machine Learning, PMLR,465 volume 37, pages 1–9, 2015. (Cited on page 4)466
Checklist467
1. For all authors...468 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s469 contributions and scope? [Yes]470 (b) Did you describe the limitations of your work? [Yes]471 (c) Did you discuss any potential negative societal impacts of your work? [N/A]472 (d) Have you read the ethics review guidelines and ensured that your paper conforms to473 them? [Yes]474 2. If you are including theoretical results...475
(a) Did you state the full set of assumptions of all theoretical results? [Yes]476 (b) Did you include complete proofs of all theoretical results? [Yes]477
3. If you ran experiments...478 (a) Did you include the code, data, and instructions needed to reproduce the main experi-479 mental results (either in the supplemental material or as a URL)? [Yes]480 (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they481 were chosen)? [Yes]482 (c) Did you report error bars (e.g., with respect to the random seed after running experi-483 ments multiple times)? [Yes]484 (d) Did you include the total amount of compute and the type of resources used (e.g., type485 of GPUs, internal cluster, or cloud provider)? [Yes]486 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...487
(a) If your work uses existing assets, did you cite the creators? [Yes]488 (b) Did you mention the license of the assets? [N/A]489 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]490
491
(d) Did you discuss whether and how consent was obtained from people whose data you’re492 using/curating? [N/A]493
(e) Did you discuss whether the data you are using/curating contains personally identifiable494 information or offensive content? [N/A]495
5. If you used crowdsourcing or conducted research with human subjects...496 (a) Did you include the full text of instructions given to participants and screenshots, if497 applicable? [N/A]498 (b) Did you describe any potential participant risks, with links to Institutional Review499 Board (IRB) approvals, if applicable? [N/A]500 (c) Did you include the estimated hourly wage paid to participants and the total amount501 spent on participant compensation? [N/A]502

Review summaries:
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. 

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.

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. 

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.