Federated Learning of a Mixture of Global and Local Models
Authors: Filip Hanzely
Peter Richtarik
Venue:  (2021)
Keywords: optimization
federated learning
personalization
local SGD

Abstract: We propose a new optimization formulation for training federated learning models. The standard formulation has the form of an empirical risk minimization problem constructed to find a single global model trained from the private data stored across all participating devices. In contrast, our formulation seeks an explicit trade-off between this traditional global model and the local models, which can be learned by each device from its own private data without any communication. Further, we develop several efficient variants of SGD (with and without partial participation and with and without variance reduction) for solving the new formulation and prove communication complexity guarantees. Notably, our methods are similar but not identical to federated averaging / local SGD, thus shedding some light on the essence of the elusive method. In particular, our methods do not perform full averaging steps and instead merely take steps towards averaging. We argue for the benefits of this new paradigm for federated learning.


Under review as a conference paper at ICLR 2021
FEDERATED LEARNING OF A MIXTURE OF GLOBAL AND LOCAL MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose optimization formulation for training federated learning mod- els. The standard formulation has the form of an empirical risk minimization problem constructed to find single global model trained from the private data stored across all participating devices. In contrast, our formulation seeks an ex- plicit trade-off between this traditional global model and the local models, which can be learned by each device from its own private data without any communi- cation. Further, we develop several efficient variants of SGD (with and without partial participation and with and without variance reduction) for solving the new formulation and prove communication complexity guarantees. Notably, our meth- ods are similar but not identical to federated averaging / local SGD, thus shedding some light on the essence of the elusive method. In particular, our methods do not perform full averaging steps and instead merely take steps towards averaging. We argue for the benefits of this new paradigm for federated learning.
INTRODUCTION
With the proliferation of mobile phones, wearable devices, tablets, and smart home devices comes increase in the volume of data captured and stored on them. This data contains a wealth of potentially useful information the owners of these devices, and more so if appropriate machine learning models could be trained on the heterogeneous data stored across the network of such devices. The traditional approach involves moving the relevant data learning techniques can be efficiently applied (Dean et al.) 2012, Reddi et al.) 2016). However, this approach is not without issues. First, many device users are increasingly sensitive to privacy concerns and prefer their data to never leave their devices. Second, moving data from their place of origin to a centralized location very inefficient in terms of energy and time.
data center where centralized machine
1.1 FEDERATED LEARNING
Federated learning (FL) McMahan et al. 2016 Konečný al. [0 McMahan et al. 2017) has emerged as an interdisciplinary field focused on addressing these issues by training machine learning models directly on edge devices. The currently prevalent paradigm (Li et al. 2019 Kairouz et al. casts supervised FI. as an empirical risk minimization problem of the form
2019)
Σ f(()), WERd
min
where n is the number of devices participating in training, x E Rd encodes the parameters of global model (e.g., weights of neural network) and
fx))) = REgD, [f(x,
represents the aggregate loss of model z the local data represented by distribution D, stored on device One of the defining characteristics of FL that the data distributions D, may possess very different properties across the devices. Hence, any potential FL method is explicitly required to be able to work under the heterogeneous data setting.
The most popular method for solving IT] in the context of FL is the FedAvg algorithm (McMahan et al. 2016). In its most simple form, when one does not employ partial participation, model com- pression, stochastic approximation, FedAvg reduces to Local Gradient Descent (L.GD) (Khaled

---

Under review as a conference paper at ICLR 2021
et al. 2019; 2020), which is extension of GD performing more than single gradient step on each device before aggregation. FedAvg has been shown to work well empirically, particularly for non-convex problems, but comes with poor convergence guarantees compared to the non-local counterparts when data are heterogeneous.
Some issues with current approaches to FL
The first motivation for our research comes from the appreciation that data heterogeneity does not merely present challenges to the design of new provably efficient training methods for solving ( but also inevitably ruises questions about the utility of such global solution to individual users. Indeed, global model trained across all the data from all devices might be removed from the typical data and usage patterns experienced by an individual user as to render it virtually useless. This issue has been observed before, and various approaches have been proposed address it. For instance, the MOCHA (Smith et al., 2017) framework uses multi-task learning approach to allow for personalization. Next, (Khodak et al., 2019) propose a generic online algorithm for gradient- based parameter-transfer meta-learning and demonstrate improved practical performance over Fe- dAvg (McMahan et al., 2017). Approaches based on variational inference (Corinzia & Buhmann] 2019 cyclic patterns in practical FL data sampling (Eichner et al. 2019) transfer learning (Zhao ct al. 2018) and explicit model mixing (Peterson et al. 2019) have been proposed.
The second motivation for our work is the realization that even very simple variants of FedAvg, such as LGD, which should be casier to analyze, fail to provide theoretical improvements in communica- tion complexity over their non-local cousins, in this case, GD (Khaled et al. 2019 2020
This observation is at odds with the practical success of local methods in FL. This leads us to ask the question: if LGD does not theoretically improve upon GD solver for the traditional global problem ( perhaps LGD should not be seen as a method for solving ( at all. In such a case, what problem does LGD solve? A good answer to this question would shed light on the workings of LGD, and by analogy, on the role local steps play in more elaborate FL methods such as local SGD (Stich 2020 Khaled al. 2020 and FedAvg.
2 CONTRIBUTIONS
In our work we argue that the two motivations mentioned the introduction point in the same direction, i.e., we show that a single solution can be devised addressing both problems at the same time. Our main contributions are:
New formulation of FL which seeks an implicit mixture of global and local models. We propose a new optimization formulation of FL. Instead of learning a single global model by solving []] we propose to learn mixture of the global model and the purely local models which can be trained by each device i using its data D; only. Our formulation (see Sec. (3) lifts the problem from
Rd to Rind allowing each device i to learn a personalized model x; E IRd. These personalized
models are encouraged to not depart too much from their mean by the inclusion of a quadratic penalty vi multiplied by parameter À > 0. Admittedly, the idea of softly-enforced similarity of the local models was already introduced in the domain of the multi-task relationship learning (Zhang
& Yeung 2010, Liu al. 2017| Wang et al. 2018) and distributed optimization (Lan et al.) 2018
Gorbunov et al. 2019 Zhang et al./ (015)). The mixture objective we propose (see (2)) is a special
case of their setup. which justiñies our approach from the modeling perspective. Note that Zhang
eet al. (2155); Liu et al. (2017); Wang et al. (2018) provide efficient algorithms to solve the mixture objective already. However, none the mentioned papers consider the FI. application, nor they shed a light on the communication complexity of LGD algorithms, which we do in our work.
Theoretical properties of the new formulation. We study the properties of the optimal solution of our formulation, thus developing an algorithmic-free theory. When the penalty parameter is set to zero, then obviously, each device is allowed to train their own model without any dependence on the data stored on other devices. Such purely local models are rarely useful. We prove that the optimal
After our paper was completed, a lower bound on the performance of local SGD was presented that is worse than the known minibatch SGD guarantee (Woodworth et al. (200a)) confirming that the local methods do not outperform their non-local counterparts in the heterogeneous setup. Similarly, the henefit of local methods in the hon-heterogsneous scenario was questioned in (Wondworth al. 2020b).
2

---

Under review as a conference paper at ICLR 2021
local models converge to the traditional global model characterized by (I) at the rate (1/2). We also show that the total loss evaluated at the local models is never higher than the total loss evaluated at the global model (see Thm. 3.I).. Moreover, we prove insightful structural result for the optimal local models: the optimal model learned by device i arises by subtracting the gradient of the loss function stored on that device evaluated at the same point (i.e., a local model) from the average of the optimal local models (see Thm. (32)). As a byproduct, this theoretical result sheds new light on the key update step in the model agnostic meta-learning (MAML) method (Finn et al. (017)) which has a similar but subtly different structure 2 The subtle difference is that the MAML update obtains the local model by subtracting the gradient evaluated the global model. While MAML was originally proposed as heuristic, we provide rigorous theoretical guarantees.
Loopless LGD: non-uniform SGD applied to our formulation. We then propose a randomized Local Gradient Descent (I.2GD))-or solving our new formula- tion (Algorithm D. This method is, in fact, a non-standard application of SGD to our problem, and can be seen as an instance of SGD with non-uniform sampling applied to the problem of minimizing the sum of two convex functions (Zhao & Zhang 2015 Gower et al. 2019): the average loss, and the penalty. When the loss function is selected by the randomness in our SGD method, the stochastic gradient step can be interpreted as the execution of a single local GD step on each device. Since we set the probability of the loss being sampled be high, this step is typically repeated multiple times, resulting in multiple local GD steps. In contrast to standard LGD,, the number of local steps is not fixed, but random, and follows a geometric distribution. This mechanism is similar in spirit to how the recently proposed loopless variants of SVRG (Hofmann et al. 2015; Kovalev et al. (020) work in comparison with the original SVRG (Johnson & Zhang 2013a] Xiao & Zhang 2014). Once the penalty is sampled by our method, the resultant SGD step can be interpreted as the execution of an aggregation step. In contrast with standard aggregation, which performs full averaging of the local models, our method merely takes a step towards averaging. However, the step is relatively large.
gradient-based
Convergence theory. By adapting the general theory from (Gower et al. 2019) to our setting, we obtain theoretical convergence guarantees assuming that each Jú is 7-smooth and ju-ttrongyy convex (see Thm. 4.2).. Interestingly, by optimizing the probability of sampling the penalty (we get
p" N+..). which is an indirect way of fixing the expected number of local steps to 1 + X we prove
22 L log _ bound on the expected number of communication rounds (see Cor. 4.3 p. We believe an X+ R.
that this is remarkable in several ways. By choosing À small, we tilt our goal towards pure local models: the number of communication rounds is tending to 0 as À + O. If À + oo, the solution our formulation converges to is the optimal global model, and L2GD obtains the communication bound O
L log ) which matches the efficiency of GD.
What problem do local methods solve? Noting that L2GD is a (mildly nonstandard) version of LGD which is a key method most local methods for FL are based on, and noting that, as we show, L2GD solves our new formulation of FL, we offer new and surprising interpretation of the role of local steps in FL. In particular, the role of local steps in gradient type methods, such as GD, is not to reduce communication complexity, as is generally believed. Indeed, there is no theoretical result supporting this claim in the key heterogeneous data regime. Instead, their role is to steer the method towards finding a mixture of the traditional global and the purely local models. Given that the stepsize is fixed, the more local steps are taken, the more we bias the method towards the purely local models. Our new optimization formulation of FL formalizes this as it defines the problem that local methods, in this case L2GD, solve. There is an added benefit here: the more we want our formulation to be biased towards purely local models (i.e., the smaller the penalty parameter is), the more local steps does L2GD take, and the better the total communication complexity of L2GD becomes. Hence, despite a lot of research on this topic, our paper provides the first proof that a local method (e.g., L2GD) can be better than its non-local counterpart (c.g., GD) in terms of total communication complexity in the heterogeneous data setting. We are able to do this by noting that local methods should better be seen methods for solving the new FL formulation proposed here.
o Generalizations: partial participation, local SGD and variance reduction. We further gener- alize and improve method by allowing for (i) stochastic partial participation of devices in each communication round,(ii) subsampling on each device which means we can perform local SGD steps
"hhe connection of Fl. and multi-task meta learning is discussed in Kairouz ct al. 2019). for example.
'To be specific, 1.2GD is equivalent to Overlap L.GD Wang et al. 2020) with random local loop size.
3

---

Under review as a conference paper at ICLR 2021
instead of local GD steps, and (iii) total variance reduction mechanism to tackle the variance com- ing from three sources: locality of the updates induced by non-uniform sampling (already present in L2GD), partial participation and local subsampling. Due to its level of generality, this method, which we call L.2GGD++ is presented in the Appendix only, alongside the associated complexity results. In the main body of this paper, we instead present simplified version thereof, which call L2SGD+ (Algorithm 3 The convergence theory for it is presented in Thm. 5.1 and Cor. 5.2
Heterogeneous data. All our methods and convergence results allow for fully heterogeneous data and do not depend on any assumptions on data similarity across the devices.
Superior empirical performance. We show through ample numerical experiments that our theo- retical predictions can be observed in practice.
3 NEW FORMULATION OF FL
We now introduce our new formulation for training supervised FL models:
min (F(x) == f(x) + xb(x))
Th ERd
(2)
[(x)= - Σ M(1)),
((x)) = 2m
Σ 2=1
l0s - x 1122,
where A > 0 is penalty parameter, 21,.... Fn Rd are local models, x (I1, (2.............................. Fn) E Rnn and T. := x -i Ty is the average of the local models.
Due to the assumptions on fi will make in Sec. a unique solution, which we denote (A) == (21 (A). F.....,,nn (A)) E RRnd We further let o (X) =
3.1 F is strongly convex and hence 2 has
(A). We now comment on the rationale behind the new formulation. Σ >
Local models (A = 0). Note that for each i, (0) solves the local problem ming,e3d f((x;). That is, (0) is the local model based on data D; stored on device i only. This model can be computed by device without any communication whatsoever. Typically, D; is not rich enough for this local model be useful. In order to learn better model, one has to take into account the date from other clients as well. This, however, requires communication.
Mixed models (A E (0, oc)). As X increases, the penalty (x) has an increasingly more substantial effect, and communication is needed to ensure that the models are not too dissimilar, as otherwise the penalty (x) would be too large.
Global model (A = -o). Let us now look at the limit case À + co. Intuitively, this limit case should force the optimal local models to be mutually identical, while minimizing the loss ʃ. In particular, this limit case will solve min { (zz $1.... In E RRd 21 = = = )n which is equivalent to the global formulation 2 Because of this, let us define (=())) for each i to be the optimal global solution of I and let ar (c)
"n.)).....,., (20))
3.1 TECHNICAL PRELIMINARIES
We make the following assumption on the functions ft:
Assumption 3.1 For each i, the function J. Rdd - R is L-smooth and j-strroglyy convex.
For F4, y E Rd, (I,, y:) denotes the standard inner product and ||ж||| = (x,, 1/2 2 is the stan- dard Euclidean norm. For vectors
Rad, y (8).... Vn E Rnd define the standard inner product and norm via (x., () = En (a.,))))) ||x] = EL 1=:111 Note that the separable structure of f implies that (Vf(())) I (z),, Vf2(z)).... (z,()))
(II,...,
x [Vf((,), i.c. Vf(z)
Note that Assumption 3.1 implies that is Ly-smooth with L, == L and py-stnongly convex with u == Clearly, & is convex by construction. It can be shown that a is sm-oohh with 4. = 1
IIf A and 21 22
Tn does not hold, we have F(x) = Therefore, we can restrict
ourselves 3i 22 F. without loss of generality.
4

---

Under review as a conference paper at ICLR 2021
(see Appendix). We also easily see that (Ve(z)), (22 =s(see Appendix), which implies (x)) = Σ I((v(=)))l= [V+(()]
3.2 CHARACTERIZATION OF OPTIMAL SOLUTIONS
Our first result describes the behavior of I (x(()) and ((((A)) as a function of X. Theorem 3.1 The function À + (b(x(A)) is non-increasiin, and for all X > O we have (x((A)) v -
(3)
Moreover, the function À (x(()) is non-decreasing, and all X we have f(x(A)) S f(((o))).
(4)
Ineq. (3) says that the penalty decreases to zero as À grows, and hence the optimal local models (A) increasingly similar as grows. The second statement suggest that the loss fx(()) increases with X, but never exceeds the optimal global loss / (=((o)) of the standard FL formulation ①
We now characterize the optimal local models which connect model to the MAML frame- work (Finn et al., 2017), as mentioned in the introduction.
Theorem 3.2 For each X 0 and $ S n we have
xy (A) ((A) (A))
(5)
Further, we have V(((z;(A)) = and vb (x(())
Xx [V((())))
The optimal local models (5) are obtained from the average model by subtracting multiple of the local gradient. Observe that the local gradients always sum up to zero at optimality. This is obviously true for oo, but it is bit less obvious that this holds for any 0.
Next, we argue the optimal local models converge to the traditional FL solution at the rate O(1AA).
Theorem 3.3 Let P(z) = # E. [i(=). Then, x0()) is the unique minimizer of P and we have \VP(E()) 212( - J(x(0)))
L2GD: LOOPLESS LOCAL GD
In this section we describe new randomized method for solving the formulation 2 Our method a non-uniform SGD for (2) seen as 2-sum problem, sampling either V or V to estimate V..
Letting 0 p < 1, we define stochastic gradient of F' at Rnd as follows
f(()) with probability
1-P
G(x)
AVv(2) with probability
Clearly, G(x) is an unbiased estimator of Fx)). This leads to the following method for minimizing F. which we call L2GD: x z² (G(**) Plugging the formulas for V Vf(x) and (+)(x) into (7. and writing the resulting method in a distributed manner, we arrive Algorithm D In each iteration, coin & is tossed and lands with probability p and with probability
p. If O. 88. and if & 1, Master shifts each local model towards the average via (9). As we shall see Sec. 4.2 our theory limits the value of the stepsize a, which has the effect that the ratio aA cannot exceed Hence, 19 convex combination of x and a.
all Devices perform one local GD step
np
Note that Algorithm 1 is only required to communicate when two consecutive coin tosses land different value (see the detailed explanation in Sec. Sec. of the appendix). Consequently, the expected number of communication rounds in k iterations of L.2GD is p(1 k)k.
Our algorithm statements do not take the data privacy into the consideration. While privacy is very important aspect of FL; in this paper, tackle different FL challenges and thus ignore privacy issues. However, the proposed algorithums can be implemented in a private fashion well using tricks that are used in the classical FL. scenario Bonawitz et al.) 2017
Remark 4.1
5

---

Under review as a conference paper at ICLR 2021
Algorithm L2GD: Loopless Local Gradient Descent
Input: xf = 5 IR:d, stepsize a, probability p
for k 0, 1, do
{ = with probability and with probability 1 -
if 0 then
All Devices i == I,..., perform a local GD step:
x+1 x
z n(1
(8)
else
Master computes the average x²
Σ
=;
i=1
Master for each computes step towards aggregation
k+1 2
(1-
ab up
(9)
end if end for
4.1 THE DYNAMICS OF LOCAL GD AND AVERAGING STEPS
Notice that the average of the local models does not change during an aggregation step. Indeed, n2
gk+1 is equal to #/2 Σ
(1 an
ad
several averaging steps take place in a sequence, the point a = 2² p remains unchanged. and each local model z merely moves along the line joining the initial value of the local model the start of the sequence and with each step pushing x closer to the average
In summary, the more local GD steps are taken, the closer the local models get to the pure local models; and the more averaging steps are taken, the closer the local models get to their average value. The relative number of local GD vs. averaging steps is controlled by the parameter p. the expected # of local GD steps is 1 and the expected number of consecutive aggregation steps is --p: p¹
4.2 CONVERGENCE THEORY
We now present our convergence result for L2GD.
Theorem 4.2 Let Assumption
3.1 hold. If S 22, then
1
E [liC x(2))1]] s 5(1 ay k
11000 0 xx))|12
2nng
where L max 1 } and 0² Σ - (VI( +1 - {A)]I²).
Let us find the parameters p. a which lead to the fastest rate, to push the error within neighborhood of the optimum i.c.. achieve < -11=0-xxi x())12 + 2nn
(O(s) + 2nao²)
P
-|aa-= - =(a)) <
(10)
Corollary 4.3 The value p TAx minimizes both the number of iterations and the expected number of communications for achieving (10). In particular, the optimal number of iterations is L log } and the optimal expected number of communications is 2X L log X+L F
we choose = p², then ad 2. and the aggregation rule 9 in Algorithm becomes
(x. x*)
(11)
'In Sec. we propose a variance reduced algorithm which removes the (2nnee neeighoorhood
4.2 In that setting, goal will be achieve E [|Ia- x(a))) s a a||00 =()i]l?
from Thm.

---

Under review as a conference paper at ICLR 2021
Conmestelar mundd ber
DA ana
BMA -w
110
0.80
Figure 1: Distance of solution (x) of pure local solution x(0) and global solution x(oo) as function of A. Logistic regression on ala dataset. See Appendix for the setup.
Figure 2: Communication rounds to get F(x*) F(=*)-f(x") I 10-6 as a function of p with F(a")-
p = 0.09 (for L2SGD+). Logistic regres- sion on ala dataset with = 0.1.
while the local GD step (8) becomes --- =-=1=
fa Notice that while our method does not support full averaging as that is too unstable, 11 suggests that one should take a large step towards averaging. As get smaller, the solution the optimization problem (2) will increasingly
favour pure local models, i.e., (A) - (0) arg min fi for all as X + 0. Pure local mod- els can be computed without any communication whatsoever and Cor. 4.3 confirms this intuition: the optimal number of communication round decreases to zero À - O. On the other hand, as + oc, the optimal number of communication rounds converges to 24 log E which recovers the performance of GD for finding the globally optimal model (see Fig. [
In summary, we recover the communication efficiency of GD for finding the globally optimal model as oo (ignoring the (2nce") neighboroooh) However, for other values of X, the communi- cation complexity of L2GD is better and decreases to as X + O. Hence, our communication complexity result interpolates between the communicution complexity of GD for finding the global model and the zero communication complexity for finding the pure local models.
LOOPLESS LOCAL SGD WITH VARIANCE REDUCTION
As we have seen in Sec. 4.2 L2GD is specific instance of SGD, thus only converges linearly to a neighborhood of the optimum. In this section, we resolve the mentioned issue by incorporating control variates to the stochastic gradient (Johnson & Zhang 2013b Defazio et al.] 2014). We go further: we assume that each local objective has finite-sum structure and propose an algorithm, L2SGD+, which takes local stochastic gradient steps, while maintaining (global) linear convergence rate. As a consequence, L2SGD+ is the first local SGD with linear convergence For convenience, present variance reduced local GD (i.e., local subsampling) in the Appendix.
Assumption 5.1 Assume that Jt has a finite-sum structure: f(x),) = 1 E Si (x.). Let Sig be convex, L' L'mshhth while fü is p-strongly convex (for each 1 j < m, 1 siiin n).
5.1 CONVERGENCE THEORY
We are now ready to present convergence rate of L2SGD+ (the algorithm, along with the efficient implementation presented in Appendix C.4).
Theorem 5.1 Let Assumption 5.1 hold and choose min {
(1-p) Then the iteration 41/+pm 4x+1
complexity of Algorithm is max
4l'+um
1ht2
log 1.
(1-P)H
pp
Next, we find the value of that yields both the best iteration and communication complexity.
"We are aware that linearly converging local SGD (with À = oc) can be obtained a particular instance of the decoupling method (Mishchenko & Richtárik 2019). Other variance reduced local SGD algorithms (Liang
2019, Karimireddy 2019) Wu 2019) achieve linear convergence.
7

---

Under review as a conference paper at ICLR 2021
Corollary 5.2 Both communication and iteration complexity of L2SGD+ are minimized for p
4hty TX+1 -4-1/-(m+1jp The resulting iteration complexity is A + 4 + +m 1) log E. while the com-
munication complexity is 41/442 44
+ m log !
Note that with + 20, the communication complexity of L22GD+ tends to (+ + m log _ which is communication complexity of minibatch SAGA to find the globally optimal model (Hanzely & Richtárik 2019). On the other hand, in the pure local setting (A = 0). the communication complexity becomes log _ this is because the Lyapunov function involves a term that measures the distance of local models, which requires communication to be estimated.
Remark 5.3 L2SGD+ is the simplest local SGD method with variance reduction. In the Appendix, we present L2SGD++ which allows for 1) an arbitrary number of data points per client and ar- bitrary local subsampling, 2) partial participation of clients, and 3) local SVRG-like updates of control variates (thus better memory). Lastly, L2SGD++ exploits the complex smoothness structure of the local objectives, resulting in lighter rates.
6 EXPERIMENTS
In this section, we numerically verify the theoretical claims from this paper. We only present single experiment here, all remaining ones along with the missing details about the setup are in the Appendix. In particular, the Appendix includes two more experiments. The first one studies how p (communication) influences the convergence of L2SGD+. The second experiment aims to examine the effect of parameter À on the convergence rate of L2SGD+
2011). The data were We consider logistic regression problem with LibSVM data (Chang & Lin
normalized that f(, is 1-smooth for each j, while the local objectives 10 -strongly convex. In order to cover a range of possible scenarios, we have chosen a different number of clients for each dataset (see the Appendix). Lastly, the stepsize was always chosen according Thm. 5.1
We compare three different methods: L2SGD++ L2GD with local subsampling (L22GG in the Ap- pendix), and L2GD with local subsampling and control variates constructed for ei only (L2SGD2 in the Appendix; similar to (Liang et al. 2019h). ). We expect L2SGD+ to converge to the global opti- mum linearly, while both L2SGD and L2SGD2 to converge to certain neighborhood. Each method is applied to two objectives constructed by different split of the data among the devices. For the homogeneous split, we randomly reshuffle the data. For heterogeneous split, we first sort the data based on the labels and then construct the local objectives according to the current order.
(250)
(250)
All
12900
125012
220004
125034
Figure 3: L.2GDD+, vs L2SGD vs 1.2SGD2 with identical stepsize (details in the Appendix).
Fig. demonstrates the importance of variance reduction it ensures fast global convergence of L2SGD+. while the neighborhood is slightly smaller for L2SGD2 compared to L2SGD. As pre- dicted, data heterogeneity does not affect the convergence speed of the proposed methods.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1200-1205.
ACM, 2017.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Kam Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Chih- Chih-Chung Chang and Chih-Jen Lin. LibSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011.
L. Corinzia and J. M. Buhmann. Variational federated multi-task learning. arXiv preprint arXiv:1906.06268. 2019.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, and et al. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, pp. 1223-12311 2012.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pp. 1646-1654, 2014.
H. Eichner, Koren, H. B. McMahan, N. Srebro, and K. Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- leta-learnnng for fast adaptation of deep networks. In International Conference on Machine Learning, 2017.
Nidham Gazagnadou, Robert M Gower, and Joseph Salmon. Optimal mini-batch and step sizes for SAGA. In International Conference on Machine Learning, 2019.
Eduard Gorbunov, Darina Dvinskikh, and Alexander Gasnikov. Optimal decentralized distributed algorithms for stochastic convex optimization. arXiv preprint 19X1::1911.0736: 2019.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory of sgd: Variance reduction,
sampling, quantization and coordinate descent. In The 23rd International Conference Artificial Intelligence and Statistics, 2020.
Robert Mansel Gower; Peter Richtárík, and Francis Bach. Stochastic quasi-gradient methods: vari- ance reduction via Jacobian sketching. vrXiv:1805.0266 2018.
Robert Mansel Gower, Nicolas Loizon, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Pe- ter Richtárik. SGD: General analysis and improved rates. In Proceedings of the 36th In- ternational Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 5200-5209, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL htttp://proceddinn mlr press /vcsss////9/ v97 / qian 9b. html
Filip Hanzely and Peter Richtárik. One method to rule them all: Variance reduction for data, param- eters and many new methods. arXiv preprint urXiv:/90s. /266, 2019.
Thomas Hofmann, Aurelien Lucchi, Simon Jaciste-Julien, and Brian McWilliams. Variance re- duced stochastic gradient descent with neighbors. In Advances in Neural Information Processing Systems, pp. 2305-2313, 2015.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26, pp. 315-323, 2013a.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Newral Information Processing Systems, pp. 115-323, 2013b.
Peter Kairouz, H. Brendan McMahan, and et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1912:1912.00477.0 2019.

---

Under review as a conference paper at ICLR 2021
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for on-device federated learning. arXiv preprint arXtv:1910.06377, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on hetero- geneous data. NeurlPS Workshop on Federated Learning for Data Privacy and Confidentiality. pp. 1-11, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference Artificial Intelligence and Statistics (AISTATS 2020), 2020.
M. Khodak, M.-F. Balcan, and A. Talwalkar. Adaptive gradient-based meta-learning methods. In Advances in Neural Information Processing Systems 32, 2019.
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: distributed machine learning for on-device intelligence. urXiv:/610.02527, 2016a.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016b.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.
Guanghui Lan, Soomin Lee, and Yi Zhou, Communication--fficiii algorithms for decentralized and stochastic optimization. Mathematical Programming, pp. 1-48, 2018.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods, and future directions. arXiv preprint
2019.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv:1912 12844, 2019.
Sulin Liu, Sinno Jialin Pan, and Qirong Ho. Distributed multi-task relationship learning. In Pro- ceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 937-946, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint arXiv: 1602.0:602..5622 05020. 2016.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas Communication-effan learning of deep networks from decentralized data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Konstantin Mishchenko and Peter Richtárik. A stochastic decoupling method for minimizing the sum of smooth and non-smooth functions. arXiv preprint 19Xiv:1955.11555 2019.
Yurii Nesterov. Introductory lectures on corvex optimization: a basic course (Applied Optinization). Kluwer Academic Publishers, 2004.
Daniel Peterson, Pallika Kanani, and Virendra Marathe. Private federated learning with domain adaptation. arXiv preprint arXiv:1912.0673 2019.
Xun Qian, Zheng Qu, and Peter Richtárik. L-SVRG and L-Katyusha with arbitrary sampling. arXiv preprint arXiv:1906.0144 2019a.
Xun Qian, Zheng Qu, and Peter Richtárik. SAGA with arbitrary sampling. The 36th International Conference Machine Learning, 2019b.
10

---

Under review as a conference paper at ICLR 2021
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling II: Expected sep- arable overapproximation. Optimization Methods and Software, 31(5):858 884, 2016. doi: 10.1080010555788.20000 201...01888.00110.19111 URL bttp://dx.com doi. wttp:/.....00011555555555511111.
2016 90361
Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczos, and Alex Smola. AIDE: fast and communication efficient distributed optimization. arXiv:1608.06879, 2016.
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1-2)4433448, 2016.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi- task learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4424-4434. Curran Associates, Inc., 2017. URL http: /tpp:///pppe..a/e nwws.cccpapp...eeee 7029 federated multi task- Learning.... .ddf
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2020.
Jianyu Wang, Hao Liang, and Gauri Joshi. Overlap local-sgd: An algorithmic approach to hide communication delays in distributed sgd. ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8871-8877 IEEE, 2020.
Weiran Wang. Jialei Wang, Mladen Kolar, and Nathan Srebro. Distributed stochastic multi-task learning with graph regularization. arXiv preprint arXiv: 2018.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. arXiv preprint MxXiv:2006.047::3 2020a.
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 preprint arXiv:2002.0783) 2020b.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance- reduced stochastic gradient descent with robustness to byzantine attacks. arXiv preprint arXiv:1912.12716. 2019.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with clastic averaging sgd. In Advances in neural information processing systems, pp. 685-693, 2015.
Yu Zhang and Dit- Yan Yeung. A convex formulation for learning task relationships in multi-task learning. Uncertainty in Artificial Intelligence, pp. 733-442, 2010.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Proceedings of the 32nd International Conference on Machine Learning, PMIR, volume 37, pp. 1-9, 2015.
Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra. Federated learning with non-iid data. arXiv preprint arXiv: 1806 00582, 2018.
11

---

Under review as a conference paper at ICLR 2021
Appendix
Federated Learning of a Mixture of Global and Local Models
CONTENTS
1
Introduction
Federated learning
2
Contributions
3
New Formulation FL
3.1
Technical preliminaries
3.2
Characterization of optimal solutions
4
L2GD: Loopless Local GD
The dynamics of local GD and averaging steps
4.2
Convergence theory
5
Loopless Local SGD with Variance Reduction
5.1
Convergence theory
Experiments
Possible Extensions
14
Experimental Setup and Further Experiments
14
B.1
Comparison of the methods
14
B.2 Effect of
16
B33 Effect of
16
Remaining Algorithms
19
C.I
Understanding communication of L2GD
19
L2GD and full averaging
19
Local GD with variance reduction
19
L.2GGD Algorithm and the efficient implementation
5 Local SGD with variance reduction general method
21
C.6
Local stochastic algorithms
Missing Lemmas and Proofs
26
D.I
Gradient and Hessian of
26
D.2 Proof of Theorem 3.1
27
D.3 Proof of Theorem 3.2
28
12

---

Under review as a conference paper at ICLR 2021
D.4 Proof of Theorem 3.3
28
D.5 Proof of Theorem
28
D.6 Proof of Lemma
29
D.7 Proof of Corollary 4.3
29
D.8 Proof of Corollary 5.2
30
D.9
Proof of Theorems 5.
C.6 and C.7
30
D.9.1
GJS
30
D.9.2
Variance reduced local SGD as special case GJS
................................
D.9.3
Proof of Theorem and Theorem C.7
31
D.9.4
Proof of Theorem 5.
33
13

---

Under review as a conference paper at ICLR 2021
A POSSIBLE EXTENSIONS
Our analysis of L2GD can be extended to cover smooth convex and non-convex loss functions fa (we do not explore these directions). Further, our methods can be extended decentralized regime where the devices correspond to devices of connected network, and communication is allowed along the edges of the graph only. This can be achieved by introducing an additional randomization over the penalty vb. Further, our approach can be accelerated in the sense of Nesterov (Nesterov)
2004) by adapting the a variant of Katyusha (Allen-Zhu, 2017 Qian et al. 2019a) to our setting, thus further reducing the number of communication rounds.
B EXPERIMENTAL SETUP AND FURTHER EXPERIMENTS
In all experiments in this paper, consider simple binary classification model logistic regres- sion. In particular, suppose that device i owns data matrix A, E imx along with corresponding labels b E ((1, 1) The local objective for client is then given as follows
f((2) = Σ (z) - |
where f = log (1 + exp ((A.),.. b,))
The rows of data matrix A were normalized to have length so that each fig is 1-smooth for each j. At the same time, the local objective on each device 10 strongly convex. Next, datasets are from LibSVM (Chang & Lin 2011).
In each case, we consider the simplest locally stochastic algorithm. In particular, each dataset is evenly split among the clients, while the local stochastic method samples single data point each iteration.
We have chosen a different number of clients for each dataset that cover different possible scenarios. See Table for details (it also includes sizes of the datasets). Lastly, the stepsize was always chosen according Thm. 5.1
Table I: Setup for the experiments.
(Sec
(Sec
(Ser
ala
1605
123
5
321
10
0.1
0.1
0.1
mushroome
1224
112
12
677
10
0.3
phiihhing
11
11
1005
10
0.1
0001
madelon
2.000
500
30
40
10
0.1
0.02
0.08
dake
7129
4
10
0.1
0.1
gieette.ccale
0.00
BBa
23 696
123
8
109
10
0.1
0.1
0.1
B.1 COMPARISON OF THE METHODS
In our first experiment, verify two phenomena:
The effect of variance reduction on the convergence speed of local methods. We compare 3 different methods: local SGD with full variance reduction (Algorithm (3). shifted local SGD (Algorithm 7 and local SGD (Algorithm (6) Our theory predicts that fully vari- ance reduced algorithm converges to the global optimum linearly, while both shifted local SGD and local SGD converge to neighborhood of the optimum. At the same time, the neighborhood should be smaller for shifted local SGD.
The claim that heterogeneity the data does not influence the convergence rate. We con- sider two splits of the data heterogeneous and homogeneous. For the homogeneous split, we first randomly reshuffle the data and then construct the local objectives according to the current order (i.e., the first client owns the first m indices, etc.). For heterogeneous split, we first sort the data based on the labels and then construct the local objectives accordingly (thus achieving the worst-case heterogeneity). Note that the overall objective to solve is
14

---

Under review as a conference paper at ICLR 2021
different in homogeneous and heterogeneous case thus plot relative suboptimality of the objective (i.e., -(=")-P(r") to directly compare the convergence speed. F(2")-
In each experiment, we choose p 0.1 and À such choice mean that p is very close to optimal. The other parameters (i.e., number of clients) are provided in Table I Fig. presents the result.
101
L25GD
L25G02
Relatave suboptimallyy
Helatare suboptimalty
10-1
L25GD
Hom L25GD
L25GD2
16-4
Hom 125GD2
Hom L25GD+
26-4
L25602
26-1
10:10
200
100
350
2:00
Data 04.5585
Data passes
Dataset:: phishing
Dataset: madelon
10
L25G02
Relative sube-fimaalty
L25GD
Relatwv subegttmaltt
L29GD=
Hom 125G02
L250DD2
Hom L25GD
10-1
L25GD
to
Hom L25602
000*
L25GD
22:12
50
200
100
203
259
300
200
400
50
200
250
200
220
300
224
100
passes
passes
Dataset: duie
Dataset: gisette, scalle
L25GD
L2SGD+
Reelative suboptiraltty
L25GD
Belative subastmaltty
L25GD
L25GD
L25GD
L2SG02
L250D2
Hom L25GD
Hom L25G0
22.5
suboptm-sltt
22-3
31-
L25GD+
L25G02
125GD
Hom L2SCD
Hom L25G0
Data passes
Figure 4: Variance reduced local SGD (Algorithm 3) shifted local SGD (Algorithm 7 and local SGD (Algorithm (6 applied on LibSVM problems for both homogeneous split of data and Hetero- geneous split of the data. Stepsize for non- non-variance reduced method was chosen the same as for the analogous variance reduced method.
As expected, Figure 4 clearly demonstrates the following:
15

---

Under review as a conference paper at ICLR 2021
Full variance reduction always converges to the global optima, methods with partial vari- ance reduction only converge to neighborhood of the optimum.
Partial variance reduction (i.e., shifting local SGD) is better than not using control variates at all. Although the improvement in the performance is rather negligible.
Data heterogeneity does not affect the convergence speed of the proposed methods. There- fore, unlike standard local SGD, mixing the local and global models does not suffer the problems with heterogeneity.
B.2 EFFECT OF p
In the second experiment, we study the effect of on the convergence rate variance reduced local SGD. Note that immediately influences the number of communication rounds average, the clients take (p-1- -1 local steps in between two consecutive rounds of communication (aggrega- tion).
In Section 5 we argue that, is optimal (in terms of the convergence rate) to choose p of order p" + Figure compares p p* against other values of p and confirms its optimality (in terms of optimizing the convergence rate).
While the slower convergence of Algorithm with < pz expected (i.c., communicating more frequently yields faster convergence), slower convergence for p > p* is rather surprising; in fact, it means that communicating less frequently yields faster convergence. This effect takes place due the specific structure of problem (12); it would be lost when enforcing I (corresponding to À = oo).
Fn
B.3 EFFECT OF
In this experiment we study how different values of influence the convergence rate of Algorithm 3 given that everything else (i.e., is fixed. Note that for each value of À we get different instance of problem (12;; thus the optimal solution is different as well. Therefore, order to make a fair com-
parison between convergence speeds, plot the relative suboptimality (i.e., F(*)) F(x" the data passes. Figure 1 presents the results.
against
F(x")-F(x")
The complexity of Algorithm 3
is
(T==)T)) log 1 soon X < X
Lp [1-p)* otherwise the
complexity is O PM log This perfectly consistent with what Figure shows the choice À < X*
resulted in comparable convergence speed than À = A+; while the choice À > A yields noticeably worse rate than À X*
Given that a is small.
16

---

Under review as a conference paper at ICLR 2021
Dataset
mushreams
10-1
0.014
Relative suboptimalty
Relative subogttmality
10
0.476
10-1
0.009
0.027
to-4
0.091
0.273
325
100
175
200
25
15
106
150
115
300
passes
Dataset: phishing
Dataset: madelon
0.009
Relatiee suterpiimaln
0.092
Relativ suboptmaaity
0.020
0.909
gisette
36"
132
Rebilive suboptrrainy bity
Relathve subostiaalty
0.003
10
0.002
0.017
0.086
0.050
0.857
0.500
Data passes
Data passes
Dataset:
21-4
0.009
0.091
0.273
201
152 3.7
Data paises
Figure 5: Effect of the aggregation probability p (legend of the plots) on the convergence rate of Algorithm Choice p p" corresponds red dotted line with triangle marker. Parameter À was chosen each case as Table indicates.
17

---

Under review as a conference paper at ICLR 2021
Dataset
007
0.18
Delative aubogttmality
Relative suboptimals
40
0.0014
wnt
0.56
0.022
to
0.0044
10-1
325
100
175
208
25
15
106
150
115
300
passes
Dataset: phishing
Dataset: madelon
0.0023
Relatvv subcptmallty
9.1e 05
Belatve subeptimalty
0. 0.0011
0.00221
3.6e-06
10
00
13-9
gisette
30"
Reiative subostraalty
Rekitive suboptrraily
t0:1
1011
0.00075
0.028
36-05
0.0011
1.2e.06
Data passes
Data passes
Dataset:
21
0.35
0.014
0028
201 1/
1/s
Data paises
Figure 6: Effect of parameter À (legend of the plot) on the convergence rate of Algorithm 3 The choice À = X corresponds to borwn dash-dotted line with diamond marker (the third one from the legend). Aggregation probability was chosen in each case as Table Tindicates.
18

---

Under review as a conference paper at ICLR 2021
C REMAINING ALGORITHMS
C.I UNDERSTANDING COMMUNICATION OF L2GD
Example C.I In order better understand when communication takes place in Algorithm L con- sider the following possible sequence of coin tosses: 0, O, 1,0,1,11 1,00 The first two coin tosses lead to two local GD steps (8) on all devices. The third coin toss lands 1, at which point all local models x are communicated to the master, averaged to form I², and the step ( towards averag- ing taken. The fourth coin toss is O, and this point, the master communicates the updated local models back to the devices, which subsequently perform single local GD step ( Then come three consecutive coin tosses landing 1. which means that the local models are again communicated to the master, which performs three averaging steps (9) Finally, the eighth coin toss lands O, which makes the master send the updated local models back to the devices, which subsequently perform single local GD step.
This example illustrates that communication needs to take place whenever two consecutive coin tosses land a different value. If O is followed by 1, all devices communicate to the master, and if followed by a 0, the master communicates back to the devices. It standard to count each pair of communications, round.
and the subsequent Masier- single communication
Lemma C.2 The expected number of communication rounds in k iterations of L2GD is p(1 p)k.
C.2 L2GD AND FULL AVERAGING
Is setup such that conditions of Thm. 4.2 are satisfied and the aggregation update ( is identical full averaging? This equivalent requiring p < such that at np. However, we have a S A S np, which means that full averaging is not supported by our theory.
2C
C.3 LOCAL GD WITH VARIANCE REDUCTION
In this section, we present variance reduced local gradient descent with partial aggregation. In partic- ular, the proposed algorithm (A (Algorithm incorporates control variates to Algorithm Therefore, the proposed method can be seen as special case of Algorithm with m We thus only present it for pedagogical purposes, as it might shed additional insights into approach.
In partieular, the update rule of proposed method will k+1 x ag where
9" = (AV
+ I= - (1 (1-p)) 1zk) -I + n - with probability 1 1
with probability p
for some control variates vectors J t Rnn A quick check gives E [g = vʃ(x*) (V VF(*").
thus the direction we are taking is unbiased regardless of the value of control variates J & The goal is to make control variates J & correlated with n v ((**) and n nx*)) One possible so-
lution to the problem is for J q to track most recently observed values of nVf(() and n. n.V))))) which corresponds to the following update rule
(n J* R f(*)))
with probability
k+1 k+1 (g (+11
with probability 1 1-p"
A specific, distributed implementation of the described method is presented as Algorithm 2 The only communication between the devices takes place when the average model _² is being computed (with probability p), which is analogous to standard local SGD. Therefore we aim to set p rather small.
Note that Algorithm 2 is a particular special case of SAGA with importance sampling Qian et al. 2019b;; thus, we obtain convergence rate the method for free. We state it as Thm. C.3
"Specifically we aim have Corr J [x**) 1 and Cor [n-
in-''ph T AV as x
19

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Variance reduced local gradient descent
Input: xf
J 4 56
IRd stepsize a, probability p
Ju =
- = 0 Rd
for 0, 1, ..... do
{ = with probability and 0 with probability 1 - p
if g then
All Devices i = ,!:
Compute V {((())))
o k+1 x a n1 (1-))) n T + -ypb
ypb
Set J )) wptt= = /
else
Master computes the average F.K = Σ i= xt
Master does for all 1,.... ni:
Set x k+1 2 np
(u xZ) (p- 1)m -11
Set k+ Maa ) g J
end if end for
Theorem C.3 Let Assumption 3.1 hold. Set a niin
(1-p)
adta) A6-n
Then, iteration complexity
of Algorithm is
max 4L++ 4d+t (w(1-p)' up
log?
Proof: Clearly,
F(x) = f()+ )p)))= = 2f(x) + (x)(2))
(
Note that v/ is 2A smooth and f is 2L smooth. At the same time, F is strongly convex. Using
convergence theorem of SAGA with importance sampling from (Qian et al. 2019b Gazagnadou et al. 2019), we get
E [[F(x*) + ST(J Tb]] s (1 a1= (F(x") gT((", TT)),
where
T(J Vb = n
| M(xiAA) - a()))| || ((((((()))11
and a min
(1-p) p 41.+p' 4x+x)
desired.
Corollary C.4 Iteration complexity of Algorithum 2 is minimized for 4X+44+2 which yields complexity 4 ( L/2 + 2 lo The communication complexity is minimized for any
Dht
p <
41 in which case the total number of communication rounds to reach e-solution is 4A + !.
4htu
As a direct consequence Corollary C.4 we see that the optimal choice of p that minimizes both communication and number of iterations to reach solution problem [17 is p 4x+41+2p"
4A+z
Remark C.5 While both Algorithm 2 and Algorithm B are special case of SAGA, the practical version of variance reduced local SGD (presented in Section CC5) is not. In particular, we wish to run the SVRG-like method locally in order to avoid storing the full gradient table Therefore,
SSAGA does not require storing full gradient table for problems with linear models by memorizing the residuals. However, in full generality, SVRG-like methods preferable.
20

---

Under review as a conference paper at ICLR 2021
variance reduced local SGD that will be proposed in Section C.5 is neither a special case of SAGA nor a special case of SVRG (or a variant of SVRG). However, it is still a special case of a more general algorithm from (Hanzely & Richtárik 2019.
As mentioned, Algorithm 3 is generalization of Algorithm 2 when the local subproblem a finite sum. Note that Algorithm constructs control variates for both local subproblem and aggregation function db and constructs corresponding unbiased gradient estimator. In contrast, Algorithm 3 con- structs extra control variates within the local subproblem in order reduce the variance of gradient estimator coming from the local subsampling.
C.4 L2SGD+: ALGORITHM AND THE EFFICIENT IMPLEMENTATION
Denote E Ih' to be vector of ones. We are now ready to state I.2SGD+ as Algorithm
Algorithm L.2GD+:: Loopless Local SGD with Variance Reduction
J = 0 E Rdxm T = Rdd stepsize o, probability p for D, do
Input: =f
= 0 E IRd (for = 1,...,n) n)
{ = with probability and 0 with probability 1 -
if' then
All Devices i = 1, I,....
Sample j E {1, {l..... m) (uniformly at random)
- <(I-p) V.l., (x+) - (J.) +
J
nm
k+1 = xt ag." 2,
Set (J ++ )id = V fíi (x - h++1 = L
)., (J++) ). for all #
else
Master computes the average z D x Master does for all
g A (ark kk) - Tpk + I J nm
Set a ++1 x agt
Set 1htt1 A(a I²),, + J
end if end for
L2SGD+ only communicates when two consecutive coin tosses land different value, thus, on average p(1 - p)k times per & iterations. However, L.2GDD+ requires communication of control variates J,1, L as well each communication round is thus three times more expensive. In the Appendix, we provide an implementation of L2SGD+ that does not require the communication of J,1, v
Here we present an efficient implementation of L2SGD+ as Algorithm 4 so that we do not have to communicate control variates. As consequence, Algorithm 4 needs communicate average p(1 - p) k times per k iterations, while each communication consists of sending only local models the master and back.
C.5 LOCAL SGD WITH VARIANCE REDUCTION GENERAL METHOD
In this section, present fully general variance reduced local SGD. We consider more general instance of (2) where each local objective includes a possibly nonsmooth regularizer, which admits cheap evaluation of proximal operator. In particular, the objective becomes
21

---

Under review as a conference paper at ICLR 2021
Algorithm 4 L2SGD+; Loopless Local SGD with Variance Reduction (communication-efficienn implementation)
Input: of = = = I E R2d, stepsize probability Initialize control variates J E Rdxm Y O E Rd (for i I,.... n), initial coin toss =0 =-1=0
for 1,... do & 1 with probability p and 0 with probability 1 P
if c* = 0 then
All Devices 1, ,
if ck-1 then
Receive z e from Master
Reconstruct E² zk-o using xy I. k-c
Set . = . ca 1 nmn J.
1 = M(x -
x²),
end if
Sample j E (I...., m) (uniformly at random)
gf m(1-pi (1 (J.)..)
+
1 2
nm
ax k+1 = rt -ag.
Set (J ):n V (1+), / V
(J) )., = (J ++ )r for all +
else
Master does for all i ,..... n. if c then
c 0
Receive of from Device and set Σi= 2 x =o
end if'
Set out = x - -a mp (z+ - F) -1 A(# 21)
Set 7 = 2
Set + 1
end if
end for
min
1
fig
(xx)
+1
1
|
12 +
Rd (x(x)
(12)
zeRdn
N
2n
i=1
j=1
1=1
N
(1)
-((x)
fi(w))
f())
=F(x)
where m, is the number of data points owned by client and EE= m4.
In order to squeeze faster convergence rate from minibatch samplings, we will assume that fi, is smooth with respect to a matrix M.,, (instead of scalar L's, Amax
Assumption C.1 Suppose that fl., My, smooth (M., E Bddd M.j > and μ strongly convex 1 S m. 1 < S n, i.e.
(l,())+(( 9) fz)(() (1)(
9)+ lly x MM.M..
Vz, y E IR
(13)
Furthermore, assume that R; is convex for 1 < <
Our method (Algotihm 5) allows for arbitrary aggregation probability (same Algorithms 2 arbitrary sampling of chints (to model the inactive clients) and arbitrary structure/sampling of the local objectives (i.e., arbitrary size of local datasets, arbitrary smoothness structure of each local
22

---

Under review as a conference paper at ICLR 2021
objective and arbitrary subsampling strategy of each client). Moreover, it allows for the SVRG-IM like update rule of local control variates Js, which requires less storage given an efficient implementa- tion.
To be specific, each device owns a distribution D, over subsets of m,. When the aggrega- tion is not performed (with probability p). subset of active devices S is selected (S fol- lows arbitrary fixed distribution D). Each of the active clients (i E S) samples a subset of lo- cal indices S; Dj and observe the corresponding part of local Jacobian (x()))))s)) (where Ga V V Vir.m, (x*)). When the aggregation is performed (with prob- ability p) we evaluate j and distribute it to each device; using which each device computes a cor- responding component of \Vv(=*). Those are the key components constructing the unbiased gradient estimator (without control variates).
remains construct control variates and unbiased gradient estimator. the aggregation is done, we just simply replace the last column of the gradient table. If the aggregation is not done, we have two options either keep replacing the columns of the Jacobian table (in such case, we obtain particular case of SAGA (Defazio et al. (014)) or do LSVRG-like replacement (Hofmann et al.) 2015 Kovalev et al. 2020) (in such case,
particular case of GJS (Hanzely & Richtárik 2019), but is not special case of neither SAGA nor LSVRG. Note that LSVRG-like replacement is preferrable in practice due to a better memory efficiency (one does not need to store the whole gradient table) for the models other than linear.
algorithm
In order to keep the gradient estimate unbiased, it will be convenient to define vector Pt E Rm such that for each j E {1, (1...., m,} we have IP (j E S.) Pi.j
Next, to give tight rate for any given pair smoothness structure and sampling strategy, we use a standard tool first proposed for the analysis of randomized coordinate descent methods (Richtárik & Takáā 2016 Qu & Richtárik (2016) called Expected Separable Overapproximation (ESO) assump- tion. ESO provides us with smoothness parameters of the objective which "account" for the given sampling strategy.
Assumption C.2 Suppose that there is 02 E 12T such for each client we have:
E
M his
Pis 1| VI Whgs E "R"", E fl,...,,m.
JES.
(14)
Lastly, denote p; be the probability that worker i is active and 1 (mc) R to be the vector of ones. The resulting algorithm stated as Algorithm
Next, Theorems C.6 and C.7 present convergence rate of Algorithm 5 (SAGA and SVRG variant, respectively).
Theorem C.6 Suppose that Assumptions
C.
and C.2
hold.
a ain
min
N(I-p)ps,
np 4h+T
je
4uy+ n
Then the iteration complexity of Algorithm
5 (SAGA option) is
4uy +
1h+a ph
log -.
max
max M.ll........Isss
p=1 PP1--P
Theorem C.7 Suppose that Assumptions C.I and C.2
hold. Let
a= min
min
N(1-p)p-
pm 4x+r
jE(L
+
Pt.j
Then the iteration complexity of Algorithm 5 (LSVRG option) is
[40s [40y PiM(1-p)
n. +HPE
max
max DE(L........IIiss
14t2
log
pH
23

---

Under review as a conference paper at ICLR 2021
Algorithm L22GD+++ Loopless Local SGD with Variance Reduction and Partial Participation
Input: æf..... on IRd parallel units n, each of them owns my data points (for S s n), distributions DD over subsets of {?....,m,} distribution DD over subsets of {1, 2, n) aggregation probability p. stepsize a J = 0 E _dxm; y = Rd (for 1....,
for = 0, 1, do
with probability p and 0 with probability 1 - p
if = 0 then
Sample S D
All Devices i E S:
Sample S Dí; S {l...., m.] (independently on each machine)
Observe V f. (2 for all E S
oft N(I-P)pi EEes, Pūj (Vfl)(of)) (J (J)) I + In
2, = prox (x agg))
if JES: otherwise
if SAGA
J
For all j [I,...,,i.] mi} set J
W. P. Pi otherwise
L L-SVRG
J
Set T T
All Devices i & S:
9 J (m,)
+ n -1
24 h+1 = prox Ri (x ag,))
Set J J 1 g+t L
else
Master computes the average z²
= Σ
i==1 2
Master does for all
1...., n1:
9 p--1p=-aaa
A(x x²) (p- 1)n-111
T 1
Set r pr (zt ag!)
Set 4b k+1 A(a 1h), k+1 J
end if end for
Remark C.8 Algotihm is special case of Algorithm 3 which is in special of Algo-
rithm 5 Similarly, Theorem is a special case of Theorem 5.7 which is again special case of Theorem C.6
C.6 LOCAL STOCHASTIC ALGORITIMSS
In this section, we present two more algorithms Local SGD with partial variance reduction (Al- gorithm 7 and Local SGD without variance reduction (Algorithm (6). While Algorithm 6 uses no control variates at all (thus is essentially Algorithm]] where with local SGD steps). Algorithm 7 construcs control variates for el only, resulting in locally drifted SGD algorithm (with the constant drift between each consecutive rounds of communication), While we do not present the convergence rates of the methods here, we shall notice they can be easily obtained using the framework from (Gorbunov al. 2020).
where local gradient descent steps are replaced
24

---

Under review as a conference paper at ICLR 2021
Algorithm 6 Loopless Local SGD (L.2SGD)
Input: d] = z E IRd, stepsize o, probability
for l 0, 1, do
ç with probability and 0 with probability 1 - if 0 then
All Devices i = 1,,,, 1.....
Sample j E {L.....
(uniformly at random)
9 n11p) p) (V (2))
++1 xx ag!
else
Master computes the average z² 1 Ei 2
Master does for all I,...,
(xf x*)
up
Set *+1 x ag. x
end
end for
Algorithm 7 Loopless Local SGD with partial variance reduction (L2SGD2)
2 Rdd, stepsize a, probability y 0 E Rd (for i = I!).., for 0, 1.... do
Input: =
{ with probability and 0 with probability 1 - if then All Devices i = 1,....
Sample j E (l,..... m) (uniformly at random)
o n(1 p) (V.( (x)) + x
2 k+1 r -ag
Set bb11 T
else
Master computes the average 1 Di x Master does for all 1,
g
A
(a.h
k
Set x k+1 x agt
Set k+1 \(a )²1
end if
end for
25

---

Under review as a conference paper at ICLR 2021
D MISSING LEMMAS AND PROOFS
D.1 GRADIENT AND HESSIAN OF vi
Lemma D.1 Let I be the d d identity matrix and be X identity matrix. Then, we have
V2((x) - (In _eee ) 21 and V =
Furthermore, Lg 1
Proof:
Let O the d x zero matrix and let
Q == 0....., O, O, ...., 0 Rdxdn
and Q = ,I..... I] E paxdd Note that 24 = Qu and ã n 1z.. So,
12
((x)= = 2n
Q x
1 Qz
2n Σ (Q
1 n
_Q) x||²
The Hessian of sb
V2((x) = Σ
Q Q T (Q: #0)
QQQ Q " Q Q Q + Q
Σ Q 0 Q Q
Σ
Q
= 5 Q Q QQQ
and by plugging in for Q and Q we get
IT
I
V2((T)
I
1
I
4)
1
m2
4
p
1
81
1 [I,
1 ec
@ I.
Notice that I, Tee is circulant matrix, with cigenvalues 1 (multiplicity 1) and 0 (multi- plicity 1). Since the eigenvalues of Kronecker product of two matrices are the products of pairs of eigenvalues of the these matrices, have
Xmax 2 vib(())) Amax ( (In Leee) s6 I) Amax (I, Lee
26

---

Under review as a conference paper at ICLR 2021
So, Lu = #.
The gradient of v is given by
Σ QQ) T (Q: - QQ)
Ve(z))
=1
Σ
QQ Q _
- -
- Q
1 Q TTTT
Q x
2//n1 /n I///
/ 8/n
+
2 2/12
3/ n
38 mm/
(2a/T1
5/n
Di/n
8 n
Fi/n
Σ
h/n
s/n
H
22
D.2 PROOF OF THEBREM 3.1
For any 0 2 0 we have
f(x(A)) (x(x(A)) AM((A) f(x(O)) + (+(x(())
< f(x(0)) + xx(x(())
(15)
S f(x(A) (x(a()))
(16)
By adding inequalities
15 and (6). we get
()((((()) - (>x(())) 2
which means that (x())) is decreasing in A. Assume X 2 A. From the 16 we we get f(((A)) 2 (x(())) (vv((()) - (=((a))) f(x(0))
where the last inequality follows since 0 2 0 and since vxx(f)) 2 v(x(A)). So, f(((A) is increasing.
27

---

Under review as a conference paper at ICLR 2021
Notice that since vi is non-negative function and since z<A) minimizes F and (x(((o)) 0, have
f(x(0)) - f(x(A)) - f(x(A)) Ab(x(A)) & f(x(oo)),
which implies (3) and 4).
D.3 PROOF OF THEOREM
The equation VF()(A)) = 0 can equivalently written as
v (z) + (Ar; =(A) = 0, i= 1,2,.....
which is identical to 5 Averaging these identities over i, we get
T(A) = = 1 v)(()(A)),
which implies
((((((A)) =0
Further, we have
(x(())) 2n Σ [2,(A)) - =(()) 2n
((((1())) = 2 IV
2m1
as desired.
D.4
PROOF OF THEOREM 3.3
First, observe that
\V - n Σ v((((A)))
1 E VA((())) - Σ - [VA((NN)
where the second identity is due to Theorem 3.2 which says that E, V)((z;(A)) = 0. By applying Jensen's inequality and Lipschitz continuity of functions fi, we get
1 Σ [VA((()) - VA(T(()) < | <
I
Σ ( xz (A)) 21))(x(A)))
remains to apply 3 and notice that is strongly convex and thus s(oc) is indeed the unique
minimizer.
D.5 PROOF OF THEBREM 4.2
We first show that our gradient estimator G(x) satisfies the expected smoothness property (Gower et al. 2018 2019).
max { ( }) and o² = + ( -
Lemma D.2 Let C = n
Then for all x IRd we have the inequalities E [IG(() G(x()))1 & -c()
and
E [[G()]]]] < 4L(F(x) - F(x(A))) + 202
Next, Theorem
4.2 from Lemma D.2 by applying Theorem 3.1 from Gower et al. 2019
28

---

Under review as a conference paper at ICLR 2021
D.6
PROOF OF LEMMA D.2
We first have
E [[G(z) C(((A))1
(1- p) Vf(e)
T- - | + [o(e) - [d(a((
1 VVf(x) - V)(+(A))] + X² P [Vb(x)) VV(=(A))]
I-p
x(), L0 Du (x
&
24 D xA))
22 D (z, np
Since D, + >D = Dy and VF(x(A)) = 0, we can continue:
E - (((())
s max
L --pi
} Dr(e,x(A))
= max
{
- }} (F(x) F(x(A))).
Next, note that
a²
(A))I + (z,(1) - =(A)))))
Y=1
+ せタ \i
I-p
(1 - p) )((((a)))
|| + |
I-p E [1G(((A))11]]
Therefore, we have
E [[G())]]]]
E [[IG(()) G(((A))1]] 2 [IGG((A))11]
S
Lemma D. +.2+((1)
4L(F(x) - F(((A))) 200.
as desired.
D.7 PROOF OF COROLLARY 4.3
Firstly, minimize the total number of iterations, it suffices minimize L which is achieved with 1 and let k = 2n log ! so p" -- Let us look at the communication. Fix >> O, choose = 22 that
2nc S c.
The expected number of communications to achieve this goal is equal to
Comm,
p(1 - p)k
2 2 2max
I-p
p(1 - p)
log
(pa log 1
The quantity Comm, is minimized by choosing any such that pL = (1-p)A,ie. for p = p², as desired. The optimal expected number communications therefore equal to
X+L
Comm
2A
log
X+L
29

---

Under review as a conference paper at ICLR 2021
D.8 PROOF OF COROLLARY 5.2
Firstly, to minimize the total number of iterations, it suffices to solve
min max
41 +ym
4h+u
(1-p)P
pp
which is achieved with p = p* AL
4x+p +
The expected number communications to reach e-solution
Comm,
p(1 - p) max { (1- (1-plk PM
4L'+tua 4h+2
log
(uxxp +um) (1n))))-p((22)))) p))
log
Minimizing the above in p yield p p" aL' 4mm desired. The optimal expected
Dht
number of communications therefore equal to
Commp- 1'+1A+(m+1)
4h+u
(4 + mm) log 1
D.9 PROOF OF THEOREMS 5.1
C.6
AND
Note first that Algorithm 3 is a special case of Algorithm 5 and Theorem 5.1 immediately follows from Theorem C.6 Therefore it suffices show Theorems C.6 and C.7 In order to do so, will
cast Algorithm as a special case of GJS from (Hanzely & Richtárik 2019). As consequence, Theorem C.6 will be special cases of Theorem 5.2 from (Hanzely & Richtárik 2019
D.9.1 GJS
In this section, we quickly summarize results from (Hanzely & Richtárik 2019), which we cast to sho convergence rate of Algorithm 3 regularized empirical risk minimization objective, i.e.,
GJS (Hanzely & Richtárik 2019) method to solve
min zERd TS Σ +()))
(17)
Defining G(x) (f) (x)),, observe SG(x), every iteration where S is random linear projection operator and 2 is random linear operator which is identity on expectation. Based on this random gradient information, GJS (Algorithm) g constructs variance reduced gradient estimator g and takes a proximal step in that direction.
Algorithm Generalized JacSketch (GJS) (Hanzely & Richtárik 2019)
1: Parameters: Stepsize a >> 0, random projector S and unbiased sketch 24
2: Initialization: Choose solution estimate z0 E Rd and Jacobian estimate J E RR
3: for k= 0, 0,1,--. 1,... do
4: Sample realizations of S and U, and perform sketches (G
(x*) and (GG(
5: J = 2 S G(z*))
update the Jacobian estimate
6: g* = 1 1 f 1 G ((**) Jk)
construct the gradient estimator
a
7: x xk+1 prox,,1(<** =ag*)
perform the proximal SGD step
8: end for
Next we quickly summarize theory of GJS.
Assumption D.1 Problem 17 has a unique minimizer x", and f is p-quasi strongly convex, i.e.,
f(x*) 2 f(y) + (Vf(y), -)) + lyl - 11,, Vy E Rd, Functions are convex and My-soooth for some M, ž 0, i.e.,
(18)
+ v) fz(x) [() w) |1y
x 2 M2
Vx, E Rd. (19)
30

---

Under review as a conference paper at ICLR 2021
Theorem D.3 (Slight simplification of Theorem 5.2 from (Hanzely & Richtárik 2019) Let As- sumption D.
hold. Define M(X) == - M,,.,,v
Let be any linear operator com-
muting with S, and assume M 2 commutes with S. Define the Lyapunov function
| --0--x11 +a BM (J+ -g(=)(x"))
(20)
where {a²} and {J²} are the random iterates produced by Algorithm with stepsize a > Suppose that and B are chosen so that
[1xx|11 + -EESS BM S (1 au) |M 2
20 E
(21)
and
[E[SS)
BM 1
S 1. M 2
20 E [
(22)
for all X E Rdxn, Then for all k 2 0, we have E | s (1 ap) wo.
D.9.2 VARIANCE REDUCED IOCAL SGD AS SPECIAL CASE OF GJS
(et = j+ m, In order to case problem 12 as special case of 17 denote n = N+1,
(R) = N+1 (1:) and fn = (N + 1)ps Therefore the objective becomes
min M(x) = 1 Σ fz(z) + R(x). zERN
(23)
Let E R0-1 be such that ()((.)
N+1 N U.j and as consequence of 14 we have
E
2 his
Pis [ha visisn Vhay E ER f1....,,..)
JES.
(24)
At the same time, Y is strongly convex.
D.9.3 PROOF OF THEOREM C.6 AND THEOREM C.7
Let E IRd be a vector of ones and p E R such that p} = Pcs i E (.....,m.,, otherwise
p/ 0. Given the notation, random operator 2/ is chosen as
(1 (1-D)-'E
(p=le ((x))
(Xime (EnEs,geTTT)
w.p. (1 p)
ux
p-1x... m.
w.p.
We next give two options on how to update Jacobian first one SAGA-like, second one is SVRG like.
(je)) w.p. - (1-p)p:,
X.ss = X.m.
SAGA-like:
(SX)..)
w.p. (1 - p1 -p:) +
X
w.p. P
(8X)...
0
w.p. 1 -
[ w.p. Pt
X X.m bi by
w.p. (1 1-p)p;
SVRG-like:
(SX)..m
w.p. 1 pi
0
w.p. (1 p) p.) +p
X
w.p. P
(SX)...
0
w.p. - p
31

---

Under review as a conference paper at ICLR 2021
We can now proceed with the proof of Theorem C.6 and Theorem C.7 Range (M,), we must have
As Vf((z) Vfi(v)
- M (M(a" G((1))
(25)
and
J = M GG(x)).
(26)
Due to 26)
25 inequalities
21
and
22
with choice Y = M become respectively:
n
2g p
M Y.
K, 1| +
2a n2
p)
E
pj
Pa. M :g
+ (I- E(S) ([))))B(Y))
JES:
S (1--au)](B()))
(27)
"2p
1
M Y
2a² 1
n
(1-p)-
Σ
E
Σ
P2. M
Y :3
+ [E ((()) B(Y)
[(())
$ +
1=1
JES,
(28)
Above, we have used
Equxe11 E [Iumixell - 11
E
Pi.
M Y.j
JES:
Note that E [S()]] X Diag ((1
where p R- such that Pr(i.)) = Pi.j-
Using 24 setting B to be right multiplication with Diag(b) and noticing that Amax M, nn
suffices to have
2n A (1 p)6 S (1 am1)b²
2n (1 (1-p) -) ()(()) + (1 - (1 - p)Pt,jp)bb < (1 aμ)b
VjE (l..)...m,),.is
ツp + pb² =
2g p1 11- Pt.j P. Un((.)) + (1- (11-p)pt..1 p)p Pib S
Vj [1..... msiisn
for SAGA case and
20 2ap 1 (1 p)b (1 am1ib²
20 p) p) ()((()))
(1 (1 - p:p.) )3 $ (1 am1)b;
Vj E m.....,,,,is
2 p 1 X + pb < 1
/ 21 (1-))) Pi. P, (o( + (1 p) p)ppppb? S Vj m.),, isn
for LSVRG case.
remains to notice that to satisfy the SAGA case, suffices to set 02 2mp ((i)))
2m (1-p)
(for j (1,...,m,),4 S n) and min {
1(1-p)pr.Ptt
(tninje(l............ (9 +nx Ix+# J.
To satisfy LSVRG case, it remains to set b2 2mp (a()))
(for j fl, mih.is
2n(1-
n) and a = min (ninge(l.....)ssssk.
n(1-p)p:
P
tappp"
TA+J
Pi.
The last step to establish is to recall that N + 1, va(t))
N+1 N
Uig and and note that
the iteration complexity is ag log 1
log 1
ou
32

---

Under review as a conference paper at ICLR 2021
D.9.4 PROOF OF THEOREM 5.1
To obtain convergence rate of Theorem 5.1 remains use Theorem C.6 with p; 1, m, m (Vi S n), where each machine samples (when the aggregation is not performed) individual data points with probability m that 1; = L' for all j < N.
and thus Pj (for all j I N). The last remaining thing realize
33


Reviews:
[{"review_id": "zGzn9-i-wtp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***Strong\t\n\nPersonalization is a hardcore problem in FL. The authors target an important problem.\n\nThe theory analysis seems correct, but the bound seems not tight enough.\n\n***Weakness\n\nRecently, there are many personalized methods proposed for FL. In the I.I.D. setting, local SGD training (FedAvg) can obtain similar accuracy as centralized training with a theory guarantee.  But in the non-I.I.D. setting, I am curious to know what’s the ultimate goal of optimization. Can the proposed personalized methods obtain accuracy comparable to centralized training? If we do not compare with the centralized accuracy, how can we know the optimized personalized model can obtain sufficient accuracy for practical applications.\n\nThe experimental results are weak. The authors only provide results on the LR model for toy datasets (LibSVM). Without non-convex experiments, it is hard to believe the proposed method works in practice given that DNN-based models dominate nearly all ML tasks.\n\nThe code style and readability are poor, which discourages the popularity of the proposed method.\n\nAlthough the authors mentioned some contributions of the proposed method, I still cannot get what’s the advantages of the new formulation over conventional Federated optimization? What is its limitation? What’s the cost to use this method? When should we choose this algorithm in practice? In which degree of non-IIDness? Playing with optimization analysis tricks won’t solve the personalized challenge of federated learning in practice.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "sDg6GZHRktx", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Interesting insights into federated learning, possibly limited by the focus on strong convexity\n\nThis paper considers distributed training problems arising in the context of federated learning. It proposes a novel framing of the problem as a compromise between fitting a model locally to the data available at a device, and fitting a model globally to the data from all devices. This leads to the so-called loopless local gradient descent (L2GD) method, which is loosely related to the popular FedAvg/LocalSGD method, and also loosely related to a randomized version of the well-studied ADMM for consensus optimization problems. \n\nThe paper provides theoretical convergence guarantees for L2GD and related variance-reduced versions L2GD+ and L2GD++. As is pointed out in footnote 1, the ideas underlying the L2GD and its analysis have been previously explored in the literature. It would be worth clarifying in the paper (in footnote 1 or elsewhere) what aspects of L2GD and its analysis which are novel and not completely subsumed by the previous works Liu et al. (2017) or Wang et al. (2018). The last sentence of footnote 1 is somewhat in this direction, but is not very precise.\n\nI generally think the perspective proposed in this paper, along with the L2GD method, are novel and interesting, and I expect they will be useful to researchers working on federated learning. The main limitation of the work, in my view, is the limited fit and interest to the broader ICLR audience. For example, the CFP emphasizes the importance of non-convex optimization, and deep learning methods and architectures for representation learning. On the other hand, this paper focuses on convex models, both for the analysis (smooth and strongly convex) and in the experiments (l2-regularized logistic regression). The analysis techniques do not appear to make use of strong global structure (beyond the definition of strong convexity). Is there reason to believe it will not be possible to provide local convergence guarantees for L2GD under more relaxed assumptions (in particular, without assuming convexity)?\n\nA few other minor points:\n* Regarding the second motivating point, see also the recent work of Woodworth et al. (arxiv:2006.04735 and arxiv:2002.07839).\n* Is there any intuition why, in Fig 1, when $\\lambda$ approaches $10^{1}$, the blue curve begins to decrease and orange curve begins to increase? (I.e., why the non-monotonic behaviour?)\n* Minor nit.: Alg 1 seems to violate the important notion in FL that devices never reveal their private information (e.g., their local decision variables or gradients) directly to the centralized master. Rather than saying that (8) is implemented at the master, would it make more sense for each device to receive $\\bar{x}^k$ from the Master and implement (8) locally? (The averaged model can be computed in a secure way using DP and secure aggregation, much the same as it is in current FL implementations.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "R4cRgYjXq3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper proposed a new formulation of federated learning, which balances between traditional global model and purely local models. The authors discuss the advantages of the new formulation and propose a new algorithm L2GD to solve the problem. They theoretically analyzed the communication complexity of L2GD under stronly-convex settings and propose several algorithmic variants.\n\n## Pros\n1. The authors developed a set of algorithms based on L2GD and provided theoretical analysis. The efforts are appreciated.\n\n\n## Cons\n\nUnfortunately, most contributions of this paper doesn't make sense to me. I have concerns regarding novelty and correctness of the statements made by this paper. Detailed comments are listed as follows.\n\n**New formulation**\n1. In section 2, the authors claim that \"we prove that the optimal local models converge to the traditional global model characterized by (1) at the rate $O(1/\\lambda)$\". However, I didn't find any discussions or proof around this statement in following sections. From my understanding, there should be some equations showing how $x(\\lambda)-x(\\infty)$ or $f(x(\\lambda))-f(x(\\infty))$ changes over $\\lambda$. But I didn't find any.\n2. In experiments, the authors didn't compare the proposed formulation with the original formulation. How much benefits one can obtain from the new formulation is unclear, making this paper to be incomplete.\n3. The formulation is not new. A nearly same formulation can be found in [1]. The authors didn't notice this paper. Since [1] also proposed an algorithm EASGD to solve the new formulation, the authors are supposed to compare L2GD with the algorithm in [1].\n\n**New algorithm: Loopless LGD**\n1. The algorithm is also not new. An extremely similar algorithm has appeared in [2]. By some re-parameterization, I believe they are equivalent to each other. The authors missed this reference. They should justify the differences and compare the results.\n2. It is unclear why L2GD uses random local steps instead of a fixed one. Or what are the benefits of the randomized one?\n\n**Convergence theory**\n1. The conclusions of convergence analysis are questionable. In particular, when obtaining the convergence rate, it seems that the authors completely ignore the second term in (9). In general, people use $f(x)-f(x_*)<\\epsilon$ or $\\|x-x_* \\| < \\epsilon$ to define the $\\epsilon$-neighborhood of the optimum. However, in this paper, the authors use $\\|x-x_* \\| < \\epsilon \\|x_0 - x_* \\| + c$ to define the neighborhood and just ignore the second term when deriving the rate. Under this definition, they draw the conclusion that L2GD can improve the communication complexity of GD. This can be misleading and questionable. In GD, we don't have the second term in (9) at all.\n2. Similarly, when obtaining the best value of $p$, the authors only optimize the first term. However, the second term in (9) also depend on $p$. The authors seem to ignore it again.\n\n**New insights about the role of local steps**\n1. The authors state that \"the role of local steps in gradient type methods is not to reduce communication complexity, as is generally believed. Indeed, there is no theoretical result supporting this claim in the key heterogeneous data regime.\" This statement is not true. It has been shown in literature (eg, [3]) that local SGD can achieve the same rate $1/\\sqrt{n K}$ as synchronous SGD but only uses $O(n^{3/4} T^{3/4})$ communication rounds, while synchronous SGD uses $T$ rounds.\n2. \"The more local steps are taken, the more we bias the method towards the purely local models.\" I feel we cannot draw this conclusion from this paper's analysis. In particular, in this paper, the choice of local steps is controlled by the parameter $\\lambda$ (expected local steps = $1+L/\\lambda$). When we set a small $\\lambda$, we get two consequences: (1) the formulation will emphasize more on $f(x)$, and hence, the solution is biased towards purely local models. (2) the \"optimal\" local steps derived in this paper becomes larger. Obviously, these two consequences are parallel to each other. We cannot say the second point is the reason of the first point. Instead of setting the expected local steps to be $1+L/\\lambda$, one can also use other values which won't influence the final solution.\n\n**Experiments**\nThe experimental results can only show the importance of variance reduction, which seems to be a minor contribution of the paper. Most theoretical claims are not validated empirically.\n\n## Post-rebuttal\nThanks the authors for the clarifications! I appreciate it. However, some of my concerns are not addressed. \n- The main concern I have is about the new insight on local update methods. Basically, the author obtain the insights based on a newly proposed algorithm (L2GD, let's call this algorithm B) and a new problem formulation (let's call this formulation B). However, they want to apply the insight from algorithm B and formulation B to algorithm A (original local update methods) and formulation A (original FL formulation). It is obvious that one cannot draw this conclusion because both the algorithm and the formulation are different.\n- Second, as I stated in the original review, I don't think one can obtain the insights from the analyses in this paper. The author didn't directly answer my question and just said \"they didn't expect people to interpret it in this way\". But it is still unclear how to correctly understand their insights.\n\nBased on the above two points, I strongly feel that their main insights about the effects of local updates should be further and carefully examined. The current version could be misleading. Besides, I also have the following minor concerns:\n\n- The authors claim that [Yu et al. ICML 2019] didn't consider the heterogeneous setting. This is not true. Although [Yu et al. ICML2019] assumes that the gradient dissimilarity is uniformly bounded (which is widely used in literature), their setting is still non-iid setting. It's unfair to say that they only study the IID data setting. So the second motivation of this paper does not make sense to me. The authors oversell their contribution. More precisely, their contribution is not the first proof under data heterogeneous setting but should be the new proof without data similarity assumption.\n- \"non-local cousins\" is unclear and hasn't been properly defined in the paper. For local SGD with mini-batch size ,  local steps and  clients, there are two non-local cousins: (a) SGD with mini-batch size ; and (b) SGD with mini-batch size . It seems that the authors misused these two algorithms. In the response, they agree that [Yu et al. ICML 2019] proves \"with data dissimilarity assumption, local SGD can improve the communication complexity of classical SGD\". Here, classical SGD refers to algorithm (a). In the updated paper, they cite two papers from Woodworth et al. to support their claim. However, the non-local methods in Woodworth et al. is algorithm (b). The authors should formally define which non-local algorithm they want to compare with.\n- In the paper, the authors claim that they prove for the first time local methods can improve the communication complexity of the non-local cousins. However, this statement is overselling. The more precise version is that they prove that the variance-reduced version of local methods can improve the communication complexity of the vanilla non-local version algorithms.\n- It seems that the authors want to claim a lot of contributions in this single paper and they didn't organize these contributions well. Hence, it causes difficulties for readers to understand their true novelty. I recommend the authors to rewrite the paper and carefully consider the paper structure. For example, if I understand correctly, the main contribution of this paper should be the insights on local updates. However, the authors didn't show any experiments on this insight in the main paper (they put them in the appendix). Instead, they just validate the effect of variance reduction in the main paper, which is just a minor point. Also, in the introduction, there is a long paragraph to introduce L2GD as one of the main contributions. However, as discussed in the responses, L2GD is not a new algorithm. The authors don't need to give it so much emphasize or should not claim it as one contribution.\n- Also, in [1] EASGD does use multiple local steps. The authors should compare L2GD with EASGD, as they both are designed to minimize the new formulation.\n\n## References\n\n[1] Zhang et al. Deep learning with elastic averaging SGD. NeurIPS 2015.\n\n[2] Wang et al. Overlap Local-SGD: An algorithmic approach to hide communication delay in distributed SGD. ICASSP 2020.\n\n[3] Yu et al. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. ICML 2019.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KPYcFDG0ti", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper: The paper proposes a new formulation for the federated learning problem, in which each agent has its local model, and a penalty term is added to the objective function to control the deviation of these local models from their average. Next, the authors develop a randomized algorithm to tackle this problem and characterize its convergence under several assumptions, such as smoothness and strong convexity. They also discuss variants of their algorithm, which uses variance reduction techniques or considers users' partial participation.\n\n\nThe paper is well-written, and the goals, problem formulation, and contributions are all explained in detail. However, the reviewer has a number of concerns, which are listed below:\n\n\n\nThe first concern is regarding the novelty of the formulation or analysis. The idea of this paper's formulation, giving a copy to each agent and adding a regularizer to keep the copies close, has been discussed in the distributed literature, for instance, in ADMM. Moreover, it is not clear which part of the analysis is novel or challenging. It seems that the authors use an unbiased estimator to solve an optimization problem with a smooth and strongly convex objective function. This setting has been studied extensively in the literature, including applying variance reduction techniques.\n\n\n\nSecond, the regularizer parameter $\\lambda$ seems to be at the heart of this framework. With $\\lambda=\\infty$, the problem reduces to the classic federated learning setting, and when $\\lambda=0$, the formulation boils down to the case that each agent solves its own problem. In particular, for the latter, the authors claim that \"such purely local models are rarely useful.\" However, this claim's reasoning is not clear; for instance, from a theoretical point of view, results such as Theorem 3.1 suggest that having $\\lambda=0$ will lead to the minimum loss $f$. In other words, it is not clear how we should compare the different trained models from setting different values for $\\lambda$, and which range of $\\lambda$ leads to a good model with respect to that measure.\n\n\n\nThird, as stated in the introduction, several methods have been recently proposed to address the heterogeneous case or achieve personalization in the federated learning problem. I wonder why the authors have only compared their methods against each other in experiments and have not included those methods for comparison.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an elegant formulation of personalized federated learning, which balances between a global model and locally trained models. It then analyzes algorithm variants inspired by local update SGD in this setting. The problem formulation using the explicit trade-off between model differences and global objective was received positively, as mentioned by R1 and R2. After a productive discussion including the authors and reviewers, unfortunately consensus remained that the paper remains below the bar in the current form. The contributions are not presented clearly enough in context, the set of competing algorithms (including e.g. EA-SGD, ADMM, SVRG/Scaffold for the heterogeneous setting, and others) needs to be clarified in particular for the modified formulation compared to traditional FL, since objectives are different. Some smaller concerns also remained on the applicability to more general non-convex settings in practice. We hope the feedback helps to strengthen the paper for a future occasion.
Decision: Reject