Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
Authors: Aritra Mitra
Rayana Jaafar
George J. Pappas
Hamed Hassani
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Distributed Optimization
Compression
Heterogeneity
Linear Convergence

Abstract: We consider a standard federated learning (FL) setup where a group of clients periodically coordinate with a central server to train a statistical model. We develop a general algorithmic framework called FedLin to tackle some of the key challenges intrinsic to FL, namely objective heterogeneity, systems heterogeneity, and infrequent and imprecise communication. Our framework is motivated by the observation that under these challenges, various existing FL algorithms suffer from a fundamental speed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at a sub-linear rate, i.e., fast convergence comes at the expense of accuracy. In contrast, when the clients' local loss functions are smooth and strongly convex, we show that FedLin guarantees linear convergence to the global minimum, despite arbitrary objective and systems heterogeneity. We then establish matching upper and lower bounds on the convergence rate of FedLin that highlight the effects of infrequent, periodic communication. Finally, we show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate. Notably, our work is the first to provide tight linear convergence rate guarantees, and constitutes the first comprehensive analysis of gradient sparsification in FL.  

Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
Aritra Mitra
Rayana Jaafar
George J. Pappas Hamed Hassani
Department of Electrical and Systems Engineering {ami famitra20,rae rayanaj, pappasg, hassani] seass wpeas.upem.eduu
Abstract
We consider standard federated learning (FL. setup where a group of clients periodically coordinate with a central server to train a statistical model. We develop general algorithmic framework called FedLin to tackle some of the key challenges intrinsic to FL, namely objective heterogeneity, systems heterogeneity, and infrequent and imprecise communication. Our framework is motivated by the observation that under these challenges, various existing FL algorithms suffer from fundamental apeed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at sub-linear rate, i.e., fast convergence comes at the expense of accuracy. In contrast, when the clients' local loss functions are smooth and strongly convex, we show that Fedl iin guarantees linear convergence to the global minimum, despite arbitrary objective and systems heterogeneity. We then establish matching upper and lower bounds the convergence rate of FedLin that highlight the effects of infrequent, periodic communication. Finally, we show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate. Notably, our work is the first to provide tight linear convergence rate guarantees, and constitutes the first comprehensive analysis of gradient sparsification in FL.
Introduction
In a canonical federated learning (FL) architecture, a set S clients periodically communicate with central server to find global statistical model that solves the following problem [1-5]:
min f(x), where f(x) ZERa
f((z).
(I)
Here, m is the number of clients, fi : IRd + R is the local objective (loss) function of client i, and f=) the global objective function. Some the core distinguishing tenets of the FL paradigm are as follows [1-5]. First, due to privacy considerations, clients cannot directly share their local training data with the server. Second, differences in the clients' data-sets may cause the clients to have non- identical loss functions with different minima this is known as statistical or objective heterogeneity. Third, due variability hardware (CPU, memory) and power (battery level), i.e., due to systems or device heterogeneity, the client devices may have different computation speeds; in particular, this may lead to slow and straggling devices that affect convergence guarantees. Finally, communication. efficiency is major concern, dictating the need to reduce the number of communication rounds, and also the size of the messages transmitted each round. The above considerations pose unique technical challenges that we aim to address in this paper.
In typical FL setting, to reduce the number communication rounds, clients perform multiple local training steps in isolation before communicating with the server. Due to such local steps. the popular
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

FedAvg algorithm suffers from "client-drift phenomenon" under objective heterogeneity [6-11]: the local iterates of each client drift-off towards the minimum of their own local loss function, leading to slow convergence rates. For analysis on FedAvg, we refer the reader to [6, 8, 12-21J. Recently, several new algorithms such as FedProx [22], SCAFFOLD [11], FedSplit [10], and FedNova [23] have been proposed as improvements to FedAvg. Despite these advances, there remain gaps in our understanding of the extent to which these algorithms match the guarantees of a centralized baseline."
For instance, even for simple, deterministic settings, FedProx [22] and FedNova [23] exhibit a fun- damental opeerracy conflict under objective heterogeneity; see [8. 9] and Section 2. Specifically, with constant step-sizes, these algorithms converge linearly, but potentially to an incorrect point. Thus, convergence to the minimum of the global loss function necessitates diminishing step-sizes. which, in turn, leads to sub-linear convergence. Thus, fast convergence comes at the expense of accuracy. Although SCAFFOLD [11] and FedSplit [10] employ variance-reduction and operator- splitting techniques, respectively, to tackle objective heterogeneity, it is not known whether the rates in these papers are tight. More importantly, neither SCAFFOLD nor FedSplit account for the effects of systems heterogeneity compression, both of which are key challenges in FL. Indeed, due to systems heterogeneity, the number of local steps may vary across clients, causing some clients to make much less progress than others in each round [23]. Moreover, while empirical studies [24, 25] have revealed significant benefits of biased sparsification, theoretical guarantees for such methods in a federated setting have remained elusive. In this context, contributions are follows.
Motivated by the above concerns, we develop a general algorithmic framework called FedLin that simultaneously accounts for objective heterogeneity, systems heterogeneity, and gradient sparsification. The key components of FedLin include gradient correction term in the local update rule that exploits memory; the use of client-specific learning rates; and error- error-feedback mechanisms at the clients and the server.
A New Algorithm:
For smooth and strongly convex losses, we show that FedLin converges the global minimum linearly in the deterministic setting, and with a O(1/T) rate for a general stochastic oracle model, thereby matching centralized rates (up to constants). We then present matching rates for smooth, convex and non-convex settings as well. Importantly, our results hold under arbitrary objective and systems heterogeneity. In contrast, the only other work in FL (as far as we are aware) that investigates both objective and systems heterogeneity [23] provides results only for the non-convex setting, under a bounded dissimilarity assumption. Moreover, the FedNova algorithm in [23] suffers from the speed-accuracy conflict, while FedLin does not.
Matching Centralized Rates:
Quantifying ing the Price of Multiple Local Steps: We establish a lower bound for FedLin that matches the upper-bound we obtain for smooth, strongly convex losses. In doing so, we provide the first (as far as we are aware) light linear convergence rate analysis. Our lower bound highlights the price paid for performing multiple local steps, i.e., the effect of infrequent communication on the convergence rate. In particular, our analysis reveals, perhaps surprisingly, that there exist simple instances (involving quadratic losses) for which performing multiple local steps does not improve the rate of convergence, indicating that even mild statistical heterogeneity can hurt. Our analysis also techniques.
provides valuable insights into the limitations of
tracking/variancce
Analyzing the Impacts of Gradient Sparsification at Server and at Clients: While several works explore the effect of unbiased random quantization in distributed settings [26-31], there are only a handful of papers [15, 32] that also consider the effect of local steps in FL. Different from all these works, we explore the impacts of sparsifying gradients using biased TOP-k operator, both at the server side and at the clients. Our results in this context (i) constitute the first formal study of gradient sparsification
a federated setting: (ii) reveal key differences between up-link and down-link compression; and (iii) quantify the effect of the compression level on the convergence rate. Notably, FedLin preserves linear convergence rates despite aggressive gradient sparsification.
Basic Notation and Terminology: Referring to (1), let x² E argmin f(x), and 2; E argmin fz(x). Every FL algorithm mentioned in this paper operates in rounds E {1,..., T. In each round 6, every client performs a certain number of local steps in isolation, starting from a
common global model α.. We will denote by 2 client i's estimate of the model at the e-th local step of round f. In particular, 20,0 F,, Vi E S.
(t)
By centralized baseline, we refer to a setup where each client can communicate with every other client at all time steps via the server.

---

Method
Linear Convergence
Lower Bounds
Variable Client Speeds
Sparsification/ Compression
to x²*
FedAvg [2]
X
Thm. II in [11]
x
X
FedProx [22]
X
x
FedNova [23]
X
/
X
FedSplit [10]
X
x
X
SCAFFOLD [11]
X
FedLin (Sec. 3)
Thm. 5
Table I: Comparison of our proposed algorithm FedLin with popular FL algorithms. We indicate whether or not each algorithm (i) guarantees linear convergence to x" for smooth, strongly convex losses in a deterministic setting under objective heterogeneity; (ii) comes with lower bounds; (iii) ac- counts for variable local steps across clients (systems heterogeneity); and (iv) performs compression.
2 Motivation: Speed-Accuracy Trade-Off
To motivate our work, we first show how some recently proposed FL algorithms, namely FedProx [22] and FedNova [23], exhibit fun- damental speed-accurate trade-off even in simple, deterministic set- tings. Specifically, we show that these schemes do not, in general, guarantee convergence to the global minimum with constant step-sizes, This, in turn, necessitates diminish- ing step-sizes, leading sub-lineat convergence rates. Our analysis here is inspired by that in [8] for FedAvg. We consider a determinis- tic quadratic model where the local loss function of client i is given by fi(z) 1/2 (x c;)l where A; is symmetric positive-definite matrix. We begin by assum- ing that all clients perform the same number local steps H. The following the FedProx update rule where proximal term is added to mitigate client-drift:
50
1) 50,
30
10
10
1 10
FedProx: 0.005
10-
FFullove: 0.005
FedProx: q
Feddova: q 0.001
FedLin: 0.005
FedEin: 0.005
Fedtin:
FedLin: 0.001
10
10
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round t
Figure 1: Simulations comparing FedProx, FedNova, and FedLin for two clients with fi( = (1/2)(r 3)² and f2(x) (x 50) Left: Clients perform the same num- ber of local steps, H 50. For FedProx, we set 3 = 5. Right: Clients 1 and 2 perform and 30 local steps, respectively.
0,... - 5 ie+1 -. (V (V + 3(x - -............
Te+l
T
(2)
iES
Proposition For any step-size 7) > O, T rounds of FedProw amount to performing T rounds of parallel GD the surrogate optimization problem given by
H Σ [ 1 7( + (A. 81)
1/2 (x ci)
min
(3)
iSS
Proposition shows that even when clients perform the same number of local updates, FedProx minimizes surrogate objective function (3) whose minimum may not, in general, coincide with the minimum of the original problem. When 3 = O, FedProx reduces to FedAvg, and our observations continue to hold. To capture systems heterogeneity as in [23], suppose now that client i performs local steps. Define Tefs e 1/m Eies Ti and a; Teft/Ta, Vi E S. The update rule of FedNova relies on normalized aggregation of cumulative local gradients, and is given by
1,441
(
xi
(1)
1/ Si Je11 3t
where 0,... - E S. Although FedNova can accommodate any local solver whose accumulated gradients are expressible as a linear combination of local gradients, we choose gradient descent, simple solver, to isolate the impact of normalized aggregation the essence of FedNiova.
3

---

Algorithm FedLin
1: Input: Client step-sizes n/. E S, compression levels óe and 6,, initial iterate Tn E R
@1 [f(),,, initial compression enrors P., 0, vi E 8 and 61
2: for = ...., do
3: for ,...,,1 do
4:
for = 0.
Ti do (t)
5:
2,6--1
(t)
Jif
TE (V V..())) -9:):
30.0 Zt
(e)
6: end for
7: Transmit
to server 2i 1,7.
(0)
8:
end for
9: Server transmits Te+1 = 1/m Σ PiiT
10:
for 1,..., m do
11:
Transmit h4,11 = Cs. (pr. + V(((5(+1) server Vf((+++1) - h1,4+1
12:
Pi.1+1 +
end for
14: Server transmits -t-1 = Co (et + 1/m Eies h4.41)
15: Er+11 t ez + 1/m Lies his+11 9++1
end for
Proposition 2. For any step-size y, O, T roundy of FedNova amount to performing T rounds of parallel GD on the surrogate optimization problem given by
1/2 (x ci)
min M IES
Σ I a1
(5)
For the proofs of Propositions 1 and 2, see Appendix B. Proposition 2 shows that in the presence of both objective and systems heterogeneity. FedNova minimizes surrogate loss function whose minimum may not coincide with x* Observe from (3) and (5) that using larger learning rate 7 introduces more distortion to the original problem. In Figure 1, we see how FedProx and FedNova both converge incorrect minimizers, even for simple instances with two clients and deterministic, quadratic losses. In contrast, FedLin, our proposed approach that we develop in the next section, guarantees linear convergence to the global minimum.
The main message we want to convey here is that even for deterministic settings, there are non-trivial challenges posed by objective and systems heterogeneity that only get amplified when one additionally considers biased compression. For such scenarios, it is not at all apparent whether (and to what extent) one can match even the basic centralized benchmark of achieving linear convergence for smooth, strongly convex loss functions. To focus on the above unresolved issues, we will primarily consider a deterministic model in this paper. Nonetheless, the general approach we develop applies to the stochastic setting as well, as aptly demonstrated by Theorem 4 in Section 4.
Main Takeaway:
3 Proposed Algorithm: FedLin
In this section, develop proposed algorithm FedLin, formally described in Algorithm 1. FedLin is initialized from a common global iterate Ti E Rd. For simplicity, we assume that gi V. i.e.. every client has access the true gradient of f(-) initially; we can allow øi to be arbitrary as well without affecting the convergence guarantees. FedLin proceeds in rounds: in each round f, starting from common global model F,, each client performs т; local training steps in parallel, as per line 5 of Algorithm 1. The key features of our local update rule are as follows: exploiting past gradients to account for objective heterogeneity, using client-spee speciff step-sizes to tackle systems heterogeneity, and employing prror-feedback to account for gradient sparsification. We now discuss each of these features detail.
In follow-up work to [8]. the authors in [9] generalize their framework to encompass proximal methods such as FedProx as well. As such, Propositions I and 2 in this section turn out to be special cases of the results in [9]. We were not aware of [9] the time of submission of this paper.

---

To gain intuition regarding the local step in line 5, note that the ideal local update at client is (0)
Fi,t+1 - ni f( However, this requires client have access to the gradients of all other clients- which it does not, since clients do not communicate between rounds. To get around this, client i exploits memory, and uses the gradient of the global function V from the beginning of round L (when the clients last communicated) as a guiding direction in its update rule.
However, since V (ā+) is evaluated at a stale point 2 = Σt, client subtracts off V (Zx) from
Vāz)), and adds in the most recently evaluated gradient f This results in the update rule: (() 22,0+1 = 7/ V (x(()) V (.,) + (z+))) Our local update rule in line 5 is precisely of the above form, where 9t is an inexact version of V ffEz) to account for gradient sparsification.
When each client i performs 7i local-steps, our analysis reveals that the bound on the drift-term ||0,e- - Fzll scales linearly in Ti (see Lemma 9 in Appendix F). Accordingly, to compensate for such drift at client i, the step-size Th needs to be chosen to vary inversely with the number of local steps Tı. In fact, the requirement that x 1/T; also turns out to be necessary (see Theorem 5), providing further motivation for the choice of client-specific learning rates in FedLin.
To explain the gradient sparsification module, let us denote by C. : R + Rd the TOP-k operator, where ō = d/k, and & E {I....,de d}. Given any I E Rd let (xr) be set containing the indices of the k largest- mageetut components of æ. Then, the TOP-k operator we consider is given by (C& (C)())) = (z); if j Ex(x), and (C)())) component of vector x. Clearly, larger 5 implies more aggressive compression. We employ standard error- feedbaee mechanism [33-35] at both the server and the clients to account for gradient sparsification. At client i, Pt., represents the accumulated error due gradient sparsification. At the end of round f, instead of just compressing V (ā client instead compresses V (f + Pi.+ to account for gradient coordinates not transmitted in the past. It then updates the aggregate error via line 12. An analogous description applies to the error-feedback scheme at the server, where e is the aggregate error at the beginning of round f. The parameters of FedLin are the client step-sizes {n hes. and the compression levels ó, and 8₂ at the clients and at the server, respectively. We now comment on some related algorithmic ideas.
0 otherwise. Here, use (x) to denote the j-th
Related Algorithmic Approaches: In the related but different setting of distributed optimization, we note that the idea of exploiting past gradients has been used to design pradienttracckin algorithms technique employed
[36-40]. In the context of FL, this idea is also related to the in SCAFFOLD [11]. A major difference of FedLin with the above works is that none of them consider the effect of systems heterogeneity or biased compression. In particular, accounting for the inexact gradient term I. in our update rule introduces new technical challenges that we address in this paper.
There are some additional basic differences between FedLin and SCAFFOLD. To see this, consider the (t) ni (. - fz.) + fz))). update rule of FedLin without sparsification: 21,++1 = i,f
Now suppose the global model ū, at the beginning of round t has already converged to x². Since (t) -r, Vi E S, and V = 0, it is easy to see that the iterates of the clients do not evolve any 22.0
further, as one would ideally want. Thus, the global optimum x² can be viewed as a f.fiee-pooin of the FedL in update rule. Adapting to our notation, and considering the case when there is no noise in the gradients, the update rule of SCAFFOLD takes the form ii,++1 e is a 'control-variate' maintained by client i, and e is the average of the e, 's. Importantly, the control variates {c))ies used in round of SCAFFOLD contain stale terms from round t 1. As result, even & = x=, it may very well be that ((..) G + c) A O, causing the iterates of the clients to move away from x², and requiring further rounds of communication to average out the imbalance. Thus, the fixed-point property we discussed for FedLin does not hold in general for SCAFFOLD. Our simulations in Section 7 reveal that FedLin converges much faster relative SCAFFOLD on simple linear regression model; we conjecture it is precisely due to the reason described above.
(1) = x (1!() - n7(V fa(a!!!) G; + c). where
Keeping aside the differences due to systems heterogeneity and compression, the FedSVRG algorithm in [i] includes a similar gradient correction term as in FedLin, but makes use of certain additional diagonal scaling and pre-conditioning matrices. Although promising empirical results are reported for FedSVRG in [1], these results come with no supporting theoretical guarantees of convergence. In contrast, we will develop rigorous complexity guarantees for FedLin in the following sections. Specifically, we will show that FedLin guarantees linear convergence rates despite the challenges of objective heterogeneity, systems heterogeneity, and aggressive gradient sparsification.
5

---

4 Matching Centralized Rates under Objective and Systems Heterogeneity
In this section, we will analyze the performance of FedLin in the face of both objective and systems heterogeneity. To focus solely on the effects of client heterogeneity, we will assume throughout this section that there is no gradient sparsification, i.e., de = 6, Ps. = 0, = 0, Vi E S, Vt E {l...., T) Thus, the local update rule for FedLin simplifies to
Accordingly, observe that
(t) T +1,+1 = i.f Th (VS((a))))) - Va,(a,) + (.))))).
(8)
(6)
Let us denote by K L/μ the condition number of an L-smooth and j-strongly convex function. Also, let 17 i,, Vi S, where n E (0, 1) is flexible parameter that we will specify based on context. We are now ready to state the main results of this section.
Theorem 1. (Strongly convex case Suppose each fi(z) L-smooth and u-strongly convex. More- over, suppose TÜ 1, Vi E S, and de = = 1. Then, with = 6L., Vi S, Fedl in guarantees:
f(oT+1) f(x)) S 1 (1-1) T
(f(#1) - f(z"))
6x
Theorem 2. (Convex case) Suppose each f((x) is L-smooth and convex. Moreover, suppose 2 1, E S, and d 8, = 1. Then, with t7s IoLri Vi e S, FedL in guarantees:
10L T (10)- ==11 |KT x 1²)
Σ
St - 1(x) S
T
Theorem 3. (Non-convex case) Suppose each f((x) is L-smooth. Moreover, suppose 2 1, Vi E S.
and 6. = 8, = 1. Then, with Ti = 26LT Vi E S, FedL in guarantees:
52L T (f(ā)) - ((T++1))-
min [E[T]
Noisy Case Analysis: We now analyze the performance of FedLin under a general stochastic oracle model. For each E S and x E RR, let (x) be an unbiased estimate of the gradient fz(z) with variance bounded above by o². We consider the update rule: -i,++
(t) xi, m (g (x.2)) (B.)
(t)
(āxz)), where ((x) & 1/m Eies (xx), Vx E Rd. We then have the following result.
Theorem 4. (Strongly convex case with noise) Consider the above stochastic oracle model. Suppose each f((z) is L-smooth and p-strongly convex. Moreover, suppose 2 1, Vi E S, and 6, ò 1. For each i E S, let 17: = - where ij (0. satisfies ij < 61. Then, Vt E (T), Fedl in guarantees:
B|| - x 101 = (1 1222111 EII - x" x²11 25
7i11
(8)
The proof's of Theorems 1, 3, and 4 are provided in Appendix F.
Main Takeaways: From Theorems 1, 2, and 3, we note that FedLin matches the convergence guarantees of centralized gradient descent (up to constants) for smooth, strongly convex, convex, and non-convex settings, respectively. As far as we are aware, this is the first work to provide such comprehensive guarantees under arbitrary objective and systems heterogeneity. In fact, all our results continue hold even when the operating speeds the client machines vary across rounds, i.e., Tú is allowed to be a function of l. Each client i can simply adjust its learning rate x 1/T,(t) locally to account for such variations. The bound for the noisy case in Theorem 4 resembles that of centralized SGD [41]: with a time-varying parameter tee O(1/t), we get the standard O(1/T)) rate after T rounds (using the exact same arguments as in [41]). The key thing to note here is that despite arbitrary heterogeneity, the assumptions we make the stochastic gradients are the same as those made in the analysis of centralized SGD: unbiased gradients with bounded variance, nothing more.
Comparison with Related Work: In the recent paper [10], the authors propose FedSplit, and analyze in a deterministic setting. For strongly-convex and smooth loss functions, FedSplit guarantees linear convergence, but only to non-vunishing neighborhood of x*. Thus, like FedAvg [2], FedProx [22), and FedNova [23], FedSplit fails to guarantee exact linear convergence to x Empirically, we observe that FedSplit diverges certain instances; see Appendix J. Compared to

---

these algorithms, we see from Theorem that FedLin guarantees linear convergence to x². Notably, the linear convergence rate we obtain in Theorem I under both objective and systems heterogeneity the best rate we know of in FI., and matches that of SCAFFOLD [11] where only objective heterogeneity considered." 3 The model of systems heterogeneity we study is taken from [23], where the authors provide guarantees only for the non-convex case under a bounded dissimilarity assumption. In contrast, our results cover all the three standard settings strongly-conver convex, and non-convex without requiring any bounded dissimilarity assumption. For further related work on straggler-robust distributed learning algorithms (without objective heterogeneity or local steps), see [43-48].
4.1 The Price of Infrequent Communication
In this section, we take a closer look at the effect of performing multiple local steps on the convergence rate. To do so, we assume that all clients perform the same number of local steps H, i.e., there is no communication for H consecutive time-steps between two communication rounds. Now consider a centralized baseline where each client can communicate with every other client all times (i.e., even between rounds). In this case, since each client can always access (x)),, gradient descent yields
(iT+1)- S exp(- (
K
after T rounds, with H synchronized local iterations within each round. Based Theorem 1, observe that we lose out by a factor of H in the exponent relative to the centralized baseline. Notably, both in the centralized case, and in FedLin, each client queries the gradient of its local objective H times in each round, thereby making TH gradient queries over T rounds. Thus, relative to a centralized baseline, FedLin incurs the same computational cost in terms of gradient queries, and reduces communication by a factor of H, at the expense of a convergence rate that is slower by a factor of H. We emphasize here that just as with FedLin, H does not show up in the convergence rate (exponent) of algorithms like FedSplit [10] and SCAFFOLD [11] either.
The primary reason for the slower convergence rate (relative to centralized baseline) stems from the need to set 17 x H/H to mitigate client-drift under objective heterogeneity. At this stage, one may conjecture that the above requirement is simply artifact of conservative analysis of Algorithm 1, and that a more refined analysis will reveal the utility of performing more local steps even in the heterogeneous setting. Our next result suggests otherwise; for proof, see Appendix E.
Theorem 5. (Lower bound for Fedl in) Suppose ó. = 8, = 1, and T; = H, = Vi E S. Then, given any L 2 14 and H 2 2, there exists instance involving 2 clients where each f((x),, i E {1,2), is 1-strongly convex and L-smooth, and an initial condition 3,, such that FedL in initialized from Z1 generates sequence of iterates } satisfying the following for any T 2 1:
|
101 =''1 2 exp (-47)) - ((ET+)) f(x')= 2 (xp(-AT)(f(2)) - f(x))) (10)
There are several key implications of Theorem 5. First, it complements Theorem 1 by providing a matching lower bound. We believe ours is the first work to provide a tight linear convergence rate analysis: [11] and [10] only provide upper-bounds for SCAFFOLD and FedSplit, respectively. Second, our analysis of Theorem 5 in Appendix E indicates that there are problem instances where setting 1) x 1/H is in fact necessary to guarantee convergence to x². As a result, for such problem instances, no matter how many local steps H each client performs, the error the end of T rounds remains bounded below by an H -independentt quantity, as is apparent from (10). Perhaps surprisingly, we show in Appendix E that the lower bound in Theorem 5 even applies to simple instances with non-identical quadratic losses (across clients) where every [a()) has the same minimum! This is particularly insightful since it highlights the limitations of exploiting stale gradient terms in the local update rule (as is done in both FedLin and SCAFFOLD), and suggests the need for more informed updating schemes that explicitly take into account the level of statistical heterogeneity.
Main Takeaways:
Proof Idea for Theorem 5: To establish Theorem 5, we set up an instance involving two clients with quadratic loss functions. Our main idea is to relate the convergence of FedLin to the Schur stability of an appropriate discrete-time linear time-invrrian (LTI) system. Based on this connection, we show that guaranteeing stability necessitates setting 7) x 1/H, which immediately leads to the lower bound. We believe that the same technique can be used to establish similar lower bound for SCAFFOLD.
"In a concurrent work [42], the authors develop linearly converging algorithm called S- S-Local-SVRe for the finite-sum sum setting. but neither consider systems heterogeneity nor compression. Moreover, unlike the lower bound we develop for FedLin in Theorem 5, no lower bounds are provided for S S-Local-SVRG in [42].
7

---

Gradient Sparsification at Server
In this section, focus will be addressing the following question: For strongly convex and smooth deterministic functions, funtttion and in the presence of both objective and systems heterogeneity, can we still hope for linear convergence x² when gradients are sparsified the server? Interestingly, we will show that not only is it possible to converge linearly to x², is possible to do so without any error-feedback. Moreover, this claim holds regardless of how aggressive the server in its sparsification scheme: it may even transmit just a single component of the aggregated gradient vector.
To isolate the impact of server-level sparsification, gradients are not sparsified at the clients, i.e., 6g = 1. Consequently, ha++1 = (i(+++))) Vi E S, VI E (1....: 7). We begin by considering simpler variant of FedLin with error-feedback the server side, i.e., line 15 is skipped, and 9++1 in line 14 of Algo. is instead updated as follows
will assume throughout this section that
1 Σ ((((E())) Y iES
9++1 Co.
Cs, (Vf(Ec+1))
(11)
Theorem 6. (Sparsification at server with no error-feedback) Suppose each f((x) is L-smooth and p-stroogly convex. Moreover, suppose T; Z L,Vi S, and 8 1. Consider variant of Fedl in, where line 14 is replaced by equation (11), and line 15 is skipped, i.e,, there is no error-feedback. Then, with πr 2(2+v6.)
1 Vi E. this variant of FedL guarantees
T
f(ī++)) f(x))
(f(a1) f(x))
25. (2 + (..)
Main Takeaways: From Theorem 6, we that even without error-feedback, it is possible linearly converge to æ²; the rate of convergence, however, is inversely proportional to 6 Thus, Theorem 6 quantifies the trade-off between the level of sparsification the server, and the rate of convergence. When there is gradient compression, i.e., when 5, 1, we exactly recover Theorem 1.
One may ask: there any potential benefit to employing error-feedback when gradients are sparsified at the server? Our next result answers this question in the affirmative.
Theorem 7. (Sparsification at server with error-feedback) Suppose each fi(x) is L-smooth and ju-strongly convex, Moreover, suppose 2 1, E S, and ó = 1. Let the step-size for client i be chosen as T 72LA,7:' Then, FedLin guarantees:
96dgk ) (((z))f(('))
- S S2x
For proofs of Theorems and 7, see Appendix and I.
Main Takeaways: Comparing the guarantee of Theorem with that of Theorem 7, we note that the convergence rate inversely proportional 8 in the former, and inversely proportional 8, the latter. Thus, the main message here is that employing error-feedback leads to faster convergence rate by improving the dependence of the rate on da.
Gradient Sparsification Clients
In this section, we will turn our attention to the case when gradients are sparsified at the clients prior to being transmitted to the server. Throughout this section, we will assume that gradients are not compressed any further at the server side, i.e., 5, 1. To proceed, we will need to make the following bounded gradient dissimilarity assumption.
Assumption 1. There exist constants C N 1 and D 2 0 such that the following holds Vr E IRd;
{ c D.
(12)
The following is the main result of this section; for proof, Appendix H.

---

Theorem 8. (Sparsification at clients with error-feedbakk) Suppose each f((z)) is L-smooth and p-strrongly convex, and suppose Assumption holds. Moreover, suppose Ti 2 1, vi E S. and 5, 1. Let the step-size for client be chosen as 1/1 FedL in guarantees:
n where 1j E (0, satisfies nj S T2L5.C- Then,
3 T1
T | - x 1² + 3 6,C + 60 D.
6
[T++ x=1 - 2
1
(13)
Main Takeaways: Intuitively, one would expect that sparsifying gradients at each client prior to aggregation at the server would inject more emror than when gradients first accurately aggregated at the server, and then the aggregated gradient vector is sparsified: Theorems 6 and 8 support this intuition. For the former, we neither required error-feedback nor Assumption convergence to the global minimum x²; for the latter, even with error-feedback and the bounded gradient dissimilarity assumption, we can establish linear convergence to only a neighborhood of a*, in general. From (13), we note that the size of this neighborhood scales linearly with D a measure of objective heterogeneity, In particular, when D O, the iterates F, converge exactly to x²
guarantee linear
Remark 1. To the best of our knowledge, our results in Sections 5 and 6 constitute the first formal analysis of biased gradient sparsification in FL. In particular, significantly generalize the recent results in [49] for a single worker to a multi-client FL setting with both objective and systems heterogeneity. To arrive at these results, develop new intential-functionn based proof technique in Appendix H. For more related work on compression in distributed learning, see Appendix A.
Extensions: We studied the effect of compressing information at the server and at the clients separately, with the goal of identifying the key differences between each of these mechanisms. The analysis techniques we developed in the process pave the way for studying various natural extensions: (i) combined sparsification both the clients and the server; (ii) gradient sparsification in tandem with model parameter compression; and (iii) stochastic counterparts of Theorems 6, 7, and 8.
7 Experimental Results
In this section, we provide numerical results for FedLin on least squares problem to validate theory. In Appendix K, we also provide additional numerical results on a logistic regression problem.
For now, we consider the following least squares regression problem:
1 Σ
min f(x) = min #ERd
A b,11?
(14)
=ER
where A, E 100000000 is a design matrix and b, E 500000 is a response vector. The client objective functions, fz( are strongly convex. Assuming that all design matrices are full column rank, problem (14) admits unique minimizer. To generate synthetic data, for each client i E S = fl...., 20). we generate A, and b; according to the model b, = AAx, E,, where 2; a weight vector and E, e R5000
is disturbance. In particular, we generate [A,],k s.d. (O, 1). and E; NO 0.5Isuo), vi S. To capture statistical heterogeneity, the entries of the local true parameter of client i are modeled as [xn]a ~ Nu,, 1), & {1, , 100}, where u, ~ ~N( a) and 2 0. Hence, a controls the level of statistical heterogeneity. To model the effect of systems heterogeneity, for each client i E S, the number of local steps is drawn uniformly and independently from [2, 100). We will primarily focus on a deterministic setting here for our experiments; in Appendix L., we evaluate FedLin on a standard stochastic oracle model. Our experiments in Appendix L reveal that under a noisy oracle, FedLin guarantees linear convergence to a ball around the true minimum, exactly as suggested by Thm. 4.
Gradient Sparsification at Server. We first consider a variant of FedLin where gradient sparsi- fication is implemented only at the server side and without any crror-feedback. In particular, we consider the cases where 8g {2,4), which correspond to the implementation of TOP-50 and a 70 operator, respectively. For comparison, we also plot the resulting performance when no gradient sparsification is implemented at the server. To examine the effect of statistical heterogeneity on the performance of FedLin, we generate two synthetic datasets corresponding to two different levels of heterogeneity in the clients' local objectives, namely in Fig. 2, irrespective of the level of gradient sparsification on the server side, FedLin achieves linear convergence the true minimum in the presence of both objective and systems heterogeneity, confirming Theorem 6. Also, both the convergence speed and accuracy of FedLin remain unaffected as the level of heterogeneity in the clients' objective functions increases.
10 and a 50. As illustrated

---

10, 6,
02 50, 6,
Gradient Sparsification at Clients. Next, we implement gradient sparsi- fication only at the clients' side, i.e. 6, = 1. In particular, we consider the cases where 6c E (4/3, 2). which correspond to the implementation of TOP-75 and TOP-50 operator, re- spectively. Once again, we gener- ate two synthetic datasets with differ- ent levels of objective heterogeneity, namely
10
Fediin:
FedLin:
10
FedLin: 4
10:10
10
10 30
10
10
20
30
40
0
10
20
30
40
Communication Round
Communicacion Round 1
10. As il- lustrated in Fig. 3, unlike the server case, FedLin with sparsification at the clients' side converges linearly, but with non-vanishing error that in- creases as the value of ó, increases. This aligns with the conclusions of Theorem 8. Furthermore, the level of objective heterogeneity has a direct impact on the convergence error. In particular, for the same level of gradi- ent sparsification, higher levels of ob- jective heterogeneity result larger values of the convergence error.
and
Figure 2: Server-side sparsification results for FedLin. The
constant 1) fixed at 10 Left: 10. Right: a 50.
5,
10, 8, =1
10
10t
FedLin & = 1:33
Fedtin:
10
T0
6
10a1
1
10
100
100 Communication Round
Communication Round
Comparison with SCAFFOLD. We now compare FedLin with SCAFFOLD on the least squares regression setup described above. To make fair comparison, we assume that there is no systems heterogeneity or gradi- ent compression. For implementing SCAFFOLD, we use Option II in their paper [11] for updating the control variates. We set the number of local steps 20, the statistical hetero- geneity parameter = 10, and use step-size of 10-3 3 for both algorithms (the step-size sults). For the deterministic setting, we note from Fig. 4 that FedLin con- verges much faster compared to SCAFFOLD. This trend persists when we perturb the gradients with zero-mean Gaussian noise with variance
Figure 3: Client-side sparsification results for FedLin. The constant i] is fixed at 5 x 10 Left: 1. Right: = 10.
10"
+ PedLin
PedLia Scaffold
Scaffold
10
10
Communication round
Communication round
Figure 4: Comparison of FedLin with SCAFFOLD. (Left) De- terministic setting. (Right) General stochastic oracle model: unbiased gradients with variance a = 10-1
tuned to get best re-
10-1. We conjecture that the faster convergence of FedLin stems from the fact that it uses less stale gradient correction terms relative to the control variates of SCAFFOLD; see the discussion about the fixed point property of FedLin in Sec. 3.
8 Conclusion
We developed novel algorithmic framework called FedLin to tackle some of the key challenges in FL, namely objective heterogeneity, systems heterogeneity, and imprecise communication. We showed that FedLin enjoys strong theoretical guarantees: (i) FedLin matches centralized rates, and, in particular, guarantees linear convergence to the global minimum under arbitrary objective and systems heterogeneity; and (ii) preserves linear convergence rates despite aggressive gradient sparsification. We also established tight lower-bound for FedLin, highlighting that even mild statistical heterogeneity can end up hurting convergence rates this is the first such result in FI.. Our current approach requires two passes of communication between the clients and the server in each round. Moreover, analysis does not account for partial client participation. As future work, plan to address these limitations. We also plan to investigate other federated learning formulations (beyond supervised learning) where statistical heterogeneity can potentially help.
10

---

Acknowledgement: This work was supported by NSF Award 1837253, NSF CAREER award CIF 1943064, and the Air Force Office of Scientific Research Young Investigator Program (AFOSR- YIP) under award FA9550-20-1-0111.
References
[1] Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 022202 2016.
[2] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiene learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[3] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, al. Towards federated learning at scale: System design. arXiv preprint 19Xiv1190..01466 2019.
[4] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.04977 2019.
[5] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
[6] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.021186 2019.
[7] Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pages (692-6701 PMLR, 2020.
[8] Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint 2rXiv:2077.00876 2020.
[9] Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta-learning. In International Conference Artificial Intelligence and Statisties, pages 2575 2583. PMLR, 2021.
[10] Reese Pathak and Martin J Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. arXiv preprint arXiv:2005.05238, 2020.
[11] 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, pages 5132-5143, PMLR, 2020.
[12] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint 1rXiv:1805.09767, 2018.
[13] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-efiiiient sgd algorithms. arXiv preprint arXiv:1808.0755 2018.
[14] Artin Spiridonoff, Alex Olshevsky, and loannis Ch Paschalidis. Local sgd with communication overhead depending only on the number workers. arXiv preprint arXiv:2006.02588 2020.
[15] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiieen federated learning method with periodic averaging and quantization. International Conference on Artificial Intelligence and Statistics, pages 2021- 2031. PMLR, 2020.
[16] Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pages 11822-1194,, 2019.

---

[17] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? arXiv preprini arXiv:2002.07839, 2020.
[18] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heterogeneous data. arXiv preprint arXiv:1909.04711 2019.
[19] 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, pages 4519-4529, PMLR, 2020.
[20] Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint
14425, 2019.
[21] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sehastian Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint arXiv:2003. 1042. 2020.
[22] Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv: 3, 2018.
[23] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
[24] Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint arXiv: 1 770400502, 2017.
[25] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient com- pression: Reducing the communication bandwidth for distributed training. arXiv preprint 17Xiv:1712.01187, 2017.
[26] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication--ffiiienn sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30: 1001700-1720, 2017.
[27] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Terngrad: Ternary gradients reduce communication in distributed deep learning. In Advances in neural information processing systems, pages 1509-1519,200
[28] Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikacl Johansson. Distributed learning with compressed gradients. arXiv preprint 1rXiv:1806.0653 2018
[29] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1rXiv:/901.0920 2019.
[30] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002.11364 2020.
[31] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 1rXiv:1904.05115. 2019.
[32] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis sis and sharp guarantees. arXiv preprins arXiv:2007.01 154, 2020.
[33] Frank Seide, Hao Fu, Jasha Droppo, Gang Li. and Dong Yu. 1-bit stochastic gradient descent and its application to data- patal-prrllel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[34] Sebastian Stich, Jean- Baptistp Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pages 4447-4458, 2018.
12

---

[35] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pages 5973-5983, 2018.
[36] Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3):1245-1266) 2017.
[37] Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
[38] Chenguang Xi, Ran Xin, and Usman A Khan. Add-opt: Accelerated distributed directed optimization. IEEE Transactions Automatic Control, 03(5):1329-1339) 2017.
[39] Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Programming, pages 1-49, 2020.
[40] Ran Xin, Anit Kumar Sahu, Usman A Khan, and Soummya Kar. Distributed stochastic optimization with gradient tracking over strongly-connected networks. In Proc. of the 58th IEEE Conference on Decision and Control (CDC), pages 5353-8358, 2019.
[41] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[42] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2021.
Unified theory and new
[43] Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. Straggler-resilien federated learning: Leveraging the interplay between statistical accuracy and system heterogeneity. arXiv preprint arXiv:2012.14453 14453, 2020.
[44] Sanghamitra Dutta, Jianyu Wang, and Gauri Joshi. Slow and stale gradients can win the race. arXiv preprint arXiv:2003. 10579, 2020.
[45] Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error- runtime trade-off local-update sgd. arXiv preprint 1rX1v:1810.08313, 2018.
[46] Rawad Bitar, Mary Wootters, and Salim El Rouayheb. Stochastic gradient coding for straggler mitigation in distributed learning. IEEE Journal on Selected Areas Information Theory, 2020.
[47] Nuwan Ferdinand and Stark C Draper. Anytime stochastic gradient descent: A time to hear from all the workers. 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 552 559-59. IEEE, 2018
[48] Amirhossein Reisizadeh, Hossein Taheri, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. Robust and communication-efficienn collaborative learning. In Advances in Neural Information Processing Systems, pages 8388-8399, 2019.
[49] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002.12410. 2020.
[50] Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
[51] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feed- back fixes signsgd and other gradient compression schemes. arXiv preprint 191.097901 2019.
[52] Sebastian U Stich and Sai Praneeth Karimireddy. The emor-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: 990.05330, 2019.
13

---

[53] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly con- verging error compensated sgd. Advances in Neural Information Processing Systems, 33, 2020.
[54] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[55] Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.4980, 2014.
[56] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, 27(():2202-223 220222222222, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We provide a lower bound for our algorithm in Theorem 5 of Section 4.1 that suggests the need for more informed local updating schemes.
(c) Did you discuss any potential negative societal impacts of your work? [No] We could think of any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide complete proofs of all our results the supplemental material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "am8IFO2uSu", "reviewer": "Reviewer_Xwfq", "summary": "This paper proposes a new algorithm called *FedLin* which, \n\nT.1) queries a full gradient oracle, \n\nT.2) de-biases the local gradients using a correction term (with the last synchronized iterate in memory) to deal with objective heterogeneity,\n\nT.3) error corrects to deal with compression at the client and the server, and\n\nT.4) uses a client-specific learning rate to deal with the different number of local steps on each client. \n\nThus, FedLin is able to accommodate both objective and system heterogeneity along with sparse gradients and local steps. In doing so it is an early work that can deal with these multiple aspects of federated learning at once, albeit at the cost of an expensive gradient oracle. \n\nThe paper provides the following theoretical guarantees for FedLin,\n\nR.1) matching upper and lower bounds in the strongly convex-smooth setting without compression,\n\nR.2) upper bounds without compression in the convex-smooth setting and the non-convex setting,\n\nR.3) an iterate sub-optimality recursion for the strongly convex-smooth setting while using a stochastic gradient oracle,\n\nR.4) upper bounds for client and server compression in the strongly convex-smooth setting.\n\nSee the main review for comments on these results.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think overall the paper is clear and well-written. I have still only given it a score of 6, because there are aspects which can be improved, some of which are just presentation issues. If the following concerns can be handled, I am willing to improve my score. \n\n**v/s Scaffold**\n\nThe upper bounds in R.1, R.2, and R.3 are not better than Scaffold [1] but they can additionally accommodate a different number of local steps. On the other hand, Scaffold uses a stochastic oracle and accommodates partial client sampling. Both these differences are not really big though. With a step size of $1/\\tau_i$, it is not surprising that FedLin can control the client drift, and it is not difficult to introduce uniform partial client sampling either. Thus if it were only for the upper bounds in R.1-R.3 (which are compression-free), the results would have been incremental to Scaffold. \n\nWhat is perhaps more interesting is the lower bound in R.1. After the Scaffold paper [1], one open question was if such a conservative client learning rate was actually necessary to compete with large mini-batch SGD (T rounds of batch size HM)? One could conjecture that it was a necessary evil to control the client drift, essentially giving us large mini-batch SGD like updates despite local steps! I.e., the obtained convergence rate can't depend on $TH$ but only $T$. This paper proves this conjecture for FedLin, giving lower bounds that depend only on $T$. This was a major limitation of Scaffold's results and analysis, and it is satisfying to see this lower bound. \n\nFor the sake of completeness and for comparison, I would encourage the authors to also provide a similar lower bound for Scaffold, perhaps in the appendix. I expect that Scaffold's lower bound might also match its upper bound. In that case, I am not sure if the results are very exciting in the uncompressed case. Do the authors believe that proving Thm. 1-4 is technically very different from Scaffold ([1] does a good exposition of its proof technique in its appendix)? Is it fundamentally different from choosing a small enough step-size to control the client drift? If there are additional technical challenges besides this, they should be highlighted, otherwise I maintain that the techniques are incrementally different.    \n\n**Sparsification results**\n\nI believe these results are indeed novel. It would have been nice to have a theorem statement with both server and client level sparsification. Did the authors try this? What were the challenges in doing so? \n\n**Presentation** \n\nBased on my comments above, I think the authors should spend less space presenting and discussing Thm 1.-4 given how they are incremental over Scaffold. The paper should actually develope the lower bound in R.1 better, talk about its construction, and what it implies about other distributed algorithms like Scaffold. Perhaps Theorem 1 doesn't even need to be in the main paper, as Theorem 6. already generalizes it. It would be good to point out how the proof techniques in section 5. are different/similar to the ones in section 4, i.e., controlling the client drift? Finally, I would encourage the authors to talk a bit more about the novel proof technique developed in section 6. \n\nIt feels a bit weird that the authors claim that all of the results can be obtained for the stochastic setting, but still don't chose to present them (even in the appendix). Why was Theorem 4. not completely worked out, along side other theorems? Having a noise term in the guarantee doesn't obfuscate the analysis or the takeaways. For instance I could go back to the Scaffold paper, and send the noise term to zero to compare the results with this paper very easily. Infact, it is important to understand if stochasticity behaves differently in presence of heterogeneity/local steps. Won't the authors be required to make more assumptions (perhaps on the stochastic gradients) to even carry out the analysis (like [2], which is a related reference that should probably be compared to as well)? It is not clear to me. Either present the stochastic results, or be upfront about the issues in doing so. In practice, it is going to be prohibitive to use a full gradient oracle, and some mini-batch version of FedLin would be used. If so how would that compare to accelerated minibatch SGD [2] ? \n\n**Experiments**\n\nContinuing on the last issue, brings me to the (lack of) baselines in experiments. The algorithm essentially compares only to itself!\n\n1) Why is Scaffold not present in any of the experiments and specially in the motivating figure 1? \n\n2) In practice people will use a stochastic oracle. Atleast some (if not all) experiments should also show a stochastic version of FedLin, along with important baselines such as accelerated minibatch SGD, Scaffold, etc. I would expect that when the local steps are the same and the heterogeneity level is low, different trade-offs will start emerging, and algorithms like  large mini-batch SGD or FedAC [3] might dominate FedLin.\n\n**Minor Comments**\n\n1) It would be better to present Theorem 4 for function sub-optimality, instead of recursion on iterate sub-optimality. This is good for uniformity w.r.t. the other results as well as to make the comparison with earlier work more transparent. \n\n# Updated Review\n\nThe authors have honestly addressed some of the limitations of their work. They have also promised to make important additions to the revised paper including experiments with other baselines and with a stochastic oracle, as well as a more detailed discussion of the baselines. I hope the authors will sincerely make these additions and will also improve upon their presentation as discussed. In light of this I am improving my score to a 7.  \n\n**References**\n\n[1] Karimireddy, Sai Praneeth, et al. \"Scaffold: Stochastic controlled averaging for federated learning.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Woodworth, Blake, Kumar Kshitij Patel, and Nathan Srebro. \"Minibatch vs Local SGD for Heterogeneous Distributed Learning.\" Advances in Neural Information Processing Systems 33 (NeurIPS 2020) (2020).\n\n[3] Yuan, Honglin, and Tengyu Ma. \"Federated Accelerated Stochastic Gradient Descent.\" Advances in Neural Information Processing Systems 33 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "Rx48wp06fEs", "reviewer": "Reviewer_wkH7", "summary": "This paper proposes and analyzes a framework for Federated optimization called FedLin. It combines client-specific local steps with (possibly) biased compression at the server and/or clients and guarantees linear convergence to the exact minimum. Algorithmic contributions are supported with lower bounds for the case of infrequent communication and carefully designed synthetic experiments on least squares and logistic regression problems, which highlight theoretical claims.", "questions": "", "limitations": "", "rating": 8, "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": "This paper is a solid piece of mainly theoretical work on the problem of linear convergence in the Federated optimization setting, and I recommend acceptance.\n\nThe paper is clearly written and well-structured. Related work is mostly adequately cited but can be complemented with the latest works on local methods with compression. I think that a much more detailed discussion is needed to compare with the briefly mentioned work [1]. I understand that it appeared quite recently, but it is essential for publication as it also suggested methods linearly converging to the exact optimum and combined with variance-reduction. It would also be helpful to include a comparison table with differences to the previous methods (e.g., with uncompressed methods like FedSplit, FedNova, SCAFFOLD, S-Local-(S)GD/SVRG from [1]) to make it easier for readers to understand the contributions.\n\nThe authors present only synthetic experiments, but they are appropriate in this case as they were carefully designed and decently support the theoretical claims. However, I recommend including real-data experiments (e.g., with LibSVM datasets) in the final version as it will help to understand the actual practical performance and limitations of the presented approach.\n\nThe main drawback of the proposed algorithm FedLin is that it requires sending uncompressed model vectors $x_{i, \\tau_{i}}^{(t)}$ from workers to the server and $\\overline{x}_{t+1}$ back at every communication round, which may not be efficient/possible in the federated learning setting. That is why the part on the compression seems is not very valuable from the practical side.\n\n## Post-rebuttal\nI have read other reviews and authors' answers. I found both of them very insightful and believe that the published paper will be significantly improved with the proposed suggestions in mind. To conclude, I keep my score as it is.\n\n***\n\n[1] E. Gorbunov, et al. “Local sgd: Unified theory and new efficient methods”. In International Conference on Artificial Intelligence and Statistics, pages 486 3556–3564. PMLR, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work were mostly addressed. Negative societal impact concerns are not applicable due to the theoretical nature of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DN6yJOvzQt0", "reviewer": "Reviewer_LmKH", "summary": "This paper considers a standard distributed optimization setup in which clients periodically coordinate with a server to train a global model. The focus is on the deterministic setting, in which each worker computes full local gradients. It is first highlighted that standard algorithms for this problem do not converge to the true global minimizer without trading off speed (for example through diminishing step-sizes).\n\nThus, the FedLin algorithm, which converges linearly to the true minimizer, is introduced to get the best of both worlds. Several theorems covering various settings (strongly convex, convex, non-convex, stochastic) are given, and show that FedLin matches the communication complexity of parallel GD, regardless of the number of local steps used. Then, a matching lower bound is given for FedLin to show that the strongly convex convergence result is tight.  \n\nThen, several gradient sparsification schemes are investigated (at the server and at the workers), which show that server-side sparsification is far less impactful than client-side sparsification. The impact of gradient sparsification is evaluated experimentally in Section 7. ", "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": "The fact that standard FL algorithms do not converge to the true minimizer is good to recall, but it's quite well-known so maybe too much space is spent on this. Otherwise, the algorithm is quite natural, and achieves its objective of providing linear convergence to the true minimizer in the deterministic setting. This being said, I have two major concerns, that I develop below. \n\n1) Convergence rates: \nI have very mixed feelings about Theorems 1-4 and the beginning of Section 4.1. It is nice to know that we can do local steps, but they do not seem to improve anything in this deterministic setting. Indeed, taking only one local step each time is enough. The step-size is divided by the number of local steps, and so workers end up doing a step of the same size as if they were only doing one step, with a similar result apparently. This only increases the computational cost, with no benefits.\n\nI believe that it would be great to highlight at least one setting in which this is not the case. Something like \"it cannot be better in the general setting but in some cases you really gain things\", because after reading Section 4 I don't see why I would use FedLin over parallel GD. It seems like FedLin was proposed and analyzed for the sake of performing local steps, instead of actually bringing something to the table. \n\nBesides, there is a matching lower bound, but it is only matching for the FedLin algorithm so it does not imply that other algorithms of this kind cannot do better. I know it is hard to use a general lower bound because it would require acceleration to match it, but if you consider the lower bound from [A], you obtain that you need at least $O(\\sqrt{\\kappa})$ communications to solve the problem (adapt the proof, or argue that you consider a graph of diameter 1 so time $\\tau \\sqrt{\\kappa}$, which means $\\sqrt{\\kappa}$ communications). \"Translated\" into a non-accelerated algorithm, this means that any algorithms requires time at least $\\kappa$ communications, and so clearly there is no hope to beat parallel-GD in this setting without further assumptions (e.g., on the local functions to allow for more parallelism). This kind of reasoning seems more convincing to me than Theorem 5 since it is not restricted to FedLin. \n\n\n2) Compression: \nWhy compress the gradients but not the parameters? They are the same dimension, and so it seems that the complicated compression scheme can only gain a factor 2 in general since full dimensional parameters will need to be sent anyway. Besides, both the server and the workers need to send full parameters so there is no upstream/downstream argument to be made on this part either. I have a hard time convincing myself of the interest of the compression scheme since it seems to affect only half of the actual communications. \n\n[A] Scaman, Kevin, et al. \"Optimal algorithms for smooth and strongly convex distributed optimization in networks.\" international conference on machine learning. PMLR, 2017.\n\n\n=====================================\n\nAfter the response and discussing with the other reviewers, I recognize that this paper advances the understanding of FL algorithms and thus raised my score accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "25Q-AGodUGb", "reviewer": "Reviewer_2DHS", "summary": "This paper proposes an optimization method for federated learning, FedLin, that is specifically designed to ensure fast convergence even in the presence of heterogeneous data. Notably, the authors show that FedLin converges to the global optimum (or just a critical point, in the case of non-convex functions) without decaying the client learning rate. This is in contrast to methods such as FedAvg, FedProx, and FedNova, which require decaying the client loss in order to circumvent \"objective mismatch\", where the methods are actually optimizing an altered surrogate loss.\n\nThis work also derives lower bounds matching the convergence of FedLin on quadratics, that explain the price and cost of performing multiple local update steps. They also analyze convergence using gradient sparsification at both the client and server. Finally, the paper shows the empirical benefits of FedLin over other methods on synthetic least squares and logistic regression problems.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper is a well-written paper with a clear focal idea, and a suite of great results to back up this idea. More specifically, I really enjoy that this paper essentially shows that certain convergence-accuracy trade-offs in federated learning (that exist for methods such as FedAvg, FedProx) can actually be circumvented in certain settings. The convergence results for FedLin are impressive, and **simple**. This is actually something wish to highlight. Client heterogeneity has caused a preponderance of assumptions needed to analyze the convergence of FL methods (eg. bounded gradient dissimilarity, specific learning rate schedules, etc.). This paper does away with all of this, and simply assumes smoothness. The results have no extra \"problem-dependent\" terms that are shrouded in asymptotics. The fact that the authors can also incorporate sparsification relatively easily into the framework is only an additional benefit.\n\nI also want to highlight the fact that the authors attempted to ensure that their results were as tight as possible via Section 4, something that can be challenging in federated learning. The takeaways from Theorem 5 are extremely informative, and give a succinct summary of the cost and gain of \"local training steps\" in federated learning. My only comment here is a question for future work: Can a similar lower bound be derived for a class of federated optimization algorithms that generalizes FedLin and other related methods (eg. SCAFFOLD, FedAvg)?\n\nThe experimental results are somewhat brief, and focus on synthetic data. I do not think this is a downside of the paper. Many works have noted that convergence failures of FedAvg can be shown in synthetic quadratic settings with just 2 clients. Moreover, this work is fundamentally a theoretical one (and a strong one at that), and I do not subscribe to the notion that all papers must offer all possible theoretical results and experimental results. I will note that even from an empirical side, the experiments that the authors do in Appendix J evincing the non-convergence of FedSplit in certain settings are also extremely valuable. One suggestion for improving these results would be to have a version of Figure 2 that compares FedLin to FedAvg, FedProx, SCAFFOLD, FedSplit, etc.\n\nOne contention I have with the work is that it ignores a number of works that first proposed and analyzed the speed-accuracy trade-off discussed in the abstract and in Section 2. In particular, it is worth noting that works such as (Malinovsky et al., 2020; Charles and Konecny, 2020; Fallah et al, 2020, and Pathak and Wainwright, 2020) showed that various federated learning and meta-learning methods (including FedAvg, FedProx, and FOMAML) are actually optimizing surrogate objectives. (Charles and Konecny, 2021) also formalized the actual underlying trade-off (as Propositions 1 & 2 don't actually show a trade-off they simply show non-optimality of the methods). Moreover, Propositions 1 and 2 are special cases of Theorem 1 of (Charles and Konecny, 2021).\n\nThis is all to say that I think that the paper would be improved by 1) giving proper credit to the works that developed the idea of speed-accuracy trade-offs and 2) focusing on what common facets of methods such as FedProx and FedNova you are going to change in order to break that trade-off. More succinctly, breaking these trade-offs is the novel, exciting contribution of this work, not showing that the trade-offs exists.\n\n$\\\\\\\\$\n\n# Review Update\n\nAfter reading the other reviews and the author feedback, I have kept my score as is. In particular, I think the convergence rates are still useful, if only as a benchmark against other methods (such as FedAvg) which do not converge globally, even in deterministic settings, unless parameters such as learning rate or number of steps is decayed so as to essentially degenerate to FedSGD.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have some discussion of limitations of the work in Section 4. However, I would argue that the primary limitation is not addressed, and should at least be discussed. Currently, FedLin effectively requires a full participation among clients. It also requires a kind of two-stage communication process in each round, where clients train, communicate with the server, and then compute a full gradient over their data. It is worth noting that this does increase the system-level complexity of FedLin as compared to methods such as FedAvg. I do not think that contending with partial participation need be in the scope of this work (as the full participation case aligns well with cross-silo federated learning), but I do believe this limitation should be mentioned.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the FedLin algorithm (which could be seen as an adaptation of FedSVRG) for cross-silo federated learning (without client sampling) and derives rigorous complexity guarantees. 

The reviewers commended the theoretical results, in particular the simple convergence proof of FedLin, and corresponding (algorithm specific) lower bound. 
Partial communication compression was studied as additional contribution. Yet, this aspect was assessed more critically by the reviewers, as  compression of the parameters is not supported.

The reviewers are of the opinion that their concerns were adequately addressed by the author's response (and that the promised changes by the authors will be implemented in the final version).

Additionally, I strongly encourage the authors to also include:
- a discussion of the relation to 'FedSVRG' [[Konecny et al, Federated Optimization: Distributed Machine Learning for On-Device Intelligence, 2016]](https://arxiv.org/pdf/1610.02527.pdf) and possibly additional literature related to 'federated SVRG' variants. In this regard, the claims on novelty should be phrased more carefully. (In particular also more carefully than in the author's response, as e.g. the mentioned algorithmic differences seem quite small and partially irrelevant (i.e. omitting a discussion of heterogenity for an algorithm that does not depend on heterogenity does not seem to be a limitation, etc.).
- a discussion of the 'client sampling' aspect would be appreciated. The limitation of FedLin to do a pass over all clients (and requiring twice as much communication as FedAvg) seems quite limiting in practice.
Decision: Accept (Poster)