Breaking the centralized barrier for cross-device federated learning
Authors: Sai Praneeth Karimireddy
Martin Jaggi
Satyen Kale
Mehryar Mohri
Sashank J. Reddi
Sebastian U Stich
Ananda Theertha Suresh
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Non-convex Optimization
Distributed Optimization
Communication Complexity

Abstract: Federated learning (FL) is a challenging setting for optimization due to the heterogeneity of the data across different clients which gives rise to the client drift phenomenon. In fact, obtaining an algorithm for FL which is uniformly better than simple centralized training has been a major open problem thus far. In this work, we propose a general algorithmic framework, Mime, which i) mitigates client drift and ii) adapts arbitrary centralized optimization algorithms such as momentum and Adam to the cross-device federated learning setting. Mime uses a combination of control-variates and server-level statistics (e.g. momentum) at every client-update step to ensure that each local update mimics that of the centralized method run on iid data. We prove a reduction result showing that Mime can translate the convergence of a generic algorithm in the centralized setting into convergence in the federated setting. Further, we show that when combined with momentum based variance reduction, Mime is provably faster than any centralized method--the first such result. We also perform a thorough experimental exploration of Mime's performance on real world datasets.

Breaking the centralized barrier for cross-device federated learning"
Sai Praneeth Karimireddy
Martin Jaggi EPFL pertin.jaggeeer
Satyen Kale
EPFL
Google Research
sai. www.kaiimieddyyppll.ccoo ch
satyenkale@google.com
Mehryar Mohri Google Research
Sashank J. Reddi Google Research
Sebastian U. Stich
EPFL
mohri8google.com com
sashank@google. com
sebastian..ttichepll..c
Ananda Theertha Suresh
Google Research theertha@google.comm
Abstract
Federated learning (FL) is a challenging setting for optimization due the het- erogeneity of the data across different clients which can cause client drift phe- nomenon. In fact, designing an algorithm for FL that uniformly better than simple centralized training has been a major open problem thus far. In this work, we propose a general algorithmic framework, MIME, which mitigates client drift and ii) adapts arbitrary centralized optimization algorithm such as mo- mentum and Adam the cross-device federated learning setting. MIME uses a combination of control-variates and server-level optimizer state (e.g. momentum) at every client-update step to ensure that each local update mimics that the cen- tralized method run i.idd. data. We prove reduction result showing that MIME can translate the convergence of generic algorithm in the centralized setting into convergence in the federated setting. Moreover, show that, when combined with momentum- based variance reduction, MIME provably faster than any cen- tralized method-the the first such result. We also perform thorough experimental exploration of MIME'S performance on real world datasets (implemented here).
1 Introduction
Federated learning (FL) is an increasingly important large-scale learning framework where the train- ing data remains distributed over large number of clients, which may be mobile phones or network sensors [38, 37, 43, 44, 28]. server then orchestrates the clients train single model, here re- ferred to server model, without ever transmitting client data over the network, thereby providing some basic levels of data privacy and security.
Two important settings are distinguished in FL [28, Table 1]: the cross-device and the cross-silo settings. The cross-silo setting corresponds to relatively small number of reliable clients, typically organizations, such as medical or financial institutions. In contrast, in the cross-device federated learning setting, the number of clients may be extremely large and include, for example, all 3.5 bil- lion active android phones [25]. Thus, in that setting, we may never make even a single pass over
"This work was also appears under the alternative title "Mime: Mimicking Centralized Stochastic Algo- rithms Federated Learnin" [31].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the entire clients' data during training. The cross pross-device setting is further characterized by resource- poor clients communicating over a highly unreliable network. Together, the essential features of this setting give rise to unique challenges not present in the cross-silo setting. In this work, we are inter- ested in the more challenging cross-device setting, for which we will formalize and study stochastic optimization algorithms. Importantly, recent advances in FL. optimization, such as SCAFFOLD [32] or FedDyn [1], are not anymore applicable since they are designed for the cross-silo setting.
The problem. The de facto standard algorithm for the cross-device setting is FEDAVG [43], which performs multiple SGD updates on the available clients before communicating to the server. While this approach can reduce the frequency of communication required, performing multiple steps on the same client can lead to 'over-fitting' to its atypical local data, phenomenon known client drift [32]. This in turn leads to slower convergence and can, somewhat counter-intuitively, require larger total communication [69]. Despite significant attention received from the optimization community, the communication complexity of heterogeneous cross-device has not improved upon that of simple centralized methods, which take no local steps (aka SERVER-ONLA methods). Furthermore, algo- rithmic innovations such as momentum [59, 14], adaptivity [35, 77], and clipping [71, 72, 76] are critical the success of deep learning applications. The lack of theoretical understanding of the impact of multiple client steps has also hindered adapting these techniques in a principled manner into the client updates, in order replace the vanilla SGD update of FEDAVG.
To overcome such deficiencies, we propose a new framework, MIMF, that mitigates client drift and can adapt arbitrary centralized optimization algorithm, e.g. SGD with momentum or Adam, to the federated setting. In each local client update, MIME uses global optimizer state, e.g. momentum or adaptive learning rates, and an SVRG-style correction to mimic the updates of the centralized algorithm run on i.idd. data. This optimizer state is computed only at the server level and kept fixed throughout the local steps, thereby avoiding overfitting the atypical local data of any single client.
Contributions.
We summarize our main results below.
MIME framework. We formalize the cross-device federated learning problem, and propose new framework MIME that can adapt arbitrary centralized algorithms to this setting.
Convergence result. We prove a result showing that MIME successfully reduces client drift. We also prove that the convergence of any generic algorithm in the centralized setting translates convergence of its MIME version in the federated setting.
Speed-up over centralized methods. By carefully tracking the bias introduced due to multiple local steps, we prove that MIME with momentum-basee based variance reduction (MVR) can beat lower bound for centralized methods, thus breaking a fundamental barrier. This is the first such result in FL, and also the first general result showing asymptotic speed-up due to local steps. Empirical validation. We propose a simpler variant, MIMELITE, with an empirical perfor- mance similar to MIME. We report the results of thorough experimental analysis demonstrating that both MIME and MIMELITE indeed converge faster than FEDAVG.
Related work. Analysis of FEDAVG: Much of the recent work in federated learning has focused
on analyzing FEDAVG. For identical clients, FEDAVG coincides with parallel SGD, for which [78]
derived an analysis with asymptotic convergence. Sharper and more refined analyses of the same
method, sometimes called local SGD, were provided by [56]. and more recently by [57], [47], [34], and [70], for identical functions. Their analysis was extended to heterogeneous clients in 168, 74, 32, 34, 36). [11] derived a tight characterization of FedAvg with quadratic functions and demonstrated the sensitivity of the algorithm to both client and server step sizes. Matching upper and lower bounds were recently given by [32] and [69] for general functions, proving that FEDAvG can be slower than even SGD for heterogeneous data, due to the client-drift.
Comparison SCAFFOLD: For the cross-silo setting where the number of clients is relatively low, proposed the SCAFFOLD algorithm, which uses control-variates (similar to SVRG) to correct for client drift. However, their algorithm crucially relies on stateful clients which repeatedly participate in the training process. FedDyn [1] reduces the communication requirements, but also requires persistent stateful clients. In contrast, we focus on the cross-device setting where clients may be visited only once during training and where they are stateless (and thus SCAFFOLDD and FedDyn are inapplicable). This akin to the difference between the finite-sum (corresponding to cross-silo) and stochastic (cross- device) settings in traditional centralized optimization [39].

---

Comparison to FedAvg and variants: [26] and [67] observed that using server momentim signifi- cantly improves over vanilla FEDAVG. This idea was generalized by [49], who replaced the server update with an arbitrary optimizer, e.g. Adam. However, these methods only modify the server up- date while using SGD for the client updates. We henceforth refer to this meta algorithu as FedAvg- FedAvgSGD, Mom, FedAvgAdam denote specific instantiations of the server optimizer in FedAvg with SGD, Momentum or Adam. MIME, on the other hand, ensures that every local client update resembles the optimizer c.g. MIME would apply momentum in every client update and not just at the server level. Beyond this, [40] proposed to add a regularizer to ensure client updates remain close. However, this may slow down convergence (cf. Fig. 5 and [32, 66]). Other orthogonal directions which can be combined with MIME include tackling computation heterogeneity, where some clients perform many more updates than others [66]. improving fairness by modifying the objective [44, 41J, incorporating differential privacy [20, 2, 61 Byzantine adversaries [48, 65, 30), secure aggregation [8, 24), etc. We defer additional discussion to the extensive survey by [28].
Momentum based variance reduction. Initial optimal methods for stochastic non-convex optimiza- tion like SPIDER [17] and SARAH [46] required intermittently computing very large batch gra- dients. Subsequently, it was shown that momentum based variance reduction (MVR) methods ob- tained a similar optimal rate without needing such large batch gradient computations [62, 14]. Mo- mentum is an exponential moving average of many stochastic gradients and so it has much smaller variance than the stochastic gradients themselves. However, because these gradients are computed at different parameters it also has a bias. MVR adds a small additional correction term which sig- nificantly reduces this bias and provides improved rates.
2 Problem setup
This section formalizes the problem of cross-device federated learning [28]. Cross-device FI. characterized by a large number of client devices like mobile phones which may potentially connect to the server at most once. Due to their transient nature, it is not possible to store any state on the clients, precluding
algorithm like SCAFFOLD. Furthermore, each client has only a few samples, and there is wide heterogeneity in the samples across clients. Finally, communication is a major bottleneck and a key metric for optimization in this setting is the number of communication rounds.
Thus, our objective will be minimize the following quantity within the fewest number of client- server communication rounds:
f(x) (f(x)=
1 nh Σ ((ax;G.)))
Here, fi denotes the loss function of client i and (Gi, } its local data. Since the number of clients is extremely large, while the size of each local data rather modest, we represent the former expectation and the latter subset of clients (of size S) and performs some updates to the server model. Due to the transient and heterogeneous nature of the clients, it is easy to see that the problem becomes intractable with arbitrarily dissimilar clients. Thus, it is necessary to assume bounded dissimilarity across clients.
finite sum. In each round, the algorithm samples
(A1) G2BGVV or bounded inter-client gradient variance: there exists G 2 0 such that
E fV-cll/((())) V f(()) G2, Vo.
Next, we also characterize the variance in the Hessians.
(A2) 5-BHV or bounded Hessian variance: Almost surely, the loss function of any client i satisfies
f - [x)] < 6, Væ
This is in contrast to the usual smoothness assumption that can be stated as:
(A2*) L-smooth: ||V O) < L, Væc a.s. for any i.
Note that if (a () is L-smooth then (A2) is satisfied with d < 2T, and hence (A2) is weaker than (A2*). realistic examples we expect the clients to be similar and hence that < L. In addition, assume that f(x) is bounded from below by f and is L-smooth, as is standard.
3

---

3 Mime framework
In this section we describe how to adapt an arbitrary centralized optimizer (referred as the "base" optimizer) which may have internal state (c.g. momentum) to the federated learning problem (I) while ensuring there is no client-drift. Algorithm 4 describes our framework. We develop two variants, MIME and MIMELITE, which consist of three components i) a base optimizer we are seeking to mimic, ii) the global (server) optimizer state computation, and iii) the local client updates.
Base optimizer: We assume the centralized base optimizer we are im- itating can be decomposed into two steps: an update step U which up- dates the parameters æ, and a opti- mizer state update step V(-) which keeps track of global optimizer state 8. Each step of the base optimizer B = (U, V)) uses gradient to up- date the parameter x and the opti- mizer state follows:
Algorithm
Mime and MimeLite
input: initial and s, learning rate y7 and base optimizer B = (4, V)
for each round t = 1....... , do
sample subset S of clients
communicate (ar, 8) to all clients i S
communicate c
[ST Ejes (z) (only Mime)
client i E S in parallel do initialize local model 6- x for 1: 1, 1,... K do
x t x nl 8) (BASEOPT)
sample mini-batch Ç from local data
Vg.
g: fi
()( (Mime)
As an example, consider SGD with momentum. The state here is the mo- mentum m, and uses the following update steps:
+ (y:: () (MimeLite)
update y: y: s) end for compute full local-batch gradient (ar())) communicate (y:, (x)) end client
D, :t-1 - 7) (11 - Vi
fm--1),
( Eies Vf(()),
(update optimizer
m, = -1- -1-33\ + 3m--1-
state)
Thus, SGD with momentum can be represented in the above generic form with W(g. 8) = (1 B)g + A8 and Vgg
x 1 [3T Eies Vi (update server parameters)
end for
3)g + 3s. Table in Appendix shows how other algo- rithms like Adam, Adagrad, etc. can be represented this manner. We keep the update to be linear in the gradient g. whereas V can be more complicated. This implies that while the parame- ter update step is relatively resilient to receiving a biased gradient g while can be much more sensitive.
Compute optimizer state globally, apply locally. When updating the optimizer state of the base algorithm, we use only the gradient computed at the server parameters. Further, they remain fixed throughout the local updates of the clients. This ensures that these optimizer state remain unbiased and representative of the global function f(-). At the end of the round, the server performs
$ t ( Eies V.((z), 8),
f((x)) 1 E f(((x; (ix)
(OPTSTATE)
Note that we use full-batch gradients computed at the server parameters æ, not client parameters y:-
Local client updates. Each client E S performs K updates using U of the base algorithm and minibatch gradient. There are two variants possible corresponding MIME and MIMELITE differentiated using colored boxes. Starting from + x, repeat the following K times
yi y: (g.
(CLIENTSTEP)
where f- ()(: for MIMELITE, and
1 + v (z - vf((z()) + [S] ESES (z)
for MIME. MIMELITE simply uses the local minibatch gradient whereas MIME uses an SVRG

---

style correction [27]. This is done to reduce the noise from sampling local mini-bated While this correction yields faster rates in theory (and in practice for convex problems), deep learning applications we found that MIMELITE closely matches the performance of MIME.
Finally, there by the number of datapoints nu [43], and we perform K epochs instead of K steps [66].
modifications made in practical FL: weight all averages across the clients
Theoretical analysis of Mime
Table I summarizes the rates of MIME (highlighted in blue) and MIMELITE (highlighted in green) and compares them to SERVER- CORYER methods when using SGD, Adam and momentum methods as the base algorithms. We will first examine the convergence of MIME and MIMELITE with generic base optimizer and show that its properties are preserved in the federated setting. We then examine a specific momentum based base optimizer, and prove that Mime and MimeLite can be asymptotically faster than the best server-only method. This is the first result to prove the usefulness of local steps and demonstrate asymptotic speed-ups.
4.1 Convergence with generic base optimizer
We will prove a generic reduction result demonstrating that the underlying base algorithm con- verges, and is robust to slight perturbations, then MIME and MIMELITE also preserve the conver- gence of the algorithm when applied to the federated setting with additinoal local steps.
Theorem I. Suppose that we have G2 inter-client gradient variance (A1), L-smooth {fi] (A2*), and o² intra-client gradient variance (A3). Further, suppose that the updater U of our base- optimizer B = (u, satisfies i) linearity for a fixed state 8: U(gi + 92; 8) = (( (U 8). and Lipschitznes:: [[[(g; 8)]l B|[g|] for some B 2 O. Then, running MIME MIMELITE with K local updates and step-size 1) is equivalent to rumning centralized algorithm with step-size n == Kn S 2LB. and updates
2t xt-1 nl + e: e 8c-1), and
8t V(gr, 81-1), where we have
an unbiased gradient [g(g.]
( with variance bounded
G²
MIME
E, 11g
MIMELITE
8
KS
and finally a small error bounded as
E, 1g:1 12
MIME
2
E
E, 1. + d K
MIMELITE
Here, we have proven that MIME and MIMELITE truly mimic the centralized base algorithm with very small perturbations- the magnitude e; is O(i²). The key to the result is the linearity of the parameter update step u4( s). By separating the base optimizer into very simple parameter step ll and a more complicated optimizer state update step V. we can ensure that commonly used algorithms such momentum, Adam, Adagrad, and others all satisfy this property. Armed with this general reduction, we can easily obtain specific convergence results.
Corollary II ((Mime/Mimelan .ite) with SGD). Given that the conditions in Theorem are satisfied, let us run T rounds with local steps using SGD as the base optimizer and output w This output
satisfies El[V (w I|2 for F := f(xo) - f G = G² + o² K and
PL inequality: 17
Ō
and
gKT
LG
LF
log
MIME
T
uSe
# LE
LG
LE log(t) #
MIMELITE
pSe
Wee
Non-convex: for 11 O(v
FS
and
TGPTK=
O
LG2F
Set +
LF
MIME
=
0
LG LZGF
LF
MIMELITE
Set
2322
5

---

Table I: Number of communication rounds required to reach [V](2)]| < (log factors are ig- nored) with S clients sampled each round. All analyses except SCAFFOLD assume C² bounded gradient dissimilarity (A1). All analyses assume L-smooth losses, except MimeLiteMVE and MimeMVR, which only assume & bounded Hessian dissimilarity (A2). Convergence of SCAFFOLD depends on the total number of clients N which is potentially infinite. FEDAVG and MIMELITE are slightly slower than the server-only methods due to additional drift terms most cases. MIME is the fastest and either matches or improves upon the optimal statistical rates (first term in the rates). In fact, MimeMVR and MieeMLitMM beat lower bounds for any server-only method when < L.
Algorithm
Non-convex
/r- inequality
SCAFFOLD" [32]
N
+
5
5
SGD
SERVER-ONLY [21]
LG + 1
C +
L
S
uSe
1
MimeLiteSGD
FedAvgSGD
LG
+
L2G
C
+
LG
Se
3/2
USE
Nve
MimeSGD
LG
G +
I.
Se
J4
ADAM
SERVER- ONLY [75]
L
c-G1S
LV8
Adde
c-G2/8
AdmeA
c-G2/8
Momentum Variance Reduction (MVR)
SERVER-ONLY [14]
LG
G 4
VS2322
Se
6(G+o)
G²
MimeLiteMVR
+
3/2
6
MimeMVR
8G
G²
VS2/22
Sc
SERVER-ONLY lower bound [5]
Q
LG
+
G2
G2 Se
VS3/22
Se
Num. clients (N) can be same order as num. total rounds or even co, making the bounds vacuous.
Adam requires large batch-size S G2 /c to converge [50, 75]. Convergence of FedAdam with client sampling is unknown ([49] only analyze with full client participation).
Requires K a² /22 number of local updates. Typically, intra-client variance is small (o² x G2). d Requires K 2 I. number of local updates. Faster than the lower bound (and hence any SERVER- ONLY algorithm) when < i.e. our methods can take advantage of Hessian similarity, whereas SERVER-ONIE methods cannot. In worst case, 5 z I, and all methods are comparable.
If take sufficient number of local steps K G2/0² then have Ō O(G) in the above rates. On comparing with the rates in Table 1 for SERVER- ONLY SGD, we see that MIME exactly matches its rates. MIMELITE matches the asymptotic term but has few higher order terms. Note that when using SGD as the base optimizer, MIMELITE becomes exactly the same as FEDAVG and hence has the same rate of convergence.
Corollary III (MMime/MimeLite with Adam). Suppose that the conditions in Theorem I are satis- fied, and further [xf(()) < H for any coordinate j E [d]. Then let us run T rounds using Adam as the base optimizer with K local steps, B, Eo > 0, r7 e KILELL (H + and any 32 E [0, 1).
Output ou chosen randomly from (xt 1...... 2T) satisfies / (z) [| < for
LF(H+zu)2) (3(c-(215)
MIME Adam
=
LP(H-Ee) cglc-G0/8)
MIMELITE Adam
where F f(zo) fr, 82 = G² O
Note that here Eo represents a small positive parameter used in Adam for regularization, and different from the error Similar to the SERVER-ORE ONLY analysis of Adam [75], we assume 81

---

and that batch size is large enough such that S 2 G²/C. A similar analysis can also be carried out for AdaGrad, and other novel variants of Adam [42].
4.2 Circumventing server-only lower bounds
The rates obtained above, while providing a safety-check, do not beat those of the SERVER-ONE approach. The previous best rates for cross-device FL correspond MimeLiteSGD which is O OLCC + L [34, 36, 69]. While, using a separate server-leaming rate can remove the effect of the second term [33]. this at best matches the rate of SERVER- -ONLY SGD O LG
Sc. Ser This is
significantly slower than simply using momentum based variance reduction (MVR) as in in the FL. setting (SERVER-ONIA. MVR) which has communication complexity of O V5
LG [14]. Thus,
even though the main reason for studying local-step methods was to improve the communication complexity, none thus far show such improvement. The above difficulty of beating SERVER-ONLY may not be surprising given the two sets of strong lower bounds known.
Necessity of local steps. Firstly, [5] show gradient oracle lower bound of D( LG )- This /Sea/ matches the complexity of MVR, and hence at first glance it seems that SERVER- MVR optimal. However, the lower bound is really only on the number of gradients computed and not on the number of clients sampled (sample complexity) [18], or number of rounds of communication required. In particular, multiple local updates increases number of gradients computed without needing additional communication offers us a potential way to side-step such lower bounds. A careful analysis of the bias introduced result of such local steps is a key part of our analysis.
Necessity of 8-BHD.
second set of lower bounds directly study the number of communication rounds required in heterogeneous optimization [6, 69]. These results prove that there exist settings where local steps provide no advantage and SERVER-ONIYY methods are optimal. This however con- tradicts real world experimental evidence [43]. As before, the disparity arises due to the contrived settings considered by the lower bounds. For distributed optimization (with full client participation) and convex quadratic objectives, 8-BHD (A2) was shown to be sufficient [54, 51J and necessary [6] condition to circumvent these lower bounds and yield highly performant methods. We simi- larly leverage 5 5-BHD (A2) to design novel methods which significantly extend prior results to i) all smooth non-convex functions (not just quadratics), and ii) cross-device FL with client sampling.
We now state our convergence results with momentum based variance reduction (MVR) as the base- algorithm since it is known be optimal in the SERVER-ONIY setting.
Theorem IV. For L-smooth with G gradient dissimilarity (A1), 8 Hessian dissimilarity (A2) and == (f(x") -"',, let us run MVR as the base algorithm for T rounds with K 2 1./5 local
steps and generate an output oo This output satisfies Fl[V I (a I|2 < for
MimeMVR 1 O min( OK
SF
)/3))
mmomentum B = 1 O g//3 (TG3)378) ) and
(TTKS
8GF
G2 S.F
T=
VS22
Se
MimeLiteMVR O (0mmn|
1/3)
momentum B = - O (1799977)) ) and
GTTK
8GF
à 5F
T=
Here, we define G := G² and the expectation in ( sampling of the clients during the running of the algorithm, the sampling of the mini-batches in local updates, and the choice of x. (which is chosen randomly from the client iterates y:).
3/2
6
<
is taken both over the
Remarkably, the rates of our methods are independent of L and only depend on 8. Thus, when 5 < T. 8 < L/s for MimeMVR and Mimel LteMMRR the rates beat the server only lower bound of 2 V5ea/2 ). In fact, if the Hessian variance is small and 5 = O, our methods only need (1/c) rounds to communicate. Intuitively, our results show that local steps are very useful when heterogeneity (represented by 5) is smaller than optimization difficulty (captured by smoothness constant T.).
LG
MineMVR uses momentum parameter B of the order of (1 D(TG9)-2/3) i.e. T increases, 3 asymptotically approaches 1. In contrast, previous analyses of distributed momentum (e.g. [73]) G² prove rates of the form SU--322 which are worse than that of standard SGD by a factor of 1-3-
1
7

---

Momentum dethods
Impact momentum
Fixed local momemntum
accuracy
0.76
Mime
FedAva. F
FedAvg
Mime, 0=
Scaffold
FedAvg, $
Mime
FedProx
Mime, A-0
Loc-Mime
0.66
200
400
600
800
1000
200 400
600
800
1000
200
400
600
800
1000
Figure 1: Mime, MimeLite FedAvg, Scaffold, FedProx and Loe-Mime with SGD+mmmmnnumm using 10 local epochs, on EMNIST62 and a hidden layer (300u-100) MLP. (Left) Mime and Mimel are nearly identical and outperform the rest (7x faster). (Center) Mime makes better use of momentum than FedAvg, with a large increase in performance. (Right) Locally adapting momentum slows down convergence and makes it more unstable.
Thus, ours is also the first result which theoretically showcases the usefulness of using large mo- mentum in distributed and federated learning. While we only prove the utility of local steps for MimeMVR, we believe our theory can be extended other local update methods well.
Our analysis highly non-trivial and involves two crucial ingredients: i) computing the momentum at the server level to ensure that it remains unbiased and then applying it locally during every client update to reduce variance, and ii) carefully keeping track of the bias introduced via additional local steps. Our experiments (Sec. 5) verify our theoretical insights are indeed applicable in deep learning settings as well. See App. for a proof sketch and App. G-H detailed proofs.
5 Experimental analysis on real world datasets
We run experiments on natively federated datasets to confirm our theory and accurately measure real world performance. Our main findings are i) MIME and MIMELITE consistently outperform FEDAVG, and ii) momentum and adaptivity significantly improves performance.
5.1 Sctup
Algorithms. We consider three (meta) algorithms: FEDAVG, MIME, and MIMELITE. Each of these adapt four base optimizers: SGD, momentum, Adam, and Adagrad.
FEDAVG follows [49] who run multiple epochs of SGD on each client sampled, and then aggregate the net client updates. This aggregated update is used as a pseudo-gradient in the base optimizer (called server optimizer). The learning rate for the server optimizer is fixed to as in [67]. This is done to ensure all algorithms have the same number of syper-parameterd MIME and MIMELITE follow Algorithm 4 and also run a fixed number of epochs on the client. How- ever, note that this requires communicating both the full local-batchs gradient as well as the parameter updates doubling the communication required to be sent by the client. For fairer comparison, we split the sampled clients MIME and MIMELITE into two groups-the the first communicates only full local-batch gradient and the latter communicates only parameter updates. Thus, all methods have equal client communication to the server. This variant retains the convergence guarantees up to constants (details in the Appendix). We also run Loc-MIME where instead of keeping the global optimizer state fixed, we update locally within the client. The optimizer state is reset after the round finishes. In all methods, aggregation is weighted by the number of samples on the clients.
Datasets and models. We run five simulations on three worldworld federated datasets: EMNIST62 with i) a linear classifier, ii) an MLP, and iii) CNN, iv) a charRNN on Shakespeare, and v) an LSTM for next word prediction on StackOverflow, all accessed through Tensorflow Federated [60]. The learning rates were individually tuned and other optimizer hyper-parameters such as 3 for mo- mentum, B1. 32, En for Adam and AdaGrad were left to their default values, unless explicitly stated otherwise. We refer to Appendix C for additional setup details and discussion.
5.2 Ablation and comparative study
In order to study the different algorithms, we train 2 hidden layer (300μ-100) MLP on EMNIST62 with 10 local epuchs for 1k rounds and use SGD+momentum (with tuned 3) as the base optimizer.
Mime R MimeLite > FedAvg > SCAFFOLD FedProx. Fig. (left) shows MIME and
MIMELITE have nearly identical performance, and are about 7x faster than FedAvg. This implies
8

---

Table 2: Validation % accuracies after training for 1000 rounds. Best results for each dataset is underlined and the best within each base optimizer is bolded. The number of clients sampled per round has been reduced for MIME and MIMELITE ensure all methods have equal client and server communication. Final accuracies obtained by MIME and MIMELITE are competitive with FEDAVG, especially with adaptive base optimizers. FEDAVG seems unstable with Adam.
EMNIST logistic EMNIST CNN Shakespeare StackOverflow
SGD
FedAvgSGD
66.8
85.8
56.7
23.8
MimeLiteSGD
66.8
85,8
56.7
23,8
MimeSGD
67.4
85.3
56.1
12.5
MOMENTUM
Mom
67.4
85.7
55.4
22.2
MomeLLteMom
67.4
86.0
49.8
19.9
MimeMom
67,5
85.9
53.6
19.3
ADAM
FedAvgAdam
67.3
85.9
18.5
3.2
MimeLiteAdam
68.0
86.4
54.0
21.5
MimeAdam
68.0
86.6
54.1
22.8
ADAGRAD
FedAvgAdagraa
67.6
86.3
55.5
24.2
Mimel LiteLLieeAiie Adagrad
66.6
85.5
56.8
23.8
MimeAdagrad
67.4
86.3
57.1
14.7
our strategy of applying momentum to client updates is faster than simply using server momentum. (u 0 is the same FedAvg).
0.5, 0.5, Regularization does not seem to reduce client drift but still slows down convergence [66]. SCAF- FOLD [32] also slower than Mime and FedAvg this setup. This is because in cross-device setting with a large number of clients (N 3.4k) means that each client is visited less than 6 times during the entire training (20 clients per round for IK rounds). This means that the correction term utilized by SCAFFOLD uses control-variates which are quite stale (computed about 200 rounds ago) which slows down the convergence. In contrast, the SVRG correction term Mime computed using clients sampled in the current or previous rounds, and so is much more accurate.
FedProx [40] uses additional regularizer f tuned over 10.1,
With momentum > without momentum. Fig. (center) examines the impact of momentum FedAvg and Mime. Momentum slightly improves the performance of FedAvg, whereas has a significant impact on the performance of Mime. This is also in line with our theory and confirms that Mime's strategy of applying it locally at every client update makes better use of momentum.
Fixed > locally updated optimizer state. Finally, changes if instead of keeping the momentum fixed throughout a round, we it change. The latter is way combine global and local momentum. The momentum is reset at the end of the round ignoring the changes the clients make to it. Fig. (right) shows that this worsens the performance, confirming that it is better to keep the global optimizer state fixed as predicted by our theory.
check how the performance of Mime
Together, the above observations validate all aspects of Mime (and Mimelite) design: compute statistics at the server level, and apply them unchanged at every client update.
5.3
Large scale comparison with equal server and client communication
We perform a larger scale study closely matching the setup of [49]. For both MIME and MIMELITE, only half the clients compute and transmit the updated parameters, and other half transmit the full local-barch gradients. Hence, client to server communication cost is the same for all methods for all clients. However, MIME and MIMELITE require sending additional optimization state to the clients. Hence, we also reduce the number of clients sampled in each round to ensure sum total of communication at each round is 40x model size for EMNIST and Shakespeare experiments, and 100x model size for the StackOverflow next word prediction experiment.
Since we only perform 1 local epoch, the hyper-parameter (e.g. epsilon for adaptive methods) are more carefully chosen following [49], and MIME and MIMELITE use significantly fewer clients per round, the difference between FEDAVG and MIME is smaller here. Table 2 summarizes the results.
For image classification tasks of EMNIST62 logistic and EMNIST62 CNN, Mime and MimeLite with Adam achieve the best performance. Using momentum (both with SGD and in Adam) signif- icantly improves their performance. In contrast, FedAvgAdam more unstable with worse perfor- mance. This is because FedAvg is excessively sensitive to hyperparameters (cf. App. E).

---

We next consider the character prediction task on Shakespeare dataset, and next word prediction on StackOverflow. Here, the momentum based methods (SGD+momentum and Adam) are slower than their non-momentum counterparts (vanilla SGD and AdaGrad). This is because the mini- gradients in these tasks are sparse, with the gradients corresponding to tokens not in the mini-batch being zero. This sparsity structure is however destroyed when using momentum or Adam. For the same reason, Mime which uses an SVRG correction also significantly increases the gradient density.
Discussion. For traditional tasks such as image classification, we observe that Mime (especially with Adam) usually outperforms MimeLite which in turn outperforms FedAvg. These methods are able to successfully leverage momentum and adaptivity to improve performance. For tasks where the client gradients are sparse, the SVRG correction used by Mime hinders performance. Adapting our techniques to work with sparse gradients (à la Yogi [75]) could lead to further improvements. Also, note that reduce communication by naively reducing the number of participating clients per round. More sophisticated approaches to save on client communication including quantization or sparsification [58, 3,, or even novel algorithmic innovations [1] could be explored. Further, server communication could be reduced using memory efficient optimizers e.g. AdaFactor [55] or SM3 [4].
6 Conclusion
Our work initiated a formal study of the cross-device federated learning problem and provided the- oretically justified algorithms. We introduced new framework MIME which overcomes the natural diient-heterogeneity in such a setting, and can adapt arbitrary centralized algorithms such as Adam without additional hyper-parametent We demonstrated the superiority of MIME via strong conver- gence guarantees and empirical evaluations. Further, we proved that a particular instance of our method, MimeMVR, beat centralized lower-bounds, demonstrating that additional local steps can yield asymptotic improvements for the first time. We believe our analysis will be of independent interest beyond the federated setting for understanding the sample complexity of non-convex opti- mization, and for yielding improved analysis of decentralized optimization algorithms.
References
[1] Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N What- mough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021.
[2] Naman Agarwal, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Brendan McMa- han. cpSGD: Communication-efficcantt and hifferreniiall-privveae distributed SGD. In Proceed- ings of NeurlPS, pages 7575-7586, 2018
[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiennn sgd via gradient quantization and encoding. In Advances in Neu- ral Information Processing Systems (NeurIPS), 2017.
[4] Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory-efficient adaptive opti- mization. arXiv preprint arXiv: 1900..115500 2019.
[5] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rXi::1912.02366: 2019.
[6] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in neural information processing systems, pages 1756-1764, 2015.
[7] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, al. Towards federated learning at scale: System design. arXiv preprint 1rx.iv/902.01044 2019.
[8] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for wrivacy-preeerving machine learning. In Proceedings of the 20/7 ACM SIGSAC Conference on Computer and Communications Security, pages 1175-1191. ACM, 2017.
10

---

[9] Sebastian Caldas, Jakub Koneěny, H Brendan McMahan, and Ameet Talwalkar. Expand- ing the reach of federated learning by reducing client resource requirements. arXiv preprint arXiv: /8/2.072 10, 2018.
[10] Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný. H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: benchmark for federated settings. arXiv preprint arXiv: 1rX.v018/2.01097, 2018.
[11] Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint arXiv:2007.00878, 2020.
[12] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extend- ing mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN) pages 2921-2926. IEEE, 2017.
[13] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. arXiv preprint arXiv:2002.033055 2020.
[14] Ashok Cutkosky and Francesco Orabona. Momentum-base variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems, pages 15210-15219, 2019.
[15] Aaron Defazio and Léon Bottou, On the ineffectiveness of variance reduced optimization for deep learning. In Advances in Neural Information Processing Systems, pages 1753-1763, 2019.
[16] Stack Exchange. Stack exchange data dump. sta stackezchange, 2021.
https: // archive. org/ details/
[17] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, pages 689-699, 2018.
[18] Dylan J Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake Woodworth. The complexity making the gradient small stochastic convex optimization. In Conference on Learning Theory, pages 1319-1345. PMLR, 2019.
[19] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. International Conference on Learning Representations (ICLR), 2019.
[20] Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.075577 2017.
[21] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2344):234--2368, 2013.
[22] Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: Communication- efficient algorithms for federated learning. In 37th International Conference on Machine Learning (ICML), 2020.
[23] Andrew Hard, Kurt Partridge, Cameron Nguyen, Niranjan Subrahmanya, Aishanee Shah, Pai Zhu, Ignacio Lopez Moreno, and Rajiv Mathews. Training keyword spotting models on non-iid data with federated learning. arXiv preprint arXiv:2005. 10406, 2020.
[24] Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learn- ing. arXiv preprint arXiv:2006.044 047477 2020.
[25] Arne Holst. Smartphone users worldwide 2016-2021. Statista https: archive.
org/ 2021 httpp///p...00000003////aaaasp/p www. s statista. com/ statistics/3306555 numb cembber-of-smeee suunberrof--mmmtppoonee- www.s-worsddaeee
2019.
[26] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0633 2019.
[27] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive vari- ance reduction. In Advances in neural information processing systems, pages 315-323, 2013.
11

---

[28] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1IXiv:9912.04977, 2019.
[29] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the volyak-tojasiewier condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
[30] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In 38th International Conference on Machine Learning (ICML), 2021.
[31] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Se- bastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algo- rithms in federated learning. arXiv preprint arXiv:2008.0366 2020.
[32] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In 37th International Conference on Machine Learning (ICML), 2020.
[33] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feed- back fixes SignSGD and other gradient compression schemes. In 36th International Confer- ence on Machine Learming (ICML), 2019.
[34] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on indentical and heterogeneous data. In Proceedings of AISTATS, 2020.
[35] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.698, 2014.
[36] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized SGD with changing topology and local updates. In 37th International Conference on Machine Learning (ICML), 2020.
[37] Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Feder- ated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527 2016.
[38] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 110.05461 2016.
[39] Lihua Lei and Michael Jordan. Less than a single pass: Stochastically controlled stochastic gradient. In AISTATS, pages 148-156, 2017.
[40] Tian Li, Anit Kumar Sahu, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06127. 2018
[41] Tian Li, Maziar Sanjabi, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprini arXiv: 10497, 2019.
[42] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint 2019.
[43] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-eftiiieee learning of deep networks from decentralized data. In Proceedings of AISTATS, pages 1273-1282, 2017.
[44] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint arXiv: /902.00/9000 2019.
[45] Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
12

---

[46] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint 1rX1v:1705.07261 2017.
[47] Kumar Kshitij Patel and Aymeric Dieuleveut. Communication trade-offs for synchronized distributed SGD with large step size. In 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
[48] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning, arXiv preprint arXiv: 2019.
[49] Sashank Reddi, Zachary Charles. Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.0022 000955 2020.
[50] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations (ICIR), 2018.
[51] Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póezós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint 1rXiv:1608.068%0 2016.
[52] Jae Hun Ro, Ananda Theertha Suresh, and Ke Wu. FedJAX: Federated learning simulation with JAX, 2020.
[53] Jae Hun Ro, Ananda Theertha Suresh, and Ke Wu. Fedjax: Federated learning simulation with jax. arXiv preprint arXiv:2108.00 02117, 2021. 2021.
[54] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-eficiann distributed optimization using an approximate newton-type method. In International conference on machine learning, pages 1008-1008, 2014.
[55] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pages 4596-4604. PMLR, 2018.
[56] Sebastian U. Stich. Local SGD converges fast and communicates little. International Confer- ence on Learning Representations (ICLR), 2019.
[57] Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Bet- ter rates for SGD with delayed gradients and compressed communication. arXiv preprint 1rXiv:1909.05350. 2019.
[58] Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Con- ference on Machine Learning
Pornning-Volumme Volume 70, pages
JMLR. org, 2017.
[59] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of ini- tialization and momentum in deep learning. In International conference on machine learning, pages 1139-1147, 2013.
[60] TFF. Tensorflow federated datasets. https: // www. tensorflow. wttgffderateee federated/ api_ docs/ docs/pythome python/ tff/
datasettsastsstooooooooaoooassee 2020.
[61] Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, and Françoise Beaufays. Understanding unintended memorization in federated learning. arXiv preprint arXiv:2006.04990, 2020.
[62] Quoc Tran-Dinh, Nhan H. Pham, Dzung Phan, and Lam M. Nguyen. Hybrid stochas- tic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint UrXiv:/905.05:: 2019.
[63] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterizee models and an accelerated perceptron. arXiv preprint 2018.
13

---

[64] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gra- dient compression for distributed optimization. In Advances Neural Information Processing Systems (NeurIPS), 2019.
[65] Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. arXiv preprint arXiv:2007.0508: 2020.
[66] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the
objective inconsistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.07881, 2020.
[67] Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communication-effiice. distributed sgd with slow momentum. International Conference on Learning Representations (ICLR), 2020.
[68] Shiqiang Wang. Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 37(6): 1205-111,,, 2019.
[69] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. arXiv preprint arXiv:2006.04735, 2020.
[70] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Bren- dan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In 37th International Conference on Machine Learning (ICML), 2020.
[71] Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprinl arXiv: 708.03888.. 2017.
[72] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xi- aodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference Learning Repre- sentations, 2019.
[73] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint 1rXiv:1905.03877 2019.
[74] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5760 5593-5700,5 2019.
[75] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pages 9793-9803, 2018.
[76] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
[77] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why ADAM beats SGD for attention models. arXiv preprint 1912v:191. 2019.
[78] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in neural information processing systems, pages 2595-2603, 2010.
14


Reviews:
[{"review_id": "mgCKEnqkKTr", "reviewer": "Reviewer_WoRC", "summary": "The paper proposes MIME, a general algorithmic framework for federated learning (FL) that can adapt to (and match the performance of) arbitrary centralized algorithms like Adam, Momentum SGD, and SGD. The authors show that via the MIME framework the convergence of any centralized algorithm can be translated into the convergence of the algorithm in the FL setting. The authors also propose a momentum-based variance reduction (MVR) algorithm that the authors claim to be faster than any centralized algorithm. Finally, the authors conduct extensive numerical experiments to show that the algorithms under the MIME framework perform well on real datasets.", "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": "Overall the paper is well written with a clear presentation. The ideas presented in the paper are significantly original and of importance to the research community. However, there are a few issues with the paper, predominantly with the technical content of the paper which the authors should address. The detailed comments are listed below:\n\n1.\tTheorem I (Corollary II and III): It seems that there is a technical issue with the results presented in Theorem I which then affects the results presented in Corollaries II and III too. Please clarify the following issue. \n\nIn the proof of Theorem I, the authors have used the fact that $\\sum_k \\nabla f_i(x; \\zeta_{i,k}^t) = K \\nabla f_i(x)$ (in Lines 873 and 877 of the supplementary material) which follows from assuming $K$ to be the number of epochs.  This implies that either $\\zeta_{i,k}^t$ are sampled without replacement or $\\zeta_{i,k}^t$ represents the full data, i.e., $\\nabla f_i(x; \\zeta_{i,k}^t) = \\nabla f_i(x)$. In my understanding, this means that the stochastic gradient is not an unbiased estimate of the local gradient (or it is the full gradient). However, in Assumption (A3) this stochastic gradient is assumed to be an unbiased estimate of the local client’s gradient. The proof Theorem I (via Lemmas 7, 8) and Corollaries II and III rely on Assumption (A3) which might not hold if $\\sum_k \\nabla f_i(x; \\zeta_{i,k}^t) = K \\nabla f_i(x)$, as in my understanding Assumption (A3) and $\\sum_k \\nabla f_i(x; \\zeta_{i,k}^t) = K \\nabla f_i(x)$ both cannot be true at the same time. If my observation is correct the proofs of Theorem I and Corollaries II and III do not hold with the stated set of assumptions. Please clarify. \n\n2.\tAssumptions: Note that the linearity of the update $\\mathcal{U}(g_1 + g_2) = \\mathcal{U}(g_1)  + \\mathcal{U}(g_2)$ in Algorithm 1 (and Theorem I) might not hold in general unless $g_1$ and $g_2$ come from the same round of Algorithm 1. This can be seen from the fact that for adaptive algorithms like Adam updates are not linear in $g$, however, since the adaptive step is fixed at the start of the round, linearity will hold, but $g_1$ and $g_2$ must be generated within the same round. Please update the assumption accordingly.   \n\n3.\tSpeed-up over centralized methods: The authors claim that MIME with MVR beats the lower bound for centralized methods, thus breaking a fundamental barrier. These claims are a bit misleading as the lower bounds corresponding to the centralized algorithms are on the computations, whereas the authors measure the total communication rounds required to reach an approximate stationary point, wherein within each round the clients compute multiple gradients. MimeMVR required total communication of $O(1/\\epsilon^{3/2})$, however, it is well known that for FL problems better  $O(1/\\epsilon)$ communication requirement can be achieved. \n\n4.\tThe authors should include Assumption (A3) in the main text of the paper as it is important and $\\sigma^2$ appears in the statements of Theorems and Corollaries. Moreover, the assumption $\\mathbb{E}_i [\\nabla f_i(x)]  = \\nabla f(x)$ is not stated in the paper, however it is being used in the proofs.  \n\n5.\tThe bounded Hessian variance and L-smooth assumptions (Assumptions (A2) and (A2*)) are strong assumptions as they are made on the stochastic samples of the local client’s data. In fact, (A2) loosely forces the data at each client to be homogeneous. Generally, for FL problems (A2) is not required and a weaker version of L-smoothness (A2*), namely, mean square smoothness is required if some sort of variance reduction is used. It seems the analysis relies on these stronger assumptions. The authors mention that Hessian similarity is crucial for federated optimization and refer to [6], however [6] considers a convex problem that is different from the non-convex problems authors tackle. Please clarify.  Moreover, the MIME framework relies on computing the full gradients of the sampled clients at each round which seems to be a stronger requirement compared to existing FL algorithms.   \n\n6.\tIn the discussion of Theorem IV the authors discuss that if $\\delta \\approx 0$ then MimeMVR requires $O(1/\\epsilon)$ communication rounds. However, the statement of Theorem IV requires $K \\geq L/\\delta$, which implies as $\\delta \\to 0$ we will have $K \\to \\infty$. What implication this will have on the performance of MimeMVR? \n\n7.\tIn the Appendix, the authors mention that Mime MVR does not exactly fit the MIME framework as it relies on gradient computation at two consecutive points. I think instead of just including the convergence result of the MVR in the main paper, the authors should also include the MVR algorithm in the main paper since it seems to be a non-trivial construction.   Also, in Table 5 it would be helpful if the authors can add the tracking step used by the Mime framework rather than the tracking step of the centralized algorithm. \n\n8.\tExperiments: \nThe authors have conducted sufficient experiments to validate the proposed algorithms. A few concerns are discussed next. In the Experiments section, from Figure 1 it seems that Mime and MimeLite clearly outperform the rest of the algorithms, however, in Table 1 the reported performance of Mime and MimeLite is very close to other algorithms. Why is this happening? \nMoreover, it seems that Mime and MimeLite compute more stochastic gradients per client compared to FedAvg between two communication rounds. If this is true isn’t it true that the improved performance of Mime framework is expected? \n\n9.\tTypos and minor issues: \n\n$x^{\\text{out}}$ in the statement of Corollary II is not defined. \n\nLine 832: Replace $(\\mathbb{E}[X - \\mathbb{E}[X]])^2$ by $\\mathbb{E}[X - \\mathbb{E}[X]]^2$\n\nLine 853: The inequality is in the wrong direction. \n\nExpression in the statement of Lemma 4: Please use braces with the l.h.s. term to show that the sum over $i \\in \\mathcal{S}$ over the complete term. \n\nWith the proofs of Theorems, Lemmas, and Corollaries the authors should explain the reasoning behind inequalities (and equalities). \n\nLine 974-975: Please state the tracking step for MimeAdam and MimeLiteAdam. \n\nThe authors first use $e^t$ to denote the perturbation in the update direction of the centralized algorithm and then later in MVR for denoting the error in server momentum. Please use a different symbol for each if possible.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None noted.", "review_text": "", "extra_scores": {"ethical_concerns": "None noted.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "VacOma8luwM", "reviewer": "Reviewer_zGM1", "summary": "The paper introduces a new generalized algorithmic optimization framework named MIME for adapting and analyzing the convergence of any optimization algorithm applied in centralized settings into cross-device federated learning environments. The algorithmic reduction is accomplished by decoupling the centralized optimization algorithm into optimizer (server-side) and parameter state (client-side) updates in federated settings. The convergence of the proposed adaptation is shown both theoretically and empirically over a range of challenging real-world datasets for different optimization algorithms. Interestingly, when applying the proposed federated adaptation for a specific momentum-based optimization algorithm, the adaptation is proven to be asymptotically faster than its centralized counterpart.", "questions": "", "limitations": "", "rating": 7, "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": "**Pros**\n-\tInteresting adaptation of any centralized optimization algorithm in federated learning settings, by decoupling the optimization problem into optimizer state (w/ complex) updates and parameter state (w/ linear) updates.\n-\tProven upper bound convergence guarantees of the MIME (MIMELite) framework for different optimizers and comparison against their centralized counterpart. The upper bound convergence rate of the Momentum-based variance federated adaptation is proven to beat the lower bound of the centralized version when clients' heterogeneity is small.\n-\tExperiments on real-world datasets and large-scale experiment setup evaluation for EMNIST62, Shakespeare, and StackOverflow datasets.\n\n**Cons**\n-\tThe proposed method introduces additional communication cost in federated cross-device settings.\n-\tEven though the empirical evaluation is sufficient, further clarification is needed.\n-\tPaper structure is not necessarily coherent; some methods are introduced differently in some parts of the paper and are hard to follow.\n\n\n**Discussion**\n\n- Communication. With your proposed framework, there seems to be a lot more extra communication cost from server to clients (global model, server state, and SVRG style correction lines 140, 141) and clients to the server (updated local model weights, plus full-batch gradients). Can you propose any approaches on how this extra cost (at least on the client-end) can be mitigated? You address some part of the latter case in line 274, and in Appendix section C.3, but I think this should be introduced earlier in the text to alleviate some concerns.\n\n- From my understanding, your analysis focus on the perspective that local batch gradient and parameter update are performed at the same client. Does the creation of the two subgroups (local batch gradient and parameter update) affect your convergence? It is clear that out of S clients, S/2 send full-batch gradients and S/2 parameter updates. Instead of creating two subgroups would a single subgroup of size S/2 lead to the same performance? My concern here is that since clients have heterogeneous distributions, considering only local batch gradients from half of the clients and parameter updates from the remaining might introduce additional noise in the state updates. Is such perspective captured in your theoretical evaluation?\n\n- Is there a case that some of the participating clients cannot compute the full local batch gradient because of resource constraints (Line 146, Algorithm 1)? Should the subsampling method take this constraint into account?\n\n- Experiments. Does Figure 1 show test accuracy or validation accuracy? Why do you provide the validation accuracy in Table 2, the testing accuracy would have been more informative. If this is not possible then, how were the validation datasets constructed and how was the validation accuracy computed across all clients? Moreover, showing the learning curves of the training methods presented in Table 2, based on federation round, would greatly simplify the understanding of the communication cost for each method. Finally, it would be nice to provide/plot the performance of the centralized model (e.g., as horizontal line) in Figure 1. \n\n- Paper structure. In Table 1 you introduce the μ-PL inequality, but in the text there is no discussion on why this convergence analysis is important, what its intricacies are (except of course in Appendix E.1) and why its analysis is not provided for ADAM and MVR – it would be better to discuss this in the text. When presenting the empirical evaluation with Momentum, it is not very clear whether you are discussing server-side or client-side momentum (additional reading is needed). Moreover, the presented momentum results are without variance (not MVR), correct? If that’s the case then what is the convergence of MVR? In addition, in Table 1 you provide convergence guarantees for SGD, Adam, and MVR, however, from the Algorithm it is not clear how the MVR or the Adam is applied since the correction term (c) seems to be always present in the MIME, which is also why MIME is different from MIMELite. Can you please elaborate more in the text to address these discrepancies? \n\n**Additional Related Work**\n\n- In [1], Momentum GD is used as part of the client local step (without server-side optimization) and it is shown to provide accelerated convergence compared to vanilla SGD (FedAvg). Their approach seems to be very similar to your FedAvgMomentum training method.\n- In the related work section, \"Comparison to FedAvg and variants\", in [2], the authors also assign more local steps to computationally fast learners in cross-silo settings and (empirically) show faster convergence.\n\n[1] https://arxiv.org/pdf/1910.03197.pdf, [2] https://arxiv.org/pdf/2102.02849.pdf \n\n**Text corrections / suggestions**\n\n- Lines 100, 107: Notation D is a bit misleading when referring to clients (most of the time denotes dataset), would another notation (e.g., C) be more appropriate?\n- Line 119: please add eq. or equation 1\n- Line 130: change table 4 reference to table 5\n- Line 133: while … while fragmentation\n- Table 1: Why is MimeLiteSGD equivalent to FedSGD? Did you refer to FedAvg? FedSGD is different from FedAvg [3], similarly in Appendix section C.5 Line 759.\n- Line 204: epsilon(ε) refers to accuracy or error? In your analysis, it refers to error\n- Line 221: which increases to increase\n- Line 259: Appendix D does not refer to proof sketch, change to B\n- Line 285: Appendix B does not refer to the experimental setup, change to C\n- Please be consistent with the Mime or MIME naming (see sections 4 and 5).\n- Please align subfigures in Figure 1.\n- Line 331: Statement slightly contradicts your empirical evaluation, which is also shown in Table 2 – MIME does not always outperform MIMELite.\n\n\n[3] https://arxiv.org/pdf/1602.05629.pdf \n\n\n\n**POST AUTHORS RESPONSE COMMENT:**\nI read carefully the response of the authors to my points and the points raised by the other reviewers. My primary concern is the additional communication cost introduced by the framework in cross-device federated settings. In their follow-up answer, the authors propose an approach to reduce this cost through sampling and indicated (in another response) that the lower bound analysis of the communication complexity remains an open question. I would like to see this question and others raised during the reviewing process as part of the paper's discussion/future work section since it can help readers to further investigate these open problems. My score remains unchanged.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work does not seem to have any limitations or potentially negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "ObHj0HioIK", "reviewer": "Reviewer_aDPX", "summary": "This paper studies cross-device federated learning setting where the number of clients is very large and most of the clients participate in only one round of communication. Because of this low client participation per round, it is hard to have any client state/memory. State is usually helpful in traditional federated learning setting (eg: in SCAFFOLD) in estimating client heterogeneity, which can then be used to correct for the bias of the client. To mitigate this, the authors propose two meta-algorithms: MIME and MIMELITE, to adaptive a general class of centralized algorithms to this cross-device setting. MIME uses variance reduction at the client (like SCAFFOLD) and MIMELITE does not.\n\nThe paper analyzes the effect of these meta-algorithms for three standard centralized (server-only) deep learning optimization methods: SGD, Adam, MomentumVarianceReduction (MVR). However, reviewer could not find the pseduo-code for the MVR in the paper. For SGD, and Adam authors show that MIME modification performs at least as good as their centralized base algorithms for nonconvex problems. For MVR, authors prove that the server-level momentum of MIME helps beat the performance of centralized baselines under low-heterogeneity.", "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": "Contributions are original and their quality seems solid, but it is hard to verify it due to lack of clarity (see below). Improving clarity could better convince the readers of the claims. Although it is not clear if the contributions are consistently useful in practice (see below), these analysis and the experiments could be impact for future research and practice. Reviewer is willing to reconsider the score if the clarity and empirical quality can be improved.\n\n-Strengths\n1. If the base centralized algorithms use a momentum, MIME and MIMELITE uses an unbiased estimator of the server-level momentum. These algorithms communicate this momentum to the participating clients at the beginning of each round, and the clients use it to correct their bias when taking gradient descent steps. Note that clients do not update the momentum for their whole round to maintain the lack of bias of the momentum.\n\n2. It it shown that for SGD and Adam, MIME matches the performance of the corresponding centralized (without local gradient steps) base algorithm. Whereas, MIMELITE is slightly worse and it could match centralized performance under certain conditions.\n\n3. For MVR algorithm, MIME is shown to perform much better than centralized algorithm when the client Hessian heterogeneity is smaller than the smoothness of the global loss. This seems to be first such result for smooth non-quadratic setting proving the benefit of federated algorithm over centralized methods. However it was hard to verify this claim as MVR algorithm is not given.\n\n4. Authors report (small scale single-run) ablation study on 2 layer MLP with base SGD+momentum algorithm, to show that MIME & MIMELITE perform better than FedAvg in cross-device setting. It is shown that momentum helps MIMEs however it doesn’t affect FedAvg.\n\n5. Reviewer appreciates that authors also report both positive and negative results they get on large-scale datasets. However, from the given single runs it is is not clear if their meta-algorithms are consistently better than baselines. One way or the other, it would be useful to know.\n\n\n\n-Comments\n1. Although there are only some subtle differences between original FedAvg/SCAFFOLD and MIME-SGD/MIMELITE-SGD, latter gets a much better rate nonconvex in cross-device setting. Can the authors provide more discussion on this difference and intuition behind this improvement?\n\n2. App A: Over-all App A is confusing. \na. Fig 1: It is not clear which algorithm is FedAvg. I think authors use FedAvg both for some meta-algorithm (not given) and standard FedAvg.\nb. What is “server-momentum” in App A and mentioned everywhere else? Can the authors please define it? Why is it called “momentum” and not some kind of pseudo “gradient” for FedAvg? \n\n3. App B is confusing. It could be written more clearly. For example,\nline 649: where is the convex case in Theorem IV? It is hard to understand the section due to the sudden analogy with convex case.\n\n4. Table 1 and Appendix: Can the authors please add the reference for optimal statistical rate?\n\n5. Where are the full pseudo codes of MVR & MIME-MVR algorithm given? Cannot verify the result without the algorithm. It is not given in Table 5. There is not MVR algorithm in [14].\n\n6. Why are there no simulations of MVR and its MIME variants?\n\n7. Table1:\na. Why is FedAvg rate not given?\nb. What is FedSGD? Same for FedSGD, FedSGDm, and FedAdam in the Appendix. \n\n8. What is the FedAvg meta algorithm used in the experiments? It is confusing to use FedAvg to refer to the original FedAvg and the some other meta algorithm from [45]. \n\n9. Table 2: It is not clear why authors are confident that numbers will hold the same over multiple runs. As this is an paper on optimization methods, it is appropriate give the numbers over multiple runs and give their standard errors. Most of the numbers are very close to each other, so it is not conclusive that Mime or Mimelite are useful for large datasets, except for Stackoverflow with Adam. \n\n10. Are authors using “SGDm” and “Momentum” interchangeably?\n\n11. Why does the theory (SGD,MVR) and expts (Adagrad,SGD+momentum) use different base algorithms? I was expecting to the see the experiment with MVR for different levels of heterogeneity.\n\n12. Ablation study: it is not clear why MIME{Adam,Adagrad} is not compared with Fed{Adam,Adagrad} which are much more practical base algorithm. [https://openreview.net/forum?id=LkFG3lB13U5]\n\n13. Although MIME predominantly can only match the centralized rates, but authors claim they may outperform centralized methods in practice (mismatch of theory and practice). Why is this the case?\n\n14. Why is there no discussion of MIME on convex problems?\n\n\n-Other Comments\n1. line 890: $\\pm$ is not a standard notation for adding and subtracting. Missing brackets for argument inside $\\mathcal{U}$\n2. line 677: uses i both outside and inside sum\n3. line. 323: “”App ??”\n4. When saying that “MimeMVR is the first algorithm which beat centralized rates”, are the authors claiming this for general nonconvex setting or is this applicable to convex problems too? Authors may want to be explicit about this for non-expert readers.\n5. Algo 1: From lines 140-141 and 146-147 it is not clear how c & s are calculated. Authors could mention the direction of communication when calculating and sending c.\n6. line 325: Why is sparsity of gradients useful?\n\n—After author response—\n\\\nI keep my score the same as I am still confused about some parts of the paper. I highly encourage authors to improve the clarity in the next revision.\n\n—__After after__ author response—\n\\\nWith their latest response, authors have clarified most of my initial concerns. Unfortunately, I am still keeping my scores the same because now I am not sure if empirical results are directly validating the theoretical results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors could improve the discussion on limitations of their methods. Authors could mention some open questions arising from their study. For example, authors could discuss why MIME predominantly can only match the centralized rates, but they may outperform centralized methods in practice (mismatch of theory and practice). Authors could also mention why or why not MIME can help in convex setting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "IWtctTeKSyo", "reviewer": "Reviewer_ebxx", "summary": "The paper proposes a framework MIME to convert centralized optimization algorithms to the federated learning setting. The key components are some control variates to reduce the effect of data distribution heterogeneity. \nContribution:\n1. A framework to convert centralized algorithms to the federated learning setting.\n2. Theoretical analysis to characterize the convergence of converted algorithms\n3. Experiments show MIME framework can have better performance than FedAvg.", "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": "Strengths:\n1. The convergence rate of converted algorithms matches their centralized versions.\n2. MimeMVR provides an improved convergence rate assuming small Hessian variance. This is an interesting theoretical result.\n3. The algorithms converted by Mime show strong empirical performance.\n\nWeaknesses:\n1. Since the 'breaking the lower bound' contribution is highlighted in the title, this point may deserve more discussion. More specifically, it will be helpful to discuss some technicality on how to use the Hessian variance to improve convergence rate and why centralized algorithms cannot achieve such a rate.\n\n\n--------------after rebuttal-------------\nMy concerns are addressed.", "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": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the concerns of the reviewers were addressed during the rebuttal period and the reviewers unanimously believe that the paper is above the acceptance threshold as the theoretical results are novel. Please revise the paper according to the reviewer's comments to clarify the confusions. In addition, please address the following concern which was raised by the reviewers in the discussion period:

-- All plots are for test accuracy/error. Please include the optimization error convergence rate plots to have a better connection with the rest of the paper. 
Decision: Accept (Poster)