Year: 2020

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.

heading: 1 INTRODUCTION
text: With the proliferation of mobile phones, wearable devices, tablets, and smart home devices comes an increase in the volume of data captured and stored on them. This data contains a wealth of potentially useful information to 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 to a data center where centralized machine 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 is very inefficient in terms of energy and time.

heading: 1.1 FEDERATED LEARNING
text: Federated learning (FL) (McMahan et al., 2016; Konečný et al., 2016b;a; 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., 2019) casts supervised FL as an empirical risk minimization problem of the form
min x∈Rd
1 n n∑ i=1 fi(x), (1)
where n is the number of devices participating in training, x ∈ Rd encodes the d parameters of a global model (e.g., weights of a neural network) and
fi(x) := Eξ∼Di [f(x, ξ)] represents the aggregate loss of model x on the local data represented by distribution Di stored on device i. One of the defining characteristics of FL is that the data distributions Di 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 (1) 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 compression, or stochastic approximation, FedAvg reduces to Local Gradient Descent (LGD) (Khaled
et al., 2019; 2020), which is an extension of GD performing more than a 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 (1), but also inevitably raises questions about the utility of such a global solution to individual users. Indeed, a global model trained across all the data from all devices might be so 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 to address it. For instance, the MOCHA (Smith et al., 2017) framework uses a multi-task learning approach to allow for personalization. Next, (Khodak et al., 2019) propose a generic online algorithm for gradientbased parameter-transfer meta-learning and demonstrate improved practical performance over FedAvg (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 et 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 easier to analyze, fail to provide theoretical improvements in communication complexity over their non-local cousins, in this case, GD (Khaled et al., 2019; 2020).1
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 as a solver for the traditional global problem (1), perhaps LGD should not be seen as a method for solving (1) 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 et al., 2020) and FedAvg.

heading: 2 CONTRIBUTIONS
text: In our work we argue that the two motivations mentioned in 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 (1), we propose to learn a mixture of the global model and the purely local models which can be trained by each device i using its data Di only. Our formulation (see Sec. 3) lifts the problem from Rd to Rnd, allowing each device i to learn a personalized model xi ∈ Rd. These personalized models are encouraged to not depart too much from their mean by the inclusion of a quadratic penalty ψ multiplied by a 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 et al., 2017; Wang et al., 2018) and distributed optimization (Lan et al., 2018; Gorbunov et al., 2019; Zhang et al., 2015). The mixture objective we propose (see (2)) is a special case of their setup, which justifies our approach from the modeling perspective. Note that Zhang et al. (2015); Liu et al. (2017); Wang et al. (2018) provide efficient algorithms to solve the mixture objective already. However, none of the mentioned papers consider the FL 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
1After 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., 2020a), confirming that the local methods do not outperform their non-local counterparts in the heterogeneous setup. Similarly, the benefit of local methods in the non-heterogeneous scenario was questioned in (Woodworth et al., 2020b).
local models converge to the traditional global model characterized by (1) at the rate O(1/λ). 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.1). Moreover, we prove an 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. 3.2). 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., 2017), 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 at the global model. While MAML was originally proposed as a heuristic, we provide rigorous theoretical guarantees.
Loopless LGD: non-uniform SGD applied to our formulation. We then propose a randomized gradient-based method—Loopless Local Gradient Descent (L2GD)—for solving our new formulation (Algorithm 1). 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 to 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., 2020) 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.
Convergence theory. By adapting the general theory from (Gower et al., 2019) to our setting, we obtain theoretical convergence guarantees assuming that each fi is L-smooth and µ-strongly convex (see Thm. 4.2). Interestingly, by optimizing the probability of sampling the penalty (we get p? = λλ+L ), which is an indirect way of fixing the expected number of local steps to 1+ L λ , we prove an 2λλ+L L µ log 1 ε bound on the expected number of communication rounds (see Cor. 4.3). We believe 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 λ→ 0. If λ→∞, the solution our formulation converges to is the optimal global model, and L2GD obtains the communication bound O ( L µ log 1 ε ) , which matches the efficiency of GD.
What problem do local methods solve? Noting that L2GD is a (mildly nonstandard) version of LGD,3 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 a 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 (e.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 as methods for solving the new FL formulation proposed here.
Generalizations: partial participation, local SGD and variance reduction. We further generalize and improve our 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
2The connection of FL and multi-task meta learning is discussed in (Kairouz et al., 2019), for example. 3To be specific, L2GD is equivalent to Overlap LGD (Wang et al., 2020) with random local loop size.
instead of local GD steps, and (iii) total variance reduction mechanism to tackle the variance coming 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 L2SGD++, is presented in the Appendix only, alongside the associated complexity results. In the main body of this paper, we instead present a simplified version thereof, which we 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 theoretical predictions can be observed in practice.

heading: 3 NEW FORMULATION OF FL
text: We now introduce our new formulation for training supervised FL models: min
x1,...,xn∈Rd {F (x) := f(x) + λψ(x)}
f(x) := 1n n∑ i=1 fi(xi), ψ(x) := 1 2n n∑ i=1 ‖xi − x̄‖2 , (2)
where λ ≥ 0 is a penalty parameter, x1, . . . , xn ∈ Rd are local models, x := (x1, x2, . . . , xn) ∈ Rnd and x̄ := 1n ∑n i=1 xi is the average of the local models.
Due to the assumptions on fi we will make in Sec. 3.1, F is strongly convex and hence (2) has a unique solution, which we denote x(λ) := (x1(λ), . . . , xn(λ)) ∈ Rnd. We further let x̄(λ) := 1 n ∑n i=1 xi(λ). We now comment on the rationale behind the new formulation.
Local models (λ = 0). Note that for each i, xi(0) solves the local problem minxi∈Rd fi(xi). That is, xi(0) is the local model based on data Di stored on device i only. This model can be computed by device i without any communication whatsoever. Typically, Di is not rich enough for this local model to be useful. In order to learn a better model, one has to take into account the date from other clients as well. This, however, requires communication.
Mixed models (λ ∈ (0,∞)). As λ 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 (λ = ∞). Let us now look at the limit case λ → ∞. Intuitively, this limit case should force the optimal local models to be mutually identical, while minimizing the loss f . In particular, this limit case will solve4 min { f(x) : x1, . . . , xn ∈ Rd, x1 = x2 = · · · = xn } , which is equivalent to the global formulation (2). Because of this, let us define xi(∞) for each i to be the optimal global solution of (1), and let x(∞) := (x1(∞), . . . , xn(∞)).

heading: 3.1 TECHNICAL PRELIMINARIES
text: We make the following assumption on the functions fi:
Assumption 3.1 For each i, the function fi : Rd → R is L-smooth and µ-strongly convex.
For xi, yi ∈ Rd, 〈xi, yi〉 denotes the standard inner product and ‖x‖ := 〈xi, xi〉1/2 is the standard Euclidean norm. For vectors x = (x1, . . . , xn) ∈ Rnd, y = (y1, . . . , yn) ∈ Rnd we define the standard inner product and norm via 〈x, y〉 := ∑n i=1〈xi, yi〉, ‖x‖ 2 := ∑n i=1 ‖xi‖ 2 . Note that the separable structure of f implies that (∇f(x))i = 1 n∇fi(xi), i.e., ∇f(x) = 1 n (∇f1(x1),∇f2(x2), . . . ,∇fn(xn)).
Note that Assumption 3.1 implies that f is Lf -smooth with Lf := Ln and µf -strongly convex with µf := µ n . Clearly, ψ is convex by construction. It can be shown that ψ is Lψ-smooth with Lψ = 1 n
4If λ = ∞ and x1 = x2 = · · · = xn does not hold, we have F (x) = ∞. Therefore, we can restrict ourselves on set x1 = x2 = · · · = xn without loss of generality.
(see Appendix). We can also easily see that (∇ψ(x))i = 1 n (xi − x̄)(see Appendix), which implies
ψ(x) = n2 n∑ i=1 ‖(∇ψ(x))i‖2 = n2 ‖∇ψ(x)‖ 2 .

heading: 3.2 CHARACTERIZATION OF OPTIMAL SOLUTIONS
text: Our first result describes the behavior of f(x(λ)) and ψ(x(λ)) as a function of λ.
Theorem 3.1 The function λ→ ψ(x(λ)) is non-increasing, and for all λ > 0 we have ψ(x(λ)) ≤ f(x(∞))−f(x(0))λ . (3) Moreover, the function λ→ f(x(λ)) is non-decreasing, and for all λ ≥ 0 we have f(x(λ)) ≤ f(x(∞)). (4)
Ineq. (3) says that the penalty decreases to zero as λ grows, and hence the optimal local models xi(λ) are increasingly similar as λ grows. The second statement suggest that the loss f(x(λ)) increases with λ, but never exceeds the optimal global loss f(x(∞)) of the standard FL formulation (1). We now characterize the optimal local models which connect our model to the MAML framework (Finn et al., 2017), as mentioned in the introduction.
Theorem 3.2 For each λ > 0 and 1 ≤ i ≤ n we have xi(λ) = x(λ)− 1λ∇fi(xi(λ)). (5)
Further, we have n∑ i=1 ∇fi(xi(λ)) = 0 and ψ(x(λ)) = 12λ2 ‖∇f(x(λ))‖ 2.
The optimal local models (5) are obtained from the average model by subtracting a multiple of the local gradient. Observe that the local gradients always sum up to zero at optimality. This is obviously true for λ =∞, but it is a bit less obvious that this holds for any λ > 0. Next, we argue the optimal local models converge to the traditional FL solution at the rateO(1/λ).
Theorem 3.3 Let P (z) := 1n ∑n i=1 fi(z). Then, x(∞) is the unique minimizer of P and we have
‖∇P (x̄(λ))‖2 ≤ 2L 2(f(x(∞))− f(x(0)))
λ . (6)

heading: 4 L2GD: LOOPLESS LOCAL GD
text: In this section we describe a new randomized method for solving the formulation (2). Our method is a non-uniform SGD for (2) seen as a 2-sum problem, sampling either∇f or∇ψ to estimate∇F . Letting 0 < p < 1, we define a stochastic gradient of F at x ∈ Rnd as follows
G(x) := { ∇f(x) 1−p with probability 1− p λ∇ψ(x)
p with probability p . (7)
Clearly,G(x) is an unbiased estimator of∇F (x). This leads to the following method for minimizing F , which we call L2GD: xk+1 = xk − αG(xk). Plugging the formulas for ∇f(x) and ∇ψ(x) into (7), and writing the resulting method in a distributed manner, we arrive at Algorithm 1. In each iteration, a coin ξ is tossed and lands 1 with probability p and 0 with probability 1 − p. If ξ = 0, all Devices perform one local GD step (8), and if ξ = 1, Master shifts each local model towards the average via (9). As we shall see in Sec. 4.2, our theory limits the value of the stepsize α, which has the effect that the ratio αλnp cannot exceed 1 2 . Hence, (9) is a convex combination of x k i and x̄ k.
Note that Algorithm 1 is only required to communicate when a two consecutive coin tosses land a different value (see the detailed explanation in Sec. C.1 of the appendix). Consequently, the expected number of communication rounds in k iterations of L2GD is p(1− p)k.
Remark 4.1 Our algorithm statements do not take the data privacy into the consideration. While privacy is a very important aspect of FL; in this paper, we tackle different FL challenges and thus we ignore privacy issues. However, the proposed algorithms can be implemented in a private fashion as well using tricks that are used in the classical FL scenario (Bonawitz et al., 2017).
Algorithm 1 L2GD: Loopless Local Gradient Descent
Input: x01 = · · · = x0n ∈ Rd, stepsize α, probability p for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ = 0 then
All Devices i = 1, . . . , n perform a local GD step:
xk+1i = x k i − αn(1−p)∇fi(x k i ) (8)
else Master computes the average x̄k = 1n n∑ i=1 xki
Master for each i computes step towards aggregation xk+1i = ( 1− αλnp ) xki + αλ np x̄
k (9) end if
end for

heading: 4.1 THE DYNAMICS OF LOCAL GD AND AVERAGING STEPS
text: Notice that the average of the local models does not change during an aggregation step. Indeed, x̄k+1 is equal to 1n n∑ i=1 xk+1i (9) = 1n n∑ i=1 [( 1− αλnp ) xki + αλ np x̄ k ] = x̄k.
If several averaging steps take place in a sequence, the point a = x̄k in (9) remains unchanged, and each local model xki merely moves along the line joining the initial value of the local model at the start of the sequence and a, with each step pushing xki closer to the average a.
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 1p , and the expected number of consecutive aggregation steps is 1 1−p .

heading: 4.2 CONVERGENCE THEORY
text: We now present our convergence result for L2GD.
Theorem 4.2 Let Assumption 3.1 hold. If α ≤ 12L , then E [∥∥xk − x(λ)∥∥2] ≤ (1− αµn )k ∥∥x0 − x(λ)∥∥2 + 2nασ2µ ,
where L := 1n max { L 1−p , λ p } and σ2 := 1n2 ∑n i=1 ( 1 1−p‖∇fi(xi(λ))‖ 2 + λ 2 p ‖xi(λ)− x(λ)‖ 2 ) .
Let us find the parameters p, α which lead to the fastest rate, to push the error within( O(ε) + 2nασ 2
µ
) -neighborhood of the optimum5, i.e., to achieve
E [∥∥xk − x(λ)∥∥2] ≤ ε∥∥x0 − x(λ)∥∥2 + 2nασ2µ . (10)
Corollary 4.3 The value p? = λL+λ minimizes both the number of iterations and the expected number of communications for achieving (10). In particular, the optimal number of iterations is 2L+λµ log 1 ε , and the optimal expected number of communications is 2λ λ+L L µ log 1 ε .
If we choose p = p?, then αλnp = 1 2 , and the aggregation rule (9) in Algorithm 1 becomes
xk+1i = 1 2 ( xki + x̄ k )
(11)
5In Sec. 5 we propose a variance reduced algorithm which removes the ( 2nασ 2
µ )-neighborhood from Thm. 4.2. In that setting, our goal will be to achieve E [∥∥xk − x(λ)∥∥2] ≤ ε∥∥x0 − x(λ)∥∥2.
F (x0)−F (x∗) ≤ 10
−5 as a function of p with
p∗ ≈ 0.09 (for L2SGD+). Logistic regression on a1a dataset with λ = 0.1.
while the local GD step (8) becomes xk+1i = x k i − 12L∇fi(x k i ). 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 to the optimization problem (2) will increasingly favour pure local models, i.e., xi(λ) → xi(0) := arg min fi for all i as λ → 0. Pure local models can be computed without any communication whatsoever and Cor. 4.3 confirms this intuition: the optimal number of communication round decreases to zero as λ → 0. On the other hand, as λ → ∞, the optimal number of communication rounds converges to 2Lµ log 1 ε , which recovers the performance of GD for finding the globally optimal model (see Fig. 1).
In summary, we recover the communication efficiency of GD for finding the globally optimal model as λ → ∞ (ignoring the ( 2nασ 2
µ )-neighborhood). However, for other values of λ, the communication complexity of L2GD is better and decreases to 0 as λ → 0. Hence, our communication complexity result interpolates between the communication complexity of GD for finding the global model and the zero communication complexity for finding the pure local models.

heading: 5 LOOPLESS LOCAL SGD WITH VARIANCE REDUCTION
text: As we have seen in Sec. 4.2, L2GD is a 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 a 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.6 For convenience, we present variance reduced local GD (i.e., no local subsampling) in the Appendix. Assumption 5.1 Assume that fi has a finite-sum structure: fi(xi) = 1m ∑m j=1 f ′ i,j(xi). Let f ′ i,j be convex, L′-smooth while fi is µ-strongly convex (for each 1 ≤ j ≤ m, 1 ≤ i ≤ n).

heading: 5.1 CONVERGENCE THEORY
text: We are now ready to present a convergence rate of L2SGD+ (the algorithm, along with the efficient implementation is presented in Appendix C.4). Theorem 5.1 Let Assumption 5.1 hold and chooseα = nmin {
(1−p) 4L′+µm , p 4λ+µ
} . Then the iteration
complexity of Algorithm 3 is max {
4L′+µm (1−p)µ , 4λ+µ pµ } log 1ε .
Next, we find the value of p that yields both the best iteration and communication complexity.
6We are aware that a linearly converging local SGD (with λ =∞) can be obtained as a particular instance of the decoupling method (Mishchenko & Richtárik, 2019). Other variance reduced local SGD algorithms (Liang et al., 2019; Karimireddy et al., 2019; Wu et al., 2019) do not achieve linear convergence.
Corollary 5.2 Both communication and iteration complexity of L2SGD+ are minimized for p = 4λ+µ 4λ+4L′+(m+1)µ . The resulting iteration complexity is ( 4λµ + 4 L′ µ +m+ 1 ) log 1ε , while the com-
munication complexity is 4λ+µ4L′+4λ+(m+1)µ ( 4L ′ µ +m ) log 1ε . Note that with λ → ∞, the communication complexity of L2SGD+ tends to ( 4L ′ µ +m )
log 1ε , which is communication complexity of minibatch SAGA to find the globally optimal model (Hanzely & Richtárik, 2019). On the other hand, in the pure local setting (λ = 0), the communication complexity becomes log 1 – 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 arbitrary 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 tighter rates.

heading: 6 EXPERIMENTS
text: In this section, we numerically verify the theoretical claims from this paper. We only present a 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+.
We consider logistic regression problem with LibSVM data (Chang & Lin, 2011). The data were normalized so that f ′i,j is 1-smooth for each j, while the local objectives are 10
−4-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 to Thm. 5.1.
We compare three different methods: L2SGD+, L2GD with local subsampling (L2SGD in the Appendix), and L2GD with local subsampling and control variates constructed for ψ only (L2SGD2 in the Appendix; similar to (Liang et al., 2019)). We expect L2SGD+ to converge to the global optimum linearly, while both L2SGD and L2SGD2 to converge to certain neighborhood. Each method is applied to two objectives constructed by a 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.
Fig. 3 demonstrates the importance of variance reduction – it ensures a fast global convergence of L2SGD+, while the neighborhood is slightly smaller for L2SGD2 compared to L2SGD. As predicted, data heterogeneity does not affect the convergence speed of the proposed methods.

heading: Appendix Federated Learning of a Mixture of Global and Local Models

heading: CONTENTS

heading: 1 Introduction 1
text: 1.1 Federated learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

heading: 2 Contributions 2

heading: 3 New Formulation of FL 4
text: 3.1 Technical preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Characterization of optimal solutions . . . . . . . . . . . . . . . . . . . . . . . . . 5

heading: 4 L2GD: Loopless Local GD 5
text: 4.1 The dynamics of local GD and averaging steps . . . . . . . . . . . . . . . . . . . 6
4.2 Convergence theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

heading: 5 Loopless Local SGD with Variance Reduction 7
text: 5.1 Convergence theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

heading: 6 Experiments 8

heading: A Possible Extensions 14

heading: B Experimental Setup and Further Experiments 14
text: B.1 Comparison of the methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
B.2 Effect of p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.3 Effect of λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

heading: C Remaining Algorithms 19
text: C.1 Understanding communication of L2GD . . . . . . . . . . . . . . . . . . . . . . . 19
C.2 L2GD and full averaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
C.3 Local GD with variance reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 19
C.4 L2SGD+: Algorithm and the efficient implementation . . . . . . . . . . . . . . . 21
C.5 Local SGD with variance reduction – general method . . . . . . . . . . . . . . . . 21
C.6 Local stochastic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

heading: D Missing Lemmas and Proofs 26
text: D.1 Gradient and Hessian of ψ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
D.2 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
D.3 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.4 Proof of Theorem 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.5 Proof of Theorem 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
D.6 Proof of Lemma D.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
D.7 Proof of Corollary 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
D.8 Proof of Corollary 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.9 Proof of Theorems 5.1, C.6, and C.7 . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.9.1 GJS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.9.2 Variance reduced local SGD as special case of GJS . . . . . . . . . . . . . 31
D.9.3 Proof of Theorem C.6 and Theorem C.7 . . . . . . . . . . . . . . . . . . . 31
D.9.4 Proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

heading: A POSSIBLE EXTENSIONS
text: Our analysis of L2GD can be extended to cover smooth convex and non-convex loss functions fi (we do not explore these directions). Further, our methods can be extended to a decentralized regime where the devices correspond to devices of a 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 ψ. 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.

heading: B EXPERIMENTAL SETUP AND FURTHER EXPERIMENTS
text: In all experiments in this paper, we consider a simple binary classification model – logistic regression. In particular, suppose that device i owns data matrix Ai ∈ Rm×d along with corresponding labels bi ∈ {−1, 1}m. The local objective for client i is then given as follows
fi(x) := 1
m m∑ j=1 f ′i,j(x) + µ 2 ‖x‖2, where f ′im+j(x) = log (1 + exp ((Ai)j,:x · bi)) .
The rows of data matrix A were normalized to have length 4 so that each f ′i,j is 1-smooth for each j. At the same time, the local objective on each device is 10−4 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 a single data point each iteration.
We have chosen a different number of clients for each dataset – so that we cover different possible scenarios. See Table 1 for details (it also includes sizes of the datasets). Lastly, the stepsize was always chosen according to Thm. 5.1.

heading: B.1 COMPARISON OF THE METHODS
text: In our first experiment, we 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 a fully variance reduced algorithm converges to the global optimum linearly, while both shifted local SGD and local SGD converge to a neighborhood of the optimum. At the same time, the neighborhood should be smaller for shifted local SGD.
• The claim that heterogeneity of the data does not influence the convergence rate. We consider 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
different in homogeneous and heterogeneous case – we thus plot relative suboptimality of the objective (i.e., F (x
k)−F (x?) F (x0)−F (x?) ) to directly compare the convergence speed.
In each experiment, we choose p = 0.1 and λ = 19 – such choice mean that p is very close to optimal. The other parameters (i.e., number of clients) are provided in Table 1. Fig. 4 presents the result.
As expected, Figure 4 clearly demonstrates the following:
• Full variance reduction always converges to the global optima, methods with partial variance reduction only converge to a neighborhood of the optimum.
• Partial variance reduction (i.e., shifting the 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. Therefore, 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 p on the convergence rate of variance reduced local SGD. Note that p immediately influences the number of communication rounds – on average, the clients take (p−1 − 1) local steps in between two consecutive rounds of communication (aggregation).
In Section 5, we argue that, it is optimal (in terms of the convergence rate) to choose p of order p? := λL′+λ . Figure 5 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 3 with p < p? is expected (i.e., communicating more frequently yields a 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 to the specific structure of problem (12); it would be lost when enforcing x1 = · · · = xn (corresponding to λ =∞).
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., p) is fixed. Note that for each value of λwe get a different instance of problem (12); thus the optimal solution is different as well. Therefore, in order to make a fair comparison between convergence speeds, we plot the relative suboptimality (i.e., F (x
k)−F (x?) F (x0)−F (x?) ) against
the data passes. Figure 6 presents the results. The complexity of Algorithm 3 is7 O ( L′
(1−p)µ ) log 1ε as soon as λ < λ ? := Lp(1−p) ; otherwise the
complexity isO ( λ pµ ) log 1ε . This perfectly consistent with what Figure 6 shows – the choice λ < λ ? resulted in comparable convergence speed than λ = λ?; while the choice λ > λ? yields noticeably worse rate than λ = λ?.
7Given that µ is small.

heading: C REMAINING ALGORITHMS

heading: C.1 UNDERSTANDING COMMUNICATION OF L2GD
text: Example C.1 In order to better understand when communication takes place in Algorithm 1, consider the following possible sequence of coin tosses: 0, 0, 1, 0, 1, 1, 1, 0. 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 xki are communicated to the master, averaged to form x̄
k, and the step (9) towards averaging is taken. The fourth coin toss is 0, and at this point, the master communicates the updated local models back to the devices, which subsequently perform a single local GD step (8). 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 0, which makes the master send the updated local models back to the devices, which subsequently perform a single local GD step.
This example illustrates that communication needs to take place whenever two consecutive coin tosses land a different value. If 0 is followed by a 1, all devices communicate to the master, and if 1 is followed by a 0, the master communicates back to the devices. It is standard to count each pair of communications, Device→Master and the subsequent Master→Device, as a single communication round.
Lemma C.2 The expected number of communication rounds in k iterations of L2GD is p(1− p)k.

heading: C.2 L2GD AND FULL AVERAGING
text: Is a setup such that conditions of Thm. 4.2 are satisfied and the aggregation update (9) is identical to full averaging? This is equivalent requiring 0 < p < 1 such that αλ = np. However, we have αλ ≤ λ2L ≤ np, which means that full averaging is not supported by our theory.

heading: C.3 LOCAL GD WITH VARIANCE REDUCTION
text: In this section, we present variance reduced local gradient descent with partial aggregation. In particular, the proposed algorithm (Algorithm 2) incorporates control variates to Algorithm 1. Therefore, the proposed method can be seen as a special case of Algorithm 3 withm = 1. We thus only present it for pedagogical purposes, as it might shed additional insights into our approach.
In particular, the update rule of proposed method will be xk+1 = xk − αgk where
gk = { p−1(λ∇ψ(xk)− n−1Ψk) + n−1Jk + n−1Ψk with probability p (1− p)−1(∇f(xk)− n−1Jk) + n−1Jk + n−1Ψk with probability 1− p .
for some control variates vectors Jk,Ψk ∈ Rnd. A quick check gives E [ gk |xk ] = ∇f(xk) + λ∇ψ(xk) = ∇F (xk),
thus the direction we are taking is unbiased regardless of the value of control variates Jk,Ψk. The goal is to make control variates Jk,Ψk correlated8 with n∇f(xk) and nλ∇ψ(xk). One possible solution to the problem is for Jk,Ψk to track most recently observed values of n∇f(·) and nλ∇ψ(·), which corresponds to the following update rule(
Ψk+1,Jk+1 ) =
{( nλ∇ψ(xk),Jk ) with probability p(
Ψk, n∇f(xk) ) with probability 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 x̄k 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 of the method for free. We state it as Thm. C.3.
8Specifically we aim to have Corr [ Jk, n∇f(xk) ] → 1 and Corr [ n−1Ψk, λ∇ψ(xk) ] → 1 as xk → x?.
Algorithm 2 Variance reduced local gradient descent
Input: x01 = · · · = x0n ∈ Rd, stepsize α, probability p J01 = · · · = J0n = Ψ01 = · · · = Ψ0n = 0 ∈ Rd for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ then
All Devices i = 1, . . . , n: Compute∇fi(xki ) xk+1i = x k i − α ( n−1(1− p)−1∇fi(xki )− n−1 p 1−pJ k i + n −1Ψki ) Set Jk+1i = ∇fi(xki ), Ψ k+1 i = Ψ k i
else Master computes the average x̄k = 1n ∑n i=1 x k i
Master does for all i = 1, . . . , n: Set xk+1i = x k i − α ( λ np (x k i − x̄k)− (p−1 − 1)n−1Ψki + n−1Jki ) Set Ψk+1i = λ(x k i − x̄k), J k+1 i = J k i
end if end for
Theorem C.3 Let Assumption 3.1 hold. Set α = nmin (
(1−p) 4L+µ , p 4λ+µ
) . Then, iteration complexity
of Algorithm 2 is max ( 4L+µ µ(1−p) , 4λ+µ µp ) log 1ε .
Proof: Clearly,
F (x) = f(x) + λψ(x) = 12 2f(x)︸ ︷︷ ︸ :=f(x) + 2λψ(x)︸ ︷︷ ︸ :=ψ(x)  . Note that ψ is 2λn smooth and f is 2L n smooth. At the same time, F is µ n strongly convex. Using convergence theorem of SAGA with importance sampling from (Qian et al., 2019b; Gazagnadou et al., 2019), we get
E [ F (xk) + α2 Υ(J k,Ψk) ] ≤ ( 1− αµn )k ( F (x0) + α2 Υ(J 0,Ψ0) ) ,
where
Υ(Jk,Ψk) := 4n2 n∑ i=1 (∥∥Ψki − λ(xi(λ)− x̄(λ))∥∥2 + ‖Jki −∇fi(xi(λ))‖2) and α = nmin ( (1−p) 4L+µ , p 4λ+µ ) , as desired.
Corollary C.4 Iteration complexity of Algorithm 2 is minimized for p = 4λ+µ4λ+4L+2µ , which yields complexity 4 ( λ µ + L µ + 1 2 ) log 1ε . The communication complexity is minimized for any p ≤ 4λ+µ4λ+4L+2µ , in which case the total number of communication rounds to reach ε-solution is( 4λ µ + 1 ) log 1ε .
As a direct consequence of Corollary C.4 we see that the optimal choice of p that minimizes both communication and number of iterations to reach ε solution of problem (17) is p = 4λ+µ4λ+4L+2µ .
Remark C.5 While both Algorithm 2 and Algorithm 3 are a special case of SAGA, the practical version of variance reduced local SGD (presented in Section C.5) is not. In particular, we wish to run the SVRG-like method locally in order to avoid storing the full gradient table.9 Therefore,
9SAGA does not require storing a full gradient table for problems with linear models by memorizing the residuals. However, in full generality, SVRG-like methods are preferable.
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 & Richtárik, 2019).
As mentioned, Algorithm 3 is a generalization of Algorithm 2 when the local subproblem is a finite sum. Note that Algorithm 2 constructs a control variates for both local subproblem and aggregation function ψ and constructs corresponding unbiased gradient estimator. In contrast, Algorithm 3 constructs extra control variates within the local subproblem in order to reduce the variance of gradient estimator coming from the local subsampling.

heading: C.4 L2SGD+: ALGORITHM AND THE EFFICIENT IMPLEMENTATION
text: Denote 1 ∈ Rm to be vector of ones. We are now ready to state L2SGD+ as Algorithm 3.
Algorithm 3 L2SGD+: Loopless Local SGD with Variance Reduction
Input: x01 = · · · = x0n ∈ Rd, stepsize α, probability p J0i = 0 ∈ Rd×m,Ψ0i = 0 ∈ Rd (for i = 1, . . . , n) for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ = 0 then
All Devices i = 1, . . . , n: Sample j ∈ {1, . . . ,m} (uniformly at random) gki = 1 n(1−p) ( ∇f ′i,j(xki )− ( Jki ) :,j ) + Jki 1 nm + Ψki n
xk+1i = x k i − αgki Set (Jk+1i ):,j = ∇f ′i,j(xki ), Ψ k+1 i = Ψ k i ,
(Jk+1i ):,l = (J k+1 i ):,l for all l 6= jelse Master computes the average x̄k = 1n ∑n i=1 x k i
Master does for all i = 1, . . . , n: gki = λ np (x k i − x̄k)− p−1−1 n Ψ k i + 1 nmJ k i 1
Set xk+1i = x k i − αgki Set Ψk+1i = λ(x k i − x̄k), J k+1 i = J k i
end if end for
L2SGD+ only communicates when a two consecutive coin tosses land a different value, thus, on average p(1 − p)k times per k iterations. However, L2SGD+ requires communication of control variates Ji1,Ψi 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 Ji1,Ψi.
Here we present an efficient implementation of L2SGD+ as Algorithm 4 so that we do not have to communicate control variates. As a consequence, Algorithm 4 needs to communicate on average p(1 − p)k times per k iterations, while each communication consists of sending only local models to the master and back.

heading: C.5 LOCAL SGD WITH VARIANCE REDUCTION – GENERAL METHOD
text: In this section, we present a fully general variance reduced local SGD. We consider a more general instance of (2) where each local objective includes a possibly nonsmooth regularizer, which admits a cheap evaluation of proximal operator. In particular, the objective becomes
Algorithm 4 L2SGD+: Loopless Local SGD with Variance Reduction (communication-efficient implementation)
Input: x01 = · · · = x0n = x̃ ∈ Rd, stepsize α, probability p Initialize control variates J0i = 0 ∈ Rd×m,Ψ0i = 0 ∈ Rd (for i = 1, . . . , n), initial coin toss ξ−1 = 0 for k = 0, 1, . . . do ξk = 1 with probability p and 0 with probability 1− p if ξk = 0 then All Devices i = 1, . . . , n:
if ξk−1 = 1 then Receive xki , c from Master Reconstruct x̄k = x̄k−c using xki , x k−c i , c
Set xki = x k i − cα 1nmJ k i 1, J k i = J k−c i , Ψ k i = λ(x k−c i − x̄k),
end if Sample j ∈ {1, . . . ,m} (uniformly at random) gki = 1 n(1−p) ( ∇f ′i,j(xki )− ( Jki ) :,j ) + Jki 1 nm + Ψki n xk+1i = x k i − αgki Set (Jk+1i ):,j = ∇f ′i,j(xki ), Ψ k+1 i = Ψ k i ,
(Jk+1i ):,l = (J k+1 i ):,l for all l 6= j
else Master does for all i = 1, . . . , n:
if ξk−1 = 0 then Set c = 0 Receive xki from Device and set x̄ = 1 n ∑n i=1 x k i , x k i = x k i end if Set xk+1i = x k i − α ( λ np (x k i − x̄)− p−1−1 n λ(x̃− x̄)
) Set x̃ = xki Set c = c+ 1
end if end for
min x∈Rdn
1 N n∑ i=1 mi∑ j=1 f ′i,j(xi)  ︸ ︷︷ ︸ = N n fi(x)︸ ︷︷ ︸
=f(x)
+λ 12n n∑ i=1
‖xi − x̄‖2︸ ︷︷ ︸ =ψ(x)
︸ ︷︷ ︸ =F (x)
+ n∑ i=1
Ri(xi)︸ ︷︷ ︸ :=R(x) , (12)
where mi is the number of data points owned by client i and N = ∑n i=1mi.
In order to squeeze a faster convergence rate from minibatch samplings, we will assume that f ′i,j is smooth with respect to a matrix Mi,j (instead of scalar L′i,j = λmaxMi,j).
Assumption C.1 Suppose that f ′i,j is Mi,j smooth (Mi,j ∈ Rd×d,Mi,j 0) and µ strongly convex for 1 ≤ j ≤ mi, 1 ≤ i ≤ n, i.e.
f ′i,j(y)+ 〈 ∇f ′i,j(y), x− y 〉 ≤ f ′i,j(x) ≤ f ′i,j(y)+ 〈 ∇f ′i,j(y), x− y 〉 + 12 ‖y − x‖ 2 Mi,j
, ∀x, y ∈ Rd. (13)
Furthermore, assume that Ri is convex for 1 ≤ i ≤ n.
Our method (Algotihm 5) allows for arbitrary aggregation probability (same as Algorithms 2, 3), arbitrary sampling of clients (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
objective and arbitrary subsampling strategy of each client). Moreover, it allows for the SVRG-like update rule of local control variates Jk, which requires less storage given an efficient implementation.
To be specific, each device owns a distribution Di over subsets of mi. When the aggregation is not performed (with probability 1 − p), a subset of active devices S is selected (S follows arbitrary fixed distribution D). Each of the active clients (i ∈ S) samples a subset of local indices Si ∼ Di and observe the corresponding part of local Jacobian Gi(xk)(:,Si) (where Gi(x k) := [∇f ′i,1(xk),∇f ′i,2(xk), . . .∇f ′i,mi(x k)). When the aggregation is performed (with probability p) we evaluate x̄k and distribute it to each device; using which each device computes a corresponding component of λ∇ψ(xk). Those are the key components in constructing the unbiased gradient estimator (without control variates).
It remains to construct control variates and unbiased gradient estimator. If 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 a particular case of SAGA (Defazio et al., 2014)) or do LSVRG-like replacement (Hofmann et al., 2015; Kovalev et al., 2020) (in such case, the algorithm is a particular case of GJS (Hanzely & Richtárik, 2019), but is not a 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.
In order to keep the gradient estimate unbiased, it will be convenient to define vector pi ∈ Rmi such that for each j ∈ {1, . . . ,mi} we have P (j ∈ Si) = pi,j . Next, to give a tight rate for any given pair of smoothness structure and sampling strategy, we use a standard tool first proposed for the analysis of randomized coordinate descent methods (Richtárik & Takáč, 2016; Qu & Richtárik, 2016) called Expected Separable Overapproximation (ESO) assumption. ESO provides us with smoothness parameters of the objective which “account” for the given sampling strategy.
Assumption C.2 Suppose that there is vi ∈ Rmi such for each client we have:
E  ∥∥∥∥∥∥ ∑ j∈Si M 1 2 i,jhi,j ∥∥∥∥∥∥ 2  ≤ mi∑ j=1 pi,jvi,j ‖hi,j‖2 , ∀ 1 ≤ i ≤ n, ∀hi,j ∈ Rmi , j ∈ {1, . . . ,mi}.
(14)
Lastly, denote pi to be the probability that worker i is active and 1(mi) ∈ Rmi to be the vector of ones. The resulting algorithm is stated as Algorithm 5.
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.1 and C.2 hold. Let
α = min { min
j∈{1,...,mi},1≤i≤n
N(1−p)pi,jpi 4vj+N
µ n
, np4λ+µ
} .
Then the iteration complexity of Algorithm 5 (SAGA option) is
max { max
j∈{1,...,mi},1≤i≤n
( 4vj
n N +µ
µ(1−p)pi,jpi ) , 4λ+µpµ } log 1ε .
Theorem C.7 Suppose that Assumptions C.1 and C.2 hold. Let
α = min { min
j∈{1,...,mi},1≤i≤n N(1−p)pi
4 vj pi,j +N µ np −1 i
, pn4λ+µ
} .
Then the iteration complexity of Algorithm 5 (LSVRG option) is
max { max
j∈{1,...,mi},1≤i≤n
( 4vj
n Npi,j +µp−1i piµ(1−p) ) , 4λ+µpµ } log 1ε .
Algorithm 5 L2SGD++: Loopless Local SGD with Variance Reduction and Partial Participation
Input: x01, . . . x0n ∈ Rd, # parallel units n, each of them owns mi data points (for 1 ≤ i ≤ n), distributions Dt over subsets of {1, . . . ,mi}, distribution D over subsets of {1, 2, . . . n}, aggregation probability p, stepsize α J0i = 0 ∈ Rd×mi ,Ψ0i = 0 ∈ Rd (for i = 1, . . . , n) for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ = 0 then
Sample S ∼ D All Devices i ∈ S:
Sample Si ∼ Di; Si ⊆ {1, . . . ,mi} (independently on each machine) Observe ∇f ′i,j(xki ) for all j ∈ Si gki = 1 N(1−p)pi (∑ j∈Si p −1 i,j ( ∇f ′i,j(xki )− ( Jki ) :,j )) + 1N J k i 1 (mi) + n−1Ψki xk+1i = proxαRi(x k i − αgki )
For all j ∈ {1, . . . ,mi} set Jk+1:,j =  { ∇f ′i,j(xki ) if j ∈ Si Jk:,j otherwise
if SAGA{ ∇f ′i,j(xki ); w. p. pi Jk:,j otherwise if L− SVRG
Set Ψk+1i = Ψ k i All Devices i 6∈ S: gki = 1 N J k i 1
(mi) + n−1Ψki xk+1i = proxαRi(x k i − αgki ) Set Jk+1i = J k i ,Ψ k+1 i = Ψ k i
else Master computes the average x̄k = 1n ∑n i=1 x k i
Master does for all i = 1, . . . , n: gki = p −1λ(xki − x̄k)− (p−1 − 1)n−1Ψki + 1N J k i 1 (mi) Set xk+1i = proxαRi ( xki − αgki ) Set Ψk+1i = λ(x k i − x̄k), J k+1 i = J k i
end if end for
Remark C.8 Algotihm 2 is a special case of Algorithm 3 which is in turn special case of Algorithm 5. Similarly, Theorem 2 is a special case of Theorem 5.1 which is again special case of Theorem C.6.

heading: C.6 LOCAL STOCHASTIC ALGORITHMS
text: In this section, we present two more algorithms – Local SGD with partial variance reduction (Algorithm 7) and Local SGD without variance reduction (Algorithm 6). While Algorithm 6 uses no control variates at all (thus is essentially Algorithm 1 where local gradient descent steps are replaced with local SGD steps), Algorithm 7 constructs control variates for ψ 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 et al., 2020).
Algorithm 6 Loopless Local SGD (L2SGD)
Input: x01 = · · · = x0n ∈ Rd, stepsize α, probability p for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ = 0 then
All Devices i = 1, . . . , n: Sample j ∈ {1, . . . ,m} (uniformly at random) gki = 1 n(1−p) ( ∇f ′i,j(xki ) ) xk+1i = x k i − αgki
else Master computes the average x̄k = 1n ∑n i=1 x k i
Master does for all i = 1, . . . , n: gki = λ np (x k i − x̄k)
Set xk+1i = x k i − αgki
end if end for
Algorithm 7 Loopless Local SGD with partial variance reduction (L2SGD2)
Input: x01 = · · · = x0n ∈ Rd, stepsize α, probability p Ψ0i = 0 ∈ Rd (for i = 1, . . . , n) for k = 0, 1, . . . do ξ = 1 with probability p and 0 with probability 1− p if ξ = 0 then
All Devices i = 1, . . . , n: Sample j ∈ {1, . . . ,m} (uniformly at random) gki = 1 n(1−p) ( ∇f ′i,j(xki ) ) + 1nΨ k i
xk+1i = x k i − αgki Set Ψk+1i = Ψ k i
else Master computes the average x̄k = 1n ∑n i=1 x k i
Master does for all i = 1, . . . , n: gki = λ np (x k i − x̄k)− p−1−1 n Ψ k i
Set xk+1i = x k i − αgki Set Ψk+1i = λ(x k i − x̄k)
end if end for

heading: D MISSING LEMMAS AND PROOFS
text: D.1 GRADIENT AND HESSIAN OF ψ
Lemma D.1 Let I be the d× d identity matrix and In be n× n identity matrix. Then, we have
∇2ψ(x) = 1n ( In − 1nee >)⊗ I and ∇ψ(x) = 1n  x−  x̄ ... x̄ x̄ x̄ ... x̄   .
Furthermore, Lψ = 1n .

heading: Proof:
text: Let O the d× d zero matrix and let Qi := [O, . . . ,O︸ ︷︷ ︸
i−1 , I,O, . . . ,O︸ ︷︷ ︸ n−i ] ∈ Rd×dn
and Q := [I, . . . , I] ∈ Rd×dn. Note that xi = Qix, and x̄ = 1nQx. So,
ψ(x) = 12n n∑ i=1 ∥∥Qix− 1nQx∥∥2 = 12n n∑ i=1 ∥∥(Qi − 1nQ)x∥∥2 . The Hessian of ψ is
∇2ψ(x) = 1n n∑ i=1 ( Qi − 1nQ )> ( Qi − 1nQ ) = 1n
n∑ i=1 ( Q>i Qi − 1nQ > i Q− 1nQ >Qi + 1 n2 Q >Q )
= 1n n∑ i=1 Q>i Qi − 1n n∑ i=1 1 nQ > i Q− 1n n∑ i=1 1 nQ >Qi + 1 n n∑ i=1 1 n2 Q >Q
= 1n n∑ i=1 Q>i Qi − 1n2 Q >Q
and by plugging in for Q and Qi, we get
∇2ψ(x) = 1n  ( 1− 1n ) I − 1nI − 1 nI · · · − 1 nI − 1nI ( 1− 1n ) I − 1nI · · · − 1 nI − 1nI − 1 nI ( 1− 1n ) I · · · − 1nI ... ... ... ...
− 1nI − 1 nI − 1 nI · · · ( 1− 1n ) I

= 1n  ( 1− 1n ) − 1n − 1 n · · · − 1 n − 1n ( 1− 1n ) − 1n · · · − 1 n − 1n − 1 n ( 1− 1n ) · · · − 1n ... ... ... ...
− 1n − 1 n − 1 n · · · ( 1− 1n ) ⊗ I = 1n ( In − 1nee
>)⊗ I. Notice that In − 1nee
> is a circulant matrix, with eigenvalues 1 (multiplicity n − 1) and 0 (multiplicity 1). Since the eigenvalues of a Kronecker product of two matrices are the products of pairs of eigenvalues of the these matrices, we have
λmax(∇2ψ(x)) = λmax ( 1 n ( In − 1nee >)⊗ I) = 1nλmax (In − 1nee>) = 1n .
So, Lψ = 1n .
The gradient of ψ is given by
∇ψ(x) = 1n n∑ i=1 ( Qi − 1nQ )> ( Qi − 1nQ ) x
= 1n n∑ i=1 ( Q>i Qi − 1nQ > i Q− 1nQ >Qi + 1 n2 Q >Q ) x
= 1n n∑ i=1   0 ... 0 xi 0 ... 0  −  0 ... 0 x̄ 0 ... 0  −  xi/n ... xi/n xi/n xi/n ... xi/n  +  x̄/n ... x̄/n x̄/n x̄/n ... x̄/n  
= 1n  n∑ i=1  0 ... 0 xi 0 ... 0  − n∑ i=1  0 ... 0 x̄ 0 ... 0  − n∑ i=1  xi/n ... xi/n xi/n xi/n ... xi/n  + n∑ i=1  x̄/n ... x̄/n x̄/n x̄/n ... x̄/n  
= 1n  x−  x̄ ... x̄ x̄ x̄ ... x̄  −  x̄ ... x̄ x̄ x̄ ... x̄  +  x̄ ... x̄ x̄ x̄ ... x̄  
= 1n  x−  x̄ ... x̄ x̄ x̄ ... x̄   .

heading: D.2 PROOF OF THEOREM 3.1
text: For any λ, θ ≥ 0 we have f(x(λ)) + λψ(x(λ)) ≤ f(x(θ)) + λψ(x(θ)) (15) f(x(θ)) + θψ(x(θ)) ≤ f(x(λ)) + θψ(x(λ)). (16)
By adding inequalities (15) and (16), we get
(θ − λ)(ψ(x(λ))− ψ(x(θ))) ≥ 0, which means that ψ(x(λ)) is decreasing in λ. Assume λ ≥ θ. From the (16) we get
f(x(λ)) ≥ f(x(θ)) + θ(ψ(x(θ))− ψ(x(λ))) ≥ f(x(θ)), where the last inequality follows since θ ≥ 0 and since ψ(x(θ)) ≥ ψ(x(λ)). So, f(x(λ)) is increasing.
Notice that since ψ is a non-negative function and since x(λ) minimizes F and ψ(x(∞)) = 0, we have
f(x(0)) ≤ f(x(λ)) ≤ f(x(λ)) + λψ(x(λ)) ≤ f(x(∞)), which implies (3) and (4).

heading: D.3 PROOF OF THEOREM 3.2
text: The equation∇F (x(λ)) = 0 can be equivalently written as
∇fi(xi(λ)) + λ(xi(λ)− x(λ)) = 0, i = 1, 2, . . . , n,
which is identical to (5). Averaging these identities over i, we get
x(λ) = x(λ)− 1λ 1 n n∑ i=1 ∇fi(xi(λ)),
which implies n∑ i=1 ∇fi(xi(λ)) = 0.
Further, we have
ψ(x(λ)) = 12n n∑ i=1 ‖xi(λ)− x(λ)‖2 = 12nλ2 n∑ i=1 ‖∇fi(xi(λ))‖2 = 12λ2 ‖∇f(x(λ))‖ 2 ,
as desired.

heading: D.4 PROOF OF THEOREM 3.3
text: First, observe that
||∇P (x̄(λ))||2 = ∥∥∥∥∥ 1n∑ i ∇fi(x̄(λ)) ∥∥∥∥∥ 2 = ∥∥∥∥∥ 1n∑ i ∇fi(x̄(λ))− 1 n ∑ i ∇fi(xi(λ)) ∥∥∥∥∥ 2 ,
where the second identity is due to Theorem 3.2 which says that 1n ∑ i∇fi(xi(λ)) = 0. By applying Jensen’s inequality and Lipschitz continuity of functions fi, we get
||∇P (x̄(λ))||2 ≤ 1 n ∑ i ||∇fi(x̄(λ))−∇fi(xi(λ))||2 ≤ L2 n ∑ i ||x̄(λ)− xi(λ)||2 = 2L2ψ(x(λ)).
It remains to apply (3) and notice that P is strongly convex and thus x(∞) is indeed the unique minimizer.

heading: D.5 PROOF OF THEOREM 4.2
text: We first show that our gradient estimator G(x) satisfies the expected smoothness property (Gower et al., 2018; 2019). Lemma D.2 LetL := 1n max { L 1−p , λ p } and σ2 := 1n2 ∑n i=1 ( 1 1−p‖∇fi(xi(λ))‖ 2 + λ 2 p ‖xi(λ)− x(λ)‖ 2 ) .
Then for all x ∈ Rd we have the inequalities E [ ‖G(x)−G(x(λ))‖2 ] ≤ 2L (F (x)− F (x(λ))) and E [ ‖G(x)‖2 ] ≤ 4L(F (x)− F (x(λ))) + 2σ2.
Next, Theorem 4.2 from Lemma D.2 by applying Theorem 3.1 from (Gower et al., 2019).

heading: D.6 PROOF OF LEMMA D.2
text: We first have E [ ‖G(x)−G(x(λ))‖2 ] = (1− p) ∥∥∥∇f(x)1−p − ∇f(x(λ))1−p ∥∥∥2 + p ∥∥∥λ∇ψ(x)p − λ∇ψ(x(λ))p ∥∥∥2 = 11−p ‖∇f(x)−∇f(x(λ))‖ 2 + λ 2 p ‖∇ψ(x)−∇ψ(x(λ))‖ 2
≤ 2Lf1−pDf (x, x(λ)) + 2λ2Lψ p Dψ(x, x(λ))
= 2Ln(1−p)Df (x, x(λ)) + 2λ2 np Dψ(x, x(λ)).
Since Df + λDψ = DF and ∇F (x(λ)) = 0, we can continue:
E [ ‖G(x)−G(x(λ))‖2 ] ≤ 2n max { L 1−p , λ p } DF (x, x(λ))
= 2n max { L 1−p , λ p } (F (x)− F (x(λ))) .
Next, note that
σ2 = 1n2 n∑ i=1 ( 1 1−p‖∇fi(xi(λ))‖ 2 + λ 2 p ‖xi(λ)− x(λ)‖ 2 )
= 11−p ‖∇f(x(λ))‖ 2 + λ 2 p ‖∇ψ(x(λ))‖ 2 = (1− p) ∥∥∥∇f(x(λ))1−p ∥∥∥2 + p ∥∥∥λ∇ψ(x(λ))p ∥∥∥2
= E [ ‖G(x(λ))‖2 ] .
Therefore, we have E [ ‖G(x)‖2 ] ≤ E [ ‖G(x)−G(x(λ))‖2 ] + 2E [ ‖G(x(λ))‖2 ] Lemma D.2+(17)
≤ 4L(F (x)− F (x(λ))) + 2σ2,
as desired.

heading: D.7 PROOF OF COROLLARY 4.3
text: Firstly, to minimize the total number of iterations, it suffices to minimize L which is achieved with p? = λL+λ . Let us look at the communication. Fix ε > 0, choose α = 1 2L and let k = 2nL µ log 1 ε , so that ( 1− µ2nL
)k ≤ ε. The expected number of communications to achieve this goal is equal to
Commp := p(1− p)k
= p(1− p) 2 max
{ L
1−p , λ p } µ log 1 ε
= 2 max{pL,(1−p)λ}µ log 1 ε .
The quantity Commp is minimized by choosing any p such that pL = (1−p)λ, i.e., for p = λλ+L = p?, as desired. The optimal expected number of communications is therefore equal to
Commp? = 2λ λ+L L µ log 1 ε .

heading: D.8 PROOF OF COROLLARY 5.2
text: Firstly, to minimize the total number of iterations, it suffices to solve min max {
4L′+µm (1−p)µ , 4λ+µ pµ
} ,
which is achieved with p = p? = 4λ+µ4L′+4λ+(m+1)µ .
The expected number of communications to reach ε-solution is Commp = p(1− p) max { 4L′+µm (1−p)µ , 4λ+µ pµ } log 1ε
= max{p(4L′+µm),(1−p)(4λ+µ)}
µ log 1 ε .
Minimizing the above in p yield p = p? = 4λ+µ4L′+4λ+(m+1)µ , as desired. The optimal expected number of communications is therefore equal to
Commp? = 4λ+µ
4L′+4λ+(m+1)µ
( 4L ′ µ +m ) log 1ε .

heading: D.9 PROOF OF THEOREMS 5.1, C.6, AND C.7
text: 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 to show Theorems C.6, and C.7. In order to do so, we will cast Algorithm 5 as a special case of GJS from (Hanzely & Richtárik, 2019). As a consequence, Theorem C.6 will be a special cases of Theorem 5.2 from (Hanzely & Richtárik, 2019).
D.9.1 GJS
In this section, we quickly summarize results from (Hanzely & Richtárik, 2019), which we cast to sho convergence rate of Algorithm 3. GJS (Hanzely & Richtárik, 2019) is a method to solve regularized empirical risk minimization objective, i.e.,
min x∈Rd
1 n n∑ j=1 fj(x) +R(x). (17)
Defining G(x) := [∇f1(x), . . . ,∇fn(x)], we observe SG(x),UG(x) every iteration where S is random linear projection operator and U is random linear operator which is identity on expectation. Based on this random gradient information, GJS (Algorithm 8) constructs variance reduced gradient estimator g and takes a proximal step in that direction.
Algorithm 8 Generalized JacSketch (GJS) (Hanzely & Richtárik, 2019) 1: Parameters: Stepsize α > 0, random projector S and unbiased sketch U 2: Initialization: Choose solution estimate x0 ∈ Rd and Jacobian estimate J0 ∈ Rd×n 3: for k = 0, 1, . . . do 4: Sample realizations of S and U , and perform sketches SG(xk) and UG(xk) 5: Jk+1 = Jk − S(Jk −G(xk)) update the Jacobian estimate 6: gk = 1nJ ke+ 1nU ( G(xk)− Jk ) e construct the gradient estimator
7: xk+1 = proxαR(x k − αgk) 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 µ-quasi strongly convex, i.e.,
f(x?) ≥ f(y) + 〈∇f(y), x? − y〉+ µ2 ‖y − x ?‖2 , ∀y ∈ Rd, (18)
Functions fj are convex and Mj-smooth for some Mj 0, i.e.,
fj(y)+〈∇fj(y), x− y〉 ≤ fj(x) ≤ fj(y)+〈∇fj(y), x− y〉+ 12 ‖y − x‖ 2 Mj , ∀x, y ∈ Rd. (19)
Theorem D.3 (Slight simplification of Theorem 5.2 from (Hanzely & Richtárik, 2019)) Let Assumption D.1 hold. DefineM(X) := [M1X:,1, . . . ,MnX:,n] Let B be any linear operator commuting with S, and assumeM† 1 2 commutes with S. Define the Lyapunov function
Ψk := ∥∥xk − x?∥∥2 + α ∥∥∥∥BM† 12 (Jk −G(x?))∥∥∥∥2 , (20)
where {xk} and {Jk} are the random iterates produced by Algorithm 8 with stepsizeα > 0. Suppose that α and B are chosen so that
2α n2 E
[ ‖UXe‖2 ] + ∥∥∥∥(I − E [S]) 12 BM† 12 X∥∥∥∥2 ≤ (1− αµ)∥∥∥∥BM† 12 X∥∥∥∥2 (21) and
2α n2 E
[ ‖UXe‖2 ] + ∥∥∥∥(E [S]) 12 BM† 12 X∥∥∥∥2 ≤ 1n ∥∥∥∥M† 12 X∥∥∥∥2 . (22) for all X ∈ Rd×n. Then for all k ≥ 0, we have E [ Ψk ] ≤ (1− αµ)k Ψ0.
D.9.2 VARIANCE REDUCED LOCAL SGD AS SPECIAL CASE OF GJS Let Ω(i, j) := j+ ∑i−1 l=1 mi In order to case problem (12) as a special case of 17, denote n := N+1, fΩ(i,j)(x) := N+1 N f ′ i,j(xi) and fn := (N + 1)ψ. Therefore the objective (12) becomes
min x∈RNd
Υ(x) := 1n n∑ j=1 f j(x) +R(x). (23)
Let v ∈ Rn−1 be such that vΩ(i,j) = N+1N vi,j and as a consequence of (14) we have
E  ∥∥∥∥∥∥ ∑ j∈Si M 1 2 i,jhi,j ∥∥∥∥∥∥ 2  ≤ mi∑ j=1 pi,jvΩ(i,j) ‖hi,j‖ 2 , ∀ 1 ≤ i ≤ n, ∀hi,j ∈ Rd, j ∈ {1, . . . ,mi}.
(24) At the same time, Υ is µ := µn strongly convex.

heading: D.9.3 PROOF OF THEOREM C.6 AND THEOREM C.7
text: Let e ∈ Rd be a vector of ones and pi ∈ RN is such that pij = pi,j if j ∈ {1, . . . ,mi}, otherwise pij = 0. Given the notation, random operator U is chosen as
UX = (1− p)−1 ∑n i=1 ( p−1i e (( pi )−1)>) ◦ (X:mi (∑j∈Si ejej>)) w.p. (1− p)
p−1X:,n w.p. p
We next give two options on how to update Jacobian – first one is SAGA-like, second one is SVRG like.
SAGA-like: (SX):,mi =
{ X:,Si = X:mi (∑ j∈Si ejej > ) , w.p. (1− p)pi,
0 w.p. (1− p)(1− pi) + p (SX):,n = {
X:,n w.p. p 0 w.p. 1− p
SVRG-like: (SX):,mi = X:mibi; bi = { 1 w.p. pi 0 w.p. 1− pi w.p. (1− p)pi
0 w.p. (1− p)(1− pi) + p (SX):,n = {
X:,n w.p. p 0 w.p. 1− p .
We can now proceed with the proof of Theorem C.6 and Theorem C.7. As ∇fi(x) − ∇fi(y) ∈ Range (Mi), we must have
G(xk)−G(x?) =M†M ( G(xk)−G(x?) ) (25)
and Jk −G(x?) =M†M ( Jk −G(x?) ) . (26)
Due to (26), (25), inequalities (21) and (22) with choice Y =M† 1 2 X become respectively:
2α n2 p −1‖M 1 2 nY:,n‖2 + 2α 2 n2 (1− p) −1 n∑ i=1 E  ∥∥∥∥∥∥p−1i ∑ j∈Si p−1i,j M 1 2 i,jY:j ∥∥∥∥∥∥ 2 + ∥∥∥∥(I − E [S]) 12 B(Y)∥∥∥∥2
≤ (1− αµ)‖B(Y)‖2 (27)
2α n2 p −1‖M 1 2 nY:,n‖2+ 2α 2 n2 (1−p) −1 n∑ i=1 E  ∥∥∥∥∥∥p−1i ∑ j∈Si p−1i,j M 1 2 i,jY:j ∥∥∥∥∥∥ 2 +∥∥∥∥(E [S]) 12 B(Y)∥∥∥∥2 ≤ 1n‖Y‖2
(28)
Above, we have used
E‖UXe‖2 = E [ ‖UM 1 2 Ye‖2 ] = p−1‖M 1 2 nY:,n‖2+(1−p)−1 n∑ i=1 E  ∥∥∥∥∥∥p−1i ∑ j∈Si p−1i,j M 1 2 i,jY:j ∥∥∥∥∥∥ 2  .
Note that E [S(X)] = X · Diag ((1− p)(p ◦ p), p) where p ∈ Rn−1 such that pΩ(i,j) = pi,j . Using (24), setting B to be right multiplication with Diag(b) and noticing that λmaxMn = nλ it suffices to have
2α n p −1λ+ (1− p)b2n ≤ (1− αµ)b2n
2α n2 (1− p) −1p−1i,j p −1 i vΩ(i,j) + (1− (1− p)pi,jpi)b 2 j ≤ (1− αµ)b2j ∀j ∈ {1, . . . ,mi}, i ≤ n
2α n p −1λ+ pb2n ≤ 1n
2α n2 (1− p) −1p−1i,j p −1 i vΩ(i,j) + (1− p)pi,jpib 2 j ≤ 1n ∀j ∈ {1, . . . ,mi}, i ≤ n
for SAGA case and 2α n p −1λ+ (1− p)b2n ≤ (1− αµ)b2n
2α n2 (1− p) −1p−1i,j p −1 i vΩ(i,j) + (1− (1− p)pipi)b 2 j ≤ (1− αµ)b2j ∀j ∈ {1, . . . ,mi}, i ≤ n
2α n p −1λ+ pb2n ≤ 1n
2α n2 (1− p) −1p−1i,j p −1 i vΩ(i,j) + (1− p)pipib 2 j ≤ 1n ∀j ∈ {1, . . . ,mi}, i ≤ n
for LSVRG case.
It remains to notice that to satisfy the SAGA case, it suffices to set b2n = 1 2np , b 2 Ω(i,j) = 1 2n(1−p)pi,jpi (for j ∈ {1, . . . ,mi}, i ≤ n) and α = min {
minj∈{1,...,mi},1≤i≤n n(1−p)pi,jpi 4vΩ(i,j)+nµ , p4λ+µ
} .
To satisfy LSVRG case, it remains to set b2n = 1 2np , b 2 Ω(i,j) = 1 2n(1−p)pipi (for j ∈ {1, . . . ,mi}, i ≤
n) and α = min { minj∈{1,...,mi},1≤i≤n
n(1−p)pi 4 vΩ(i,j) pi,j +nµp−1i , p4λ+µ
} .
The last step to establish is to recall that n = N + 1, vΩ(i,j) = N+1N vi,j and µ = µ n and note that the iteration complexity is 1αµ log 1 ε = n αµ log 1 ε .

heading: D.9.4 PROOF OF THEOREM 5.1
text: To obtain convergence rate of Theorem 5.1, it remains to use Theorem C.6 with pi = 1,mi = m (∀i ≤ n), where each machine samples (when the aggregation is not performed) individual data points with probability 1m and thus pj = 1 m (for all j ≤ N ). The last remaining thing is to realize that vj = L′ for all j ≤ N .

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