FedChain: Chained Algorithms for Near-optimal Communication Cost in Federated Learning
Authors: Charlie Hou
Kiran Koshy Thekumparampil
Giulia Fanti
Sewoong Oh
Venue: ICLR 2022 Poster (2022)
Keywords: Federated Learning
Optimization
Distributed Optimization

Abstract: Federated learning (FL) aims to minimize the communication complexity of training a model over heterogeneous data distributed across many clients. A common approach is local methods, where clients take multiple optimization steps over local data before communicating with the server (e.g., FedAvg).  Local methods can exploit similarity between clients' data. However, in existing analyses, this comes at the cost of slow convergence in terms of the dependence on the number of communication rounds R.  On the other hand, global methods, where clients simply return a gradient vector in each round (e.g., SGD), converge faster in terms of R but fail to exploit the similarity between clients even when clients are homogeneous.  We propose FedChain, an algorithmic framework that combines the strengths of local methods and global methods to achieve fast convergence in terms of R while  leveraging the similarity between clients.  Using FedChain, we instantiate algorithms that improve upon previously known rates in the general convex and PL settings, and are near-optimal (via an algorithm-independent lower bound that we show) for problems that satisfy strong convexity.  Empirical results support this theoretical gain over existing methods. 

Published as a conference paper at ICLR 2022
FEDCHAIN:
CHAINED ALGORITHMS FOR NEAR-OPTIMAL COMMUNICATION COST IN FEDERATED LEARNING
Charlic Hou
Kiran K. Thekumparampil
Department of Electrical and Computer Engineering Camegie Mellon University Pitsburgh, Pennsylvania, USA charl @eerliih@aaee andrew. www.cmc.....oooooo
Department of Electrical and Computer Engineering University of Illinois at Urbana-Chann cabaaa-Chammaign Champaign, Illinois, USA thekump288 20 i1l inois.ii.......... ..ddu
Giulia Fanti
Sewoong Oh
Department of Electrical and Computer Engineering Cameeie Mellon University Pittshurhh, Pennsylvania, USA gfant @andrew. cmu edu
Allen School of Computer Science and Engineering University of Washington Seattle, Washington, USA sewoongêcs cs. wash nggtonnto edu
ABSTRACT
Federatedd learning (FL) aims to minimize the communication complexity of training model over heterogeneous data distributed across many clients. common approach is local update methods, where clients take multiple optimization steps over local data before communicating with the server (e.g., FedAvg). Local update methods can exploit similarity between clients' data. However, in existing analyses, this comes at the cost of slow convergence terms of the dependence the number of communication rounds R. On the other hand, global update methods, where clients simply return a gradient vector in each round (e.g.. SGD), converge faster in terms of R but fail to exploit the similarity between clients even when clients are homogeneous. We propose FedChain, an algorithmic framework that combines the strengths of local update methods and global update methods achieve fast convergence in terms of R while leveraging the similarity between instantiate algorithms that improve upon previously
clients. Using FedChain, known rates in the general convex and PL settings, and are near-optimal (via an algorithm-indee indeeeededdee lower bound that we show) for problems that satisfy strong convexity. Empirical results support this theoretical gain over existing methods.
INTRODUCTION
In federated learning (FL.) (McMahan et al. 2017: Kairouz et al. 2019 Li et al. 2020), distributed clients interact with a central server to jointly train single model without directly sharing their data with the server. The training objective is to solve the following minimization problem:
N
F(()) Σ
F((x)
where variable x is the model parameter, i indexes the clients (or devices), is the number of clients, and (x) is loss that only depends on that client's data. Typical FL deployments have two properties that make optimizing Eq. (1) challenging: (i) Data heterogeneity: We want to minimize the average of the expected losses Fi(z) EL,~D, (x; 2)) for some loss function f evaluated on client data 2; drawn from client-specific distribution D,. The convergence rate of the optimization depends on the heterogeneity of the local data distributions, (D.), and this dependence is captured by popular notion of client heterogeneity, <², defined as follows:
sup M
VF(x) 2=(22)
(2)

---

Published as a conference paper at ICLR 2022
This captures the maximum difference between a local gradient and the global gradient, and is standard measure of heterogeneity used in the literature (Woodworth et al. 2020a Gorbunov et al.
2020
Deng et al. [2000] Woodworth et al. 2020al Gorbunno et al.. [020 Yuan et al. 2020 et al.,
2021 Deng & Mahdavi 2021). (ii) Communication cost: In many FL. deployments, communication costly because clients have limited bandwidths. Due to these two challenges, most federated optimization algorithms alternate between local rounds of computation, where each client locally processes only their own data save communication, and global rounds, where clients synchronize with the central server to resolve disagreements due to heterogeneity in the locally updated models.
Several federated algorithms navigate this trade-off between reducing communication and resolving data beterogeneity by modifying the amount and nature of local and global computation (McMahan
ct al. 2017 Li et al., 2018; Wang et al. 20T9b a Li et al. 2019,
Karimireddy et al. [202bb a
Al-Shedivat et al. 2020 Reddi et al. [020 Charles & Konečný 2020) Mitra et al., 2021 Woodworth
al. (000a).. These first-order federated optimization algorithms largely fall into one of two camps:
(i) clients in local update methods send updated models after performing multiple steps of model updates, and (ti) clients in global update methods send gradients and do not perform any model updates locally. Examples of (i) include FedAvg (McMahan et al. 2017). SCAFFOLD (Karimireddy) jet al. (020b), and FedProx (Li et al., 2018). Examples of (iz) include SGD and Accelerated SGD (ASG), where in each round r the server collects from the clients gradients evaluated on local data the current iterate (r)) and then performs a (possibly Nesterov-acceeeraated) model update.
As an illustrating example, consider the scenario when Pt's are u-strongly convex and B-smooth such that the condition number is x = B//u as summarized in Table and also assume for simplicity that all clients participate in each communication round (i.e., full participation). Existing convergence analyses show that local update methods have a favorable dependence the heterogeneity Ç. For example, Woodworth et al. (200aa) show that FedAvg achieves an error bound of ((<{² R-) after R rounds of communication. Hence FedAvg achieves theoretically faster convergence for smaller heterogeneity levels Ç by using local updates. However, this favorable dependency on comes at the cost of slow convergence in R. On the other hand, global update methods converge faster in R. with error rate decaying as exp( RR)) (for the case of ASG), where A is the initial function value gap to the (unique) optimal solution. This is an exponentially faster rate in R, but it does not take advantage of small heterogeneity even when client data is fully homogeneous.
Our main contribution is to design a novel family of algorithms that combines the strengths of local and global methods to achieve a faster convergence while maintaining the favorable dependence on the heterogeneity, thus achieving an error rate of Ō( (() exp(-R/ /K) in the strongly convex scenario. By adaptively switching between this novel algorithm and the existing best global method, we can achieve an error rate of O(min /²/u} optimal by providing a matching lower bound in Thm. 5.4] This lower bound tightens an existing one from (Woodworth et al.) 2020a) by considering a smaller class of algorithms that includes those presented in this paper.
(R)). We further show that this near-
We propose FedChain, a unifying chaining framework for federated optimization that enjoys the benefits of both local update methods and global update methods. For given total number of rounds R, FedChain first uses a local-update method for a constant fraction of rounds and then switches to global-update method for the remaining rounds. The first phase exploits client homogeneity when possible, providing fast convergence when heterogeneity is small. The second phase uses the unbiased stochastic gradients of global update methods to achieve faster convergence rate in the heterogeneous setting. The second phase inherits the benefits of the first phase through the iterate output by the local-update method. An instantiation of FedChain consists of combination of specific local-update method and global-update method (e.g., FedAvg - SGD).
Contributions. We propose the FedChain framework and analyze various instantiations under strongly convex, general convex, and nonconvex objectives that satisfy the PI. condition] [ Achievable rates are summarized in Tables 1 2 and In the strongly convex setting, these rates nearly match the poporithm-independden lower bounds we introduce in Theorem 5.4 which shows the near-optimality of FedChain. For strongly convex functions, chaining is optimal up to a factor that decays exponentially in the condition number k. For convex functions, it is optimal in the high-heterogeneity regime, when
F satisfics the ptPP condition if (F((()) F(=")) < ()))())
2

---

Published as a conference paper at ICLR 2022
Algorithm 1 Federated Chaining (FedChain)
Input: Alocal local update algorithm, Aglobal centralized algorithm, initial point Tg. K, rounds R Run Alocal for R/2 rounds
11/2 1//2 f Atocal (2o)
Choose the better point between Z0 and 21/2
Sample S clients S [N]
Draw 2,, ~ D,, i..iE i. E {O....,. K --1
1 arg gi 5K Lies 2k=0 f(z; 2,,))
Finish convergence with Aglobal for R/2 rounds
22 + (0)
Return d2
<> /DR For nonconvex PL functions, optimal for constant condition number x. In all three settings, FedChain instantiations improve upon previously known worst-case rates in certain regimes of Ç. We further demonstrate the empirical gains of our chaining framework in the convex case (logistic regression on MNIST) and in the nonconvex case (ConvNet classification on EMNIST (Cohen et al., 2017) and ResNet-18 classification on CIFAR-100 (Krizhevsky) 2009)).
1.1 RELATED WORK
The convergence of FedAvg in convex optimization has been the subject of much interest in the machine learning community, particularly as federated learning (Kairouz et al. (019) has increased in popularity. The convergence of FedAvg for convex minimization was first studied in the homogeneous client setting (Stich) 2018 Wang & Joshi 2018, Woodworth al. 2020b). These rates were later extended to the heterogencous client setting (Khaled et al. [020 Karimireddy al. 2020b Woodworth et al. 2020a Koloskova et al. 2020), including a lower bound (Woodworth et al. 2020a). The only current known analysis for FedAvg that shows that FedAvg can improve SGD/ASG
in the heterogeneous data case is that of Woodworth et al. (2020a), which has been used to prove slightly tighter bounds in subsequent work Gorbunov et al. (2020).
Many new federated optimization algorithms have been proposed to improve on FedAvg and SGD/ASG, such as SCAFFOLD (Karimireddy al. 2020b), S-Local-SVRG (Gorbunov al. 2020), FedAdam (Reddi et al. 2020). FedLin (Mitra et al. 2021). FedProx @Li 20.8)) However, under full participation (where all clients participate in a communication round; otherwise the setting is partial participation) existing analyses for these algorithms have not demonstrated any improve- ment over SGD (under partial participation, SAGA (Defazio al. 2014)). In the smooth nonconvex full participation setting, MimeMVR (Karimireddy et al.] (2020a) was recently proposed, which improves over SGD the low-heterogeneity setting. Currently MimeMVR and SGD are the two best algorithms for worst-case smooth nonconvex optimization with respect to communication efficiency, depending on client heterogeneity. In partial participation, MimeMVR and SAGA are the two best algorithms for worst-case smooth nonconvex optimization, depending client heterogeneity.
Lin et al. (2018) proposed a scheme, post-local SGD, opposite ours by switching from a global- update method to local-update method (as opposed to proposal of switching from local-update method to global-update method). They evaluate the setting where Ç = 0. The authors found that while post-local SGD has training accuracy improvement of 1 %% test accuracy on ResNet-20 CIFAR-10 classification), though theoretical analysis was not provided. Wang Joshi (2019) decrease the number (K) of local updates transition from FedAvg to SGD in the homogeneous setting. This is conceptually similar to FedChain, but they do show order-wise convergence rate improvements. Indeed, in the homogeneous setting, simple variant of ASG achieves the optimal worst-case convergence rate (Woodworth et al. 2021).
than SGD, the test accuracy can be better (an
SETTING
Federated optimization proceeds in rounds. We consider the partial participation setting, where at the beginning of each round, 5 E Z, of total N clients are sampled uniformly random without
3

---

Published as a conference paper at ICLR 2022
replacement. Between each global communication round, the sampled clients each access either (i) their own stochastic gradient oracle K times, update their local models, and return the updated model, or (ii) their own stochastic function value oracle K times and return the average value to the server. The server aggregates the received information and performs a model update. For each baseline optimization algorithm,
analyze the sub-optimality error after R rounds of communication between the clients and the server. Suboptimality is measured in terms of the function value EF (FF()) F(xx), where è is the solution estimate after It rounds and
arg ming F(x)) is (possibly non-unique) optimum of F. We let the estimate for the initial suboptimality gap be A (Assumption B.9). and the initial distance to a (not necessarily unique) optimum be D [Assumption B.10). If applicable, c the target expected function value suboptimality.
We study three settings: strongly convex Ft's, convex Fi's and Jı-PI. F; for formal definitions, refer to App. [ Throughout this paper, we assume that the F.'s are 3-smooth (Assumption B.4). If F,'s are u-strongly convex /Assumption B.1) or F is p--PL. (Assumption B.3), we denote = 13/ as the condition mumber. D; is the data distribution of client i. We define the heterogeneity of the problem as x² == [ sup,, [VF(>) (x) in Assumption B.5 We assume unless otherwise specified that <² > 0, i.c., that the problem is heterogeneous. We assume that the client gradient variance is upper bounded by x² (Assumption B.6 We also define the analogous quantities for function value oracle queries: S Assumption B.8 of Assumption B.7 We use the notation O 52 to hide polylogarithmic factors, and 0, we are only hiding constant factors.
3 FEDERATED CHAINING (FEDCHAIN) FRAMEWORK
We start with toy example FFig. D to illus- trate FedChain. Consider two strongly con- vex client objectives: (z(x) = (1/2)(z 1)² and (x) (I 1)?. The global objective F(x) = (z) + F2(x))/2 is their average. Fig. (top) plots the objectives, Fnd. (bot- tom) displays their gradients. Far from the op- timum, due to strong convexity, all client gradi- ents point towards the optimal solution; specifi- cally, this occurs when z E (-00, -1] oc). In this regime, clients can use local steps (e.g.. FedAvg) to reduce communication without sacri- ficing the consistency of per-client local updates. On the other hand, close to the optimum, i.e., when E (-1, 1), some client gradients may point away from the optimum. This suggests that clients should nor take local steps to avoid driving the global estimate away from the op- timum. Therefore, when
Fx
F(x)
(x)
Objective Functions
Gradients
FF,(x)
VF(x)
VF, (x)
Client Gradients Agroe sign(VV;(x)) = (VF)(VF
close the optimum, we use an algorithm without local steps (e.g. SGD), which is less affected by client gradient disagreement.
Client Gradients Disagree Sigal (x)) + (ig)(VF,
This intuition seems to carry over to the non- convex setting: Charles et al. (202T) show that over the course FedAvg execution on neural network StackOverflow next word prediction, client gradients become more orthogonal.
Figure 1: A toy example illustrating FedChain. We have two client objectives: Fi (a:) and Fz)... F(x) is their average. The top plot displays the objec- tives and the bottom plot displays the gradients. In regions where client gradients agree in direction, i.c. (-oc, -1] [1, oo) may be better to use an algorithm with local steps (like FedAvg), and in the region where the gradient disagree in direction, i.e. (-1, it may be better to use an algorithm without local steps (like SGD).
FedChain:
To exploit the strengths of both local and global update methods, we propose the fed- erated chaining (FedChain) framework in Alg. There are three steps: (1) Run a local-update method Alocal. like FedAvg. (2) Choose the bet- ter point between the output of Ancal (which we denote 21)2). and the initial point &o to initialize (3) global-update method Agtobal like SGD. Note that when heterogeneity is large, Aleall can actually
4

---

Published as a conference paper at ICLR 2022
Table 1: Rates for the strongly convex case.
+ Rate requires R 2 N/S.
Rate requires S = N.
Method/Analysis
EF - F(x") S O()
Centralized Algorithms
SGD
A Aexp(-n- + (1 9
N PSR
ASG
A 1opp(1x-21) + (1 N USR
Federated Algorithms
FedAvg Karimiroddy et al.
2020b)
A Axxp( 1oxp(-x-11) R) - ni +
K( E R- 24
FedAvg Woodworth et al.
2020a)
SCAFFOLD Karimireddy et al.
2020h
A exxp(= - min(x-1 }R)
This paper
FedAvg + SGD
Thm. 4.1
min
eep((xx R) + 5) C²
uSR
FedAvg + SAGA
Thm. 4.3
min
fx- ' }
min(4, |exp(=x" R) + + {) C²
FedAvg + ASG
Thm. 4.2)
PSR
FedAvg - SSNM Thm. 4.4
k kmin A E exp( min (v
NE N }))+
5 $
Algo--independen LB
Thm. 5.4
min A K 3 ((5) exp( - -
output an iterate with higher suboptimality gap than &g. Hence, selecting the point (between 2o and 22) with smaller F allows to adapt to the problem's 's heterogeneity, and initialize Agusbal appropriately to achieve good convergence rates. To compare 11/2 and the initial point dn. we approximate F(Zu) and 1 by averaging; we compute SK Eies, f(x; 21,x) for 2 do. where K is also the number of local steps per client per round in Ataual, and S is sample of S clients. In practice, one might consider adaptively selecting how many rounds of Assaal to run, which can potentially improve the convergence by a constant factor. Our experiments in App. J.1 show significant improvement when using only I round of Alocal with large enough K for convex losses.
4 CONVERGENCE OF FEDCHAIN
We first analyze FedChain Algo. when Atccll is FedAvg and Agtohal is (Nesterov accelerated) SGD, The first theorem without Nesterov acceleration and the second with Nesterov acceleration.
Theorem 4.1 (FedArg SGD). Suppose that client objectives Fy's and their gradient queries satisfy Assumptions B.4 B.5, B.6 B.7 and B.8 Then running FedChain Algo. T. with Atseal as FedAvg Algo. 4 with the parameter choices of Thm. E.I and Aglobal as SGD (Algo. 2 with the parameter choices Thm. D.1 we get the following rates
Strongly convex: If Ey's satisfy Assumption B.l for some > 0 then there exists fi- nite K above which we get, BF(22) - F(x*) S O A, (2/n) exp( R/k) +
S/N)ç2 (ar22//USAR (uSR)).
General convex: If Fi's satisfy Assumption B.2 then there exists a finite K above which we get the rate EF(iz) - F(x*) < (mmin(3D2/A) R, /BCD3/VR
(V1 (/11S//N(//BDDD BBD33/CD///// /SR)).
PL condition: If F. 's satisfy Assumption B.3 for μ 0, then there exists a finite K above which we get the rate the rate EF((2) F(x*) OminnA,, (²/p) exppppepp-ppppp (aappRR//) (1
S/N)(x<? (USR))
We ignore variance terms and C maXie[N] sup,, (f) - F(x))² as the former can be made negligible by increasing K and the latter can be made zero by running the better of FedAvg + SGD and SGD instead of choosing the hetter of /1/2 /2 and to as in Algo. 1 Furthermore, ? terms are similar to the ç² terms. The rest of
the theorems in the main paper will also be stated this way. To the formal statements, see App. F
5

---

Published as a conference paper at ICLR 2022
Table 2: Rates for the general convex case. Analysis from Karimireddy et al. (2020b). Method/Analysis
Rate requires R 2
Rate requires S = N.
g.
EF - F(x*) S O()
Centralized Algorithms
SGD
+
5 CD
π
N VSR
ASG
3D
R²
+
/
N VSR
$ CD
Federated Algorithms
3D +
DC
8 CD
FedAvg
R²
N VSR
FedAvg Woodworth et al.
2020a
DC
SCAFFOLD*
N AD² *
B R
This paper
min 8D V
S VBCD
FedAvg - SGD Thm, 4.1
1
it /R
N USH
FedAvg -> ASG Thm. 4.2
min { AD2 VBLDa
VBLD3
+ V
S CD VBR
R
VSR
Algo--independent LB Thm. 5.4
min { _D CD)
R yRS
For the formal statement, see Thm. F.1
Theorem 4.2 (FedAvg - ASG). Under the hypotheses Thm. 4.1 with choice of Aglobal ASG
Algo. 3) and the parameter choices of D.3 we get the following guarantees:
Strongly convex: If Pe's satisfy Assumption B. fororr μ > then there exists a finite K above which we get the rate, (F2())) F(x*) S (m (//) exp(- R/VR) (1 (IN)(//pSR))
General convex: If Ft's satisfy Assumption B.2
then there exists finite K O(min[3D3 R? : VBCD3/RR
above which get the rate, (F( F(x") <
V1 (1-S/N(CD/VSR) +
For the formal statement, see Thm. F.2. We show and discuss the pearooptimality of FedAvg + ASG under strongly convex and PL conditions (and under full participation) in Section 5 where
we introduce matching lower bounds. Under strong-con convexity shown in Table 1 FedAvg - ASG.
when compared to ASG, converts the A cxp( - R/ RK) term into min A m $3,5%pp exp(-R/ term, improving over ASG when heterogeneity moderately small: <2/1 < A. It also significantly improves over FedAvg, min (²/u) exp(-R/ vk) is exponentially faster than x({"/u)(t" Under the PL condition (which not necessarily convex) the story is similar (Table 4), except we use FedAvg - SGD as representative algorithm, as Nesterov acceleration is not known to improve under non-convex settings.
In the general convex case Tabll 2) let 8 = D = 1 for the purpose of comparisons. Then FedAvg ASG's convergence rate is min 1/ R /// + - S/N(C/VSR) + V1 S/N /C/V/// S/R", then f1 S/N / VSR < 1/R2, so the FedAvg > ASG convergence rate is better than the convergence rate of ASG under the regime << min 11/22, / ). The rate of Karimireddy et al. (2020b) for FedAvg (which does not require S = N) is strictly worse than ASG, and so has a worse convergence rate than FedAvg + ASG if Ç < min 1/2 J. Altogether, Ç < min(1/R² S/RR) FedAvg - ASG achieves the best known worst-case rate. Finally, in the $ N case, FedAvg + ASG does not have regime in Ç where it improves over both ASG and FedAvg (the analysis of Woodworth et al. (2020a), which requires 5 N) at the same time. It is unclear if this is due to looseness in the analysis.
[ < R then ///2/R < 1/R2 and í < <
Next, we analyze variance reduced methods that improve convergence when a random subset of the clients participate in each round (i.e., partial participation).

---

Published as a conference paper at ICLR 2022
500
SCATTCL
Polleg +500
DOSAPPORD 500
Figure 2:
Plot titles denote data homogeneity 6). "X-X"" denotes FedChain instantiation with X
as Alocal and as Aglobal. circle markers denote stepsize decay events and plusses denote switching from Ateal to Aglobal- Across all heterogeneity levels, the multistage algorithms perform the best. Stepsize decayed baselines are left out to simplify the plots; we display them in App. J.2
Theorem 4.3 (FedAvg - SAGA), Suppose that client objectives F; and their gradient queries satisfy Assumptions B.4 B.5 B.6 B.7 and B.8 Then running FedChain Algo. 11 with Atscal as FedAvg Algo. 4) with the parameter choices of Thm. E. and Agtobal as SAGA (Algo. 5 with the parameter choices of Thm. D.4 we get the following guarantees as long R 2 (3
Strongly convex: If FF'' 's satisfy Assumption B. B.7 for 0, then there exists finite K above which we get the rate EF (F2) F(x") S O (min4 A <2/u) exp(- (/ R))
for PL condition: If Fs's satisfy Assumption B.3 for μ. > 0, then there exists a finite K above which we get the rate EF (fz F(x*) O (min (2/u] exp(- R/w)).
For the formal statement, see Thm. F3
Theorem 4.4 (FedAvg + SSNM). Suppose that client objectives F, 's and their gradient queries satisfy Assumptions B.4 B.5 B.6 and and Then running FedChain AAlgo 1) with Alocal as FedAvg Algo. 4) with the parameter choices of Thm. E. and Agiabat as SSNM (Algo. 6) with the parameter choices of Thm. D.5 get the following guarantees as long R 2 )
Strongly convex:
If F,'s satisfy Assumption B.I for μ 0, then there exists finite (same as in FedAvg - SGD) above which we get the rate EF((2) - F(x*) S
((min|(,<2//ul exp(-eppp)) (S/N /S)(Nx))Rt).
For the formal statement, see Thm. F.4 SSNM (Zhou et al. 2019) is the Nesterov accelerated version of SAGA (Defazio al. 2014).
The main contribution of using variance reduced methods in Aglobal is the removal of the sam- pling error (the terms depending on the sampling heterogeneity error (1 S/N) from the convergence rates, in exchange for requiring a round complexity of least N/S. To il- lustrate this, observe that in the strongly convex case, FedAvg + SGD has convergence rate /SR) and FedAvg - SAGA (FedAvg SGD's variance- reduced counterpart) has convergence rate min (A, //) exp( min(1/K. (/,,SS//N)))))/ S/N) Rt), dropping the (1 - S/N) (uS Rt) sampling heterogeneity error term exchange for harming the rate of linear convergence from 1/K min[1/x, S/N}.
min(A, /²/Hx) (1o(-R/))((LS/NN))))
This same tradeoff occurs finite sum optimization (the problem min, (T (2),,, where v (typically) represent losses on data points and the main concern is computation cost), which is what variance reduction is designed for. In finite sum optimization, variance reduction methods such SVRG (Johnson & Zhang 2013) and SAGA (Defazio et al. 2014 Reddi et al. 2016) achieve linear rates of convergence (given strong convexity of v. 's in exchange for requiring at least N/S treat FL.
updates. Because finite sum of objectives and <² as the variance between F2 s), these results from variance-reduced finite sum optimization can be extended federated learning. This is the idea behind SCAFFOLD (Karimiredyy et al. 2020b).
instance of finite-sum optimization (by viewing Eiq. (1) as
It is not always the case that variance reduction in Agtohal achieves better rates. In the strongly convex case if (1 (SN))(()//)))) ((Se)) N/S, then variance reduction gets gain, otherwise not.
7

---

Published as a conference paper at ICLR 2022
5 LOWER BOUNDS
Our lower bound allows full participation. It assumes deterministic gradients and the following class from (Woodworth al. 2020a Woodworth 202T; Carmon et al.] 2020):
Definition 5.1. For zero-respecting if for any i, k, r, the k-th iterate on the i-th client in the r-th round xir) satisfy
IR let supp(u) {i [d] es # 0}. An algorithm is distributed
Ti
supp S U supp((VF((a?))))
U
supp Supp(V P.
(3)
OS
X' [EN],0S
Distributed zero-respecting algorithms' iterates have components in coordinates that they have any information on. As discussed in (Woodworth et al. 2020a). this means that algorithms which are not distributed zero-respecting are just "wild guessing" Algorithms that distributed zero-respecting include SGD, ASG, and FedAvg. We assume the following class of algorithms in order to bound the heterogeneity of our construction for the lower bound proof.
Definition 5.2. We say that an algorithm is distributed distance-conserving if for any k, we have for the k-th iterate on the i-th client in the r-th round Ti (r) satisfies ||a2,,2 x= 1|2 S (c/2)]l]
x" 1|2 Σ I| x; [|²], where x; == arg min Ex) and x² := arg ming F(x) ( and Winit is the initial iterate, and is some scalar parameter.
Algorithms which do not satisfy Defimition 5.2 with at most logarithmic in problem parameters (see (2) are those that move substantially far away from x², even farther than the 2 's are from x". With this definition in mind, we slightly overload the usual definition of heterogeneity for the lower bound:
Definition 5.3. A distributed optimization problem is (C. -htterogggoo if
[N s V (z) VF(x)]12 S Ç², where we define (c/2) - x 2 Σ
{x || x S
=i=1 || x² } for some scalar parameter
Those achievable convergence rates in FL that assume Eq. (2) can be readily extended to account for Definition 5.3 as long as the algorithm satisfies Definition 5.2, We show that the chaining algorithms we propose satisfy Definition 5.3 in Thm. D.I. Thm. D.3, and Thm. [.I c at most polylogarithmic
in the problem parameters defined in $ 2 Other FL. algorithms also satisfy DDfinition 5.2, notably
FedAvg analyzed in Woodworth et al. (2020a) for an absolute constant, which is the current tightest
known analysis of FedAvg in the full participation setting.
Theorem 5.4. For any number of rounds R. number of local steps per-round K, and (C,c)- heterogeneity (Definition 5.3). there exists a global objective F which is the average of two B-smooth Assumption B.4) and plz O)-strongly convex (Assumption B. quadratic client objectives F, and F2 with an initial sub-optimality gap of A, such that the oulput &t of any distributed zero-respecting Definition 5. and cooouncceonnsviinggg algorithm Definition 5.2)
satisfies
Strongly convex: F(t) F(xx) 2 Mmmin( 1/(xx exp( (R/(()))/)) when μ > O, and
.General Convex F(5) - F(x*) 2 Q(min /R², (22 when P =
Corollary 5.5. Under the hypotheses of Theorem 5.4 there exists a global objective F which is Jt-PI.
and satisfies F(2) - F(x") ) 2 (mmin 1/ (Tx")))((" (8)} exp(-R/Vii)
A proof of the lower bound is in App. G. and the corollary follows immediately from the fact that j-strong convexity implies μ-PL. This result tightens the lower bound in Woodworth et al. (020a)), which proves similar lower bound but in terms of a much larger class of functions with heterogeneity bounded in Ç. = (1/N) E.", (V 12. To the best of our knowledge, all achievable rates that can take advantage of heterogeneity require (Ç, c) -hterrgeenetty (which a smaller class than (-- heterogeneity), which are incomparable with the existing lower bound from (Woodworth et al. (020a) that requires Ç. -eterrregeeety. By introducing the class of distributed distance-conserving algorithms
We do not formally show it for SAGA and SSNM, as the algorithms are functionally the same as SGD and ASG under full participation.
8

---

Published as a conference paper at ICLR 2022
Table 3: Test accuracies (t). "Constant" means the stepsize does not change during optimization.
while "w/ Decay" means the stepsize decays during optimization. Left: Comparison among algo- rithms in the EMNIST task. Right: Comparison among algorithms in the CIFAR-100 task. "SCA." " abbreviates SCAFFOLD.
Algorithm
Constant
w/ Decay
Algorithm
Constant w/ Decay
Baselines
Baselines
SGD
0.7842
0.7998
SGD
0.1987
0.1968
FedAvg
0,8314
0.8224
FedAvg
0.4944
0,5059
SCAFFOLD
0.8157
0.8174
SCAFFOLD
FedChain
FedChain
FedAvg + SGD
0.8501
0.8355
FedAvg - SGD
0.5134
0.5167
SCA. SGD
0.8508
0.8392
SCA.
(which includes most the algorithms we are interested in). Thm. 3.4 alllow us, for the first time, to identify the optimality of the achievable rates as shown in Tables 2 and
Note that this lower bound allows full participation and should be compared to the achievable rates with S N; comparisons with variance reduced methods like FedAvg SAGA and FedAvg SSNM are unnecessary. Our lower bound proves that FedAvg + ASG is optimal up to condition number factors shrinking exponentially in VK among algorithms satisfying Definition 5.2 and Definition 5.3 Under the PL-condition, the situation is similar, except FedAvg + SGD loses v in the exponential versus the lower bound. On the other hand, there remains a substantial gap between FedAvg + ASG and the lower bound in the general convex case. Meaningful progress in closing the gap in the general convex case an important future direction.
EXPERIMENTS
We evaluate the utility of our framework on strongly convex and nonconvex settings, We compare the communication round complexities of four basclines: FedAvg, SGD, ASG, and SCAFFOLD, the stepsize decaying variants of these algorithms (which are prefixed by M- in plots) and the various instantiations of FedChain (Agoo.
Convex Optimization (Logistic Regression) We first study federated regularized logistic regres- sion, which is strongly convex (objective function in App. 1.1) In this experiment, we use the MNIST dataset of handwritten digits (LeCun et al., 2010). We (roughly) control client heterogeneity by creating "clients" through shufiling samples across different digit classes. The details of this shuffling process are described in App. L.I] if dataset is more shuffled (more homogeneous), it roughly corresponds to a lower heterogeneity dataset. All clients participate in each round.
Fig. compares the convergence chained and non-chained algorithms in the stochastic gradient setting (minibatches are 1% of client's data), over R 100 rounds (tuning details in App. I.I). We observe that all heterogeneity levels, FedChain instantiations (whether two or more stages) outperform other baselines. We also observe that SCAFFOLD- including SCAFFOLD-
outperforms all other curves, This can be explained by the fact that acceleration increases the effect of noise, which can contribute to error one does not take K large enough (we set K 20 in the convex experiments). The effect of large K is elaborated upon in App. J.I
Nonconvex Optimization (Neural Networks) We also evaluated nonconvex image classification tasks with convolutional neural networks. In all experiments, we consider client sampling with S 10. We started with digit classification over EMNIST (Cohen et al. (017) (tuning details in App. I. where handwritten characters are partitioned by author. Table 3 (Left) displays test accuracies on the task. Overall, FedChain instantiations perform better than baselines.
We also considered image classification with ResNet-18 18 on CIFAR-100 100 (Krizhevsky 2009) (tuning details in App. I.2.2). TTable 3 (Right) displays the test accuracies on CIFAR-IO0 SCAFFOLD not included due to memory constraints. FedChain instantiations again perform the best.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is supported by Google faculty research award, JP Morgan Chase, Siemens, the Sloan Foundation, Intel, NSF grants CNS- CNS-2002664, CA-2040675, IIS- IIS-1929955, DMS-213400 2134012. CCF. 2019844 as part of NSF Institute for Foundations of Machine Learning (IFML), and CNS-21 12471 as part of NSF AI Institute for Future Edge Networks and Distributed Intelligence (AI-EDGE). Most of this work was done prior the second author joining Amazon, and it does not relate to his current position there.
REFERENCES
Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated learning via posterior averaging; A new perspective and practical algorithms. arXiv preprint arXiv:2010.05273. 2020.
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. arXiv preprint arXiv:1506.01900 2015.
Needet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated stochastic gradient method. arXiv preprint 1eXivv/901.080000 2019.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120 2020.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates local update methods. arXiv preprint arXiv:2007.00877 2020.
Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large-cohort training for federated learning. arXiv preprint arXiv:2106.07820, 2021.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN), pp.
IEEE, 2017.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pp. 1387-1395. PMLR, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, and Mchrdad Mahdavi. Adaptive personalized federated learning, arXiv preprint 2rXhv:2003.13461 2020.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. arXiv preprint 202.
2021.
Alireza Fallah, Asuman Ozdaglar, and Sarath Pattathil. An optimal multistage stochastic gradient method for minimax problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 3573-3579. IEEE, 2020.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 1264):1469-144 2012.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-288) 2013.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. arXiv preprint arXiv:201 02828, 2020.
10

---

Published as a conference paper at ICLR 2022
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-3222 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:/912.04977 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint urXiv:2008.33606 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143, PMLR, 2020b.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5393 PMLR, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.eeae wwtp://ww......cc//eeee..e.. www.ex/b////isstt...pmmmmmm/ 2, 2010.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06127 2018.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 1227-1231. IEEE, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. JEEE Signal Processing Magazine, 37(3):50-00) 60, 2020.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- mini-batches, local sgd. arXiv preprint 1808.v8808.07220 2018.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efficieett learning of deep networks from decentralized data. Artificial Intelli- gence and Statistics, pp. 12822 PMLR. 2017.
Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients. arXiv e-prints, art. arXiv:2102.07053. February 2021.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00225. 2020.
Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Fast incremental method for nonconvex optimization. arXiv preprint arXiv:1603.06155 2016.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv: 1805 2018.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-efficieeen sgd algorithms. arXiv preprint arXiv: (afo::/8000757 2018.
11

---

Published as a conference paper at ICLR 2022
Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update sgd. In SysML, 2019.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pp. 299-300. IEEE, 2019a.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication-effiieen distributed sgd with slow momentum. arXiv preprint 1101v:1910.00643, 2019b.
Blake Woodworth. The minimax complexity of distributed optimization. arXiv preprint arXiv:2109.00534, 2021.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning, arXiv preprint arXiv:2006. 04735, 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020b.
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication, arXiv preprint arXiv:2102.01583, 2021.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. arXiv preprint arXiv:2006.0899 2020.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. arXiv preprint arXiv:2011.08474, 2020.
Kaiwen Zhou, Qinghua Ding, Fanhua Shang, James Cheng, Danli Li, and Zhi-Quan Luo. Direct acceleration of saga using sampled negative momentum. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1602 1610. PMLR, 2019.
12

---

Published as a conference paper at ICLR 2022
Appendices
Additional Related Work
14
Definitions
14
Omitted Algorithm Definitions
15
Proofs for global update methods
17
DJ
SGD
17
D.2 ASG
21
D.3 SAGA
24
D.4 SSNM
29
Proofs for local update methods
34
F,1
FedAvg
34
F
Proofs for FedChain
37
F.1 FedAvg > SGD
37
F2
FedAvg + ASG
F3
FedAvg - SAGA
39
FedAvg > SSNM
39
Lower Bound
39
Strong convexity and smoothness of F, Fi, F2
G.2
The solutions of F, Fi F2
G.3
Initial suboptimality gap
41
Suboptimality gap after rounds of communication
G.5
Computation of (
41
G.6
Theorem
42
Technical Lemmas
44
Experimental Setup Details
47
I.1
Convex Optimization
47
Nonconvex Optimization
47
J
Additional Convex Experiments
48
U.1 Verifying the effect of increased K and
48
Including Stepsize Decay Baselines
49
13

---

Published as a conference paper at ICLR 2022
Table 4: Rates under the PL condition.
Rate requires R 2 N (i) F(x"(())))))))))))) S (.))
5'
Methos/Analysis
Centralized Algorithms
SGD
A exp(-xx +R] + -
)
Ac USR
Federated Algorithms
FedAvg Karimireddy et al. 2020a
R. expl -n R) +
=²c² UR
This paper
FedAvg - SGD
Thm. 4.1
min A C exp( -n R) +
N
5 "
USR
FedAvg - SAGA TTmm 4.3
min A exp( (1 (
Algo--independen LB Corollary 5.5)
min [A, K exp(-x i
A ADDITIONAL RELATED WORK
Multistage algorithms. Our chaining framework has similarities in analysis to multistage algorithms which have been employed in the classical convex optimization setting (Aybat et al. 2019 Fallah al., 2020 Ghadimi & Lan| 2012] Woodworth al., 2020a). The idea behind multistage algoritmms to manage stepsize decay to balance fast progress in "bias" error terms while controlling variance error. However chaining differs from multistage algorithms in few ways: (1) We do not necessarily decay stepsize (2) In the heterogeneous FL setting, we have to accomodate error due to client drift (Reddi et al. 2020 Karimireddy et al. 2020b), which is not analyzed in prior multistage literature. (3) Our goal is to minimize commuincation rounds rather than iteration complexity.
B DEFINITIONS
Assumption B.1. Ft's is are p-strongly convex for μ > 0, i.e.
(VP(()), S (F)(x) Fl(r) 2 -11 y/l3)
(4)
for any i, x. y.
Assumption B.2. FI's are general convex, i.c.
(VF()), - (F,(())) F(()))
(5)
for any i. y-
Assumption B.3. Fis p-PL for μ > 0, i..
2F((F F(x*)) < [VF(2))
(6)
for any æ.
Assumption B.4.
F.' are 3-smooth where
VV((x) VF(( & B|| vll
for any i. y.
Assumption B.5. Fi's are ( (ehhterogeneoous defined defined as
2 == sup max (VF()) SE[N]
(8)
Assumption B.6. Gradient queries within a client have uniform upper bound on variance and are also unbiased.
E..DD, [V
(V VI(
VF
Assumption B.7. Cost queries within a client have a uniform upper bound on variance and are also unbiased.
E (f();)) F((x))² < soz (x F((x))
(10)
14

---

Published as a conference paper at ICLR 2022
Assumption B.8. Cost queries within a client have an absolute deviation.
C
sup max ((() F.(x))2
(11)
N
Assumption B.9. The initial suboptimality gap is upper bounded by A, where is the initial feasible iterate and x" the global minimizer.
(F(x)) F(x*) SA
(12)
Assumption B.10. The expected initial distance from the optimum is upper bounded by D, where To the initial feasible iterate and x" is one the global minimizers:
Tu - x112 & D
(13)
C OMITTED ALGORITHM DEFINITIONS
Algorithm 2 SGD
Input: initial point x (9), stepsize 1), loss f
for ... R 1 do
Run a step of SGD
Sample clients S, S [ [1,....N]
Send (x)) to all clients in S, (r)
Receive {0. JiES (rad(z S,, 2(1) Algo. 7
(( Eies. 9i (P)
(r+1)) (r) 77 (()
end for
Algorithm ASG
Input: initial point z (0) = (0)
farherrsn for Irrirrsn loss f
for 1...., do
Run a step of ASG
Sample 5 clients S, S [I.....N]
Send (x) to all clients in S,
(r)
(1-a:Xutar). (r-1) or (1-0 (r-1)
x 3.+(1 7-+(1-a3)) oz Jag
(-+(1-a?] )
Receive [g, (r) hes, Gr md S,, (rr) Algo. 7
(r) Eies. Di
(r(r) arg min, {ar (7) .x) + / (1 x1l3] + ((1 o,) + ++3 (x((r(1-11 x=|3]}
Jag (r))()) 0r Ja
(r)
(r-1)
end for
15

---

Published as a conference paper at ICLR 2022
Algorithm 4 FedAvg
Input: Stepsize 7, initial point (0))
for = 0..... R-
Sample 5 clients S, S [I.....
Send (x) to clients in S,, all clients set 0;,0 (r()
for client E S, in parallel do
for k ...., VK 1 do
Client samples Pi,k vR
1 EK=
(z), 1
where (r) LAVR+H
"ikyK+k Dr
1ik-1 = iik 1) Di,k
end for Receive 9j = =K== end for
(r) from client 9i,k
glr)
Σ iES. 9i (r) ((r+1) t (1)) - 17 -r)
end for
Algorithm 5 SAGA
Input: stepsize 77, loss f. initial point (0)
Send a( (0) = (0)) to all clients i
Receive (0) = K Σk= f((o (0) (-1)), 2(11) D, from all clients, c(0)
N Σ d
2i,
for 0, ...... do
Sample 5 clients S,
C [N.
Send (1))) to all clients in S,,, Receive (g. (r) hies, = Grad (s,,
Algo.
(r) = Eies. Hi
(r)
Eies, C (r) (rr)
(r+1)) (r) -7.g(1)
Option I: Set cf (r+1) = n/ 0i (((+1)) = (r) for E S,
Option II: New independent sample of clients S,, send x(r) to all clients in S/ receive
{0] Jre;; = (rad(x((), (,, g(1), set c;
(r+1) g!r)) of ((+1)) (rr) for i e S,
c (r+1) = =c² and Φ (r+1) = (r) for any i not yet updated
(r)
(r+1) Σe 0g (r-1)
end for
16

---

Published as a conference paper at ICLR 2022
Algorithm 6 SSNM
Input: stepsize 7, momentum 7, client losses are P((x) Be,D,, x))++(()) - th())
where F; can be general convex and h(z) is p-strongly convex, initial point 20
Send of = x (0) to all clients i
Receive C; (0)
K-1
(0), ff(o) : 2,,k 2(-1)), (-1) Dr from all clients c00) 1/4 Li=1 Ci
N (0)
2k=0
2i,
for 0, ..... R do
Sample 5 clients S, [I,....,, N7
Send (1) to all clients in S,, Vi (r) rx( + + (1- -) for ip S
Receive (r) D. R E K-1 Vi( (n) 2
(r)
k for ES,, (r)
",,b Dj
g0 Er Ri
E,,es, 1rr + c())
(r)
a(r+1) = arg min, (h(x) + (1 + 2n ||x((r (077-x10 =z((²}
1
Sample new independent sample of S clients S S [[]
Send (01) to all clients in Sy, ((/+1)))= (z(rtl) + (1 1 (r) for E ES,
(r) 1 -K-i V. ( k1..k) for I, S. (1)) ~ D;
Receive 91. K
((+1))
q
91. for I, S.
[r+1]
Eg and Pi (r+1)=
(r)
(r)
0; for any i not yet updated
c(++1)= = 1
N Ei= Ci
11-1)
end for
Algorithm 7 Grad(x, for client i E S in parallel do
Client samples gi,k (f(((r;; (() where 207 Dí, k (0, (0,........ K --13
(r)
_k-1 K-1 (r)
9 end for return
k
k= 9i.k
{g) hies,
(r)
D PROOFS FOR GLOBAL UPDATE METHODS
D.I SGD
Theorem D.1. Suppose that client objectives Fi's and their gradient queries satisfy Assumption B.4 and Assumption B.6 Then running Algo. 2 gives the following for returned iterate
Strongly convex: F 's satisfy Assumption B.1 for >> O. If return à = 1
WR EP wr)(1)
with wr (1- - and WR Er= Wr. = Ö (mint 3: (1,)), and R > K,
R +
0²
S 2
EF($) - F(x*) < O(Aexpl
expl
+ (1 -)
uSKR
N uSR
E E| (r) -
for any 0 OSTER
General convex (grad norm): F, 's satisfy Assumption B.2 If we return the average iterate R 1r=1 - ,), and = min p. ( BcRl 1/2] where c is the update variance
31 E V ō
BDD
S BCD
+V1
R
VSKR
N VSR
(r - 1012 113 < O(D2) for any 5 R
17

---

Published as a conference paper at ICLR 2022
PL condition: Fl's satisfy Assumption B.3 1) (min pRI) }. then
If return the final iterate & x(R), set
R +
KO² uSKR
S
xC²
(F(x - F(x*) Ó(D exp(
+ (1
K
N
uSR
Lemma D.2 (Update variance), For SGD, we have that
o²
S S-1 5²
E 11) < ||F
+
(14)
SK
N
Proof. Observing that
E, |
(15)
and using Lemma H.T we have
S + 5-1 c²
o² SK
(16)
N N-1 S
D.1.1 CONVERGENCE OF SGD FOR STRONGLY CONVEX FUNCTIONS
Proof. Using the update of SGD,
| x²1| 112 S ||,-(0)==*11 -
2) -x)) + 1711
(17)
Taking expectation up to the r-th round
E, Ex|lx(+11) - x=1 S ||x(() - 1=1 27 (VF((())) ,,x0)
x0) - -x³> ) + 1r
(18)
By Assumption B.1.
2ny( V F ())
- -x) - (F) - F(x*)) - n)) - x1
(19)
Using Lemma D.2 Assumption B.4, and setting 17 S 2
E [, x11
(20)
(F((x())) ((F(=()))F((a²))) + 172 0²
S - 1 C2
$ (1 - (1) x²
+ (1
N N-12 155)
(21)
SK
5
Rearranging and taking full expectation,
(F - < (1 - 1 (r)
12
E (((x(++1) - x=1
σ² SK
S -
7
+ (1
N 1 (5)
11
(22)
letting Wy (1 pmn) pun) 1r--1), Wn = DR 2t =
1
x((), then
Wn
E0 x²1
17( 0²
S 5-1 2
$
EF($) - F(x*)=
+ (1
(23)
W/R
SK
N 5
log (mxx 1 RD RDD/ where
From Karimireddy et al. 2020b Lemma 1, R > and min
23
+
8=1)$
NK
R +
d²
S 2 N
EF(#) - F(x") < Ō exp(
+ (1
(24)
pSKR
PSR
Which finishes our work on the convergence rate. Next we consider the distance bound. Returning to the recurrence
E, || (1+1) - x²11
(25)
< (1 - ()) 112 -x= -(F(((()))((()) + +1² d² S 2
+ (1
(26)
SK
N
5
18

---

Published as a conference paper at ICLR 2022
Taking full expectation and unrolling,
B|(xx()) - 2=2
(27)
$ E x - x² exp( nur) + 2 o²
+ (1 -
N - 1 1 3
5
(28)
SK
Note that Karimireddy et al. 2020b chose 7, so that 77 o. + And so
(1- (1- S Ö(uD² exp(-umB))
-1z(())=111 =2"))=
(29)
D.1.2 CONVERGENCE OF SGD FOR GENERAL CONVEX FUNCTIONS
Proof. By smoothness
Assumption B.4). we have that
Bn²
F(z(rt1)) - F(x())) S (VF((())
+
(30)
2
Taking expectation conditioned up to and using Lemma D.2
- - s -(1 31d² )(F + Bip o²
S - C
+ (1
(31)
2 SK
N 5
If S B.
Bn2 o²
S-1 52 N- S
E -(( |F(}
+ (1
(32)
2
SK
Taking full expectation and rearranging.
E < EF(o(++1)- EF(xx
Bn 0²
S-1 1
52
+
+
(33)
2
SK
N - S
Summing both sides over r and averaging.
11 R-1
M1 (F( (R)
Bq 0²
S 1 ?
Σ -=
+
+ (1
(34)
2
nR
2 SK
N S
Letting å be an average of all the "s))s, noting that (F(x
EF(((
A, A S 3D3 and
choosing 17 min
1 BeR 3/23 where
SK
+ (1
N-I
8-1
34
D
3CD
VFF < 0
(35)
R
VSKR
N VSR
So we have our convergence rate. Next, for the distance bound,
(rx(+ - x² 1|2 = (|x(r) - 12 (r) x0)) - -x)) + 11
(36)
Taking expectation up to to r, we know from Lemma D.2
[x(2(+111) 112
(37)
(1))) -x)) + ( + 1 0²
S 2
$ (t) 2²112 ,x))) By Assumption a.d Assumption B.4
+ (1
(38)
SK
(x+1) - 2 < (1) - 112 2|12 2n(1 - F(x*)) + +
(39)
x²
S 2
-
+ (1
(40)
SK
N
5
19

---

Published as a conference paper at ICLR 2022
with 17 S 8
5 5 N 5)
-
E,]la(++1) - =x111 || x²11 1 + +
+ (1
(41)
SK
Unrolling and taking full expectation,
B| x²11 - 1e| x²11 + n2²{( Ri σ²
S 2
+ (1
5
(42)
SK
We chose 17 so that 3m(
2 SK
+ (1 - )) = A. Therefore
E||x(()) x=1 < B1| 2011 + A
S 2D
(43)
8
D.1.3 CONVERGENCE OF SGD UNDER THE PL-CONDITION
Proof. Using Assumption B.4 we have that
Bn² 11
F(a(rt)) "
(44)
Taking expectations of both sides conditioned on the r-th step.
B1Z
E, - - )1
)|2 +
E, 11
(45)
2
Using Lemma D.2]
31² o²
S - N
E, Ex - F( - |
(1
(46)
2 SK
5
Using Assumption B.3
have that
S - B1j² o²
S - 1 N
2
(1
(47)
SK
Rearranging,
E (xx(((())1)) -(x)) S - ( - F(x")) + Bap² o²
S 8-1 6
+ (1
(48)
2 SK
N 5
Letting g² + 8-1 $ and subtracting
Ben from both sides, 24
(, F(x*) Ben
I (1 (())())((()))) - F(x*) Ben
(49)
24
2/
Which, upon unrolling the recursion, gives us
Ben
(F(x(1)) F(x*) S A Aexp(-nuRR) +
(50)
2,u
Now, if we choose stepsize
log (og(maxfe {e,
1ZAN }) "e
min(
(51)
3
1R
Then the final convergence rate
) + ko²
S xt2
(F) F(**) S0 exp(
+ (1
(52)
uSKR
N USS
20

---

Published as a conference paper at ICLR 2022
D.2 ASG
The precise form of accelerated stochastic gradient we run is AC-SA (Ghadimi & Lan 2012 2013). The following specification taken from Woodworth al. (2020a):
We run Algo. 3 for Rg iterations using (0)) Ps-1, farte1 and (rtess, with definitions
Rg |max(4//
48 128c /
3 (0+17
2 r+1
10.
7,-
-(r-1))
0 max [23, 332-(c-1) R. (R, (1) 1/23
pC
d² SK + (1 - N Set p. = Jag (R.)
(R.) where Zag is the solution obtained in the previous
Where c =
step.
Theorem D.3. Suppose that client objectives Ft's and their gradient queries satisfy Assumption B.4 and Assumption B.6 Then running Algo. 3 gives the following for returned iterate T:
(R.) Strongly convex: F satisfy Assumption B. for μ > O. If we return & Iag after R rounds of the multistage AC-SA specified above,
R
S c² N
EF - F(x") S cxpp
+
+
VR
HSKR
HSR
R
0²
S
-' 1- O(KBl1 - x11 expp
+
+ (1
VR
SRSK
R
N
1 SR
And given no randomness, for any 0 05 r R
[kx(r) - x² 1/ - ||ا 1²1
[|r((r) x² x11 S 10x 1²1
and any 15rsR R
| - xx 212 S 1|x - x11
General convex (grad norm): Ft's satisfy Assumption B.2 If we return Ing after
(R.)
R rounds of the multistage AC-SA specified above on the regularized objective F, Fx(1)=
F(x) + 1 (0) 112 with μ = max f R2
28
log? (c² + R²), V
302 ASKR
11- N )8{2 ASR
}, we have
3A R
0²
S 2
BoD
S CD
B| < O
(1
SKR
N SR
VSKR
N VSR
- - S Ō(D?)
D.2.1 CONVERGENCE OF ASG FOR STRONGLY CONVEX FUNCTIONS
Proof. The convergence rate proof comes from Woodworth et al. 2020a) Lemma 5, What remains is to show the distance bound.
From Proposition 5, (Eq. 3.25, 4.25) of Ghadimi & Lan 2012). we have that the generic (non- multistage) AC-SA satisfies (together with Lemma H.I
EF (F (r)) + pu (r) x=1 F(x)
(53)
r 4r σ²
S 2 N s
r, (r 1) - x11 2 Bl(z(() x= 10111
+ (1
(54)
p. SK
21

---

Published as a conference paper at ICLR 2022
1, r=
Where r,
Notice that
(1 a,)]rr111
r
7r E [ (x(11)11) - x=11 11 - x=
==11²] Te
x²1 ||x((r) - =x11
(55)
r
So
4r
5²
S
(p + F -x
x²12 T (TmBlla 11 + r,
+ (1
(56)
/1
SK
N
S
Which implies
4r
a²
8 5²
Bl(ad!)) - x=1 < [E||x:10) x=1
r
(1
N 5
(57)
n
SK
Furthermore, T, r(r+1)
2 so
8
0²
$ 2
E B( x= 1| E|
11
+ (1
(58)
1r(rr
1)
SK
N
If there is no gradient variance or sampling,
| x=11 ozx x=1
(59)
Next, we show the above two conclusions hold for c.(() and arg
(r) For Fag show by induction:
Base case: Dag = (0) so is true
Inductive case: Zag Tag as well.
(r)
convex combination of (x)) and zag (r-1) 1) so the above statements hold for
(r) For md note it is convex combination of x (r-1) and x(r-1), so the above statements on distance
also hold for amd
(r)
For the distance bound on the returned solution, use strong convexity on the convergence rate:
R
E| - = - x'1' x²112expi exp(
(60)
VK
n2
D.2.2 CONVERGENCE ASG FOR GENERAL CONVEX FUNCTIONS
For the general convex case, we use Nesterov smoothing. Coneretely, we will run Algo. assuming strong convexity by optimizing instead a modified objective
(x) F(x)
/
2 ( 20|2
(61)
Define =4 arg ming (x) and A,, EF, (0) - F(x We will choose μ carefully balance the error introduced by the regularization term and the better convergence properties of having larger μ.
Proof. Observe that
E| V - p(2 - 2110)) < [ 21²E| - x 10)
(62)
We evaluate the second term first. We know that from the theorem statement on strongly convex functions and letting r²' 8+H and x f because F is now B + j-smooth,
8
R
o²
S
2
(+) Fa(=;)) S ((FF((()))) F2(x(t) exp(
+
(63)
VKl
μSKR
N
HSR
22

---

Published as a conference paper at ICLR 2022
Which implies
(.) & (1)) + o²
S 2
uSKR + (1
(64)
N
uSR
0²
8 2²
= -((F(1))) +
μSKR + +11
(65)
N
USR
So it is true that
= =F,(()=B(((() + - 119
(66)
= =)()F(x())+ 0²
S 2 N
+ (1
(67)
μSKR
uSR
If we rearrange,
F(2) ド E - 100-=(00) 10 < O(FF(z)))
-E
+ F())+
0² HSKR
+ (1
S S
(68)
N HSR
0²
S 5²
< (O(FF() F(x") + USKR
+11
(69)
N uSR
S C
50IA+
μSKR +
(70)
N USR
Next we evaluate 2 Observe that the smoothness of F. is + μ. Returning to the convergence rate,
EF₂(#) - (x))))) S 504 exp(- R
o² pSKR
+ +(1 S S
)+
(71)
V
N PSR
We have that
Fd (0) Fu(x))) F(z F( マリ -12(00 (0)
-2iil S F(x - F(x')
(72)
So A, S A. By Assumption B.4
R
0²
S 2
E EI F2 (+) < (3+ ( exp(
+
+ (1
(73)
VR
uSKR
N uSR
s <0(3Aexpl
R
+ u
+
B
0²
+ (1
N
S 2
+ (1
S
352
Vi
PSKR
SKR
N SR
N
μSR
(74)
So altogether,
R (1+ R)
a²
S E
E [FF < ((3 exp(- Vil
+ (1 + k)(1
nA)
(75)
SKR
N SR
Choose μ = m
2 log (e² + R²), v
Ar ASKR
(1- 1187 ASR
}. By Theorem E.I's proof in Yuan &
R
Ma (020)).
3A
S
2 SR
D
S CD N
E || < 1
+
+V1
(76)
R
SKR
N
VSKR
VSR
Next we evaluate the distance bound for the returned iterate. Observe that from the distance bound in the strongly convex case,
1 S 0 3 + 1 (1 -xxll exp(
R +
S 2
B
E
+ +(1
(77)
VR
PSSKR
N
12SR
Given that μ = max
R log" 2 (c² + +R²), v
Ro? ASKR
11- 33822
ASR }.
Ela 12 < O (0)
-//1l22 + ||0 - x 111)
(78)
< (( (0) - -r, )1²)
(79)
23

---

Published as a conference paper at ICLR 2022
Now we look at the actual distance want to bound:
E - 11 < (FE| - =1 + Eljo - x 112 Bl|=" - 2000
(80)
(81)
Observe that
(x F(x + || - x S F(x*) + || - x²11 = Fx(x*)
(82)
which implies that
||x - -,,,11 2 S ||,:10) x=11
(83)
So altogether
- x012 ==00==000000 <Ō(D3)
(84)
D.3 SAGA
Theorem D.4. Suppose that client objectives FÇ's and their gradient queries satisfy Assumption B.4
and Assumption B.6 Then running Algo. 3 gives the following for returned iterate
Strongly convex: F,'s satisfy Assumption B.1 for p O. If return ā WR Er wpa(r)
with w, (1 (1-np)²-i (r+1)
(
and R - Wr, 1l (minn 1 aRt)), R > n. and
use Option
11 S )R)
o²
EF( F(x") O(Acxp(-minn
8 N
PRKS'
PL condition: Fy's satisfy Assumption B.3 If we set n
38(N/8/73 use Option II in
multistage manner (details specified in proof), and return a uniformly sampled iterate from the final stage,
R
EF(+) F(x*) S O(Aexp(
(85)
x(N/S)2/3
USK
D.3.1 CONVERGENCE SAGA FOR STRONGLY CONVEX FUNCTIONS
The proof of this is similar to that of Karimireddy al. (20206) Theorem VII).
Proof. Following the standard analysis.
E, (r+1) =12 = [|x(r) 20112 - (g -x)) + E, (1) (r) 1
(86)
(87)
(88)
We treat each of these terms separately. Second term: Observe first that
K-1 V ffx (1 1 +())
E,g = E,
(89)
IES,
k=0
(r)
(90)
And so the middle term has, by (strong) convexity,
-2 (t) (r) xx)) -2n ( x²) < 22)((((())))) - F(x*) ) + 11 - -x*1(²)
(91)
(92)
24

---

Published as a conference paper at ICLR 2022
Third term:
E,
(93)
K-
=B,lin( 5 ieS,
Vf -2()) + c1
(94)
K
-nl'Brll
[2ikk) - c0 + 1
(r)
(95)
KS
S
S 4n ||
+ vf(l(() 2()) - - 417
(96)
KS
K
+ 4n Erll KS
Σ K,
VF((")) - 1/- + 4n KS
E K,iES,
VF((= - \V
(97)
(98)
Where the last inequality comes from the relaxed triangle inequality. Then, by using Assumption B.4, and Assumption B.2]
Assumption B.6
E 1/
(99)
4np00
I En Erl
Σ VF:(2') - 1/ 12/ - F(x*))
KS
KS
K.ESS,
(100)
Taking full expectation and separating out the variance of the control variates,
(0
(101)
12
s 47/ 4n2
- -
KS K,
KS
(102)
Now observe that because c(r)_ N d?
(1 8n²
- F(x")] 12n/aa2
[F(('') Be("") + 8,317 8,11 -
(103)
KS
Bn + 83n 8 F F(x') (xx)] + 12n2a0²
(104)
KS
Bounding the control lag:
Recall that
(r) C w.p. S
(r+1)
(105)
Σ k=0
K-1
V (z(())) (1)) w.p. &
K
Therefore
(r+1) Be
(1
s N B
S N
(VF(
(106)
Returning to the definition of Cr+1,
C++1
1
(r+1]] (11
(107)
N
N
1 (1
Σ
5
(E(c))) - VF(xx)) + (EVR - -V)(('))
(108)
N
1=1
N
S
S
< (1
Cr
+
Σ
-
-
(109)
N
N2
1=1
25

---

Published as a conference paper at ICLR 2022
where in the last inequality applied Jensen's inequality twice. By smoothness of F/'s (Assump Nc,
tion B.4).
C++1 S (1 N Cr + 2BS N (EF(x())--((C)
(110)
Putting together:
So putting it all together, we have
E| (r+1) x
(111)
12np0²
S (1 - m1) - x² 113 n22 (B3))-))) -F)))=F(()))) + 8nP +
(112)
KS
From our bound on the control lag,
9v N
9 (1
S Crr + 183() F(x')]
S Cr+1
(113)
S
N
N
C. + 9n MnN
1p1
I)C, (83 - F(x))
(114)
S
S
Adding both inequalities, we have
E||x((+1)) - x² 11 + N C,+1
(115)
$ (1-11p1 - mdtn 1Bl) x²1 11? + 2
Crl 17(2 - 26F - -F(x))
(116)
S
+ 1 MnnN 1)C, +
12n2a²
(117)
KS
Let S 36 1 S
1
8 then
9uN
N
- =2111 (r+)
(r+1)
C,+1
(118)
5
N N
Cr] - 7) (EF((11)) F(x*)) + 12n/002
(1 7n) (BI x² 1|2
(119)
S
KS
Then by using Lemma in (Karimiredyy al.
2020b), setting 7/max mint 26,3 9p. }. R
2
and choosing v = min 1og(max(1, Kdo/e))
(mmax where do = EF(:: - 1=1 + 9N
3 Co and
12o2 KS we have that by outputting f =
WR = wr)(() with WR = E Wr and w, =
(1 -r) we have
EF($) F(x*) 5 Ō(udo exp(- (0xmxxxxxx + uR
(120)
Öudo exp(- 1:5(--ummnxxP? R2) + uRt
(121)
Nn²
a²
)( 111 +
Co) exp(-=mmaxx1 +
(122)
S
PRKS
We use a warm-start strategy initialize all control variates in the first N/S rounds such that
(0)
(f( 12, (-1)
K
By smoothness of Fi' Assumption B.4
1 N
C. N E|EE (0) [F((2')]1
Σ
(123)
N
= N
(. - VF((2*)]2
(124)
< (E(F - F(x"))
(125)
26

---

Published as a conference paper at ICLR 2022
And recalling that 7) S min 1
9pN }. we know that
S
263
9N 2 Co
9.N1²
I nB
- 1 A
(B(((z()) F(*1))
(F(x -(x*))
(126)
S
s
H
So altogether,
o²
EF(2) -100-F((a2 F(x') S O(Aex((Aexxxppppp exp((xmmxxx)) +
(127)
HRKSS S
D.3.2 CONVERGENCE OF SAGA UNDER THE PL CONDITION
This proof follows Reddi et al. (2016).
Proof. We start with Assumption B.4
B 2 [llo(rt()) - x00)
(F(x()t2)) < B[F(x!!)) + (VF(c())),,x()))) - xx(0)) ) +
(128)
Using the fact that (()) is unbiased,
B12 |
EF(((+1)) < /
(129)
Now we consider the Lyapunov function
L = ElF(x
Cr
||r(r) - -
(130)
We bound L,+1 using
E (l(
11
(131)
N
B1x
E
N S +
Bl(((++1) - 1,
(132)
N
Where the equality comes from how ofr4t)) xr) with probability S/N and is "(n² otherwise. Observe that we can bound
E Bl - 112
(133)
= -1]l - (12 + [|x(()) -6( 1/2 + 2(x - x0)) - -b(">>=
(134)
[r]]a - 1r)
-2() + || -
+ 2n 26
VF + 1 マタ -
(135)
Where used unbiasedness of (0)) and Fenchel- inequality. Plugging this into b,+1.
307
L,41 < E[F(x(")) - // )1 +
1
11
(136)
2
(1(+
+ Cr+1
N S
Σ
|zo(1) 0f
(137)
N2
2(N S)cr421/
N
E 2h
V
(2(((r)) )12
- (bllo(1)) - -6!-)))) 1!11191
1
(138)
N2
1=1
Cr C (N 5) (1) 112 + (
Br7
< (F) - (17
+ 2
(139)
bN
2
(
N - S
N c++1
( -)) 1
(r) -//5
(140)
N
N
27

---

Published as a conference paper at ICLR 2022
Now must bound E glgg
K-
Bli
+
NK Σ
flo
:
(141)
S
K
k=0
2B
(142)
iES.
k=
V/6 2E
12
(+)))
(143)
NK
NK
va²
s 2 5
- +
(144)
SK
KES.
Where the second to last inequality is an application of VXr(X) v E[X²), and separating out the variance (taking advantage of the fact that é's and z's are independent), and is some constant.
We use Assumption B.4 and take expectation over sampled clients to get
2.3
vO?
1| S Σ B B of 2
2E
VF
(145)
SK
Returning to our bound on Ttp+1,
L,41 < EF(x())) (1 C411(N -S)
1/² 2c,+1 | (F
(146)
bN
+ (c.41l
N-S
+ N
nb(N S)
N
+ 2n 2 + ) 33)
N
N
Bll - -o!")
(147)
07700
(cr+1 + 3
2)
(148)
SK
We set c, c+11 N-S + Nb(N-5)) 227)2 + 1 which results in
Iy+1
(149)
$ L, - -nn C++17(N (N - -S) -123 22
vn20²
17 E (F
SK (cr+1 + (
(150)
bN
Let r, = 1) Cc+1n(N-3) 2 2c,+11/. Then by rearranging bN
v12002
(G++ + 8
I.E (F S Lor L1+11 +
2
(151)
SK
Letting 7n minogrsr-1 R-1 P..
E
< Σ r E V 11)
(152)
R-1 vn220
(c++1 + 8
S
LR + Σ
(153)
SK
Implying
A
02
(cr+1 + 3 2 SK
(
(154)
Yn
Therefore, if we take a uniform sample from all the x(r), denoted =²!
A
R-1
un²o²
(crt1 + ")) SK
E (
+
(155)
R.
Rn
2
28

---

Published as a conference paper at ICLR 2022
We start by bounding Cy. Take 1f
1 2/33 and b 3/ Let nb(N-5)
38 1
21/² 3². Observe that 0 < and
>
N
$
Then C, G+1(1 0) + 1/33% which implies
33 33 - I I f )/3
" "
0
N
So we can conclude that
7/ = min(n
Cr+17
- 12 20,+11²)
y2/3
(156)
5
128 N
So altogether,
E (I |1
1233
N
)2/3
1
(157)
R
SK
12B(N/S)2/3
1234
N
vBO
2/3
(128(N/S)
2/ 9,3 (N33(45
(158)
R
SK
123
N
2vo2
2/3
(159)
R
5
SK
Now we run Algo. 5 in repeated fashion, as follows:
1. Set x Ps-1
2. Run Algo. for R, iterations
3. Set p, to the result of Algo. 3
Repeat for stages. Let po be the initial point. Letting R. = [24 /2/3 this implies that
2p(EF(p)) F(x")) EIVFF))1 (EFF(P;-1)
F(x)))
2va2
(160)
2
SK
Which gives
EF(p.) F(x') < O(AeO(Aeexpx)) exp(-s) o²
(161)
PSS
If the total number of rounds R, then
R
(F($) - F(x)) 0(A SOAeepp
-)
(162)
K μSK
D.4 SSNM
Note that our usual assumption F((x: is p-strongly convex can be straightforwardly converted into the assumption that our losses are F. (x)) F((x)) h(()) where F((x)) is merely convex and h(x)) is ju-strongly convex (see (Zhou al. 2019 section 4.2).
Theorem D.5. Suppose that client objectives Ft's and their gradient queries satisfy Assumption B.4 and Assumption B.6 Then running Algo. 6 glives the following for returned iterate Z:
Strongly convex: F.'s satisfy Assumption B. for 0. If we return the final iterate and set = 2n(N/S]="
(N/S)au if (N/S) and 3p(N/333,
(N/8)yR if 1+
141
(N/S) < T N
S S RR
kO²
(F)) F((*)) s O(A expl min N V NE HKS
29

---

Published as a conference paper at ICLR 2022
D.4.1 CONVERGENCE OF SSNM ON STRONGLY CONVEX FUNCTIONS
Most of this proof follows that of (Zhou et al. 2019) Theorem 1.
First, we compute the variance of the update g(*).
Blllg
v (1()
(163)
Σ Vig, -V 1 N E(vE - vVP(o!
va
s El|
1)
+
(164)
N
KS
E.
i=1
VF, (v!,)) - (6.))) vO²
$ El|
(165)
KS
L,ES,
va²
S {
Σ
F.. (000)) - (... - (V (v.. 10 -
(166)
S
KS
E.
=291
)
N Σ (V -
va
(167)
KS
For some constant v. In the first inequality we separated out the gradient variance, second inequality we use the fact that Var(X) < E[X²], third inequality used Assumption B.4, and fourth we took expectation with respect to the sampled clients. From convexity we have that
F,, ) (x)
(168)
S (V R. (vl.),
). Vir x²)
(r)
(169)
1 - (V P..((... (r)) ). 1,001 - -
(0)) + (VF.. (v.")) (r)) - xx")
(170)
T
1-T (VP. (1h ), (0)) - Vi. + (V (v/ (3)) - 5) (0()) - xx))
(7)
(171)
( x) x (r+1)) () (r+1) - x²)
(172)
where the second to last inequality comes from the definition that vi. = (r()) + (1 -1-777 () expectation with respect to the sampled clients, we have
(r)
Taking
N
N
F(( - F(z*) S 1-T
1. - =1')) + Es, (1 x(1) - (((r))) (173)
N
NN
Es, (1) (((+1) x²)
(174)
For Es, (1()), ,0(1) - 1((+1)), can employ smoothness (ø), :vi.),
(0((t1) ( which holds for any
I, S
F1.(0/ Fr. (vf.)) s (VFr. (r+1) -
11. - -
(r)
+
- -
3 (r+1) ?
(175)
2
using of (1+1) (r((+1) (1- (1-7) k and y (r)
(1(1) + (1 - ?)0 (1- (though the second is never
explicitly computed and only implicitly exists)
(3) ) ((+1)) - =(1)) + 3r2
Fr. Fi.(of (v))) < (VV
(1) 11((+1)=2(())
-
(176)
2
Taking expectation over St and using of, we see that
(r+1) (r+1) + -1--) (r) and 1/ا = (x((r) + (1-7)
Es 5
Σ Fr.(olttt))
1
Σ
A(u S 5
1
v Vi(yl ( ),((+1)) - 2(())
(177)
N
NV
LESS
1=1
1=1
372
+
||
(++1) - 112
(178)
30

---

Published as a conference paper at ICLR 2022
and rearranging,
(00)) - r((t1))
(179)
N
1
F((ul())
75 Es, Σ (of(of(t1))
(180)
v. i=1
1,S,,
N
- g(t) (((+)) ,(())())))))))))))))))))))))))) - xl()) + 3r
v
|| 200
(181)
N
2
Substituting this into Eq. (173) after taking expectation over S,, and observing that from Zhoou et al.
2019 Lemma 2) we have identity
( u) S
1 - 12(1) || [|x((++1) - u/1 - h(()) - 11(((+11)
2n |xx(r) u11²
(182)
2m
1+ 17
(183)
21j
so with u = x=, we get
1 N
F((u FFxx)
(184)
N
E
N Σ
1
(V ),00 ( +
Ru(ul") ))
(185)
NN
TN
Σ F1.
(186)
TS
I,ES
+ Es.
N
V FV. (r)) (r)))
3r
Es. [ 212)
(187)
2
1 Es, (r( x 11
+ - 11x(00) - x=112
+ 7pp
Es. 1| 11 (r+1) - x11
(188)
20
2n
2n
+ h(xx) 1s, (1x(1)
(189)
We use the constraint that BT 5 1 - Ar
T-o plus Young's inequality (a, < |||l + ||b6| with
بيم on Es, + EN'1 (v:(v (r)) g(r), x((+1) (r)) to get
F(( F(x')
(190)
N
N
N Σ
()) -
(191)
Σ
F((u
Es..s: Σ
Fr. (o.((((tt))
(192)
NN
TS
t=1
1.ESY
N
+
1-T Es..l
||
(.(( - 111
1
|1 - 112
(193)
2,T
N
2n
1=1
1 + 1//1
Es,, E.,,|1 ([((()
xz + h1(x)) (Esh(ar(++1))
(194)
2m
31

---

Published as a conference paper at ICLR 2022
using the bound variance, we get
N
) - (xx))
(195)
N )
1-T N
ss
s:
Σ Fr. )
+
Σ
)
(196)
TS
NN
==1
E,ES,
1=1
1 + 2n
||x(r) - x=11²-
1 111 Es, || - x= $12
(197)
2n
+ h(xx)) Es, ((x((t()))))) + (1 - T)UO²
(198)
2,3
combining terms,
s Σ F1. (((())))))]]101(( - Flx*)
(199)
TS
N
(((((()) + 2n
|12 - -x-122
1+ +n
Es. [lx( - ==
(200)
2n
Es, h2z + (1 - T)UO2
(201)
2 KS
Using convexity of h and of (r+1) = (r()+1) + (1-7)Øf (r) for Is E St.
M60 (1 S rh(xx(+11) + (1 r))()))))
(202)
After taking expectation with respect to S, and S
-Es, (M(x((+t)))]] S NN
((o - 1 -s. s;
Σ h(of
(203)
T 1.ES%
and plugging this back in, multiplying by S/N on both sides, and adding both sides by Es; 1 igs; (F((o("))F((())) F((x)))
N 1
Es,.s:
Σ - FF((t']
(204)
7
1=1
(1-
N R)) - Fx(x))) + TN
E. ( - -x(x)))
(205)
TN
1=1
145
S
(1 + n4)s
(1 - T)UO²
(
x 1|2
Es. (1+1)) - x=1 +
(206)
N
2n/N
2 KN
Observe that the probability of choosing any client index happens with probability S/N, so
1
-(P(O)))F((>)))
N-S S 1 NN
F( -F(("))
(207)
TN
N
which implies
N
S:
1
Fi(o!
(1+)))
- F(('')
(208)
N
N
1
((( F((a)))
(209)
N
S
(1 + n
-x=1+ (1- T)UO²
(r)
x=112 112
Es,, || (r+1)
(210)
2n
2n7
28TKN
32

---

Published as a conference paper at ICLR 2022
To complete our Lyapunov function so the potential is always positive, we need another term:
VF:(x"),
of (r+1) x²)
(211)
1
VFi, (x"), (r+1)
000,
xx) Σ
[(VP)(E').
1/ x²)
(212)
N
N
=
Σ L
N
T
(x'),
x((t)))))))) x²)) + N
(x,,,(x)),
01 x²)
(213)
N (VF((")) o/ -2"
(214)
N
Taking expectation with respect to S,, S
Es..;; N
1
(FF("))
0 (r+1) - xx')| = -1
TS
)
1
(F((x") ) (r) xx")) (215)
N
N
1=1
Let B, == N EE= F(() F(x*) - N E (x")
(r)
x²) and P.. == =1/(()) 1=1
then we can write
S
1-
T
s
Pr + (1- -)
s;,.s:((B+1)) +
N Es, [Pr+1] S
B
+
(216)
7
2np
2BrKN KN
(N/9)
Case 1: Suppose that (N/S)
<
3 I. then choosing
(N/S'm It4l
3R
1
3u(N/333.
I+V 3[N33T
2'
we evaluate the parameter constraint 3T
S
_r I-7¹
(N/S)
BT < 1 BT (1 (1+1++110
1
1
2
2-T
3x
3(N/S)
(217)
1
By
K
3(N/S)K
which shows our constraint satisfied. We also know that
1
1
r
1
(218)
T(1 + m7)
T
(N/S)nP
So can write
(N/S) Es. St [B--1] + 2n/(N/5)
Es, [P++]]
(219)
S)
1
B, (T/(N) P.) + (1 (1-15 T)
1
$ (1 + m1)
(220)
(N/S)mH
23rKN
Telescoping the contraction and taking expectation with respect to all randomness, we have
1
(N/S) E[BRl+ +
E[PR]
(221)
2n/NN/)
1
1
EPo) + (1-T)vo² 1 (1+
$ (1 + mH) R(
EBo +
(222)
(N/S)m
(n(S))
2
Bo = F)) - Fx**) and EBR 2 0 based on convexity. Next, we calculate the coefficient of the
variance term
T + Tp
1 -1)( 1 =
S N
(1+ 1 - 1)(1
1
(223)
T
T1
T1
TH
S
1) 1)(1 + v=ll// 1
.N.
N
011 N
(1 + Vklyy V/
(224)
=011
S
+ Vkl
S
1/2 1) + vx( N
/ 2(2)
(225)
N
N
-K(k)
(226)
33

---

Published as a conference paper at ICLR 2022
Substituting the parameter choices and using strong convexity,
R( (
c(-A+ D2) + O a²
B|(x(R) - x011 S (1+ +1++
(227)
3(N/S)
122NN'
Case On the other hand, we can have
(N/S)
3 and choose 1) 2u(N/5} T
(N/S
147u
(1/2)
2 One can check that the constraint BT S # I-7 is satisfied.
After telescoping and taking expectation,
[B[Ba] + (n)(N/) E[PR]
(228)
EP)) + (1- T) (1-T)vo² 1 np
- (1 + n4) - (2EBo + (T/N/
(229)
28TKN
Next, we calculate the coefficient the variance term.
7/
( 1)(1 + 1
= S
1 1, 1)(1 +
1
+1+
(230)
T
7/
nH N
np11
mp
N
N
=0(( N
(1
- 1)(1 + ))
(231)
s
= =0 3)
(232)
which gives us
2 -R(2 ( + 0 - "
a² BuKS'
( 1²1 S (1 2(N/S)
(233)
Altogether, supposing we choose our parameters as stated in the two cases, we have:
S S
RO²
EF(x(0)) - F(x*) s OO:A min
RR) +
(234)
N NE
μKS
PROOFS FOR LOCAL UPDATE METHODS
E. FEDAVG
Theorem E.1. Suppose that client objectives F;'s and their gradient queries satisfy Assumption B.4 and Assumption B.6 Then running Algo. 4gives the following for returned iterate
Strongly convex: F:'s satisfy Assumption B.I for μ. > O. we return the final iterate, set n g. and sample S clients per round arbitrarily,
RVK
2
o²
(R) S O(Dexp(-ee-11
11
/
Further, if there no gradient variance and only one client is sampled the entire algorithm.
(t - 11 O(Ix= 1²1 + (0) x; ) for any 0 1rrs S R
If we return the last iterate after run- 8 ning the algorithm Fx(x) = F(x:) 1 | x11 with μ O(max Rz log" (e2
General convex: F,'s satisfy Assumption B.2
R²), 5. Da and n StF'
3D2 oD
(F)) F(x*) < 1
K1/4 (D)
VRR
and for any OSTSR. R.
El( - x012 Ö(D2)
34

---

Published as a conference paper at ICLR 2022
PL condition: F,'s satisfy Assumption B.3 B μ > O. If we return the final iterate, set 1 = gr and sample one client per round,
RVK 5²
o²
- S O(A
2/
2
E.1.1 CONVERGENCE OF FEDAVG FOR STRONGLY CONVEX FUNCTIONS
Proof. By smoothness of F Assumption B.4), we have for k E {o...., VK - 1
Bn
((11))1) - (( - (VF((
(T)) 1, 91.k) +
(r)
(235)
2
Using the fact that for any a, b we have -2ab (a - b)2 a² - -b,
F( S "IV B18²
1
11
(r) 12
2
7
1n VF(x)2)
(236)
2
1 Letting 17 8
F(a (r) - F (1 S 1VP
(3)
110
VF(x(,2)11
(237)
2
Conditioning on everything up to the k-th step of the r-th round,
(x ()x 5 IIFF(
1 + 7
(2) - VF(=
(238)
n no²
1 + 2
(239)
2VK
Where the last step used the fact that [[X*] = (X) + [[ the assumption on heterogeneity Assumption B.5), and the assumption on gradient variance (Assumption B.6) along with the fact that 9,6k is an average over vK client gradient queries. Next, using μ-strong convexity of F Assumption B.I
n
no²
E, F - --
F(x")) +
(240)
2
2/K
which after taking full expectation gives
BF F(x*) s (1-m)) - -F(x') + ?2
(241)
2
2 K
Unrolling the recursion over & we get
EF(x - F(x*)
(242)
(1- V ( - n 2
no² 2
VK
+
(1 mm)*
(243)
2v K
k=0
Also note that x ((+1)) = 3// Eies, (r) ".V So by convexity of F,
(r(x - F(x*)
(244)
S EF(x i.vR) ) -F(x")
-
(245)
VES.
(1 - (1-m K (EF( - F(x*)) + -FF(()))-(((
=(T5²
2
+
n0² 2
VK-1
Σ (1 - )1)*
(246)
2
2 K
k=0
Unrolling the recursion over R. we get
(F( F(x²)
(247)
2
no²
< (1 - nu (F( +
+
(1 TVK
(248)
2
2v
7=0
k=
35

---

Published as a conference paper at ICLR 2022
Which can be upper bounded as
2² o²
EF(x!)) - F(x*) s (1-1/1) nn)) RVK (F(x!0)) - F(x))())))))))))))))))))))
(249)
2 2
The final statement comes from the fact that V - S | z because of 1j S and applying triangle inequality.
E.1.2 CONVERGENCE OF FEDAVG FOR GENERAL CONVEX FUNCTIONS
For the general convex case, use Nesterov smoothing. Concretely, we will run Algo. 3 assuming strong convexity by optimizing instead a modified objective
F (z) = F(x) + / 11x(00) x01
(250)
2
Define / arg ming (x) and A,, = (z)) - F(x We will choose μ carefully to balance the error introduced by the regularization term and the better convergence properties of having larger μ.
Proof. We know that running Algo. with 1) B+u gives (from the previous proof)
R K
o²
BF (x)))) (x) < A exp(
(251)
B-
2/
2 K
We have that by Yuan & Ma 2020
Proposition E.7)
EF(x (R) F(x*) EF, (x(R)) F2(o)) + # D
(252)
So we have (because A S A shown in Thm. D.3).
(F) F(x') A exp(
RvK K
2
0²
+ # D2
(253)
S+
2/1
2μv/K
K
Then if we choose μ 2 0 VKR log" (6² VKR)), 1 0(5) (
and μ 2 O DkIAA):
3D2
oD
()) - F(x*) < Ö
VKR K1/4 +DD)
+
(254)
Now we show the distance bound. Recall that
RVK B-H +
d²
(F) Fx(x)t & 4 exp(
+
(255)
2p
2
P
By smoothness, strong convexity of Fp., and the choice of μ (as we chose each term above divided by to match D up to log factors), we have that
E El
xtil S Ō(D²)
(256)
So,
E (R) 2²1 < (R) x1, + ( -x11 2 3El|2* - 100 Ō(D²)
(257)
Where the last inequality follows because
F(x;)) + H 11 - 21 < F(x*) + 5リ (,r =2112
(258)
E.1.3 CONVERGENCE OF FEDAVG UNDER THE PL CONDITION
Proof. The same proof follows as in the strongly convex case, except Eq. (244) where we avoid having convexity by only sampling one client at time. This follows previous work such as Karimireddy et al. (2020)). Averaging when the functions are not convex can cause the error to blow up, though in practice this is not (as mentioned in Karimireddy et al. (2020)))
36

---

Published as a conference paper at ICLR 2022
F PROOFS FOR FEDCHAIN
F.1 FEDAVG - SGD
F.1.1 CONVERGENCE OF FEDAVG SGD STRONGLY CONVEX FUNCTIONS
Theorem F.1. Suppose that client objectives F 's and their gradient queries satisfy Axsumption B.4
Assumption B.6 Assumption B.7 Assumption B.5 Assumption B.8 Then running [Algo. 1 where
Alocal is Algo. 4 ii the setting of Thm. E.1 and Aglobal is Algo. 2 in the setting Thm. D.1
Strongly convex: F satisfy Assumption B. for p > Then there exists lower bound of K such that we have the rate
S N
S SF
Ommin A} exp(
pSKR + (1
pSR +
N VS
General convex: Fe's satisfy Assumption B.2 that we have the rate
Then there exists lower bound of K such
81/2 2
3D2
1/2
Õ( mmiin
R1/2
(SKR)2/4
S 11 N S1/4R1/2
B2
CF 1/2
1/1 )
S
82/22/22//2231
(1
+
N
(SR)
PL condition: F3's satisfy Assumption B.3 for > 0. Then there exists a lower bound of K such that we have the rate
R
RO²
S
RC²
S EF
Ō(ming
A expl
(1
p
PNKR
N
USR
N
VS
Proof. From Thm. E.
we know that with K > max { at x²²
( R² log ( (1
EF F(x") $0
(259)
of
From Lemma H.2
min (A.
2 [ + 1
S-1 SF N VS
(ft - F(x*) O (min
(260)
And so from Thm. D.I we know that
EF(i2) F(x")
(261)
< Ómmin <2, A} Axxp((=
R )
a²
S 2 N
S SF N Vs
+ (1
+
(262)
RNKR
SSR
F.1.2 CONVERGENCE OF FEDAVG SGD GENERAL CONVEX FUNCTIONS
Proof. From Thm. E.I we know that with > max @DD2)
EF (F) < OO(DD)
F(x*)<((())
of
From Lemma H.2 if
min min(A,, (
S-1 SF
EF( F(x*)
+
(263)
N 158
37

---

Published as a conference paper at ICLR 2022
And so from Thm. D.I
know that
min (nin(
S BCF
3
S BCD
(+2)) = Ō
(264)
R
N
VSR
VSKR
N VSR
Next, using that El|d22 x²1l S ( from
Thm. E.1 and Thm. D.1
as well convexity,
EF( F(x*)
(265)
$ v 112 Bll - x²12
(266)
0 1//2 min{ (//222//2 A!
(267)
R1/2
(SKR)
(1
)
N
8
3 1/2 D S1/1R1/2
+ +1
(1-
8 1/1 N
(SR)
(268)
One can pre-run SGD before all of this for constant fraction of rounds that Woodworth et al. 2020a Section 7):
3D A S Ó
oD
S CD
+ +V1 VSR
(269)
R
VSKR
This likely not practically necessary
6
Altogether,
EF(f2) F(x")
(270)
$ /VEIVF( E - 1=
(271)
< Smmin /1/221/2D3/2 3D²
(272)
R1/2
R
32/201/2
S
1/1
22/2 D
S 8u11 D312
+ (1
(273)
(SKR)1/4
N
81/4R1/2
N (SR)
F.1.3 CONVERGENCE OF FEDAVG SGD UNDER THE PL-CONDITION
Proof. The proof is the same as in the strongly convex case.
F.2 FEDAVG + ASG
Theorem F.2. Suppose that client objectives F; 's and their gradient queries satisfy Assumption B.4
Assumption B.6 AAssupttin B.7 Assumption B.5 Assumption B.8 Then running Algo. 1 where
Atneat Algo. 4in the setling of Thm. E. and Aglohat is Algo. in the setting Thm. D.1
Strongly convex: Fe's satisfy Assumption B. for p > Then there exists lower bound of K (same as in FedAvg > SGD) such that we have the rate
2 E.A)
R
82 2
S
S CF
Ō(min{ A} Exp(
(1
PSKR
N
PSR
N
VS
General convex: Fé's satisfy Assumption B.2 Then there exists a lower bound of (same as in FedAvg -> SGD) such that we have the rate
Ö min 2/2 D3322
3D2
2/
oD (SKR) S 1/4 312211222812
S 1/2 CD N (SR)
+
R
(SKR)
5) 1/4
S
3 //22
1/2
+ (1
(1
11/4
(SR)1/4
Proof follows those of FedAvg SGD Thm. F.
38

---

Published as a conference paper at ICLR 2022
F.3 FEDAVG - SAGA
Theorem F.3. Suppose that client objectives Fq's and their gradient queries satisfy Assumption B.4
Assumption B.6 Assumption B.7 Assumptioon B.5 Assumption B.8 Then running AAgo. I where
Alocat is Algo. 4 in the setling of Thm. E. Had Aglobal is Algo. 5 in the setting Thm. D.4
Strongly convex: Fi's satisfy Assumption B. for p. > Then there exists lower bound of K (same as in FedAvg - SGD) such that we have the rale
Ómin S A} expl- max 3. k3 =
μSKR
PL condition: F; 's satisfy Assumption B.3 such that we have the rate
0. Then there exists lower bound of K
(mink A} exp(pp 2/3 )
μ.S
Proof follows those of FedAvg - SGD TTm. F. and using Lemma H.2 with S = N as the algorithm already requires 5
F.4 FEDAVG - SSNM
Theorem F.4. Suppose that client objectives Fy's and their gradient queries satisfy Assumption B.4
Assumption 8.6 Assuuptioo B.5 Assumption B.8 Then running Algo. Twere Alocal is Algo. in
the setting Thm. E.7aadd Aglohal Algo. 6in the setting Thm. D.5
* Strongly convex: Fi's satisfy Assumption B. ffoor p. O. Then there exists lower bound of K (same as in FedAvg > SGD) such that we have the rate
Ómin < A} exp(( max
N
RO²
R)) +
S
UKS
Proof follows those of FedAvg + SGD (Thm. F. and using Lemma H.2 with S = N as the
algorithm already requires >> 5
G LOWER BOUND
In this section we prove the lower bound. All gradients will be noiseless, and we will allow full communication to all clients every round. There will be only two functions in this lower bound: Fj and F2. > 2, then Fi is assigned to the first [N/2] clients and F2 to the next [N/2] clients. there is odd number of machines we let the last machine be Fz)z) 5 || This only reduces
the lower bound by a factor of most N So we look at the case 2.
Let E,, C be values to be chosen later. Let d be even. At high level, &a essentially controls the smoothness of Fj and F2, C is basically constant, and Ç is quantity that affects the heterogeneity, initial suboptimality gap, and initial distance. We give the instance:
Ch
E
Ri(x) - Ezsa
+
xd
(x2411
x22) ) + |0]|2
(274)
2
2
d/2
(2(2)
{2
Σ
(12s
121-1)² 1)2 + 1 ||x
T2i
(275)
1=1
Where F = Fi-Fa
These functions are the same as those used in (Woodworth et al., 2020a Woodworth, 202I) for lower bounds in distributed optimization. They are also similar the instances used prove convex
39

---

Published as a conference paper at ICLR 2022
optimization lower bounds (Nesterov 2003) and distributed optimization lower bounds
(Arjevani &
Shamir 2013).
These two functions have the following property
V Fi (Teven) E span (1, .,, C2i411
Feven E span(ei, e2.
(276)
v F2 (Feven) E span (11, 62 ,
VF (Toda) E span Opanfers (e1, e2,...; e2i-1
Zodd E se. e2,..... .2--13 e2,...,,.2117
(277)
.,,,.., v V2( E e2,, e2i)
What the property roughly says is the following. Suppose oven number of coordinates nonzero. Then we can only use gradient queries of F1 to access the next coordinate. After client 1 queries the gradient of F1, it now has odd number of unlocked coordinates, and cannot unlock any more coordinates until a communication occurs. Similar is true the number of unlocked coordinates is odd. And each round of communication can only unlock single new coordinate.
far have managed to turn
We start by writing out the gradients of Fj and F2. Assume that d is even. Then:
[+)())] t22 pai
(278)
(V) Cl2ra pard
(279)
[i)]; = E2 - x2-1) + pad, i odd, 2 siidd-
(280)
[zVF( -22(1141 - xi) + pa, i even, 2 25isd-1
and
[V2(2)) f2(22 - 211 pad
(281)
[T)(aa (a xa-1) p.dd
(282)
[2)]==)] -2( x2. + pad odd, < d-1 [V = (2(1; - 11,-1) + μmd even, 2 2 d-1
(283)
We define the class of functions that our lower bound will apply to. This definition follows (Wood worth et al., 2020a Woodworth 2021 Carmon et al. 2020):
Definition G.1 (Distributed zero-respecting algorithm). For vector v, let supp(v) { (1....,d) d) Us * 0}. We say that an optimization algorithm distributed zero-respecting for any i, k,r, the k-th iterate on the i-th client in the r-th round LiA satisfy
(r)
supp
C
U DSK<kk
supp (FF((())))
U
Su
(284)
Broadly speaking, distributed zero-respecting algorithms are those whose iterates have components in only dimensions that they can possibly have information on. As discussed in (Woodworth et al. 2020a), this means that algorithms which not distributed zero-respecting are just "wild guessing" Algorithms that are distributed zero-respecting include SGD, ASG, FedAvg, SCAFFOLD, SAGA, and SSNM.
Next, we define the next condition we require on algorithms for our lower bound.
Definition G.2. We say that algorithm is distributed fistance-conserviigg if for any i, k, we have for the k-th iterate on the i-th client the r-th round ((r) satisfies ||a:5,7 x 112 < (c/2)
xx 11112 +12++ Em || - x [|3] where x² := arg min, (x) and x= arg min, F(x) and Tiii the initial iterate, for some scalar parameter
Algorithms which do not satisfy Definition 5.2 for polylogarithmic e problem parameters (see 2 are those that move substantially far away from x=,, even farther than the x! 's are from x*. With this definition in mind, we slightly overload the usual definition of heterogeneity for the lower bound:
G.3. A distributed optimization problem is heterreeetoo if maxie[N] sup (x) VF(x)|12 S <², where we define := {x ||z - x²1 5 (c/2)([ x² 112 Di=1 ||aiiit x" (1]) for some scalar parameter
Definition
40

---

Published as a conference paper at ICLR 2022
While convergence rates in FL usually proven under under/Assumption B.5 the proofs be converted to work under Definition G.3 as well, so long as one can prove all iterates stay within as defined in Definition G.3] We show that algorithms satisfy Definition G.3Jas well as result (Thm. E.I] Thmm D.3 Thm. D.I Other proofs of FL. algorithms also satisty this requirement, most notably the proof of the convergence of FedAvg in Woodworth et al. (2020a).
Following Woodworth et al., 2020a), we start by making the argument that, given the algorithm is only unlock one coordinate at time. Let E; = se,, ei).
distributed zero-respecting, and Eg be the null span. Then
Lemma G.4. Let ă be the output of a distributed zero-respecting algorithm optimizing = 1/2 {FF F2) after R rounds of communication. Then we have
supp(E) E ER
(285)
Proof. A proof is in Woodworth al. (2020a Lemma 9).
We now compute various properties of this distributed optimization problem.
G.1
STRONG CONVEXITY AND SMOOTHNESS OF F1,1,F2
From Woodworth 22021 Lemma 25), as long as la S 8-
4 have that F, F1, F2 are 8-smooth and
ju-strongly convex.
G.2
THE SOLUTIONS OF F, Fi,
First, observe that from the gradient of F2 computed in Eq. (281)
23 = arg min, F2(x) = Ō. Next
observe that from the gradient of F1 computed in Eq. (278)
sf arg min, Fi(x) f25 61. Thus
| 0 and | 1
From
Woodworth
2021
Lemma 25), if we let a =
V1 262
a-1 a+1
C = - q. then
(1 (1-9)-(199)
||2" 11
G.3
INITIAL SUBOPTIMALITY GAP
2021 Lemma 25), F(0) F(x*) ) & gl2d"
From
Woodworth
((14)
G.4
SUBOPTIMALITY AFTER ROUNDS COMMUNICATION
From
Woodworth 2021
Lemma 25), F(t) F(**) 2 16(1 (01-g)"1 (1--)) -1
pg
long as
log 2
(lgg)
G.5 COMPUTATION OF ?
We start by writing out the difference between the gradient of Fi and F2, using Eq. (278) and
Eq. (281)
d-
[VF V Eg- 22 - + Cg(Caa Ia + x2-1)² + Σ
(a x;-1)²
(286)
We upper bound each of the terms:
(I++1 x1-1)² = 201412;-11 + + S 2a + 2
(287)
'We do not formally show it for SAGA and SSNM, as the algorithms functionally the same SGD and ASG under full participation.
41

---

Published as a conference paper at ICLR 2022
(- + 22 21) == = 2² +22+1 +2 -2{x2 2fx1 -x
(288)
1 382 + +32 301
(289)
(Cra - x2 + x2-1)² =
2Cx + 2CI - 2r-1
(290)
<C' + 2n + 202-1 + 2Cx2-1
(291)
So altogether, using the fact that C 1
1 2 [F(
[=2
(292)
d-1
$3 + 3x2 + अ + 3x + 3x
+ Σ
2x + 2x
(293)
1=2
< " + 7||=/|2
(294)
S $35² + 14/l - x²1 + 14|2"113
(295)
2²99
Lg 112
S 55²² + 28c (1 - 2) - q2)
28c
(296)
Next we use Definition G.2 which says that || - x² || S 2] Fimit - x²112+ + |
x 1). For
ease of calculation, we assume c 2 1. Recall that we calculated
||x0|| S (1 (1-9)((1-g2) (because
220
< g < 1), | 12 = O, || 55 w²
1
- VVF())) s 35² + 24c||="|| 112 + Tc||==]12 [
(297)
220
Tolf6²
< k3 + (1 2- 92) +
(298)
Altogether,
24c8252 22
Telg8²
$32 + (1 - 9) (1
(299)
112
G.6 THEOREM
With all of the computations earlier, we are now prepared to prove the theorem.
Theorem G.S. For any number of rounds R. number of local steps per-round K, and e)- heterogeneity (Definition 5.3), there exists a global objective F which is the average of two 3-smooth Assumption B.4 and pl2 O)-strongly convex (Assumption B.1y quadratic client objectives Fi and F2 with an initial sub- sub-optimality gap of A, such that the output & of any distributed zero-respecting Definition 5.1 and distance-conss ceatanc-coonerving algorithm DDefmition 5.2)
satisfies
Strongly convex: F(2) F(x*)* 2 M(min( (/3////////////////// exp(p)///RR # > O, and
(10))///)//)x)) R/).).) when
General Convex F(t) F(x*) (R
when p
Proof. The convex case:
By the previous computations, we know that after R rounds.
2²29²
F(0) - F(x") 2 16(1 (1 q2) 2R
(300)
22
||0112 < (1 (1- -)2 - -2)
(301)
24c 22
Telg
(x) ( < 36552 +
(302)
(1 ②) (1 92)
42
42

---

Published as a conference paper at ICLR 2022
To maintain the property that ||_(0) x² || ||20|| D and Definition G.3.
Choose Ç s.t.
(1 q) x²)<²
c²
(1 q) g²)
Ç² = min
(303)
c2
c22
q²
For an absolute constant V.
This leads to (throughout we use
_
(1-9)² 24
Woodworth 2021 Eq 769))
8
F(6) - F(x))
(304)
u²²99²
2 16(1 - 9)2 - q²) Q
(305)
2 smmin 2 p(l 9) 2 [1 )22 2²²²
-22 p(l -L) (2(1--4)1 (1)
q²
q 2t
dg
q²
16(1 - q)3
q3)
(306)
(1 (2- 1(1
31 g²
2 zumnn
(307)
2029
( 9)
1n(1
q)
D2
q²
2R
(308)
4el24²
g²
16(1 - 9) (1 (1 q²)
<²9
uc²
( -9) nD² 2n
2 m 3182(1 )2)
}9
(309)
16el
64el2
4) 16
(310)
We choose
/ = 6IR
8
which ensures a 2 2. So noting that (1 (1-g²) = (1 =--=")(1-=11
g) + 9) $ (1+g)
1 + a+1
20
a+I
F()) - F(x*)
(311)
2 mminf 2²
0K 1
a
+
n²²
uC²
a+1 1
nD2
}q
(312)
32l
+1
20
16cl
64cl2
a + 1
20
16
Q
1a
10+1 + 1
uC²
a a+11
DD
a +
2 mmin|
exp(
2R log
326
+
1
20
16ol2
64el
@ +
2a
16
0:
(313)
nC²
nD²
4R
2 min!
exp(
(314)
6462" 16el2"
64el2
16
So.
F()) F(x*)
(315)
2 vmin (2 u²2 n6² 1
ND2
8RvP
11/2
} exp(-
(316)
6462" 16el 64cl2
362
16
Vlz
2 A(min) ② 2
$
lzD
R² =
(317)
1
dnR R3
5²
l2D
})
(318)
d22 R2
(319)
Where we used c > 1. Setting & = Ominn マ appropriate constants chosen), Which altogether gives us
}) (which will ensure that & < 8- with 4
CD
3D2
((t))F(z*)+ 2 Q(min(
})
(320)
R5/2
R2
Strongly Convex Case:
43

---

Published as a conference paper at ICLR 2022
By the previous computations, know that after R. rounds,
u²²0²
F(Ø) F(x)) 2 16(1 9) - - 2R
(321)
9l2l
F(ē) - F(x)) $ 4(1 -q)
(322)
22c Telge²
[V) (>2(2)] & 33252² +
(323)
(1 )) - 92)
112
To maintain the property that F(t) Fx*') A and that [F((x)) encountered during the execution of the algorithm,
[F2(x)]13 C² for all
Choose { s.t.
2 (1 9) 22)
2²² (1 4
Ç² = y min
(324)
2
c2
cl
q22
For some constant v.
Again using H/2 = (ف=ي and following the same calculations as in the convex case, we use the fact
that 9p & 8, and that is possible to choose f2 s.t. 24 S f2 S 8= which ensures 3 2 2.
4
F()) - F(x*)
(325)
2²
22
(326)
16(1
2)
q2)
5²
ps²
us²
( A exp(-
4R
mmnn
(327)
6482
16el
64elz
a
(328)
We use 9p S 3 and because it is possible to choose & such that 2p S lg S 8-M Eq. 800), which ensures a 2 and
Woodworth
2021
1
36,
( F(x*)
(329)
2² n²² 2 n 1 1/1/2, A} exp(
SR
(min
(330)
l
cl
cly
l2
Vl2
uS²
H 1/2
8R/F1 ))
2 A(min
A} exp(
(331)
cl
Vt2
Next note that lg < B and lg >
Woodworth
2021
Eg 801), which gives us
3/222
18R
F - F(x)) 2 Mmin)
A} exp(
Vk )
(332)
e/35/2
H TECHNICAL LEMMAS
Lemma H.1. Let
K
(0)
gi,k
(r)
(333)
SK iES, k=1
Given Assumption 8.6
Assumption B.5
and uniformly sampled clients per round,
K
VF(x - 0²
S - 1 5
9ik
+ (1
(334)
SK
SK
N - 5
VES.
1=1
44

---

Published as a conference paper at ICLR 2022
instead the clients are arbitrarity (possibly randomly) sampled and there is no gradient variance,
9itk
=
(335)
SK iES,
k=1
Proof.
K
Tf(x 2,) VF
(336)
SK
iES, k=1
= =
Σ
[F((x) VF(x) Es.l
-
(337)
SK
iES,
iES,
s 1 Σ
VF(3) - SK
VF(())
B Bl (+)
(338)
iES,
(339)
Where the first inequality uses the fact that E[X = Var(X) + E[X]² and the second equality uses the fact that the variance is i.dd across and k. Note that EE| V (æ; 2.) VF((2)]1 - o² by Assumption B.6 On the other hand by AAssmmption B.5
S 1 Vx(()) VF(*] S
S S-1 $
E
Σ iES,
-F()) S (1
N
N 1 8
(340)
So altogether
o²
S S-1 1 2 N
(((;)))V(()11)
+(1
(341)
SK iES,
SK
The second conclusion follows by noting
S Σ
- VF(C)-
1 Σ VF(()) VF(=)]]
(342)
S
iES.
iES.
Lemma
H.2. Let u,v be arbitrary (possibly random) points.
Define
F(z)
Eies KK-1 f(x; where bi DD Let
SK
arg min F(x)
zE(u,v}
Then
E[F(w) - F(x")]
(343)
S S-1 Gr
<min(F(u) F(x*), F(v) F(x*)) +4 VSK +4
(344)
N N- 1ss
and
- [[F(w)=((z'))
(345)
(in((F F(x"), EF(v) F(z)) +4 OF + 4
S-1 CF
(346)
VSK
N VS
Proof. Suppose that F(u) + 2a F(v). where 0. Then,
E[F(w) F(x*)] P( (F)) F(z")) + P(w (F(())) (F()))))))))
(347)
45

---

Published as a conference paper at ICLR 2022
Substituting F(u) = F(u) + 2a,
( - P(w - (F(u - F(x")) + P(w - ()((w)) + 2a - F(x)))
(348)
< F(u) - F(x*) + 2a
(349)
Observe that ( < of 3K
+ (1 N-1 3
by Assumption B.7 and
Assumption B.8
Therefore by Chebyshev's inequality,
P((F(z) 2 a) - //2
/
1 of
N 1 (
S S 1 2
+ +(1
(350)
SK
Observe that
P(w= u) F(u) + + P(F(() < F(v) a)) a)
(351)
-/2 SK
2 of
5 N ,
+(1 (1
5
(352)
And so it is also true that
B[F(w) F(x")] - F(u) - F(x') + 22 2a
(353)
< Fu) F(x") + 20 2/2 SK
2 of
S - 1 G
(
+(1
(354)
N S
2
S-1 1 S
= F(u) - F(x) + - SK
+ (1
(355)
N --1
S
Therefore altogether we have that
- F(u) - F(x*) + max min
4 - OF
+ +11-
5-1
2
58
)
(356)
a SK
N N-1 1 S
So by maximizing for
4 2
S
1 2,
2 2(
S 5-1 N
LE S
+ (1
N 5
= 2a = a=
+ (1
(357)
a SK
5
5K
which gives us
([F(w)-F(zz)) =(u) + OF
S-1 SF
+4 1
(358)
VSK
N -VV
Then proof also holds if we switch the roles of u and v, and so altogether we have that: if F(u) F(u).
<
B[F(w) - ([[[)>F(="")) S F(u) - F(x²) + 4 OF
+ +4
1
S-16.
(359)
VSK
1
N
if F(u) > F(c).
s(() +4 OF
S S-1 1 CF
4 1
(360)
VSK
VS
implying the first part of the theorem.
((F(w))F(z') -io
F(x')) 4 OF
+ + 1- N- 1--1V 15
S- 1 CF
VSK
(361)
For the second part,
[[min(F(u)) - F(**), F(v) - -(o))))0)= S F(u) - F(x*)
(362)
S <min(EF(u) F(x*), F(u) - -F(x))
(363)
and then
(EF())EF(v) (F=))) F()) - F(x*))]= SToOsER F(u) Flx*) A min(EF(u)) - F(x"), EF(()) - FF(x)))
(364)
(365)
46

---

Published as a conference paper at ICLR 2022
1 EXPERIMENTAL SETUP DETAILS
1.1 CONVEX OPTIMIZATION
We empirically evaluate FedChain on federated regularized logistic regression, Let (Ii Vi.s) be the jth datapoint of the ith client and n, is the number of datapoints for the i-th client. We minimize
Eq. (1) where
Vi. log(w' ( - (1 Vi.))og((1 - w ((,)a)))))) + 1 1|0l1?
F((w)
Dataset. We use the MNIST dataset of handwritten digits (LeCun et al. 2010). We model federated setting with five clients by partitioning the data into groups. First, we take 500 images from each digit class (total 5,000). Each client's local data is a mixture of data drawn from two digit classes (leading to heterogeneity), and data sampled uniformly from all classes.
We call federated dataset X% homogeneous if the first X % of each class's 500 images is shuffled and evenly partitioned to each client. The remaining (100 - 1% is partitioned as follows: client i 5)) receives the remaining non-shuffled data from classes 2i and 2i - 1. For example, in a 50% homogeneous setup, client 3 has 250 samples from digit 4, 250 samples from digit 5, and 500 samples drawn uniformly from all classes. Note that 100% homogeneity is not the same thing as setting heterogeneity Ç = 0 due to sampling randomness; we use this technique for lack of better control over Ç. To model binary classification, let even classes represent O's and odd classes represent I's, and set K 20. All clients participate per round.
Hyperparameters. All experiments initialize iterates at 0 with regularization μ = 0.1. We fix the total number of rounds R (differs across experiments). For algorithms without stepsize decay, the tuning process is as follows.
We tune all stepsizes in the range below:
(10-3, 10-2.1 2.5
10- 105 10-1
(366)
We tune the percentage of rounds before switching from Asocal to Aglobal (if applicable)
{10-3 101111110000 1.625 100100-....
0.875 10.07
10 10-0.5
(367)
For algorithms with acceleration, we run experiments using the more easily implementable (but less mathematically tractable for our analysis) version Aybat et al. (2019) as opposed to Alloo..
For algorithms with stepsize decay, we instead use the range Eq. (367) to decide the percentage of rounds wait before decreasing the stepsize by half denote this number of rounds as Raesay- Subsequently, every factor of 2 times Raecay we decrease the stepsize by half.
We use the heuristic that when the stepsize decreases to 1// K, we switch to Aglobal and begin the stepsize decay process again. All algorithms are tuned to the best final gradient norm averaged over 1000 runs.
I.2 NONCONVEX OPTIMIZATION
1.2.1 EMNIST
In this section we detail how we use the EMNIST (Cohen et al., 2017) dataset for our nonconvex experiments, where the handwritten characters are partitioned by their author. In this dataset, there are 3400 clients, with 671. 671,58; ,,885 images in the train set and 77,483 in the test set. The task is to train convolutional network with two convolutional layers, max-pooling, dropout, and two dense layers as in the Federated Learning task suite from (Reddi et al. 2020).
Hyperparameters. We set R 500, and rather than fixing the number of local steps, we fix the number of local client epochs (the number of times a client performs gradient descent over its own dataset) 20. The number of clients sampled per round is 10. These changes were made in light of the imbalanced dataset sizes across clients, and is standard for this dataset-task (Reddi et al. 2020
Charles & Konečný 2020 Charles al. 202T). b. For all algorithms aside from (M-SGD), we tune
47

---

Published as a conference paper at ICLR 2022
7) in the range {0.05, 0.1, 0.1.0.1.,,,..,,0.,,,,,, 0.25). We tune the percentage of rounds before switching from Atocal to Aglobal in {0.1, 0.3, 0.5, 0.7,0.7..9.. 0.9), where applicable.
We next detail the way algorithms with stepsize decay
We tune the stepsize in {0.1, 0.2, 0.3, 0.4, 0.5}. Let Riteca be the number of rounds before the first decay event. We [(0.1R, 0.275R, 0.45R]]- Whenever the number of passed rounds is power of 2 of Rassay- we halve the stepsize/ After R' rounds have passed, we enter Aglobal. where we tune R' E [[0.5R, O.7RR 0.9R]]. We restart the decay process upon entering Aglobal-
tune Raecay
For M-SGD we tune
1 E {0.1, 0,3,003,,43444403
and
Raecay = 10 1025 R, 10-1..5 R, 10 0.875
10-05875 R, 10 R}
For stepsize decaying SCAFFOLD and FedAvg, tune 1 (0.1, 0.3, 0.4, 0.5) and Raeca E [[0.1 R, 0.275R, 0.45R)) When evaluating a particular metric the algorithms are tuned according to the mean of the last evaluated iterates of that particular metric. Reported accuracies also the mean of the last evaluated iterates, as the values mostly stabilized during training.
1.2.2 CIFAR-100
For the CIFAR-100 100 experiments, we use the CIFAR-100 (Krizhevsky) 2009) dataset, where the handwritten characters are partitioned via the method proposed in (Reddi et al. al.| 2020). In this dataset, there are 500 train clients, with a total of 50,000 images in the train set. There are 100 test clients and 10,000 images in the test set. The task to train ResNet- 18, replacing batch normalization layers with group normalization as in the Federated Learning task suite from (Reddi et al. (2220). We leave out SCAFFOLD in experiments because of out of memory issues.
Hyperparameters. We set R = 5000, and rather than fixing the number of local steps, we fix the number of local client epochs (the number of times a client performs gradient descent over its own dataset) to 20. 'hee number of clients sampled per round is 10. These changes were made in light of the imbalanced dataset sizes across clients, and is standard for this dataset-task (Reddi cet al. 2020 Charles & Konečný 2020 Charles et al. 2021). For all algorithms we tune 7) in 0.5, Algorithms without stepsize decay tune the percentage of rounds before switching to Aglabul in {0.1, 0.3, 0.5, 0.7, 0.9). Algorithms with stepsize decay (aside from M-SGD) tune the number of rounds before the first decay event in {0.1, 0.275, 0.45) (and for every power of of that percentage, the stepsize decays in half), and the number of rounds before swapping to Aglohal in {0.5, 0.7, 0.9) if applicable (stepsize decay process restarts after swapping). M-SGD tunes the number of rounds before the first decay event (0.01, 0.0237, 0. 0.0562, 0.1334, 0.3162). We tune for and return the test accuracy of the last iterate, as accuracy was still improving as we trained.
{0.1, 0.2,
J ADDITIONAL CONVEX EXPERIMENTS
In this section, we give supplemental experimental results to verify the following claims:
1. Higher K allows (1) accelerated algorithms to perform better than non-accelerated algo- rithms, and furthermore (2) allows us to run Aleall for one round to get satisfactory results.
2. Our FedChain instantiations outperform stepsize decaying baselines
J.1 VERIFYING THE EFFECT OF INCREASED K AND =
Our proofs of FedChain all also work if we run Atocal for only one communication round, so long as K is sufficiently large (exact number is in the formal theorem proofs). In this section we verify the effect of large K in conjunction with running Avcaal for only one round. The setup is the same in except we tune the stepsize 17 in a larger grid:
App. 1.1
7) E {10- 3 10 2.5 10 2, 10 1.5 10-1,,11111111111111 10 0.5 100)
(368)
The plots are in Fig. 3 For algorithms that are "I-X-+Y", we run algorithm X for one round and algorithm Y for the rest of the rounds. These algorithms are tuned in the following way. Algorithm X
48

---

Published as a conference paper at ICLR 2022
Orsteet Fanmes
Figure 3: We investigate the effect of high K (K = 100). "1-X-+Y" denotes a chained algorithm with X run for one round and Y run for the rest of the rounds. Chained algorithms, even with one round allocated to Aocal, perform the best. Furthermore, accelerated algorithms outperform their non-accelerated counterparts.
50% atdde
Figure 4: The same as Fig. 2 except we include stepsize decay for baseline algorithms. Chained algorithms still perform the best.
has its stepsize tuned in Eq. (368) and Algorithm Y independently has its stepsize tuned in Eq. (368) We require these to be tuned separately because local update algorithms and centralized algorithms have stepsizes that depend on K differently if K is large (see, for example, (Tm. D.T and Thmm. E.T).
The baselines have single stepsize tuned in Eq. (368) These tuned for the lowest final gradient norm averaged over 1000 runs.
Overall, we see that in the large K regime, algorithms that start with local update algorithm and then finish with an accelerated centralized algorithm have the best communication complexity. This because larger K means the eтror due variance decreases, for example as seen Thm. F.2 Acceleration increases instability (if one does not perform carefully calibrated stepsize decay, as we do not in the experiments), so decreasing variance helps accelerated algorithms the most. Furthermore, single round for Alecal suffices to see large improvement as seen in Fig. 3 This is expected, because both the "bias" term (the A exp(- RvK) term in Thm. E. and the variance term become negligible, leaving just the heterogeneity term desired.
*
J.2 INCLUDING STEPSIZE DECAY BASELINES
In this section, we compare the performance of the algorithms against learning rate decayed SGD, FedAvg, ASG, and SCAFFOLD. We use the same setting as App. for the decay process and the stepsize. In this case, we still see that the chained methods outperform their non-chained counterparts.
49


Reviews:
[{"review_id": "RObtSDWX3ly", "reviewer": "Reviewer_AN2w", "summary": "", "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": "The paper tries to answer a theoretical problem in federated optimization.\nThe paper proposed a multi-stage algorithm to match the lower bound established by Woodworth for intermediate heterogeneity levels.\nIn particular, they first run a local method up to reach certain error floor and then switch to a centralized method for the rest steps.\nThe method is intuitive and supported with theoretical analysis assuming strongly-convex objective functions.\nThe result is new for FL.\nThe proof seems correct and the writing is clear and easy to follow.\nThey also demonstrate the effectiveness of their method in mage classification tasks.\n\nI have the following concerns:\n1. In the proof of Theorem 1, the $n$ in the expression of $\\Phi$ and $\\eta$ of the first stage should be $N$. \n2. I find that both Theorem 1 and Theorem 2 require sufficiently large $K$, which is important to make the $\\widetilde{O}(\\frac{\\beta\\zeta^2}{\\mu^2R^2})$ dominate the error (e.g., see (25) and (29)). Besides, Section 3.1 provides a two-stage instantiation of proposed algorithm. It first lets each device run Local SGD and then run SGD to approach the local optimal point. The two results make me to wonder, why not we first run pure local training, letting each device obtain a local minimizer, and the run (accelerated) SGD. This is equivalent to let the first stage be a pure local training rather than local SGD. In this way, the communication cost is saved as much as possible, since it only requires one communication round. By contrast, current result (Theorem 1 and Theorem 2) requires $R/2$ rounds. \n3. The paper only analyzes the strongly-convex case and omit the generally-convex case. Woodworth et al. (2020a) provides analysis for Local SGD under both cases. Considering the analysis method used in the paper is just to combine convergence rates of outputs from two (super)stages, I think it is not hard to extend the result to the generally-convex case. However, it is quite interesting and unclear to see the theoretical performance of proposed multistage algorithms for non-convex functions. \n4. I don’t quite see why the work explains empirically-successful stepsize decay methods in FL, which is declaimed in the abstract. I feel it is exaggerated and should be supported with more evidence. In my opinion, what makes the proposed algorithm have a better dependence on $\\zeta^2$ is not the stepsize decay but the switch to centralize methods. It supports my point that most of theorems is derived under constant small step sizes. The discussion in Appendix A is weak and farfetched. I think the author should support the claim with other suppport analysis, for example, analysis for simple cases or additional experiments to show the adaptive optimization methods indeed swtich to a centralized counterpart. \n\n============================================\n\nI have read the authors’ responses as well as other reviewers’ feedback.\nAt the moment, I think the proposed two-stage method is more like a trick rather than a universal method that can be implemented to other scenarios. There are two reasons supporting my thought.\nFirst, the author can’t extend the theory to general convex and nonconvex settings, which implies the method replies on the strong-convexity, which brings great convenience for analysis.\nSecond, the author didn’t justify the necessity of the first-stage. From the author’s feedback (the added footnote 3), using one-round even has better performance. In this case, the two-stage algorithm is reduced to the last stage which is the accelerated SGD. Hence, it is not surprising it has so good performance. At this moment, I feel the proposed method is more like a trick rather than a universal component.\nTherefore, I think the paper could provide limited insights for future work.\n\nI think the author could improve their work in the following directions: (i) provide analysis for general convex and nonconvex settings, (ii) find a more distinguishable method to close the gap. For example, a softer decay of local update length.", "summary_of_the_paper": "The paper proposed a provable multi-stage algorithm to match the lower bound established by Woodworth for intermediate heterogeneity levels in federated optimization.\n", "summary_of_the_review": "The theoretical result is new in FL.\nThe proposed method has strong empirical performance in typical datasets.\nTheir match the lower bound and  fill the blank. \nThough it has some limitations, I think it is worth to be published.   \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A_423Yyqcp", "reviewer": "Reviewer_y87n", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "- **Writing**\n\nIn general, the writing of the main paper is good and well organized, which is not the case for the appendix, where there are many typos and missing details in the proofs.\n\nI would point the following statement in the main paper. At the end of page 4, it is mentioned that $\\zeta_*^2$ is scaled by exponentially decaying term in the lower bound (6), while $\\zeta^2$ is scaled by $\\frac{1}{R^2}$ in the rate of FedAvg (6). Then, Theorem 1 claims to improve exponentially the dependence on heterogeneity from $\\frac{\\zeta^2}{R^2}$ to $\\frac{\\zeta^2}{R^2} \\textrm{exp}(-\\frac{R}{\\kappa})$. What about the rate of SCAFFOLD, where instead of $\\zeta^2$ it is (smaller term) $\\zeta_*^2$ and dependence is $\\frac{\\zeta_*^2}{\\beta^2} \\textrm{exp}(-\\frac{R}{\\kappa})$ ?\n\n\n- **Correctness and optimality of the rates.**\n\nFirst, the sub-optimality rates of FedAvg$\\to$SGD and FedAvg$\\to$ASG given in Table 1 are slightly different from those shown in Theorems 4&5. For example, for FedAvg$\\to$ASG, it $\\min(\\Delta, \\frac{\\beta\\zeta^2}{\\mu^2 R^2})$ in Table 1, and $ \\frac{\\beta\\zeta^2}{\\mu^2 R^2}$ in Theorem 5 (see (27)). More importantly, I failed to get the claimed sub-optimality rates from the proof.\n\nLet me provide some details for the proof of FedAvg$\\to$ASG. From the proof of Theorem 5, we get (28) (ignoring constants and poly-log factors) by running FedAvg.\n$$\n\\mathbb{E}[F(x^{(1)})] - F(x^*) \\le  \\Delta_1 := \\beta \\\\,\\textrm{exp}(-\\frac{KR}{\\kappa})\\||x^{(0)} - x^*\\||^2 + \\frac{\\sigma^2}{\\mu N K R} + \\frac{\\beta \\sigma^2}{\\mu^2 K R^2} + \\frac{\\beta \\zeta^2}{\\mu^2 R^2} \\qquad (28)\n$$\n\n\nThen switching to ASG, we have (31)\n$$\n\\mathbb{E}[F(x^{(2)})] - F(x^*) \\le  2\\Delta_1 \\\\,\\textrm{exp}(-\\frac{R}{\\sqrt{\\kappa}}) + \\frac{\\sigma^2}{\\mu N K R} + \\frac{\\beta \\sigma^2}{\\mu^2 K R^3} \\qquad (31)\n$$\n\nThe proof is terminated by plugging $\\Delta_1$ in (31). However, it is easy to see that then we have (among others) the term $\\beta \\textrm{exp}(-\\frac{K R}{\\kappa}) \\textrm{exp}(-\\frac{R}{\\sqrt{\\kappa}})$, which remains even in the case when $\\zeta^2=\\sigma^2=0$. On the other hand, the rates shown in Table 1 and in Theorem 5 vanish in this case. Furthermore, if we let $\\zeta^2=\\zeta_*^2=0$, then the lower bound becomes $\\frac{\\sigma^2}{\\mu N K R}$, while the actual rate of FedAvg$\\to$ASG includes other terms like $\\frac{\\beta \\sigma^2}{\\mu^2 K R^2}\\textrm{exp}(-\\frac{R}{\\sqrt{\\kappa}})$.\n\nA similar argument can be made for FedAvg$\\to$SGD in the proof of Theorem 4 when plugging (24) into (26).\n\nCould you please provide complete proofs of the theorems, addressing the above points, either in the rebuttal or updating the paper (if possible)?\n\n\n- **Technical novelty**\n\nMost of the analyses heavily use the results of previous works. Besides, the analyses of the central claims of Theorems 4 (1 in the main paper) and 5 (2 in the main paper) are direct concatenations of the previous rates. I did not find anything new in the analyses.\n\n- **Experiments**\n\nExperiments do not seem to be aligned with the given theory.  In the convex experiment in Figure 2, the best performing method is SCAFFOLD$\\to$SGD, which (i) has an inferior rate than, say SCAFFOLD$\\to$ASG, and (ii) as far as I get, the presented theory for SCAFFOLD$\\to$SGD is the same as FedAvg$\\to$SGD, which is not the case for SCAFFOLD versus FedAvg. It is mentioned that the good performance of SCAFFOLD$\\to$SGD can be attributed to small $K$ in the experiment. Do you have an experiment with large $K$ with the predicted behavior?\n\nThe non-convex experiment in Figure 3 is strange too. Multi-staging does improve over the two-stage method, and in the second plot, FedAvg almost reaches to FedAvg$\\to$SGD.\n\n\n\n\n\n\n\n", "summary_of_the_paper": "It is known that if the level of heterogeneity is sufficiently high, then accelerated minibatch SGD is optimal for federated optimization matching the known lower bound of (Woodworth et al., 2020a). On the other hand, when the level of heterogeneity is very low, then FedAvg/LocalSGD outperforms the former in terms of communication complexity and needs only a few communication rounds given enough local computation. This paper *proposes* a multi-stage optimization procedure and *claims* that it nearly matches the lower bound for all heterogeneity levels.", "summary_of_the_review": "The paper provides a clear intuition on why multistage algorithms are useful in practice. However, I made several critical comments in my main review regarding the correctness of the results, the technical novelty of the proofs, and the connection between experiments and theory. As of now, the paper seems weak (at least the way it is presented now). However, I am looking forward to reading the authors' rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "48pvapSQwfA", "reviewer": "Reviewer_ZoaG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please see the \"Summary Of The Paper\" for the brief summary.\n\nFrom the theoretical point of view, in the strongly convex case, multistage algorithms indeed outperform the other methods like SCAFFOLD or minibatch algorithms.\n\nFrom the empirical perspective, this paper considers the strongly convex case with logistic regression and the nonconvex case with neural networks. It also compares many algorithms, and I think the experiment part is generally enough.\n\nHowever, I think this paper suffers from the following weaknesses:\n\n1. In my point of view, neither the algorithm itself nor its analysis is interesting enough. The algorithm seems like a direct combination of different algorithms and the proof is also very straightforward: directly applying and combining the convergence analysis from the algorithm algorithms.\n\n2. Missing important citation \"Federated Accelerated Stochastic Gradient Descent\" by Honglin Yuan, Tengyu Ma. This paper presents accelerated local methods. The results are not discussed in Table 1.\n\n3. Although in the contribution part, the author claims: \"This multistage has the added benefit of not requiring the knowledge of the noise bound $\\sigma^2$, the heterogeneity $\\xi^2$, or the initial distance to the optimum $\\Delta$.\" However, in my understanding, the algorithm also needs to know the heterogeneity parameter $\\xi^2$ in advance in order to choose the appropriate local steps $K$ in the first stage. Otherwise, I can choose all the functions $f_i$ to be the same thus $\\xi^2 = 0$, and choosing $\\sigma^2 = 0$. Theorem 4 and 5 imply that if $\\xi^2 = \\sigma^2 = 0$, it requires 0 communication rounds to achieve 0 training loss. Without knowing the heterogeneity parameters in advance, it seems impossible to do that. Also, please do not use \"large enough $K$\" in the theorems (e.g. Theorem 4 and Theorem 5), directly write out the constraints on $K$.\n\n4. For the experiment hyperparameter selection, I think that the comparison is not very fair. In Appendix K \"Experiment Setup Details\", for single-stage algorithms, the global learning rate $\\eta_g$ and the local learning rate $\\eta_l$ are the same and they do not change during the training procedure. However, for two-stage algorithms, the learning rate for the second stage is $K$ times smaller than the global learning rate in the first stage. Even for one-stage algorithms, using two different learning rates may also speed up the training (i.e. we may not need to choose the local learning rate in the second stage to be 0, shrinking global and local LR in the second stage may also work).\n\nBased on the previous concerns, I have the following suggestions and questions:\n1. In terms of the algorithm, I think that it is better to analyze a single algorithm with different learning rates in different stages, e.g. only running FedAvg or SCAFFOLD with different learning rates. As minibatch algorithms are special cases for local step algorithms by choosing $\\eta_l = 0$ (local learning rate), I believe that, in fact, we do not need to choose $\\eta_l = 0$ in the second stage, we just need $\\eta_l$ to be smaller.\n\n2. Please have a check on the paper \"Federated Accelerated Stochastic Gradient Descent\" by Honglin Yuan, Tengyu Ma, and compare the results with multi-stage procedures. Or see if the results from that paper can improve the results for multi-stage algorithms.\n\n3. This paper only analyzes the strongly convex case. I think that adding the analysis (just using different $\\eta_g$ and $\\eta_l$ in different stages, but not choosing $\\eta_l = 0$ in the second stage) for the nonconvex case will make the results more interesting.\n\n4. Please write the theorem more formally. Especially, should specify how $K$ is chosen.\n\n5. I suggest adding some experiment results when keeping the same $\\eta_g$ in different stages, or when decaying $\\eta_g$ for a single algorithm, e.g. for FedAvg, using $\\eta_{1,g} = \\eta_{1,l} = 0.01, \\eta_{2,g} = \\eta_{2,l} = 0.005$.\n\nPlease point out if I have conceptual errors or misunderstandings.", "summary_of_the_paper": "This paper introduces the multistage optimization technique for federated learning applications. Specifically, multistage optimization first uses federated optimization algorithms like FedAvg and SCAFFOLD and converges to some budget, and then uses minibatch algorithms like SGD or accelerated SGD in order to converge faster to a point with very small error. Because centralized methods are optimal when data are heterogeneous and local methods are optimal when data are purely homogeneous, using a multistage optimization technique can incorporate the benefits from both sides.\n\nThe theoretical part is relatively easy. The proof is to choose an appropriate error budget to which federated optimization algorithms converge, and then choose the hyperparameters for the federated optimization algorithms in the first stage and the minibatch algorithms in the second stage, e.g. learning rate, momentum, etc. The theoretical part only includes the convergence results for the strongly convex case.\n\nThe empirical part includes two experiments: logistic regression and neural network, which belongs to strongly convex case and nonconvex case respectively. For each experiment, the authors compare different minibatch algorithms like SGD, AGD, different local methods like FedAvg, SCAFFOLD, and some multistage procedures that combine local methods with minibatch methods. For the convex setting, multistage procedures perform the best, and for the nonconvex setting, multistage algorithms also perform generally the best.\n\n", "summary_of_the_review": "In summary, I think this paper needs to be revised because of the following reasons:\n1. The algorithm and the analysis seem a little incremental.\n2. Missing important citation and comparison.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-17iLUCqva2", "reviewer": "Reviewer_BBMC", "summary": "", "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": "- The paper is not well-written. I had difficulty following some key parts of the paper. see the comments below.\n- The writing of the paper is misleading about the methods. It took me a while to figure out that all the methods and analyses that are covered in the paper require full participation from the clients. First of all, this limits the applicability of the results in any realistic FL scenarios as all FL algorithms across many devices can only work with limited participation. It is important to note that the dominating terms in convergence guarantees would actually change when one looks at the limited participation regime for each of these methods and it is not clear how much of the results translate to that regime. Moreover, this means that the methods that are called SGD, FedAvg, and .... are not what they are called. For example, FedAvg sub-samples the clients in each step and does not use full participation. \n- The assumptions and many other necessary details about algorithms and theorems are unnecessarily relegated to the appendix. This made it very hard to understand the paper and results. \n- I never understood what is difference between $\\zeta$ and $\\zeta_*$. Only one is defined in the assumptions.\n- The StageWeightedAverage step of algorithm 1 has a lot of implications for the communication and memory of the method (as it requires access to the intermediate local updates of the clients). I believe this makes the algorithm impractical.\n- In most of the rates, e.g. eq (9), the non-exponential terms are actually more important/dominant practically than the exponential part. But the authors are mainly focused on the exponential part (which is not dominating in practice). The only reasonable justification for that is assuming $K=\\infty$ or very large, which is not necessarily the case and limits the significance of the results in practice. At the minimum, such a scenario should be elaborated in the paper and authors should refrain from over-claiming the significance of their results.\n- Theorem 3 was very difficult to understand due to the complications in the definition of M-FedAvg and M-ASG.\n- In Theorem 3 it seems that the regime in which the authors have proven the optimality of their methods ($\\zeta^2<\\kappa \\mu \\Delta$) is only a very small fraction of the original target regime ($\\zeta^2<\\sqrt{\\kappa}\\beta\\Delta$) and gets even smaller with higher $\\kappa$.\n- The experimental section is very limited. \n  - It is not very clear to me how the HP tuning is done for each algorithm. what HPs are tuned, and based on what metric and which values. This is of utmost importance because there are many algorithms with many different HPs. And in fact, one selling point of some multi-stage algorithms is their capability to be independent of many constants. But it is not clear to me how it plays in practice and is different from the other algorithms.\n  - There is only one result on the test accuracy and it is very low (far from the state of the art) which makes the results not very convincing. The other result on accuracies in L.2 is not even clear which experimental setup it is referring to.\n\nIt is worth noting that I did not check the proofs thoroughly and in detail, but the claims of the paper seem to be reasonable and correct.\n\nMinor comments:\n- the authors mention that FedAvg's lower bound can only result in lower communication complexity than AC-SA when $\\zeta_*^2\\leq \\mu \\epsilon$. Is it possible to elaborate on how this result is driven?\n- why is there a need to consider a batch size of B for Theorem 3; it seems to only affect the variance.\n\n===================== After reading other reviews and the authors' responses ========================\n- I agree with other reviewers that the novelty of the work is limited, especially given the fact that it applies to limited scenarios and does not even consider the general convex setting (which in my opinion would be more informative as the local updates can converge to different solutions of the same problem). Also, the obtained results are not as strong as advertised (for example as I mentioned Theorem 3 results are far from closing the gap). But at the same time, I commend the authors for improving the paper and including partial participation scenarios. Because of this, I will increase my score to 6.\n- One point that was brought up by reviewer AN2w and I think does actually question the need and possible insight from the results is the fact that you do not need to run two stages with multiple steps, and the local update could all be done in 1 step and then run centralized method afterwards and get the same rate. This limits the importance of the achieved results (basically just changing the initialization for the centralized approach based on a local method could result in an optimal rate). I do not think that this is translatable to more complicated cases (other than strongly convex cases), but the authors have not empirically or theoretically studied the limitations of such an approach.", "summary_of_the_paper": "The paper proposes \"multi-stage FL algorithms\" to bridge the gap between local step methods (that are theoretically known to be optimal for a no-heterogeneity regime where $\\zeta=0$) and SGD type methods that are known to be good for high heterogeneity regimes. The goal of the paper is to find methods that are optimal across all values of $\\zeta$, esp $0<\\zeta^2< \\beta^{3/2}\\Delta/{\\mu^{1/2}}$.", "summary_of_the_review": "Based on the above comments, I believe the paper lacks in the areas of contribution, applicability, significance, practicality, experiments, and writing. As a result, I believe the current version of the paper is slightly below the acceptance criteria. I would like the authors to address the comments above before I can increase the score of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes a 2-stage method for federated learning, first using FL with local steps, followed by a final phase of 'always-communicate' centralized SGD. For the convex case, the paper studies the influence of the data heterogeneity, a key parameter in FL, on the convergence of related schemes. Surprisingly the results of the 2-stage method seem to be basically identical to pure local training followed by the final centralized phase, and almost match the lower bound for communication.

Reviewers liked the interesting aspect of the heterogeneity-induced error floor when the phases are switched, and its impact on the convergence rates, which can be substantial. Downsides are that the analysis only works for strongly convex setting, and the combination of the two methods and proof being relatively straight-forward. Simplicity of the algorithm is a plus, while of the proof depends on novelty, about which reviewers are border-line but positive. 

Deep learning experiments should be expanded, as there the very opposite order of the two phases https://arxiv.org/abs/1808.07217 is more commonly used (i.e. more communication in early phase can help), which should be discussed. Also, in the experiments the tuning of hyperparameters in the single-stage baselines needs to be improved to be more fair, which the authors have started but not fully finished for the Cifar case.

We hope the authors will incorporate the open points as mentioned by the reviewers.
Decision: Accept (Poster)