Abstract
Federated learning makes a large amount of edge computing devices jointlylearn a model without data sharing. As a leading algorithm in this setting,Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent (SGD) inparallel on a small subset of the total devices and averages the sequences onlyonce in a while. Despite its simplicity, it lacks theoretical guarantees underrealistic settings. In this paper, we analyze the convergence of\texttt{FedAvg} on noniid data and establish a convergence rate of$\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$is the iteration number of SGDs. Importantly, our bound demonstrates atradeoff between communicationefficiency and convergence rate. As userdevices may be disconnected from the server, we relax the assumption of fulldevice participation to partial device participation and study differentaveraging schemes; low device participation rate can be achieved withoutseverely slowing down the learning. Our results indicate that heterogeneity ofdata slows down the convergence, which matches empirical observations.Furthermore, we provide a necessary condition for \texttt{FedAvg}'s convergenceon noniid data: the learning rate $\eta$ must decay, even if fullgradient isused; otherwise, the solution will be $\Omega (\eta)$ away from the optimal.
Quick Read (beta)
On the Convergence of FedAvg on NonIID Data
Abstract
Federated learning makes a large amount of edge computing devices jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (FedAvg) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of FedAvg on noniid data and establish a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the iteration number of SGDs. Importantly, our bound demonstrates a tradeoff between communicationefficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for FedAvg’s convergence on noniid data: the learning rate $\eta $ must decay, even if fullgradient is used; otherwise, the solution will be $\mathrm{\Omega}(\eta )$ away from the optimal.
On the Convergence of FedAvg on NonIID Data
Xiang Li 

School of Mathematical Sciences 
Peking University 
Beijing, 100871, China 
[email protected] 
Kaixuan Huang 

School of Mathematical Sciences 
Peking University 
Beijing, 100871, China 
[email protected] 
Wenhao Yang 

Center for Data Science 
Peking University 
Beijing, 100871, China 
[email protected] 
Shusen Wang 

Department of Computer Science 
Stevens Institute of Technology 
Hoboken, NJ 07030, USA 
[email protected] 
Zhihua Zhang 

School of Mathematical Sciences 
Peking University 
Beijing, 100871, China 
[email protected] 
noticebox[b]\[email protected]
1 Introduction
Federated Learning (FL), also known as federated optimization, allows multiple parties to collaboratively train a model without data sharing [9, 29, 20, 11, 26, 48]. Similar to the centralized parallel optimization [7, 14, 15, 28, 44, 22, 24, 25, 31, 46, 36], FL lets the user devices (aka worker nodes) perform most of the computation and a central parameter server update the model parameters using the descending directions returned by the user devices. Nevertheless, FL has three characters that distinguish it from the standard parallel optimization [16].
First, the training data are massively distributed over an incredibly large number of devices, and the connection between the central server and a device is slow. A direct consequence is the slow communication, which motivated communicationefficient FL algorithms [20, 30, 26, 27]. Federated averaging (FedAvg) is the first and perhaps the most widely used FL algorithm. It runs $E$ steps of SGD in parallel on a small sampled subset of devices and then averages the resulting model updates via a central server once in a while.^{1}^{1} 1 In the original paper [20], $E$ epochs of SGD are performed in parallel. For theoretical analyses, we denote by $E$ the times of updates rather than epochs. In comparison with SGD and its variants, FedAvg performs more local computation and less communication.
Second, unlike the traditional distributed learning systems, the FL system does not have control over users’ devices. For example, when a mobile phone is turned off or WiFi access is unavailable, the central server will lose connection to this device. When this happens during training, such a nonresponding/inactive device, which is called a straggler, appears tremendously slower than the other devices. Unfortunately, since it has no control over the devices, the system can do nothing, but waiting or ignoring the stragglers. Waiting for all the devices to response is obviously infeasible; it is thus impractical to require all the devices to be active.
Third, the training data are noniid^{2}^{2} 2 Throughout this paper, “noniid” means data are independent but not identically distributed. More precisely, the data distributions in the $k$th and $l$th devices, denoted ${D}_{k}$ and ${D}_{l}$, can be different.; that is, a device’s local data cannot be regarded as samples drawn from the overall distribution. The data available locally fail to represent the overall distribution. This not only brings challenges to algorithm design but also makes theoretical analysis much harder. While FedAvg actually works when the data are noniid [20], FedAvg on noniid data lacks theoretical guarantee even in the convex optimization setting.
There have been much efforts on developing convergence guarantees for FL algorithms based on the assumptions that (1) the data are iid and (2) all the devices are active. Khaled et al. [8], Yu et al. [40], Wang et al. [35] made the latter assumption, while Zhou and Cong [47], Stich [33], Wang and Joshi [34], Woodworth et al. [38] made both assumptions. These two assumptions obviously violate the second and third characters of FL.
Notation.
Let $N$ be the total number of user devices and $K$ ($\le N$) be the maximal number of the devices that participate in every round’s communication. Let $T$ be the total number of every device’s SGDs and $E$ be the number of local iterations performed in a device between two communications. Thus $\frac{T}{E}$ is the number of communications.
Contributions.
For strongly convex and smooth problems, we establish a convergence guarantee for FedAvg without making the two impractical assumptions: (1) the data are iid, and (2) all the devices are active. To the best of our knowledge, this work is the first to show the convergence rate of FedAvg without making the two assumptions.
We show in Theorems 1, 2, and 3 that FedAvg has $\mathcal{O}(\frac{1}{T})$ convergence rate. In particular, Theorem 3 shows that to attain a fixed precision $\u03f5$, the number of communications is
$$\frac{T}{E}=\mathcal{O}\left[\frac{1}{\u03f5}\left(\left(1+\frac{1}{K}\right)E{G}^{2}+\frac{{\sum}_{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}+\mathrm{\Gamma}+{G}^{2}}{E}\right)\right].$$  (1) 
Here, $G$, $\mathrm{\Gamma}$, ${p}_{k}$, and ${\sigma}_{k}$ are problemrelated constants defined in Section 3.1. The most interesting insight is that $E$ is a knob controlling the convergence rate: neither setting $E$ oversmall ($E=1$ makes FedAvg equivalent to SGD) nor setting $E$ overlarge is good for the convergence.
This work also makes algorithmic contributions. We summarize the existing sampling^{3}^{3} 3 Throughout this paper, “sampling” refers to how the server chooses $K$ user devices and uses their outputs for updating the model parameters. “Sampling” does not mean how a device randomly selects training samples. and averaging schemes (which do not have convergence bounds before this work) and propose a new scheme (see Table 1). We point out that a suitable sampling and averaging scheme is crucial for the convergence of FedAvg. To the best of our knowledge, we are the first to theoretically demonstrate that FedAvg with certain schemes (see Table 1) can achieve $\mathcal{O}(\frac{1}{T})$ convergence rate in noniid federated setting. We show that heterogeneity of training data and partial device participation slow down the convergence. We empirically verify our results through numerical experiments.
Our theoretical analysis requires the decay of learning rate (which is known to hinder the convergence rate.) Unfortunately, we show in Theorem 4 that the decay of learning rate is necessary for FedAvg’s convergence with $E>1$, even if full gradient descent is used.^{4}^{4} 4 It is well know that the full gradient descent (which is equivalent to FedAvg with $E=1$ and full batch) does not require the decay of the learning rate. If the learning rate is fixed to $\eta $ throughout, FedAvg would converge to a solution at least $\mathrm{\Omega}(\eta (E1))$ away from the optimal. To establish Theorem 4, we construct a specific ${\mathrm{\ell}}_{2}$norm regularized linear regression model which satisfies our strong convexity and smoothness assumptions.
Paper  Sampling  Averaging  Convergence rate 

McMahan et al. [20]  ${\mathcal{S}}_{t}\sim \mathcal{U}(N,K)$  ${\sum}_{k\notin {\mathcal{S}}_{t}}{p}_{k}{\mathbf{w}}_{t}+{\sum}_{k\in {\mathcal{S}}_{t}}{p}_{k}{\mathbf{w}}_{t}^{k}$   
Sahu et al. [26]  ${\mathcal{S}}_{t}\sim \mathcal{W}(N,K,\mathbf{p})$  $\frac{1}{K}{\sum}_{k\in {\mathcal{S}}_{t}}{\mathbf{w}}_{t}^{k}$  $\mathcal{O}(\frac{1}{T})$^{5}^{5} 5 The sampling scheme is proposed by Sahu et al. [26], but this convergence rate is obtained in our paper. 
Ours  ${\mathcal{S}}_{t}\sim \mathcal{U}(N,K)$  ${\sum}_{k\in {\mathcal{S}}_{t}}{p}_{k}\frac{N}{K}{\mathbf{w}}_{t}^{k}$  $\mathcal{O}(\frac{1}{T})$^{6}^{6} 6 The convergence relies on the assumption that data are balanced, i.e., ${n}_{1}={n}_{2}=\mathrm{\cdots}={n}_{N}$. However, we can use a rescaling trick to get rid of this assumption. We will discuss this point later in Section 3. 
Paper organization.
In Section 2, we elaborate on FedAvg. In Section 3, we present our main convergence bounds for FedAvg. In Section 4, we construct a special example to show the necessity of learning rate decay. In Section 5, we discuss and compare with prior work. In Section 6, we conduct empirical study to verify our theories. All the proofs are deferred to the appendix.
2 Federated Averaging (FedAvg)
Problem formulation.
In this work, we consider the following distributed optimization model:
$$\underset{\mathbf{w}}{\mathrm{min}}\left\{F(\mathbf{w})\triangleq \sum _{k=1}^{N}{p}_{k}{F}_{k}(\mathbf{w})\right\},$$  (2) 
where $N$ is the number of devices, and ${p}_{k}$ is the weight of the $k$th device such that ${p}_{k}\ge 0$ and ${\sum}_{k=1}^{N}{p}_{k}=1$. Suppose the $k$th device holds the ${n}_{k}$ training data: ${x}_{k,1},{x}_{k,2},\mathrm{\cdots},{x}_{k,{n}_{k}}$. The local objective ${F}_{k}(\cdot )$ is defined by
$${F}_{k}(\mathbf{w})\triangleq \frac{1}{{n}_{k}}\sum _{j=1}^{{n}_{k}}\mathrm{\ell}(\mathbf{w};{x}_{k,j}),$$  (3) 
where $\mathrm{\ell}(\cdot ;\cdot )$ is a userspecified loss function.
Algorithm description.
Here, we describe one round (say, the $t$th) of the standard FedAvg algorithm. First, the central server broadcasts the latest model, ${\mathbf{w}}_{t}$, to all the devices. Second, every device (say, the $k$th) lets ${\mathbf{w}}_{t}^{k}={\mathbf{w}}_{t}$ and then performs $E$ ($\ge 1$) local updates:
$${\mathbf{w}}_{t+i+1}^{k}\u27f5{\mathbf{w}}_{t+i}^{k}{\eta}_{t+i}\nabla {F}_{k}({\mathbf{w}}_{t+i}^{k},{\xi}_{t+i}^{k}),i=0,1,\mathrm{\cdots},E1,$$ 
where ${\eta}_{t+i}$ is the learning rate (a.k.a. the step size) and ${\xi}_{t+i}^{k}$ is a sample uniformly chosen from the local data. Last, the server aggregates the local models, ${\mathbf{w}}_{t+E}^{1},\mathrm{\cdots},{\mathbf{w}}_{t+E}^{N}$, to produce the new global model, ${\mathbf{w}}_{t+E}$. Because of the noniid and partial device participation issues, the aggregation step can vary.
IID versus noniid.
Suppose the data in the $k$th device are i.i.d. sampled from the distribution ${\mathcal{D}}_{k}$. Then the overall distribution is a mixture of all local data distributions: $\mathcal{D}={\sum}_{k=1}^{N}{p}_{k}{\mathcal{D}}_{k}$. The prior work [41, 47, 33, 34, 38] assumes that the data are iid generated by or partitioned among the $N$ devices, that is, ${\mathcal{D}}_{k}=\mathcal{D}$ for all $k\in [N]$. However, realworld applications do not typically satisfy the iid assumption. One of our theoretical contributions is avoiding the iid assumption.
Full device participation.
The prior work [3, 47, 33, 40, 34, 35] requires the full device participation in the aggregation step of FedAvg. In this case, the aggregation step performs
$${\mathbf{w}}_{t+E}\u27f5\sum _{k=1}^{N}{p}_{k}{\mathbf{w}}_{t+E}^{k}.$$ 
Unfortunately, the full device participation requirement suffers from serious “straggler’s effect” (which means everyone waits for the slowest) in realworld applications. For example, if there are thousands of users’ devices in the FL system, there are always a small portion of devices offline. Full device participation implies that the central server must wait for these “stragglers”, which is obviously unrealistic.
Partial device participation.
This strategy is much more realistic because it does not require all the devices’ output. We can set a threshold $K$ ($$) and let the central server collect the outputs of the first $K$ responded devices. After collecting $K$ outputs, the server stops waiting for the rest; the $(K+1)$th to $N$th devices are regarded stragglers in this iteration. Let ${\mathcal{S}}_{t}$ (${\mathcal{S}}_{t}=K$) be the set of the indices of the first $K$ responded devices in the $t$th iteration. The aggregation step performs
$${\mathbf{w}}_{t+E}\u27f5\frac{N}{K}\sum _{k\in {\mathcal{S}}_{t}}{p}_{k}{\mathbf{w}}_{t+E}^{k}.$$ 
It can be proved that $\frac{N}{K}{\sum}_{k\in {\mathcal{S}}_{t}}{p}_{k}$ equals one in expectation.
Communication cost.
The FedAvg requires tworound communications—one broadcast and one aggregation—per $E$ iterations. If $T$ iterations are performed totally, then the number of communications is $\lfloor \frac{2T}{E}\rfloor $. During the broadcast, the central server sends ${\mathbf{w}}_{t}$ to all the devices. During the aggregation, all or part of the $N$ devices send their outputs, say ${\mathbf{w}}_{t+E}^{k}$, to the server.
3 Convergence Analysis of FedAvg in Noniid Setting
In this section, we show that FedAvg converges to the global optimum at a rate of $\mathcal{O}(1/T)$ for strongly convex and smooth functions and noniid data. The main observation is that when the learning rate is sufficiently small, the effect of $E$ steps of local updates is similar to one step update with a larger learning rate. This coupled with appropriate sampling and averaging schemes would make each global update behave like an SGD update. Partial device participation ($$) only makes the averaged sequence $\{{\mathbf{w}}_{t}\}$ have a larger variance, which, however, can be controlled by learning rates. These imply that the convergence property of FedAvg should not differ too much from SGD. Next, we will first give the convergence result with full device participation (i.e., $K=N$) and then extend this result to partial device participation (i.e., $$).
3.1 Notation and Assumptions
We make the following assumptions on the functions ${F}_{1},\mathrm{\cdots},{F}_{N}$. Assumptions 1 and 2 are standard; typical examples are the ${\mathrm{\ell}}_{2}$norm regularized linear regression, logistic regression, and softmax classifier.
Assumption 1.
${F}_{1},\mathrm{\cdots},{F}_{N}$ are all $L$smooth, that is, for all $\mathrm{v}$ and $\mathrm{w}$, $f\mathit{}\mathrm{(}\mathrm{v}\mathrm{)}\mathrm{\le}\mathrm{f}\mathit{}\mathrm{(}\mathrm{w}\mathrm{)}\mathrm{+}{\mathrm{(}\mathrm{v}\mathrm{}\mathrm{w}\mathrm{)}}^{T}\mathit{}\mathrm{\nabla}\mathit{}f\mathit{}\mathrm{(}\mathrm{w}\mathrm{)}\mathrm{+}\frac{L}{\mathrm{2}}\mathit{}{\mathrm{\parallel}\mathrm{v}\mathrm{}\mathrm{w}\mathrm{\parallel}}_{\mathrm{2}}^{\mathrm{2}}$.
Assumption 2.
${F}_{1},\mathrm{\cdots},{F}_{N}$ are all $\mu $strongly convex, that is, for all $\mathrm{v}$ and $\mathrm{w}$, $f\mathit{}\mathrm{(}\mathrm{v}\mathrm{)}\mathrm{\ge}\mathrm{f}\mathit{}\mathrm{(}\mathrm{w}\mathrm{)}\mathrm{+}{\mathrm{(}\mathrm{v}\mathrm{}\mathrm{w}\mathrm{)}}^{T}\mathit{}\mathrm{\nabla}\mathit{}f\mathit{}\mathrm{(}\mathrm{w}\mathrm{)}\mathrm{+}\frac{\mu}{\mathrm{2}}\mathit{}{\mathrm{\parallel}\mathrm{v}\mathrm{}\mathrm{w}\mathrm{\parallel}}_{\mathrm{2}}^{\mathrm{2}}$.
Assumption 3.
Let ${\xi}_{t}^{k}$ be sampled from the $k$th device’s local data uniformly at random. The variance of stochastic gradients in each device is bounded: $\mathrm{E}\mathit{}{\mathrm{\parallel}\mathrm{\nabla}\mathit{}{F}_{k}\mathit{}\mathrm{(}{\mathrm{w}}_{t}^{k}\mathrm{,}{\xi}_{t}^{k}\mathrm{)}\mathrm{}\mathrm{\nabla}\mathit{}{F}_{k}\mathit{}\mathrm{(}{\mathrm{w}}_{t}^{k}\mathrm{)}\mathrm{\parallel}}^{\mathrm{2}}\mathrm{\le}{\sigma}_{k}^{\mathrm{2}}$ for $k\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\cdots}\mathrm{,}N$.
Assumption 4.
The expected squared norm of stochastic gradients is uniformly bounded, i.e., $\mathrm{E}\mathit{}{\mathrm{\parallel}\mathrm{\nabla}\mathit{}{F}_{k}\mathit{}\mathrm{(}{\mathrm{w}}_{t}^{k}\mathrm{,}{\xi}_{t}^{k}\mathrm{)}\mathrm{\parallel}}^{\mathrm{2}}\mathrm{\le}{G}^{\mathrm{2}}$ for all $k\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\cdots}\mathrm{,}N$ and $t\mathrm{=}\mathrm{0}\mathrm{,}\mathrm{\cdots}\mathrm{,}T\mathrm{}\mathrm{1}$.
Quantifying the degree of noniid (heterogeneity).
Let ${F}^{*}$ and ${F}_{k}^{*}$ be the minimum values of $F$ and ${F}_{k}$, respectively. We use the term $\mathrm{\Gamma}={F}^{*}{\sum}_{k=1}^{N}{p}_{k}{F}_{k}^{*}$ for quantifying the degree of noniid. If the data are iid, then $\mathrm{\Gamma}$ obviously goes to zero as the number of samples grows. If the data are noniid, then $\mathrm{\Gamma}$ is nonzero, and its magnitude reflects the heterogeneity of the data distribution.
3.2 Convergence Result: Full Device Participation
Here we analyze the case that all the devices participate in the aggregation step; see Section 2 for the algorithm description. Let the FedAvg algorithm terminate after $T$ iterations and return ${\mathbf{w}}_{T}$ as the solution. We always require $T$ is evenly divisible by $E$ so that FedAvg can output ${\mathbf{w}}_{T}$ as expected.
Theorem 1.
Let Assumptions 1 to 4 hold, and $L\mathrm{,}\mu \mathrm{,}{\sigma}_{k}\mathrm{,}G$ be defined therein. Choose $\kappa \mathrm{=}\frac{L}{\mu}$, $\gamma \mathrm{=}\mathrm{max}\mathit{}\mathrm{\{}\mathrm{8}\mathit{}\kappa \mathrm{,}E\mathrm{\}}$ and the learning rate ${\eta}_{t}\mathrm{=}\frac{\mathrm{2}}{\mu \mathit{}\mathrm{(}\gamma \mathrm{+}t\mathrm{)}}$. Then FedAvg with full device participation satisfies
$$\mathbb{E}\left[F({\mathbf{w}}_{T})\right]{F}^{*}\le \frac{2\kappa}{\gamma +T}\left(\frac{B}{\mu}+2L{\parallel {\mathbf{w}}_{0}{\mathbf{w}}^{*}\parallel}^{2}\right),$$  (4) 
where
$$B=\sum _{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}+6L\mathrm{\Gamma}+8{(E1)}^{2}{G}^{2}.$$  (5) 
3.3 Convergence Result: Partial Device Participation
As discussed in Section 2, partial device participation has more practical interest than full device participation. Let the set ${\mathcal{S}}_{t}$ ($\subset [N]$) index the active devices in the $t$th iteration. To establish the convergence bound, we need to make assumptions on ${\mathcal{S}}_{t}$.
Assumption 5 assumes the $K$ indices are selected from the distribution ${p}_{k}$ independently and with replacement. The aggregation step is simply averaging. This is first proposed in [26], but they did not provide theoretical analysis.
Assumption 5 (Scheme I).
Assume ${\mathrm{S}}_{t}$ contains a subset of $K$ indices randomly selected with replacement according to the sampling probabilities ${p}_{\mathrm{1}}\mathrm{,}\mathrm{\cdots}\mathrm{,}{p}_{N}$. The aggregation step of FedAvg performs ${\mathrm{w}}_{t}\mathrm{\u27f5}\frac{\mathrm{1}}{K}\mathit{}{\mathrm{\sum}}_{k\mathrm{\in}{\mathrm{S}}_{t}}{\mathrm{w}}_{t}^{k}$.
Theorem 2.
Let Assumptions 1 to 4 hold, and $L\mathrm{,}\mu \mathrm{,}{\sigma}_{k}\mathrm{,}G$ be defined therein. Let $\kappa \mathrm{,}\gamma $, ${\eta}_{t}$, and $B$ be defined in Theorem 1. Let Assumption 5 hold and define $C\mathrm{=}\frac{\mathrm{4}}{K}\mathit{}{E}^{\mathrm{2}}\mathit{}{G}^{\mathrm{2}}$. Then
$$\mathbb{E}\left[F({\mathbf{w}}_{T})\right]{F}^{*}\le \frac{2\kappa}{\gamma +T}\left(\frac{B+C}{\mu}+2L{\parallel {\mathbf{w}}_{0}{\mathbf{w}}^{*}\parallel}^{2}\right).$$  (6) 
Alternatively, we can select $K$ indices from $[N]$ uniformly at random without replacement. As a consequence, we need a different aggregation strategy. Assumption 6 assumes that the $K$ indices are selected uniformly without replacement and the aggregation step is the same as in Section 2. However, to guarantee convergence, we require an additional assumption of balanced data.
Assumption 6 (Scheme II).
Assume ${\mathrm{S}}_{t}$ contains a subset of $K$ indices uniformly sampled from $\mathrm{[}N\mathrm{]}$ without replacement. Assume the data is balanced in the sense that ${p}_{\mathrm{1}}\mathrm{=}\mathrm{\cdots}\mathrm{=}{p}_{N}\mathrm{=}\frac{\mathrm{1}}{N}$. The aggregation step of FedAvg performs ${\mathrm{w}}_{t}\mathrm{\u27f5}\frac{N}{K}\mathit{}{\mathrm{\sum}}_{k\mathrm{\in}{\mathrm{S}}_{t}}{p}_{k}\mathit{}{\mathrm{w}}_{t}^{k}$.
Theorem 3.
Scheme II requires ${p}_{1}=\mathrm{\cdots}={p}_{N}=\frac{1}{N}$ which obviously violates the unbalance nature of FL. Fortunately, this can be addressed by the following transformation. Let ${\stackrel{~}{F}}_{k}(\mathbf{w})={p}_{k}N{F}_{k}(\mathbf{w})$ be a scaled local objective ${F}_{k}$. Then the global objective becomes a simple average of all scaled local objectives:
$$F(\mathbf{w})=\sum _{k=1}^{N}{p}_{k}{F}_{k}(\mathbf{w})=\frac{1}{N}\sum _{k=1}^{N}{\stackrel{~}{F}}_{k}(\mathbf{w}).$$ 
Theorem 3 still holds if $L,\mu ,{\sigma}_{k}$, and $G$ are replaced by $\stackrel{~}{L}\triangleq \nu L$, $\stackrel{~}{\mu}\triangleq \varsigma \mu $, ${\stackrel{~}{\sigma}}_{k}=\sqrt{\nu}\sigma $, and $\stackrel{~}{G}=\sqrt{\nu}G$, respectively. Here, $\nu =N\cdot {\mathrm{max}}_{k}{p}_{k}$ and $\varsigma =N\cdot {\mathrm{min}}_{k}{p}_{k}$.
3.4 Discussions
Choice of $E$.
Since ${\parallel {\mathbf{w}}_{0}{\mathbf{w}}^{*}\parallel}^{2}\le \frac{4}{{\mu}^{2}}{G}^{2}$ for $\mu $strongly convex $F$, the dominating term in eqn. (6) is
$$\mathcal{O}\left(\frac{{\sum}_{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}+L\mathrm{\Gamma}+\left(1+\frac{1}{K}\right){E}^{2}{G}^{2}+\kappa {G}^{2}}{\mu T}\right).$$  (7) 
Let ${T}_{\u03f5}$ denote the number of required steps for FedAvg to achieve an $\u03f5$ accuracy. It follows from eqn. (7) that the number of required communication rounds is roughly
$$\frac{{T}_{\u03f5}}{E}\propto \left(1+\frac{1}{K}\right)E{G}^{2}+\frac{{\sum}_{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}+L\mathrm{\Gamma}+\kappa {G}^{2}}{E}.$$  (8) 
Thus, $\frac{{T}_{\u03f5}}{E}$ is a function of $E$ that first decreases and then increases, which implies that oversmall or overlarge $E$ may lead to high communication cost and that the optimal $E$ exists.
Stich [33] showed that if the data are iid, then $E$ can be set to $\mathcal{O}(\sqrt{T})$. However, this setting does not work if the data are noniid. Theorem 1 implies that $E$ must not exceed $\mathrm{\Omega}(\sqrt{T})$; otherwise, convergence is not guaranteed. Here we give an intuitive explanation. If $E$ is set big, then ${\mathbf{w}}_{t}^{k}$ can converge to the minimizer of ${F}_{k}$, and thus FedAvg becomes the oneshot average [42] of the local solutions. If the data are noniid, the oneshot averaging does not work because weighted average of the minimizers of ${F}_{1},\mathrm{\cdots},{F}_{N}$ can be very different from the minimizer of $F$.
Choice of $K$.
Stich [33] showed that if the data are iid, the convergence rate improves substantially as $K$ increases. However, under the noniid setting, the convergence rate has a weak dependence on $K$, as we show in Theorems 2 and 3. This implies that FedAvg is unable to achieve linear speedup. We will empirically see this phenomenon in Section 6. Thus, in practice, the participation ratio $\frac{K}{N}$ can be set small to alleviate the straggler’s effect without affecting the convergence rate.
Choice of sampling schemes.
We have considered two sampling and averaging schemes in Theorems 2 and 3. Scheme I selects $K$ devices according to the probabilities ${p}_{1},\mathrm{\cdots},{p}_{N}$ with replacement. The nonuniform sampling results in faster convergence than uniform sampling, especially when ${p}_{1},\mathrm{\cdots},{p}_{N}$ are highly nonuniform. If the system can choose to active any of the $N$ devices at any time, then Scheme I should be used.
However, oftentimes the system has no control over the sampling; instead, the server simply uses the first $K$ returned results for the update. In this case, we can assume the $K$ devices are uniformly sampled from all the $N$ devices and use Theorem 3 to guarantee the convergence. If ${p}_{1},\mathrm{\cdots},{p}_{N}$ are highly nonuniform, then $\nu =N\cdot {\mathrm{max}}_{k}{p}_{k}$ is big and $\varsigma =N\cdot {\mathrm{min}}_{k}{p}_{k}$ is small, which makes the convergence of FedAvg slow. This point of view is empirically verified in our experiments.
4 Necessity of Learning Rate Decay
In this section, we point out that diminishing learning rates is crucial for the convergence of FedAvg in the noniid setting. Specifically, we establish the following theorem by constructing a ridge regression model (which is strongly convex and smooth).
Theorem 4.
We artificially construct a strongly convex and smooth distributed optimization problem. With full batch size, $E\mathrm{>}\mathrm{1}$, and any fixed step size, FedAvg will converge to suboptimal points. Specifically, let ${\stackrel{\mathrm{~}}{\mathrm{w}}}^{\mathrm{*}}$ be the solution produced by FedAvg with a small enough and constant $\eta $, and ${\mathrm{w}}^{\mathrm{*}}$ be the optimal solution. Then we have
$${\parallel {\stackrel{~}{\mathbf{w}}}^{*}{\mathbf{w}}^{*}\parallel}_{2}=\mathrm{\Omega}((E1)\eta )\cdot {\parallel {\mathbf{w}}^{*}\parallel}_{2},$$ 
where we hide some problem dependent constants.
Theorem 4 and its proof provide several implications. First, the decay of learning rate is necessary for FedAvg’s convergence. On one hand, Theorem 1 shows that with $E>1$ and a decaying learning rate, FedAvg converges to the optimum. On the other hand, Theorem 4 shows that with $E>1$ and any fixed learning rate, FedAvg does not converge to the optimum.
Second, FedAvg behaves very differently from gradient descent. Note that FedAvg with $E=1$ and full batch size is exactly the Full Gradient Descent; with a proper and fixed learning rate, its global convergence to the optimum is guaranteed [23]. However, Theorem 4 shows that FedAvg with $E>1$ and full batch size cannot converge to the optimum. This conclusion does not contradict with Theorem 1 in [8], which, when tranformed into our case, asserts that ${\stackrel{~}{\mathbf{w}}}^{*}$ will locate in the neighborhood of ${\mathbf{w}}^{*}$ with a constant learning rate.
Third, Theorem 4 shows that the requirement of learning rate decay is not an artifact of our analysis; instead, it is inherently required by FedAvg. An explanation is that constant learning rates, combined with $E$ steps of possiblybiased local updates, form a suboptimal update scheme, but a diminishing learning rate can gradually eliminate such bias.
The efficiency of FedAvg principally results from the fact that it performs several update steps on a local model before communicating with other workers, which saves communication. Diminishing step sizes often hinders fast convergence, which may counteract the benefit of performing multiple local updates. Theorem 4 motivates more efficient alternatives to FedAvg.
5 Related Work
Federated learning (FL) was first proposed by McMahan et al. [20] for collaboratively learning a model without collecting users’ data. The research work on FL is focused on the communicationefficiency [10, 20, 26, 30] and data privacy [1, 2, 4, 5, 21]. Our work is focused on the communicationefficiency issue.
FedAvg, a synchronous distributed optimization algorithm, was proposed by [20] as an effective heuristic. Sattler et al. [27], Zhao et al. [45] studied the noniid setting. However, they do not give convergence rate. A contemporaneous and independent work of Xie et al. [39] analyzed asynchronous FedAvg, but they did not require iid data and their bound does not guarantee convergence to saddle point or local minimum. Sahu et al. [26] proposed a federated optimization framework called FedProx to deal with statistical heterogeneity and provided the convergence guarantees in the noniid setting. FedProx adds a proximal term to each local objective. When these proximal terms vanish, FedProx is reduced to FedAvg. However, their convergence theory requires the proximal terms always exist and hence fails to cover FedAvg.
When data are iid and all devices are active, FedAvg is referred to as LocalSGD. Thanks to the two assumptions, theoretical analysis of LocalSGD is easier than FedAvg. Stich [33] demonstrated that LocalSGD provably achieves the same linear speedup with strictly less communication for stronglyconvex stochastic optimization. Coppola [3], Zhou and Cong [47], Wang and Joshi [34] studied LocalSGD in the nonconvex setting and established convergence results. Yu et al. [40], Wang et al. [35] recently analyzed LocalSGD for nonconvex functions in heterogeneous settings. In particular, Yu et al. [40] demonstrated that LocalSGD also achieves $\mathcal{O}(1/\sqrt{NT})$ convergence (i.e., linear speedup) for nonconvex optimization. Lin et al. [18] empirically shows that variants of LocalSGD increase training efficiency and improve the generalization performance of large batch sizes while reducing communication. For LocalGD on noniid data (as opposed to LocalSGD), the best result is by the contemporaneous work (but slightly later than our first version) [8]. Khaled et al. [8] used fixed learning rate $\eta $ and showed $\mathcal{O}(\frac{1}{T})$ convergence to a point $\mathcal{O}({\eta}^{2}{E}^{2})$ away from the optimal. In fact, the suboptimality is due to their fixed learning rate. As we show in Theorem 4, using a fixed learning rate $\eta $ throughout, the solution by LocalGD is at least $\mathrm{\Omega}((E1)\eta )$ away from the optimal.
6 Numerical Experiments
Models and datasets
We examine our theoretical results on a logistic regression with weight decay $\lambda =1e4$. This is a stochastic convex optimization problem. We distribute MNIST dataset [12] among $N=100$ workers in a noniid fashion such that each device contains samples of only two digits. We further obtain two datasets: mnist balanced and mnist unbalanced. The former is highly unbalanced with the number of samples among devices following a power law, while the latter is balanced such that the number of samples in each device is the same. To manipulate heterogeneity more precisly, we synthesize unbalanced datasets following the setup in Sahu et al. [26] and denote it as synthetic($\mathrm{\alpha}\mathrm{,}\mathrm{\beta}$) where $\alpha $ controls how much local models differ from each other and $\beta $ controls how much the local data at each device differ from that of other devices. We obtain two datasets: synthetic(0,0) and synthetic(1,1). Details can be found in Appendix D.
Experiment settings
For all experiments, we initialize all runnings with ${\mathbf{w}}_{0}=0$. In each round, all selected devices run $E$ steps of SGD in parallel. We decay the learning rate at the end of each round by the following scheme ${\eta}_{t}=\frac{{\eta}_{0}}{1+t}$, where ${\eta}_{0}$ is chosen from the set $\{1,0.1,0.01\}$. We evaluate the averaged model after each global synchronization on the corresponding global objective. For fair comparison, we control all randomness in experiments so that the set of activated devices is the same across all different algorithms on one configuration.
Impact of $E$
We expect that ${T}_{\u03f5}/E$, the required communication round to achieve curtain accuracy, is a hyperbolic finction of $E$ as Eqn. (8) indicates. Intuitively, a small $E$ means a heavy communication burden, while a large $E$ means a low convergence rate. One needs to trade off between communication efficiency and fast convergence. We empirically observe this phenomenon on the unbalanced datasets in Figure (a)a. The reason why the phenomenon does not appear in mnist balanced dataset requires future investigations.
Impact of $K$
Our theory suggests that a larger $K$ may slightly accelerate convergence because ${T}_{\u03f5}/E$ contains a term $\mathcal{O}\left(\frac{E{G}^{2}}{K}\right)$. Figure (b)b shows that $K$ has limited influence on the convergence of FedAvg in synthetic(0,0) dataset. It reveals that the curve of an enough large $K$ is slightly better. We observe the similar phenomenon among the other three datasets and attach additional results in Appendix D. This justifies that when the variance resulting from sampling is not too large (i.e., $B\gg C$), one can use a small number of devices without severely harming the training process, which also removes the need to sample as many devices as possible in convex federated optimization.
Effect of sampling and averaging schemes.
We compare four schemes among four federated datasets. Since the original scheme involves a history term and may be conservative, we carefully set the initial learning rate for it. Figure (c)c indicates that when data are balanced, Schemes I and II achieve nearly the same performance, both better than the original scheme. Figure (d)d shows that when the data are unbalanced, i.e., ${p}_{k}$’s are uneven, Scheme I performs the best. Scheme II suffers from some instability in this case. This is not contradictory with our theory because we do not guarantee the convergence of Scheme II when data are unbalanced. As expected, transformed Scheme II performs stably at the price of a lower convergence rate. Compared with Scheme I, the original scheme converges at a slower speed even if its learning rate is fine tuned. All the results show the crucial position of appropriate sampling and averaging schemes for FedAvg.
7 Conclusion
Federated learning becomes increasingly popular in machine learning and optimization communities. In this paper we have studied the convergence of FedAvg, a heuristic algorithm suitable for federated setting. We have investigated the influence of sampling and averaging schemes. We have provided theoretical guarantees for two schemes and empirically demonstrated their performances. Our work sheds light on theoretical understanding of FedAvg and provides insights for algorithm design in realistic applications. Though our analyses are constrained in convex problems, we hope our insights and proof techniques can inspire future work.
References
 [1] (2018) How to backdoor federated learning. arXiv preprint arXiv:1807.00459. Cited by: §5.
 [2] (2017) Practical secure aggregation for privacypreserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Cited by: §5.
 [3] (2015) Iterative parameter mixing for distributed largemargin training of structured predictors for natural language processing. PhD thesis. Cited by: §2, §5.
 [4] (2017) Differentially private federated learning: a client level perspective. arXiv preprint arXiv:1712.07557. Cited by: §5.
 [5] (2017) Deep models under the GAN: information leakage from collaborative deep learning. In ACM SIGSAC Conference on Computer and Communications Security, Cited by: §5.
 [6] (2018) Gradient primaldual algorithm converges to secondorder stationary solution for nonconvex distributed optimization over networks. In International Conference on Machine Learning (ICML), Cited by: §5.
 [7] (2013) Distributed optimization: algorithms and convergence rates. PhD, Carnegie Mellon University, Pittsburgh PA, USA. Cited by: §1.
 [8] (2019) First analysis of local gd on heterogeneous data. arXiv preprint arXiv:1909.04715. Cited by: §1, §4, §5.
 [9] (2015) Federated optimization: distributed optimization beyond the datacenter. arXiv preprint arXiv:1511.03575. Cited by: §1.
 [10] (2016) Federated learning: strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. Cited by: §5.
 [11] (2017) Stochastic, distributed and federated optimization for machine learning. arXiv preprint arXiv:1707.01155. Cited by: §1.
 [12] (1998) Gradientbased learning applied to document recognition. Proceedings of the IEEE 86 (11), pp. 2278–2324. Cited by: §D.1, §6.
 [13] (2017) Communicationefficient sparse regression. The Journal of Machine Learning Research 18 (1), pp. 115–144. Cited by: §5.
 [14] (2014) Scaling distributed machine learning with the parameter server. In 11th $\{$USENIX$\}$ Symposium on Operating Systems Design and Implementation ($\{$OSDI$\}$ 14), pp. 583–598. Cited by: §1.
 [15] (2014) Communication efficient distributed machine learning with the parameter server. In Advances in Neural Information Processing Systems (NIPS), Cited by: §1.
 [16] (2019) Federated learning: challenges, methods, and future directions. arXiv preprint arXiv:1908.07873. Cited by: §1.
 [17] (2017) Distributed learning with regularized least squares. Journal of Machine Learning Research 18 (1), pp. 3202–3232. Cited by: §5.
 [18] (2018) Don’t use large minibatches, use local sgd. arXiv preprint arXiv:1808.07217. Cited by: §5.
 [19] (2018) An efficient distributed learning algorithm based on effective local functional approximations. Journal of Machine Learning Research 19 (1), pp. 2942–2978. Cited by: §5.
 [20] (2017) CommunicationEfficient Learning of Deep Networks from Decentralized Data. In International Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: §B.2, §D.2, Table 1, §1, §1, §1, §5, §5, footnote 1.
 [21] (2019) Exploiting unintended feature leakage in collaborative learning. In IEEE Symposium on Security & Privacy (S&P), Cited by: §5.
 [22] (2016) MLlib: machine learning in Apache Spark. Journal of Machine Learning Research 17 (34), pp. 1–7. Cited by: §1.
 [23] (2013) Introductory lectures on convex optimization: a basic course. Vol. 87, Springer Science & Business Media. Cited by: §4.
 [24] (2016) AIDE: fast and communication efficient distributed optimization. arXiv preprint arXiv:1608.06879. Cited by: §1, §5.
 [25] (2016) Distributed coordinate descent method for learning with big data. Journal of Machine Learning Research 17 (1), pp. 2657–2681. Cited by: §1.
 [26] (2018) Federated optimization for heterogeneous networks. arXiv preprint arXiv:1812.06127. Cited by: item I, §D.1, §D.2, §D.2, Table 1, §1, §1, §3.3, §5, §5, §6, footnote 5.
 [27] (2019) Robust and communicationefficient federated learning from noniid data. arXiv preprint arXiv:1903.02891. Cited by: §1, §5.
 [28] (2014) Communicationefficient distributed optimization using an approximate Newtontype method. In International conference on machine learning (ICML), Cited by: §1, §5.
 [29] (2015) Privacypreserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Cited by: §1.
 [30] (2017) Federated multitask learning. In Advances in Neural Information Processing Systems (NIPS), Cited by: §1, §5, §5.
 [31] (2016) CoCoA: a general framework for communicationefficient distributed optimization. arXiv preprint arXiv:1611.02189. Cited by: §1, §5.
 [32] (2018) Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NIPS), pp. 4447–4458. Cited by: §3.1.
 [33] (2018) Local SGD converges fast and communicates little. arXiv preprint arXiv:1805.09767. Cited by: §A.1, §1, §2, §2, §3.1, §3.4, §3.4, §5.
 [34] (2018) Cooperative SGD: a unified framework for the design and analysis of communicationefficient SGD algorithms. arXiv preprint arXiv:1808.07576. Cited by: §1, §2, §2, §5.
 [35] (2019) Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications. Cited by: §1, §2, §5.
 [36] (2018) GIANT: globally improved approximate newton method for distributed optimization. In Conference on Neural Information Processing Systems (NeurIPS), Cited by: §1, §5.
 [37] (2019) A sharper generalization bound for divideandconquer ridge regression. In The ThirtyThird AAAI Conference on Artificial Intelligence (AAAI), Cited by: §5.
 [38] (2018) Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2.
 [39] (2019) Asynchronous federated optimization. arXiv preprint arXiv:1903.03934. Cited by: §5.
 [40] (2019) Parallel restarted sgd with faster convergence and less communication: demystifying why model averaging works for deep learning. In AAAI Conference on Artificial Intelligence, Cited by: §1, §2, §3.1, §5.
 [41] (2015) Deep learning with elastic averaging SGD. In Advances in Neural Information Processing Systems (NIPS), Cited by: §2.
 [42] (2013) Communicationefficient algorithms for statistical optimization. Journal of Machine Learning Research 14, pp. 3321–3363. Cited by: §3.1, §3.4, §5.
 [43] (2015) Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates. Journal of Machine Learning Research 16, pp. 3299–3340. Cited by: §5.
 [44] (2015) DiSCO: distributed optimization for selfconcordant empirical loss. In International Conference on Machine Learning (ICML), Cited by: §1, §5.
 [45] (2018) Federated learning with noniid data. arXiv preprint arXiv:1806.00582. Cited by: §5.
 [46] (2016) A general distributed dual coordinate optimization framework for regularized loss minimization. arXiv preprint arXiv:1604.03763. Cited by: §1.
 [47] (2017) On the convergence properties of a kstep averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv:1708.01012. Cited by: §1, §2, §2, §5.
 [48] (2019) Federated reinforcement learning. arXiv preprint arXiv:1901.08277. Cited by: §1.
Appendix A Proof of Theorem 1
We analyze FedAvg in the setting of full device participation in this section.
A.1 Additional Notation
Let ${\mathbf{w}}_{t}^{k}$ be the model parameter maintained in the $k$th device at the $t$th step. Let ${\mathcal{I}}_{E}$ be the set of global synchronization steps, i.e., ${\mathcal{I}}_{E}=\{nEn=1,2,\mathrm{\cdots}\}$. If $t+1\in {\mathcal{I}}_{E}$, i.e., the time step to communication, FedAvg activates all devices. Then the update of FedAvg with partial devices active can be described as
${\mathbf{v}}_{t+1}^{k}={\mathbf{w}}_{t}^{k}{\eta}_{t}\nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k}),$  (9)  
${\mathbf{w}}_{t+1}^{k}=\{\begin{array}{cc}{\mathbf{v}}_{t+1}^{k}\hfill & \text{if}t+1\notin {\mathcal{I}}_{E},\hfill \\ {\displaystyle \sum _{k=1}^{N}}{p}_{k}{\mathbf{v}}_{t+1}^{k}\hfill & \text{if}t+1\in {\mathcal{I}}_{E}.\hfill \end{array}$  (10) 
Here, an additional variable ${\mathbf{v}}_{t+1}^{k}$ is introduced to represent the immediate result of one step SGD update from ${\mathbf{w}}_{t}^{k}$. We interpret ${\mathbf{w}}_{t+1}^{k}$ as the parameter obtained after communication steps (if possible).
In our analysis, we define two virtual sequences ${\overline{\mathbf{v}}}_{t}={\sum}_{k=1}^{N}{p}_{k}{\mathbf{v}}_{t}^{k}$ and ${\overline{\mathbf{w}}}_{t}={\sum}_{k=1}^{N}{p}_{k}{\mathbf{w}}_{t}^{k}$. This is motivated by [33]. ${\overline{\mathbf{v}}}_{t+1}$ results from an single step of SGD from ${\overline{\mathbf{w}}}_{t}$. When $t+1\notin {\mathcal{I}}_{E}$, both are inaccessible. When $t+1\in {\mathcal{I}}_{E}$, we can only fetch ${\overline{\mathbf{w}}}_{t+1}$. For convenience, we define ${\overline{\mathbf{g}}}_{t}={\sum}_{k=1}^{N}{p}_{k}\nabla {F}_{k}({\mathbf{w}}_{t}^{k})$ and ${\mathbf{g}}_{t}={\sum}_{k=1}^{N}{p}_{k}\nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k})$. Therefore, ${\overline{\mathbf{v}}}_{t+1}={\overline{\mathbf{w}}}_{t}{\eta}_{t}{\mathbf{g}}_{t}$ and $\mathbb{E}{\mathbf{g}}_{t}={\overline{\mathbf{g}}}_{t}$.
A.2 Key Lemmas
To convey our proof clearly, it would be necessary to prove certain useful lemmas. We defer the proof of these lemmas to latter section and focus on proving the main theorem.
Lemma 1 (Results of one step SGD).
Assume Assumption 1 and 2. If ${\eta}_{t}\mathrm{\le}\frac{\mathrm{1}}{\mathrm{4}\mathit{}L}$, we have
$$\mathbb{E}{\parallel {\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{\star}\parallel}^{2}\le (1{\eta}_{t}\mu )\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+{\eta}_{t}^{2}\mathbb{E}{\parallel {\mathbf{g}}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}+6L{\eta}_{t}^{2}\mathrm{\Gamma}+2\mathbb{E}\sum _{k=1}^{N}{p}_{k}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{k}^{t}\parallel}^{2}$$ 
where $\mathrm{\Gamma}\mathrm{=}{F}^{\mathrm{*}}\mathrm{}{\mathrm{\sum}}_{k\mathrm{=}\mathrm{1}}^{N}{p}_{k}\mathit{}{F}_{k}^{\mathrm{\star}}\mathrm{\ge}\mathrm{0}$.
Lemma 2 (Bounding the variance).
Assume Assumption 3 holds. It follows that
$$\mathbb{E}{\parallel {\mathbf{g}}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}\le \sum _{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}.$$ 
Lemma 3 (Bounding the divergence of $\{{\mathbf{w}}_{t}^{k}\}$).
Assume Assumption 4, that ${\eta}_{t}$ is nonincreasing and ${\eta}_{t}\mathrm{\le}\mathrm{2}\mathit{}{\eta}_{t\mathrm{+}E}$ for all $t\mathrm{\ge}\mathrm{0}$. It follows that
$$\mathbb{E}\left[\sum _{k=1}^{N}{p}_{k}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{k}^{t}\parallel}^{2}\right]\le \mathrm{\hspace{0.25em}4}{\eta}_{t}^{2}{(E1)}^{2}{G}^{2}.$$ 
A.3 Completing the Proof of Theorem 1
Proof.
It is clear that no matter whether $t+1\in {\mathcal{I}}_{E}$ or $t+1\notin {\mathcal{I}}_{E}$, we always have ${\overline{\mathbf{w}}}_{t+1}={\overline{\mathbf{v}}}_{t+1}$. Let ${\mathrm{\Delta}}_{t}=\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\mathbf{w}}^{\star}\parallel}^{2}$. From Lemma 1, Lemma 2 and Lemma 3, it follows that
$${\mathrm{\Delta}}_{t+1}\le (1{\eta}_{t}\mu ){\mathrm{\Delta}}_{t}+{\eta}_{t}^{2}B$$  (11) 
where
$$B=\sum _{k=1}^{N}{p}_{k}^{2}{\sigma}_{k}^{2}+6L\mathrm{\Gamma}+8{(E1)}^{2}{G}^{2}.$$ 
For a diminishing stepsize, ${\eta}_{t}=\frac{\beta}{t+\gamma}$ for some $\beta >\frac{1}{\mu}$ and $\gamma >0$ such that ${\eta}_{1}\le \mathrm{min}\{\frac{1}{\mu},\frac{1}{4L}\}=\frac{1}{4L}$ and ${\eta}_{t}\le 2{\eta}_{t+E}$. We will prove ${\mathrm{\Delta}}_{t}\le \frac{v}{\gamma +t}$ where $v=\mathrm{max}\{\frac{{\beta}^{2}B}{\beta \mu 1},(\gamma +1){\mathrm{\Delta}}_{1}\}$.
We prove it by induction. Firstly, the definition of $v$ ensures that it holds for $t=1$. Assume the conclusion holds for some $t$, it follows that
${\mathrm{\Delta}}_{t+1}$  $\le (1{\eta}_{t}\mu ){\mathrm{\Delta}}_{t}+{\eta}_{t}^{2}B$  
$=\left(1{\displaystyle \frac{\beta \mu}{t+\gamma}}\right){\displaystyle \frac{v}{t+\gamma}}+{\displaystyle \frac{{\beta}^{2}B}{{(t+\gamma )}^{2}}}$  
$={\displaystyle \frac{t+\gamma 1}{{(t+\gamma )}^{2}}}v+\left[{\displaystyle \frac{{\beta}^{2}B}{{(t+\gamma )}^{2}}}{\displaystyle \frac{\beta \mu 1}{{(t+\gamma )}^{2}}}v\right]$  
$\le {\displaystyle \frac{v}{t+\gamma +1}}.$ 
Then by the strong convexity of $F(\cdot )$,
$$\mathbb{E}[F({\overline{\mathbf{w}}}_{t})]{F}^{*}\le \frac{L}{2}{\mathrm{\Delta}}_{t}\le \frac{L}{2}\frac{v}{\gamma +t}.$$ 
Specifically, if we choose $\beta =\frac{2}{\mu},\gamma =\mathrm{max}\{8\frac{L}{\mu}1,E\}$ and denote $\kappa =\frac{L}{\mu}$, then ${\eta}_{t}=\frac{2}{\mu}\frac{1}{\gamma +t}$ and
$$\mathbb{E}[F({\overline{\mathbf{w}}}_{t})]{F}^{*}\le \frac{2\kappa}{\gamma +t}\left(\frac{B}{\mu}+2L{\mathrm{\Delta}}_{1}\right).$$ 
∎
A.4 Deferred proofs of key lemmas
Proof of Lemma 1..
Notice that ${\overline{\mathbf{v}}}_{t+1}={\overline{\mathbf{w}}}_{t}{\eta}_{t}{\bm{g}}_{t}$, then
${\parallel {\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{\star}\parallel}^{2}$  $={\parallel {\overline{\mathbf{w}}}_{t}{\eta}_{t}{\mathbf{g}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t}+{\eta}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}$  
$=\underset{{A}_{1}}{\underset{\u23df}{{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}}}+\underset{{A}_{2}}{\underset{\u23df}{2{\eta}_{t}\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t},{\overline{\mathbf{g}}}_{t}{\mathbf{g}}_{t}\u27e9}}+{\eta}_{t}^{2}{\parallel {\mathbf{g}}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}$  (12) 
Note that $\mathbb{E}{A}_{2}=0$. We next focus on bounding ${A}_{1}$. Again we split ${A}_{1}$ into three terms:
$${\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}={\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}\underset{{B}_{1}}{\underset{\u23df}{2{\eta}_{t}\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star},{\overline{\mathbf{g}}}_{t}\u27e9}}+\underset{{B}_{2}}{\underset{\u23df}{{\eta}_{t}^{2}{\parallel {\overline{\mathbf{g}}}_{t}\parallel}^{2}}}$$  (13) 
From the the $L$smoothness of ${F}_{k}(\cdot )$, it follows that
$${\parallel \nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\parallel}^{2}\le 2L\left({F}_{k}\left({\mathbf{w}}_{t}^{k}\right){F}_{k}^{\star}\right).$$  (14) 
By the convexity of $\parallel \cdot {\parallel}^{2}$ and eqn. (14), we have
$${B}_{2}={\eta}_{t}^{2}{\parallel {\overline{\mathbf{g}}}_{t}\parallel}^{2}\le {\eta}_{t}^{2}\sum _{k=1}^{N}{p}_{k}{\parallel \nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\parallel}^{2}\le 2L{\eta}_{t}^{2}\sum _{k=1}^{N}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}_{k}^{*}\right).$$ 
Note that
${B}_{1}$  $=2{\eta}_{t}\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star},{\overline{\mathbf{g}}}_{t}\u27e9=2{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star},\nabla {F}_{k}({\mathbf{w}}_{t}^{k})\u27e9$  
$=2{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{t}^{k},\nabla {F}_{k}({\mathbf{w}}_{t}^{k})\u27e92{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\u27e8{\mathbf{w}}_{t}^{k}{\mathbf{w}}^{\star},\nabla {F}_{k}({\mathbf{w}}_{t}^{k})\u27e9.$  (15) 
By CauchySchwarz inequality and AMGM inequality, we have
$$2\u27e8{\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{t}^{k},\nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\u27e9\le \frac{1}{{\eta}_{t}}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{t}^{k}\parallel}^{2}+{\eta}_{t}{\parallel \nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\parallel}^{2}.$$  (16) 
By the $\mu $strong convexity of ${F}_{k}(\cdot )$, we have
$$\u27e8{\mathbf{w}}_{t}^{k}{\mathbf{w}}^{\star},\nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\u27e9\le \left({F}_{k}\left({\mathbf{w}}_{t}^{k}\right){F}_{k}({\mathbf{w}}^{*})\right)\frac{\mu}{2}{\parallel {\mathbf{w}}_{t}^{k}{\mathbf{w}}^{\star}\parallel}^{2}.$$  (17) 
By combining eqn. (13), eqn. (A.4), eqn. (16) and eqn. (17), it follows that
${A}_{1}={\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}$  $\le {\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+2L{\eta}_{t}^{2}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}_{k}^{*}\right)$  
$\mathrm{\hspace{1em}}+{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({\displaystyle \frac{1}{{\eta}_{t}}}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{k}^{t}\parallel}^{2}+{\eta}_{t}{\parallel \nabla {F}_{k}\left({\mathbf{w}}_{t}^{k}\right)\parallel}^{2}\right)$  
$\mathrm{\hspace{1em}}2{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}\left({\mathbf{w}}_{t}^{k}\right){F}_{k}({\mathbf{w}}^{*})+{\displaystyle \frac{\mu}{2}}{\parallel {\mathbf{w}}_{t}^{k}{\mathbf{w}}^{\star}\parallel}^{2}\right)$  
$\le (1\mu {\eta}_{t}){\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{k}^{t}\parallel}^{2}$  
$\mathrm{\hspace{1em}}+\underset{C}{\underset{\u23df}{4L{\eta}_{t}^{2}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}_{k}^{*}\right)2{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}\left({\mathbf{w}}_{t}^{k}\right){F}_{k}({\mathbf{w}}^{*})\right)}}$ 
where we use eqn. (14) again.
We next aim to bound $C$. We define ${\gamma}_{t}=2{\eta}_{t}(12L{\eta}_{t})$. Since ${\eta}_{t}\le \frac{1}{4L}$, ${\eta}_{t}\le {\gamma}_{t}\le 2{\eta}_{t}$. Then we split $C$ into two terms:
$C$  $=2{\eta}_{t}(12L{\eta}_{t}){\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}_{k}^{*}\right)+2{\eta}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}^{*}){F}_{k}^{*}\right)$  
$={\gamma}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}^{*}\right)+(2{\eta}_{t}{\gamma}_{t}){\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}^{*}{F}_{k}^{*}\right)$  
$=\underset{D}{\underset{\u23df}{{\gamma}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}^{*}\right)}}+4L{\eta}_{t}^{2}\mathrm{\Gamma}$ 
where in the last equation, we use the notation $\mathrm{\Gamma}={\sum}_{k=1}^{N}{p}_{k}\left({F}^{*}{F}_{k}^{*}\right)={F}^{*}{\sum}_{k=1}^{N}{p}_{k}{F}_{k}^{*}$.
To bound $D$, we have
$\sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}^{*}\right)$  $={\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\mathbf{w}}_{t}^{k}){F}_{k}({\overline{\mathbf{w}}}_{t})\right)+{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\overline{\mathbf{w}}}_{t}){F}^{*}\right)$  
$\ge {\displaystyle \sum _{k=1}^{N}}{p}_{k}\u27e8\nabla {F}_{k}({\overline{\mathbf{w}}}_{t}),{\overline{\mathbf{w}}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\u27e9+\left(F({\overline{\mathbf{w}}}_{t}){F}^{*}\right)$  
$\ge {\displaystyle \frac{1}{2}}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left[{\eta}_{t}{\parallel \nabla {F}_{k}({\overline{\mathbf{w}}}_{t})\parallel}^{2}+{\displaystyle \frac{1}{{\eta}_{t}}}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\parallel}^{2}\right]+\left(F({\overline{\mathbf{w}}}_{t}){F}^{*}\right)$  
$\ge {\displaystyle \sum _{k=1}^{N}}{p}_{k}\left[{\eta}_{t}L\left({F}_{k}({\overline{\mathbf{w}}}_{t}){F}_{k}^{*}\right)+{\displaystyle \frac{1}{2{\eta}_{t}}}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\parallel}^{2}\right]+\left(F({\overline{\mathbf{w}}}_{t}){F}^{*}\right)$ 
where the first inequality results from the convexity of ${F}_{k}(\cdot )$, the second inequality from AMGM inequality and the third inequality from eqn. (14).
Therefore
$C$  $={\gamma}_{t}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\left[{\eta}_{t}L\left({F}_{k}({\overline{\mathbf{w}}}_{t}){F}_{k}^{*}\right)+{\displaystyle \frac{1}{2{\eta}_{t}}}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\parallel}^{2}\right]{\gamma}_{t}\left(F({\overline{\mathbf{w}}}_{t}){F}^{*}\right)+4L{\eta}_{t}^{2}\mathrm{\Gamma}$  
$={\gamma}_{t}({\eta}_{t}L1){\displaystyle \sum _{k=1}^{N}}{p}_{k}\left({F}_{k}({\overline{\mathbf{w}}}_{t}){F}^{*}\right)+\left(4L{\eta}_{t}^{2}+{\gamma}_{t}{\eta}_{t}L\right)\mathrm{\Gamma}+{\displaystyle \frac{{\gamma}_{t}}{2{\eta}_{t}}}{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\parallel}^{2}$  
$\le 6L{\eta}_{t}^{2}\mathrm{\Gamma}+{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{t}\parallel}^{2}$ 
where in the last inequality, we use the following facts: (1) ${\eta}_{t}L1\le \frac{3}{4}\le 0$ and ${\sum}_{k=1}^{N}{p}_{k}\left({F}_{k}({\overline{\mathbf{w}}}_{t}){F}^{*}\right)=F({\overline{\mathbf{w}}}_{t}){F}^{*}\ge 0$ (2) $\mathrm{\Gamma}\ge 0$ and $4L{\eta}_{t}^{2}+{\gamma}_{t}{\eta}_{t}L\le 6{\eta}_{t}^{2}L$ and (3) $\frac{{\gamma}_{t}}{2{\eta}_{t}}\le 1$.
Recalling the expression of ${A}_{1}$ and plugging $C$ into it, we have
${A}_{1}$  $={\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}{\eta}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}$  
$\le (1\mu {\eta}_{t}){\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+2{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{k}^{t}\parallel}^{2}+6{\eta}_{t}^{2}L\mathrm{\Gamma}$  (18) 
Using eqn. (A.4) and taking expectation on both sides of eqn. (A.4), we erase the randomness from stochastic gradients, we complete the proof. ∎
Proof of Lemma 2.
From Assumption 3, the variance of the stochastic gradients in device $k$ is bounded by ${\sigma}_{k}^{2}$, then
$\mathbb{E}{\parallel {\mathbf{g}}_{t}{\overline{\mathbf{g}}}_{t}\parallel}^{2}$  $=\mathbb{E}{\parallel {\displaystyle \sum _{k=1}^{N}}{p}_{k}(\nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k})\nabla {F}_{k}({\mathbf{w}}_{t}^{k}))\parallel}^{2},$  
$={\displaystyle \sum _{k=1}^{N}}{p}_{k}^{2}\mathbb{E}{\parallel \nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k})\nabla {F}_{k}({\mathbf{w}}_{t}^{k})\parallel}^{2},$  
$\le {\displaystyle \sum _{k=1}^{N}}{p}_{k}^{2}{\sigma}_{k}^{2}.$ 
∎
Proof of Lemma 3.
Since FedAvg requires a communication each $E$ steps. Therefore, for any $t\ge 0$, there exists a ${t}_{0}\le t$, such that $t{t}_{0}\le E1$ and ${\mathbf{w}}_{{t}_{0}}^{k}={\overline{\mathbf{w}}}_{{t}_{0}}$ for all $k=1,2,\mathrm{\cdots},N$. Also, we use the fact that ${\eta}_{t}$ is nonincreasing and ${\eta}_{{t}_{0}}\le 2{\eta}_{t}$ for all $t{t}_{0}\le E1$, then
$\mathbb{E}{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}_{t}^{k}\parallel}^{2}$  $=\mathbb{E}{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel ({\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{{t}_{0}})({\overline{\mathbf{w}}}_{t}{\overline{\mathbf{w}}}_{{t}_{0}})\parallel}^{2}$  
$\le \mathbb{E}{\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\mathbf{w}}_{t}^{k}{\overline{\mathbf{w}}}_{{t}_{0}}\parallel}^{2}$  
$\le {\displaystyle \sum _{k=1}^{N}}{p}_{k}\mathbb{E}{\displaystyle \sum _{t={t}_{0}}^{t1}}(E1){\eta}_{t}^{2}{\parallel \nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k})\parallel}^{2}$  
$\le {\displaystyle \sum _{k=1}^{N}}{p}_{k}{\displaystyle \sum _{t={t}_{0}}^{t1}}(E1){\eta}_{{t}_{0}}^{2}{G}^{2}$  
$\le {\displaystyle \sum _{k=1}^{N}}{p}_{k}{\eta}_{{t}_{0}}^{2}{(E1)}^{2}{G}^{2}$  
$\le 4{\eta}_{t}^{2}{(E1)}^{2}{G}^{2}.$ 
∎
Appendix B Proofs of Theorems 2 and 3
We analyze FedAvg in the setting of partial device participation in this section.
B.1 Additional Notation
Recall that ${\mathbf{w}}_{t}^{k}$ is the model parameter maintained in the $k$th device at the $t$th step. ${\mathcal{I}}_{E}=\{nEn=1,2,\mathrm{\cdots}\}$ is the set of global synchronization steps. Unlike the setting in Appendix A, when it is the time to communicate, i.e., $t+1\in {\mathcal{I}}_{E}$, the scenario considered here is that FedAvg randomly activates a subset of devices according to some sampling schemes. Again, ${\overline{\mathbf{g}}}_{t}={\sum}_{k=1}^{N}{p}_{k}\nabla {F}_{k}({\mathbf{w}}_{t}^{k})$ and ${\mathbf{g}}_{t}={\sum}_{k=1}^{N}{p}_{k}{F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k})$. Therefore, ${\overline{\mathbf{v}}}_{t+1}={\overline{\mathbf{w}}}_{t}{\eta}_{t}{\mathbf{g}}_{t}$ and $\mathbb{E}{\mathbf{g}}_{t}={\overline{\mathbf{g}}}_{t}$.
Multiset selected.
All sampling schemes can be divided into two groups, one with replacement and the other without replacement. For those with replacement, it is possible for a device to be activated several times in a round of communication, even though each activation is independent with the rest. We denote by ${\mathscr{H}}_{t}$ the multiset selected which allows any element to appear more than once. Note that ${\mathscr{H}}_{t}$ is only well defined for $t\in {\mathcal{I}}_{E}$. For convenience, we denote by ${\mathcal{S}}_{t}={\mathscr{H}}_{N(t,E)}$ the most recent set of chosen devices where $N(t,E)=\mathrm{max}\{nn\le t,n\in {\mathcal{I}}_{E}\}$.
Updating scheme.
Limited to realistic scenarios (for communication efficiency and low straggler effect), FedAvg first samples a random multiset ${\mathcal{S}}_{t}$ of devices and then only perform updates on them. This make the analysis a little bit intricate, since ${\mathcal{S}}_{t}$ varies each $E$ steps. However, we can use a thought trick to circumvent this difficulty. We assume that FedAvg always activates all devices at the beginning of each round and then uses the parameters maintained in only a few sampled devices to produce the nextround parameter. It is clear that this updating scheme is equivalent to the original. Then the update of FedAvg with partial devices active can be described as: for all $k\in [N]$,
${\mathbf{v}}_{t+1}^{k}={\mathbf{w}}_{t}^{k}{\eta}_{t}\nabla {F}_{k}({\mathbf{w}}_{t}^{k},{\xi}_{t}^{k}),$  (19)  
${\mathbf{w}}_{t+1}^{k}=\{\begin{array}{cc}{\mathbf{v}}_{t+1}^{k}\hfill & \text{if}t+1\notin {\mathcal{I}}_{E},\hfill \\ \text{samples}{\mathcal{S}}_{t+1}\text{and average}{\{{\mathbf{v}}_{t+1}^{k}\}}_{k\in {\mathcal{S}}_{t+1}}\hfill & \text{if}t+1\in {\mathcal{I}}_{E}.\hfill \end{array}$  (20) 
Sources of randomness.
In our analysis, there are two sources of randomness. One results from the stochastic gradients and the other is from the random sampling of devices. All the analysis in Appendix A only involve the former. To distinguish them, we use the notation ${\mathbb{E}}_{{\mathcal{S}}_{t}}(\cdot )$, when we take expectation to erase the latter type of randomness.
B.2 Key Lemmas
Two schemes.
For full device participation, we always have ${\overline{\mathbf{w}}}_{t+1}={\overline{\mathbf{v}}}_{t+1}$. This is true when $t+1\notin {\mathcal{I}}_{E}$ for partial device participation. When $t+1\in {\mathcal{I}}_{E}$, we hope this relation establish in the sense of expectation. To that end, we require the sampling and averaging scheme to be unbiased in the sense that
$${\mathbb{E}}_{{\mathcal{S}}_{t+1}}{\overline{\mathbf{w}}}_{t+1}={\overline{\mathbf{v}}}_{t+1}.$$ 
We find two sampling and averaging schemes satisfying the requirement and provide convergence guarantees.

(I)
The server establishes ${\mathcal{S}}_{t+1}$ by i.i.d. with replacement sampling an index $k\in \{1,\mathrm{\cdots},N\}$ with probabilities ${p}_{1},\mathrm{\cdots},{p}_{N}$ for $K$ times. Hence ${\mathcal{S}}_{t+1}$ is a multiset which allows a element to occur more than once. Then the server averages the parameters by ${\mathbf{w}}_{t+1}^{k}=\frac{1}{K}{\sum}_{k\in {\mathcal{S}}_{t+1}}{\mathbf{v}}_{t+1}^{k}$. This is first proposed in [26] but lacks theoretical analysis.

(II)
The server samples ${\mathcal{S}}_{t+1}$ uniformly in a without replacement fashion. Hence each element in ${\mathcal{S}}_{t+1}$ only occurs once.Then server averages the parameters by ${\mathbf{w}}_{t+1}^{k}={\sum}_{k\in {\mathcal{S}}_{t+1}}{p}_{k}\frac{N}{K}{\mathbf{v}}_{t+1}^{k}$. Note that when the ${p}_{k}$’s are not all the same, one cannot ensure ${\sum}_{k\in {\mathcal{S}}_{t+1}}{p}_{k}\frac{N}{K}=1$.
Unbiasedness and bounded variance.
Lemma 4 shows the mentioned two sampling and averaging schemes are unbiased. In expectation, the nextround parameter (i.e., ${\overline{\mathbf{w}}}_{t+1}$) is equal to the weighted average of parameters in all devices after SGD updates (i.e., ${\overline{\mathbf{v}}}_{t+1}$). However, the original scheme in [20] (see Table 1) does not enjoy this property. But it is very similar to Scheme II except the averaging scheme. Hence our analysis cannot cover the original scheme.
Lemma 5 shows the expected difference between ${\overline{\mathbf{v}}}_{t+1}$ and ${\overline{\mathbf{w}}}_{t+1}$ is bounded. ${\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{t+1}\parallel}^{2}$ is actually the variance of ${\overline{\mathbf{w}}}_{t+1}$.
Lemma 4 (Unbiased sampling scheme).
If $t\mathrm{+}\mathrm{1}\mathrm{\in}{\mathrm{I}}_{E}$, for Scheme I and Scheme II, we have
$${\mathbb{E}}_{{\mathcal{S}}_{t}}({\overline{\mathbf{w}}}_{t+1})={\overline{\mathbf{v}}}_{t+1}.$$ 
Lemma 5 (Bounding the variance of ${\overline{\mathbf{w}}}_{t}$).
For $t\mathrm{+}\mathrm{1}\mathrm{\in}\mathrm{I}$, assume that ${\eta}_{t}$ is nonincreasing and ${\eta}_{t}\mathrm{\le}\mathrm{2}\mathit{}{\eta}_{t\mathrm{+}E}$ for all $t\mathrm{\ge}\mathrm{0}$. We have the following results.

(1)
For Scheme I, the expected difference between ${\overline{\mathbf{v}}}_{t+1}$ and ${\overline{\mathbf{w}}}_{t+1}$ is bounded by
$${\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{t+1}\parallel}^{2}\le \frac{4}{K}{\eta}_{t}^{2}{E}^{2}{G}^{2}.$$ 
(2)
For Scheme II, assuming ${p}_{1}={p}_{2}=\mathrm{\cdots}={p}_{N}=\frac{1}{N}$, the expected difference between ${\overline{\mathbf{v}}}_{t+1}$ and ${\overline{\mathbf{w}}}_{t+1}$ is bounded by
$${\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{t+1}\parallel}^{2}\le \frac{NK}{N1}\frac{4}{K}{\eta}_{t}^{2}{E}^{2}{G}^{2}.$$
B.3 Completing the Proof of Theorem 2 and 3
Proof.
Note that
${\parallel {\overline{\mathbf{w}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}$  $={\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}+{\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}$  
$=\underset{{A}_{1}}{\underset{\u23df}{{\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}}}+\underset{{A}_{2}}{\underset{\u23df}{{\parallel {\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}}}+\underset{{A}_{3}}{\underset{\u23df}{2\u27e8{\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1},{\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{*}\u27e9}}.$ 
When expectation is taken over ${\mathcal{S}}_{t+1}$, the last term (${A}_{3}$) vanishes due to the unbiasedness of ${\overline{\mathbf{w}}}_{t+1}$.
If $t+1\notin {\mathcal{I}}_{E}$, ${A}_{1}$ vanishes since ${\overline{\mathbf{w}}}_{t+1}={\overline{\mathbf{v}}}_{t+1}$. We use eqn. (11) to bound ${A}_{2}$. Then it follows that
$$\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}\le (1{\eta}_{t}\mu )\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+{\eta}_{t}^{2}B.$$ 
If $t+1\in {\mathcal{I}}_{E}$, we additionally use Lemma 5 to bound ${A}_{1}$. Then
$\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}$  $=\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}+\mathbb{E}{\parallel {\overline{\mathbf{v}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}$  
$\le (1{\eta}_{t}\mu )\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t}{\mathbf{w}}^{\star}\parallel}^{2}+{\eta}_{t}^{2}(B+C),$  (21) 
where $C$ is the upper bound of $\frac{1}{{\eta}_{t}^{2}}{\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{t+1}\parallel}^{2}$ ($C$ is defined in Theorem 2 and 3).
The only difference between eqn. (B.3) and eqn. (11) is the additional $C$. Thus we can use the same argument there to prove the theorems here. Specifically, for a diminishing stepsize, ${\eta}_{t}=\frac{\beta}{t+\gamma}$ for some $\beta >\frac{1}{\mu}$ and $\gamma >0$ such that ${\eta}_{1}\le \mathrm{min}\{\frac{1}{\mu},\frac{1}{4L}\}=\frac{1}{4L}$ and ${\eta}_{t}\le 2{\eta}_{t+E}$, we can prove $\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\mathbf{w}}^{*}\parallel}^{2}\le \frac{v}{\gamma +t}$ where $v=\mathrm{max}\{\frac{{\beta}^{2}(B+C)}{\beta \mu 1},(\gamma +1){\parallel {\mathbf{w}}_{1}{\mathbf{w}}^{*}\parallel}^{2}\}$.
Then by the strong convexity of $F(\cdot )$,
$$\mathbb{E}[F({\overline{\mathbf{w}}}_{t})]{F}^{*}\le \frac{L}{2}{\mathrm{\Delta}}_{t}\le \frac{L}{2}\frac{v}{\gamma +t}.$$ 
Specifically, if we choose $\beta =\frac{2}{\mu},\gamma =\mathrm{max}\{8\frac{L}{\mu}1,E\}$ and denote $\kappa =\frac{L}{\mu}$, then ${\eta}_{t}=\frac{2}{\mu}\frac{1}{\gamma +t}$ and
$$\mathbb{E}[F({\overline{\mathbf{w}}}_{t})]{F}^{*}\le \frac{2\kappa}{\gamma +t}\left(\frac{B+C}{\mu}+2L{\parallel {\mathbf{w}}_{1}{\mathbf{w}}^{*}\parallel}^{2}\right).$$ 
∎
B.4 Deferred proofs of key lemmas
Proof of Lemma 4.
We first give a key observation which is useful to prove the followings. Let ${\{{x}_{i}\}}_{i=1}^{N}$ denote any fixed deterministic sequence. We sample a multiset ${\mathcal{S}}_{t}$ (with size $K$) by the procedure where for each sampling time, we sample ${x}_{k}$ with probability ${q}_{k}$ for each time. Pay attention that two samples are not necessarily independent. We only require each sampling distribution is identically. Let ${\mathcal{S}}_{t}=\{{i}_{1},\mathrm{\cdots},{i}_{K}\}\subset [N]$ (some ${i}_{k}$’s may have the same value). Then
$${\mathbb{E}}_{{\mathcal{S}}_{t}}\sum _{k\in {\mathcal{S}}_{t}}{x}_{k}={\mathbb{E}}_{{\mathcal{S}}_{t}}\sum _{k=1}^{K}{x}_{{i}_{k}}=K{\mathbb{E}}_{{\mathcal{S}}_{t}}{x}_{{i}_{1}}=K\sum _{k=1}^{N}{q}_{k}{x}_{k}.$$ 
For Scheme I, ${q}_{k}={p}_{k}$ and for Scheme II, ${q}_{k}=\frac{1}{N}$. It is easy to prove this lemma when equipped with this observation. ∎
Proof of Lemma 5.
We separately prove the bounded variance for two schemes. Let ${\mathcal{S}}_{t+1}=\{{i}_{1},\mathrm{\cdots},{i}_{K}\}$ denote the multiset of chosen indexes.
(1) For Scheme I, ${\overline{\mathbf{w}}}_{t+1}=\frac{1}{K}{\sum}_{l=1}^{K}{\mathbf{v}}_{t+1}^{{i}_{l}}$. Taking expectation over ${\mathcal{S}}_{t+1}$, we have
$${\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}={\mathbb{E}}_{{\mathcal{S}}_{t}}\frac{1}{{K}^{2}}\sum _{l=1}^{K}{\parallel {\mathbf{v}}_{t+1}^{{i}_{l}}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}=\frac{1}{K}\sum _{k=1}^{N}{p}_{k}{\parallel {\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}$$  (22) 
where the first equality follows from ${\mathbf{v}}_{t+1}^{{i}_{l}}$ are independent and unbiased.
To bound eqn. (22), we use the same argument in Lemma 5. Since $t+1\in {\mathcal{I}}_{E}$, we know that the time ${t}_{0}=tE+1\in {\mathcal{I}}_{E}$ is the communication time, which implies ${\{{\mathbf{w}}_{{t}_{0}}^{k}\}}_{k=1}^{N}$ is identical. Then
$\sum _{k=1}^{N}}{p}_{k}{\parallel {\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2$  $={\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel ({\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{w}}}_{{t}_{0}})({\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{{t}_{0}})\parallel}^{2}$  
$\le {\displaystyle \sum _{k=1}^{N}}{p}_{k}{\parallel {\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{w}}}_{{t}_{0}}\parallel}^{2}$ 
where the last inequality results from ${\sum}_{k=1}^{N}{p}_{k}({\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{w}}}_{{t}_{0}})={\overline{\mathbf{v}}}_{t+1}{\overline{\mathbf{w}}}_{{t}_{0}}$ and $\mathbb{E}{\parallel \bm{x}\mathbb{E}\bm{x}\parallel}^{2}\le \mathbb{E}{\parallel \bm{x}\parallel}^{2}$. Similarly, we have
${\mathbb{E}}_{{\mathcal{S}}_{t}}{\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}$  $\le {\displaystyle \frac{1}{K}}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\mathbb{E}{\parallel {\mathbf{v}}_{t+1}^{k}{\overline{\mathbf{w}}}_{{t}_{0}}\parallel}^{2}$  
$\le {\displaystyle \frac{1}{K}}{\displaystyle \sum _{k=1}^{N}}{p}_{k}\mathbb{E}{\parallel {\mathbf{v}}_{t+1}^{k}{\mathbf{w}}_{{t}_{0}}^{k}\parallel}^{2}$  
$\le {\displaystyle \frac{1}{K}}{\displaystyle \sum _{k=1}^{N}}{p}_{k}E{\displaystyle \sum _{i={t}_{0}}^{t}}\mathbb{E}{\parallel {\eta}_{i}\nabla {F}_{k}({\mathbf{w}}_{i}^{k},{\xi}_{i}^{k})\parallel}^{2}$  
$\le {\displaystyle \frac{1}{K}}{E}^{2}{\eta}_{{t}_{0}}^{2}{G}^{2}\le {\displaystyle \frac{4}{K}}{\eta}_{t}^{2}{E}^{2}{G}^{2}$ 
where in the last inequality we use the fact that ${\eta}_{t}$ is nonincreasing and ${\eta}_{{t}_{0}}\le 2{\eta}_{t}$.
(2) For Scheme II, when assuming ${p}_{1}={p}_{2}=\mathrm{\cdots}={p}_{N}=\frac{1}{N}$, we again have ${\overline{\mathbf{w}}}_{t+1}=\frac{1}{K}{\sum}_{l=1}^{K}{\mathbf{v}}_{t+1}^{{i}_{l}}$.
${\mathbb{E}}_{{\mathcal{S}}_{t}}$  $\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}{\parallel}^{2}={\mathbb{E}}_{{\mathcal{S}}_{t}}\parallel {\displaystyle \frac{1}{K}}{\displaystyle \sum _{i\in {S}_{t+1}}}{\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}{\parallel}^{2}={\displaystyle \frac{1}{{K}^{2}}}{\mathbb{E}}_{{\mathcal{S}}_{t}}\parallel {\displaystyle \sum _{i=1}^{N}}\mathbb{I}\{i\in {S}_{t}\}({\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}){\parallel}^{2}$  
$={\displaystyle \frac{1}{{K}^{2}}}[{\displaystyle \sum _{i\in [N]}}\mathbb{P}(i\in {S}_{t+1})\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}{\parallel}^{2}+{\displaystyle \sum _{i\ne j}}\mathbb{P}(i,j\in {S}_{t+1})\u27e8{\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1},{\mathbf{v}}_{t+1}^{j}{\overline{\mathbf{v}}}_{t+1}\u27e9]$  
$={\displaystyle \frac{1}{KN}}{\displaystyle \sum _{i=1}^{N}}{\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}+{\displaystyle \sum _{i\ne j}}{\displaystyle \frac{K1}{KN(N1)}}\u27e8{\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1},{\mathbf{v}}_{t+1}^{j}{\overline{\mathbf{v}}}_{t+1}\u27e9$  
$={\displaystyle \frac{1}{K(N1)}}\left(1{\displaystyle \frac{K}{N}}\right){\displaystyle \sum _{i=1}^{N}}{\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}$ 
where we use the following equalities: (1) $\mathbb{P}(i\in {S}_{t+1})=\frac{K}{N}$ and $\mathbb{P}(i,j\in {S}_{t+1})=\frac{K(K1)}{N(N1)}$ for all $i\ne j$ and (2) ${\sum}_{i\in [N]}{\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}+{\sum}_{i\ne j}\u27e8{\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1},{\mathbf{v}}_{t+1}^{j}{\overline{\mathbf{v}}}_{t+1}\u27e9=0$.
Therefore,
$\mathbb{E}{\parallel {\overline{\mathbf{w}}}_{t+1}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}$  $={\displaystyle \frac{N}{K(N1)}}\left(1{\displaystyle \frac{K}{N}}\right)\mathbb{E}\left[{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{v}}}_{t+1}\parallel}^{2}\right]$  
$\le {\displaystyle \frac{N}{K(N1)}}\left(1{\displaystyle \frac{K}{N}}\right)\mathbb{E}\left[{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{\parallel {\mathbf{v}}_{t+1}^{i}{\overline{\mathbf{w}}}_{{t}_{0}}\parallel}^{2}\right]$  
$\le {\displaystyle \frac{N}{K(N1)}}\left(1{\displaystyle \frac{K}{N}}\right)4{\eta}_{t}^{2}{E}^{2}{G}^{2}.$ 
where in the last inequality we use the same argument in (1). ∎
Appendix C The empirical risk minimization example in Section 4
C.1 Detail of the example
Let $p>1$ be a positive integer. To avoid the trivial case, we assume $N>1$. Consider the following quadratic optimization
$$\underset{\mathbf{w}}{\mathrm{min}}F(\mathbf{w})\triangleq \frac{1}{2N}\left[{\mathbf{w}}^{\top}\mathrm{\mathbf{A}\mathbf{w}}2{\mathbf{b}}^{\top}\mathbf{w}\right]+\frac{\mu}{2}{\parallel \mathbf{w}\parallel}_{2}^{2},$$  (23) 
where $\mathbf{A}\in {\mathbb{R}}^{(Np+1)\times (Np+1)}$ , $\mathbf{w},\mathbf{b}\in {\mathbb{R}}^{Np+1}$ and $\mu >0$. Specifically, let $\mathbf{b}={\mathbf{e}}_{1}\triangleq {(1,0,\mathrm{\cdots},0)}^{\top}$, and $\mathbf{A}$ be a symmetric and tridiagonal matrix defined by
$${\left(\mathbf{A}\right)}_{i,j}=\{\begin{array}{cc}2,\hfill & i=j\in [1,Np+1],\hfill \\ 1,\hfill & ji=1\text{and}i,j\in [1,Np+1],\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}$$  (24) 
where $i,j$ are row and column indices, respectively. We partition $\mathbf{A}$ into a sum of $N$ symmetric matrices ($\mathbf{A}={\sum}_{k=1}^{N}{\mathbf{A}}_{k}$) and $\mathbf{b}$ into $\mathbf{b}={\sum}_{k=1}^{N}{\mathbf{b}}_{k}$. Specifically, we choose ${\mathbf{b}}_{1}=\mathbf{b}={\mathbf{e}}_{1}$ and ${\mathbf{b}}_{2}=\mathrm{\cdots}={\mathbf{b}}_{N}=0$. To give the formulation of ${\mathbf{A}}_{k}$’s, we first introduce a series of sparse and symmetric matrices ${\mathbf{B}}_{k}(1\le k\le N)$:
$$  (25) 
Now ${\mathbf{A}}_{k}$’s are given by ${\mathbf{A}}_{1}={\mathbf{B}}_{1}+{\mathbf{E}}_{1,1},{\mathbf{A}}_{k}={\mathbf{B}}_{k}(2\le k\le N1)$ and ${\mathbf{A}}_{N}={\mathbf{B}}_{N}+{\mathbf{E}}_{Np+1,Np+1}$, where ${\mathbf{E}}_{i,j}$ is the matrix where only the $(i,j)$th entry is one and the rest are zero.
Back to the federated setting, we distribute the $k$th partition $({\mathbf{A}}_{k},{\mathbf{b}}_{k})$ to the $k$th device and construct its corresponding local objective by
$${F}_{k}(\mathbf{w})\triangleq \frac{1}{2}\left[{\mathbf{w}}^{\top}{\mathbf{A}}_{k}\mathbf{w}2{\mathbf{b}}_{k}^{\top}\mathbf{w}+\mu {\parallel \mathbf{w}\parallel}_{2}^{2}\right].$$  (26) 
In the next subsection (Appendix C.3), we show that the quadratic minimization with the global objective (23) and the local objectives (26) is actually a distributed linear regression. In this example, training data are not identically but balanced distributed. Moreover, data in each device are sparse in the sense that nonzero features only occur in one block. The following theorem (Theorem 5) shows that FedAvg might converge to suboptimal points even if the learning rate is small enough. We provide a numerical illustration in Appendix C.2 and a mathematical proof in Appendix C.4.
Theorem 5.
In the above problem of the distributed linear regression, assume that each device computes exact gradients (which are not stochastic). With a constant and small enough learning rate $\eta $ and $E\mathrm{>}\mathrm{1}$, FedAvg converges to a suboptimal solution, whereas FedAvg with $E\mathrm{=}\mathrm{1}$ (i.e., gradient descent) converges to the optimum. Specifically, in a quantitative way, we have
$$\parallel {\stackrel{~}{\mathbf{w}}}^{*}{\mathbf{w}}^{*}\parallel \ge \frac{(E1)\eta}{16}\parallel {\mathbf{A}}_{1}{\mathbf{A}}_{2}{\mathbf{w}}^{*}\parallel $$ 
where ${\stackrel{\mathrm{~}}{\mathrm{w}}}^{\mathrm{*}}$ is the solution produced by FedAvg and ${\mathrm{w}}^{\mathrm{*}}$ is the optimal solution.
C.2 Numerical illustration on the example
We conduct a few numerical experiments to illustrate the poor performance of FedAvg on the example introduced in Section 4. Here we set $N=5,p=4,\mu =2\times {10}^{4}$. The annealing scheme of learning rates is given by ${\eta}_{t}=\frac{1/5}{5+t\cdot a}$ where $a$ is the best parameter chosen from the set $\{{10}^{2},{10}^{4},{10}^{6}\}$.
C.3 Some properties of the example
Recall that the symmetric matrix $\mathbf{A}\in {\mathbb{R}}^{(Np+1)\times (Np+1)}$ is defined in eqn. (24). Observe that $\mathbf{A}$ is invertible and for all vector $\mathbf{w}\in {\mathbb{R}}^{Np+1}$,
$${\mathbf{w}}^{\top}\mathrm{\mathbf{A}\mathbf{w}}=2\sum _{i=1}^{Np+1}{\mathbf{w}}_{i}^{2}2\sum _{i=1}^{Np}{\mathbf{w}}_{i}{\mathbf{w}}_{i+1}={\mathbf{w}}_{1}^{2}+{\mathbf{w}}_{Np+1}^{2}+\sum _{i=1}^{Np}{({\mathbf{w}}_{i}{\mathbf{w}}_{i+1})}^{2}\le 4{\parallel \mathbf{w}\parallel}_{2}^{2}.$$  (27) 
which implies that $0\prec \mathbf{A}\u2aaf4\mathbf{I}$.
The sparse and symmetric matrices ${\mathbf{B}}_{k}(1\le k\le N)$ defined in eqn. (25) can be rewritten as
$$\left({\mathbf{B}}_{k}\right)=\left(\begin{array}{ccc}\hfill {\mathrm{\U0001d7ce}}_{(k1)p\times (k1)p}\hfill & & \\ & \hfill {\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & & & \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 1\hfill & & \\ & \hfill 1\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\ddots}\hfill & \\ & & \hfill \mathrm{\ddots}\hfill & \hfill 2\hfill & \hfill 1\hfill \\ & & & \hfill 1\hfill & \hfill 1\hfill \end{array}\right)}_{(p+1)\times (p+1)}\hfill & \\ & & \hfill {\mathrm{\U0001d7ce}}_{(Nk)p\times (Nk)p}\hfill \end{array}\right).$$ 
From theory of linear algebra, it is easy to follow this proposition.
Proposition 1.
By the way of construction, ${\mathrm{A}}_{k}$’s have following properties:

1.
${\mathbf{A}}_{k}$ is positive semidefinite with ${\parallel {\mathbf{A}}_{k}\parallel}_{2}\le 4$;

2.
$\mathrm{rank}({\mathbf{A}}_{2})=\mathrm{\cdots}=\mathrm{rank}({\mathbf{A}}_{N1})=p$ and $\mathrm{rank}({\mathbf{A}}_{1})=\mathrm{rank}({\mathbf{A}}_{N})=p+1$;

3.
For each $k$, there exist a matrix ${\mathbf{X}}_{k}\in {\mathbb{R}}^{{r}_{k}\times (Np+1)}$ such that ${\mathbf{A}}_{k}={\mathbf{X}}_{k}^{\top}{\mathbf{X}}_{k}$ where ${r}_{k}=\mathrm{rank}({\mathbf{A}}_{k})$. Given any $k$, each row of ${\mathbf{X}}_{k}$ has nonzero entries only on a block of coordinates, namely ${\mathcal{I}}_{k}=\{(k1)p+1,(k1)p+2,\mathrm{\cdots},kp+1\}$. As a result, $\mathbf{A}={\sum}_{k=1}^{N}{\mathbf{A}}_{k}={\mathbf{X}}^{\top}\mathbf{X}$, where $\mathbf{X}={({\mathbf{X}}_{1}^{\top},\mathrm{\cdots},{\mathbf{X}}_{N}^{\top})}^{\top}\in {\mathbb{R}}^{(Np+2)\times (Np+1)}$.

4.
${\mathbf{w}}^{*}={\mathbf{A}}^{1}\mathbf{b}$ is the global minimizer of problem eqn. (23), given by ${({\mathbf{w}}^{*})}_{i}=1\frac{i}{Np+2}(1\le i\le Np+1)$. Let $\stackrel{~}{\mathbf{w}}\triangleq {(\underset{p+1}{\underset{\u23df}{1,\mathrm{\cdots},1}},\underset{(N1)p}{\underset{\u23df}{0,\mathrm{\cdots},0}})}^{\top}\in {\mathbb{R}}^{Np+1}$, then ${\mathbf{A}}_{1}\stackrel{~}{\mathbf{w}}={\mathbf{X}}_{1}^{\top}{\mathbf{X}}_{1}\stackrel{~}{\mathbf{w}}={\mathbf{b}}_{1}$.
From Proposition 1, we can rewrite these local quadratic objectives in form of a ridge linear regression. Specifically, for $k=1$,
${F}_{1}(\mathbf{w})$  $={\displaystyle \frac{1}{2}}\left[{\mathbf{w}}^{\top}{\mathbf{A}}_{1}\mathbf{w}2{\mathbf{b}}_{1}^{\top}\mathbf{w}+\mu {\parallel \mathbf{w}\parallel}^{2}\right],$  
$={\displaystyle \frac{1}{2}}\left[{\mathbf{w}}^{\top}{\mathbf{X}}_{1}^{\top}{\mathbf{X}}_{1}\mathbf{w}2{\stackrel{~}{\mathbf{w}}}^{\top}{\mathbf{X}}_{1}^{\top}{\mathbf{X}}_{1}\mathbf{w}+\mu {\parallel \mathbf{w}\parallel}^{2}\right],$  
$={\displaystyle \frac{1}{2}}{\parallel {\mathbf{X}}_{1}\left(\mathbf{w}\stackrel{~}{\mathbf{w}}\right)\parallel}_{2}^{2}+{\displaystyle \frac{1}{2}}\mu {\parallel \mathbf{w}\parallel}^{2}+C,$ 
where $C$ is some constant irrelevant with $\mathbf{w}$). For $2\le k\le N$,
${F}_{k}(\mathbf{w})$  $={\displaystyle \frac{1}{2}}\left[{\mathbf{w}}^{\top}{\mathbf{A}}_{k}\mathbf{w}2{\mathbf{b}}_{k}^{\top}\mathbf{w}+\mu {\parallel \mathbf{w}\parallel}^{2}\right],$  
$={\displaystyle \frac{1}{2}}{\parallel {\mathbf{X}}_{k}\mathbf{w}\parallel}_{2}^{2}+{\displaystyle \frac{1}{2}}\mu {\parallel \mathbf{w}\parallel}^{2}.$ 
Similarly, the global quadratic objective eqn. (23) can be written as $F(\mathbf{w})=\frac{1}{2N}{\parallel \mathbf{X}(\mathbf{w}{\mathbf{w}}^{*})\parallel}_{2}^{2}+\frac{1}{2}\mu {\parallel \mathbf{w}\parallel}^{2}$ .
Data in each device are sparse in the sense that nonzero features only occur in the block ${\mathcal{I}}_{k}$ of coordinates. Blocks on neighboring devices only overlap one coordinate, i.e., ${\mathcal{I}}_{k}\cap {\mathcal{I}}_{k+1}=1$. These observations imply that the training data in this example is not identically distributed.
The $k$th device has ${r}_{k}\phantom{\rule{veryverythickmathspace}{0ex}}(=p\text{or}p+1)$ nonzero feature vectors which are vertically concatenated into the feature matrix ${\mathbf{X}}_{k}$. Without loss of generality, we can assume all devices hold $p+1$ data points since we can always add additional zero vectors to expand the local dataset. Therefore ${n}_{1}=\mathrm{\cdots}={n}_{N}=p+1$ in this case, which implies that the training data in this example is balanced distributed.
C.4 Proof of Theorem 5.
Proof of Theorem 5..
To prove the theorem, we assume that (i) all devices hold the same amount of data points, (ii) all devices perform local updates in parallel, (iii) all workers use the same learning rate $\eta $ and (iv) all gradients computed by each device make use of its full local dataset (hence this case is a deterministic optimization problem). We first provide the result when $\mu =0$.
For convenience, we slightly abuse the notation such that ${\mathbf{w}}_{t}$ is the global parameter at round $t$ rather than step $t$. Let ${\mathbf{w}}_{t}^{(k)}$ the updated local parameter at $k$th worker at round $t$. Once the first worker that holds data $({\mathbf{A}}_{1},{\mathbf{b}}_{1})$ runs $E$ step of SGD on ${F}_{1}(\mathbf{w})$ from ${\mathbf{w}}_{t}$, it follows that
$${\mathbf{w}}_{t}^{(1)}={(\mathbf{I}\eta {\mathbf{A}}_{1})}^{E}{\mathbf{w}}_{t}+\eta \sum _{l=0}^{E1}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}{\mathbf{b}}_{1}.$$ 
For the rest of workers, we have ${\mathbf{w}}_{t}^{(k)}={(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}{\mathbf{w}}_{t}(2\le k\le N)$.
Therefore, from the algorithm,
$${\mathbf{w}}_{t+1}=\frac{1}{N}\sum _{k=1}^{N}{\mathbf{w}}_{t+1}^{(k)}=\left(\frac{1}{N}\sum _{i=1}^{N}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right){\mathbf{w}}_{t}+\frac{\eta}{N}\sum _{l=0}^{E1}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}{\mathbf{b}}_{1}.$$ 
Define $\rho \triangleq {\parallel \frac{1}{N}{\sum}_{i=1}^{N}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\parallel}_{2}$. Next we show that when $$, we have $$. From Proposition 1, ${\parallel {\mathbf{A}}_{k}\parallel}_{2}\le 4$ and ${\mathbf{A}}_{k}\u2ab00$ for $\forall k\in [N]$. This means ${\parallel \mathbf{I}\eta {\mathbf{A}}_{k}\parallel}_{2}\le 1$ for all $k\in [N]$. Then for any $\mathbf{x}\in {\mathbb{R}}^{Np+1}$ and ${\parallel x\parallel}_{2}=1$, we have ${\mathbf{x}}^{\top}{(\mathbf{I}\eta {\mathbf{A}}_{k})}^{E}\mathbf{x}\le 1$ and it is monotonically decreasing when $E$ is increasing. Then
${\mathbf{x}}^{\top}\left({\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)\mathbf{x}$  $\le {\mathbf{x}}^{\top}\left({\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}(\mathbf{I}\eta {\mathbf{A}}_{i})\right)\mathbf{x}$  
$$ 
since $0\prec \mathbf{A}\u2aaf4\mathbf{I}$ means $0\u2aaf(\mathbf{I}\frac{\eta}{N}\mathbf{A})\prec \mathbf{I}$.
Then ${\parallel {\mathbf{w}}_{t+1}{\mathbf{w}}_{t}\parallel}_{2}\le \rho {\parallel {\mathbf{w}}_{t}{\mathbf{w}}_{t1}\parallel}_{2}\le {\rho}^{t}{\parallel {\mathbf{w}}_{1}{\mathbf{w}}_{0}\parallel}_{2}$. By the triangle inequality,
$${\parallel {\mathbf{w}}_{t+n}{\mathbf{w}}_{t}\parallel}_{2}\le \sum _{i=0}^{n1}{\parallel {\mathbf{w}}_{t+i+1}{\mathbf{w}}_{t+i}\parallel}_{2}\le \sum _{i=0}^{n1}{\rho}^{t+i}{\parallel {\mathbf{w}}_{1}{\mathbf{w}}_{0}\parallel}_{2}\le {\rho}^{t}\frac{{\parallel {\mathbf{w}}_{1}{\mathbf{w}}_{0}\parallel}_{2}}{1\rho}$$ 
which implies that ${\{{\mathbf{w}}_{t}\}}_{t\ge 1}$ is a Cauchy sequence and thus has a limit denoted by ${\stackrel{~}{\mathbf{w}}}^{*}$. We have
$${\stackrel{~}{\mathbf{w}}}^{*}={\left(\mathbf{I}\frac{1}{N}\sum _{i=1}^{N}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)}^{1}\left[\frac{\eta}{N}\sum _{l=0}^{E1}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}\mathbf{b}\right].$$  (28) 
Now we can discuss the impact of $E$.

(1)
When $E=1$, it follows from eqn. (28) that ${\stackrel{~}{\mathbf{w}}}^{*}={\mathbf{A}}^{1}\mathbf{b}={\mathbf{w}}^{*}$, i.e., FedAvg converges to the global minimizer.

(2)
When $E=\mathrm{\infty}$, $\underset{E\to \mathrm{\infty}}{lim}\eta {\sum}_{l=0}^{E1}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}\mathbf{b}={\mathbf{A}}_{1}^{+}{\mathbf{b}}_{1}=\stackrel{~}{\mathbf{w}}$ and $\underset{E\to \mathrm{\infty}}{lim}\frac{1}{N}{\sum}_{i=1}^{N}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}=\mathrm{diag}\{(1\frac{1}{N}){\mathbf{I}}_{p};(1\frac{1}{N})\mathbf{I}\frac{1}{N}\mathbf{M};(1\frac{1}{N}){\mathbf{I}}_{p}\}$ where $\mathbf{M}\in {\mathbb{R}}^{(N2)p+1\times (N2)p+1}$ is some a symmetric matrix. Actually $\mathbf{M}$ is almost a diagonal matrix in the sense that there are totally $N2$ completely the same matrices (i.e., $\frac{1}{p+1}{\mathrm{\mathbf{e}\mathbf{e}}}^{T}\in {\mathbb{R}}^{(p+1)\times (p+1)}$) placed on the diagonal of $\mathbf{M}$ but each overlapping only the lower right corner element with the top left corner element of the next block. Therefore ${\stackrel{~}{\mathbf{w}}}^{*}={(\underset{p}{\underset{\u23df}{1,\mathrm{\cdots},1}},\underset{(N2)p+1}{\underset{\u23df}{{\mathbf{V}}_{11},\mathrm{\cdots},{\mathbf{V}}_{(N2)p+1,1}}},\underset{p}{\underset{\u23df}{0,\mathrm{\cdots},0}})}^{T}$ where $\mathbf{V}={(\mathbf{I}\mathbf{M})}^{1}$. From (4) of Proposition 1, ${\stackrel{~}{\mathbf{w}}}^{*}$ is different from ${\mathbf{w}}^{*}$

(3)
When $$, note that
${\stackrel{~}{\mathbf{w}}}^{*}{\mathbf{w}}^{*}$ $=$ ${\left(\mathbf{I}{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)}^{1}\left[{\displaystyle \frac{\eta}{N}}{\displaystyle \sum _{l=0}^{E1}}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}\mathbf{A}\left(\mathbf{I}{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)\right]{\mathbf{w}}^{*}.$ (29) The right hand side of the last equation cannot be zero. Quantificationally speaking, we have the following lemma. We defer the proof for the next subsection.
Lemma 6.
If the step size $\eta $ is sufficiently small, then in this example, we have
$$\parallel {\stackrel{~}{\mathbf{w}}}^{*}{\mathbf{w}}^{*}\parallel \ge \frac{(E1)\eta}{16}\parallel {\mathbf{A}}_{1}{\mathbf{A}}_{2}{\mathbf{w}}^{*}\parallel .$$ (30) Since ${\mathbf{A}}_{1}{\mathbf{A}}_{2}\ne \mathrm{\U0001d7ce}$ and ${\mathbf{w}}^{*}$ is dense, the lower bound in eqn. (30) is not vacuous.
Now we have proved the result when $\mu =0$. For the case where $\mu >0$, we replace ${\mathbf{A}}_{i}$ with ${\mathbf{A}}_{i}+\mu \mathbf{I}$ and assume $$ instead of the original. The discussion on different choice of $E$ is unaffected. ∎
C.5 Proof of Lemma 6
Proof.
We will derive the conclusion mainly from the expression eqn. (29). Let $f(\eta )$ be a function of $\eta $. We say a matrix $\mathbf{T}$ is $\mathrm{\Theta}(f(\eta ))$ if and only if there exist some positive constants namely ${C}_{1}$ and ${C}_{2}$ such that ${C}_{1}f(\eta )\le \parallel \mathbf{T}\parallel \le {C}_{2}f(\eta )$ for all $\eta >0$. In the following analysis, we all consider the regime where $\eta $ is sufficiently small.
Denote by $\mathbf{V}={\sum}_{i=1}^{N}{\mathbf{A}}_{i}^{2}$. First we have
$\mathbf{I}{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}$  $=\mathbf{I}{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}(\mathbf{I}E\eta {\mathbf{A}}_{i}+{\displaystyle \frac{E(E1)}{2}}{\eta}^{2}{\mathbf{A}}_{i}^{2}+\mathrm{\Theta}({\eta}^{3}))$  
$={\displaystyle \frac{E\eta}{N}}\mathbf{A}{\displaystyle \frac{E(E1)}{2N}}{\eta}^{2}\mathbf{V}+\mathrm{\Theta}({\eta}^{3}).$  (31) 
Then by plugging this equation into the right hand part of eqn. (29), we have
$\frac{\eta}{N}}{\displaystyle \sum _{l=0}^{E1}}{(\mathbf{I}\eta {\mathbf{A}}_{1})}^{l}\mathbf{A}\left(\mathbf{I}{\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^{N}}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)$  
$=$  $\frac{\eta}{N}}{\displaystyle \sum _{l=0}^{E1}}(\mathbf{I}l\eta {\mathbf{A}}_{1}+\mathrm{\Theta}({\eta}^{2}))\mathbf{A}\left({\displaystyle \frac{E\eta}{N}}\mathbf{A}{\displaystyle \frac{E(E1)}{2N}}{\eta}^{2}\mathbf{V}+\mathrm{\Theta}({\eta}^{3})\right)$  
$=$  $\frac{{\eta}^{2}}{N}}\left({\displaystyle \frac{E(E1)}{2}}(\mathbf{V}{\mathbf{A}}_{1}\mathbf{A})+\mathrm{\Theta}(\eta )\right)$ 
Second from eqn. (C.5), we have that
$${\left(\mathbf{I}\frac{1}{N}\sum _{i=1}^{N}{(\mathbf{I}\eta {\mathbf{A}}_{i})}^{E}\right)}^{1}={\left(\frac{E\eta}{N}\mathbf{A}+\mathrm{\Theta}({\eta}^{2})\right)}^{1}=\frac{N}{E\eta}{\mathbf{A}}^{1}+\mathrm{\Theta}(1).$$ 
Plugging the last two equations into eqn. (29), we have
$\parallel {\stackrel{~}{\mathbf{w}}}^{*}{\mathbf{w}}^{*}\parallel $  $=\parallel \left({\displaystyle \frac{N}{E\eta}}{\mathbf{A}}^{1}+\mathrm{\Theta}(1)\right){\displaystyle \frac{{\eta}^{2}}{N}}\left({\displaystyle \frac{E(E1)}{2}}(\mathbf{V}{\mathbf{A}}_{1}\mathbf{A})+\mathrm{\Theta}(\eta )\right){\mathbf{w}}^{*}\parallel $  
$=\parallel \left({\displaystyle \frac{E1}{2}}\eta {\mathbf{A}}^{1}(\mathbf{V}{\mathbf{A}}_{1}\mathbf{A})+\mathrm{\Theta}(\eta )\right){\mathbf{w}}^{*}\parallel $  
$\ge {\displaystyle \frac{(E1)\eta}{16}}\parallel (\mathbf{V}{\mathbf{A}}_{1}\mathbf{A}){\mathbf{w}}^{*}\parallel $  
$={\displaystyle \frac{(E1)\eta}{16}}\parallel {\mathbf{A}}_{1}{\mathbf{A}}_{2}{\mathbf{w}}^{*}\parallel $ 
where the last inequality holds because (i) we require $\eta $ to be sufficiently small and (ii) $\parallel {\mathbf{A}}^{1}\mathbf{x}\parallel \ge \frac{1}{4}\parallel \mathbf{x}\parallel $ for any vector $\mathbf{x}$ as a result of $$. The last equality uses the fact (i) $\mathbf{V}{\mathbf{A}}_{1}\mathbf{A}={\mathbf{A}}_{1}{\sum}_{i=2}^{n}{\mathbf{A}}_{i}$ and (ii) ${\mathbf{A}}_{1}{\mathbf{A}}_{i}=\mathrm{\U0001d7ce}$ for any $i\ge 3$. ∎
Appendix D Experimental Details
D.1 Experimental Setting
Model and loss.
We examine our theoretical results on a multinomial logistic regression. Specifically, let $f(\mathbf{w};{x}_{i})$ denote the prediction model with the parameter $\mathbf{w}=(\mathbf{W},\mathbf{b})$ and the form $f(\mathbf{w};{\mathbf{x}}_{i})=\text{softmax}({\mathrm{\mathbf{W}\mathbf{x}}}_{i}+\mathbf{b})$. The loss function is given by
$$F(\mathbf{w})=\frac{1}{n}\sum _{i=1}^{n}\text{CrossEntropy}(f(\mathbf{w};{\mathbf{x}}_{i}),{\mathbf{y}}_{i})+\lambda {\parallel \mathbf{w}\parallel}_{2}^{2}.$$ 
This is a convex optimization problem. The regularization parameter is set to $\lambda ={10}^{4}$.
Datasets.
We evaluate our theoretical results on both real data and synthetic data. For real data, we choose MNIST dataset [12] because of its widely academic use. To impose statistical heterogeneity, we distribute the data among $N=100$ devices such that each device contains samples of only two digits. To explore the effect of data unbalance, we further vary the number of samples among devices. Specifically, for unbalanced cases, the number of samples among devices follows a power law, while for balanced cases, we force all devices to have the same amount of samples.
Synthetic data allow us to manipulate heterogeneity more precisely. Here we follow the same setup as described in [26]. In particular, we generate synthetic samples $({\mathbf{X}}_{k},{\mathbf{Y}}_{k})$ according to the model $y=argmax(\text{softmax}({\mathbf{W}}_{k}x+{\mathbf{b}}_{k}))$ with $x\in {\mathbb{R}}^{60},{\mathbf{W}}_{k}\in {\mathbb{R}}^{10\times 60}$ and ${\mathbf{b}}_{k}\in {\mathbb{R}}^{10}$, where ${\mathbf{X}}_{k}\in {\mathbb{R}}^{{n}_{k}\times 60}$ and ${\mathbf{Y}}_{k}\in {\mathbb{R}}^{{n}_{k}}$. We model each entry of ${\mathbf{W}}_{k}$ and ${\mathbf{b}}_{k}$ as $\mathcal{N}({\mu}_{k},1)$ with ${\mu}_{k}\sim \mathcal{N}(0,\alpha )$, and ${({x}_{k})}_{j}\sim \mathcal{N}({v}_{k},\frac{1}{{j}^{1.2}})$ with ${v}_{k}\sim \mathcal{N}({B}_{k},1)$ and ${B}_{k}\sim \mathcal{N}(0,\beta )$. Here $\alpha $ and $\beta $ allow for more precise manipulation of data heterogeneity: $\alpha $ controls how much local models differ from each other and $\beta $ controls how much the local data at each device differs from that of other devices. There are $N=100$ devices in total. The number of samples ${n}_{k}$ in each device follows a power law, i.e., data are distributed in an unbalanced way. We denote by synthetic$(\alpha ,\beta )$ the synthetic dataset with parameter $\alpha $ and $\beta $.
We summary the information of federated datasets in Table 2.
Experimental.
For all experiments, we initialize all runnings with ${\mathbf{w}}_{0}=0$. In each round, all selected devices run $E$ steps of SGD in parallel. We decay the learning rate at the end of each round by the following scheme ${\eta}_{t}=\frac{{\eta}_{0}}{1+t}$, where ${\eta}_{0}$ is chosen from the set $\{1,0.1,0.01\}$. We evaluate the averaged model after each global synchronization on the corresponding global objective. For fair comparison, we control all randomness in experiments so that the set of activated devices is the same across all different algorithms on one configuration.
Dataset  Details  $\mathrm{\#}$ Devices $(N)$  $\mathrm{\#}$Training samples $(n)$  Samples/device  

mean  std  
MNIST  balanced  100  54200  542  0 
unbalanced  100  62864  628  800  
Synthetic Data  $\alpha =0,\beta =0$  100  42522  425  1372 
$\alpha =1,\beta =1$  100  27348  273  421 
D.2 Theoretical verification
The impact of $E$.
From our theory, when the total steps $T$ is sufficiently large, the required number of communication rounds to achieve a certain precision is
$${T}_{\u03f5}/E\approx \mathcal{O}\left(\frac{E{G}^{2}}{K}+E{G}^{2}+\frac{{\sum}_{k=1}^{N}{p}_{k}^{2}{\sigma}^{2}+L\mathrm{\Gamma}+\kappa {G}^{2}}{E}\right),$$ 
which is s a function of $E$ that first decreases and then increases. This implies that the optimal local step ${E}^{*}$ exists. What’s more, the ${T}_{\u03f5}/E$ evaluated at ${E}^{*}$ is
$$\mathcal{O}\left(G\sqrt{\sum _{k=1}^{N}{p}_{k}^{2}{\sigma}^{2}+L\mathrm{\Gamma}+\kappa {G}^{2}}\right),$$ 
which implies that FedAvg needs more communication rounds to tackle with severer heterogeneity.
To validate these observations, we test FedAvg with Scheme I on our four datasets as listed in Table 2. In each round, we activate $K=30$ devices and set ${\eta}_{0}=0.1$ for all experiments in this part. For unbalanced MNIST, we use batch size $b=64$. The target loss value is $0.29$ and the minimum loss value found is $0.2591$. For balanced MNIST, we also use batch size $b=64$. The target loss value is $0.50$ and the minimum loss value found is $0.3429$. For two synthetic datasets, we choose $b=24$. The target loss value for synthetic(0,0) is $0.95$ and the minimum loss value is $0.7999$. Those for synthetic(1,1) are $1.15$ and $1.075$.
The impact of $K$.
Our theory suggests that a larger $K$ may accelerate convergence since ${T}_{\u03f5}/E$ contains a term $\mathcal{O}\left(\frac{E{G}^{2}}{K}\right)$. We fix $E=5$ and ${\eta}_{0}=0.1$ for all experiments in this part. We set the batch size to 64 for two MNIST datasets and 24 for two synthetic datasets. We test Scheme I for illustration. Our results show that, no matter what value $K$ is, FedAvg converges. From Figure 3, all the curves in each subfigure overlap a lot. To show more clearly the differences between the curves, we zoom in the last few rounds in the upper left corner of the figure. It reveals that the curve of a large enough $K$ is slightly better. This result also shows that there is no need to sample as many devices as possible in convex federated optimization.
Sampling and averaging schemes.
We analyze the influence of sampling and averaging schemes. As stated in Section 3.3, Scheme I iid samples (with replacement) $K$ indices with weights ${p}_{k}$ and simply averages the models, which is proposed by Sahu et al. [26]. Scheme II uniformly samples (without replacement) $K$ devices and weightedly averages the models with scaling factor $N/K$. Transformed Scheme II scales each local objective and uses uniform sampling and simple averaging. We compare Scheme I, Scheme II and transformed Scheme II, as well as the original scheme [20] on four datasets. We carefully tuned the learning rate for the original scheme. In particular, we choose the best step size from the set $\{0.1,0.5,0.9,1.1\}$. We did not fine tune the rest schemes and set ${\eta}_{0}=0.1$ by default. The hyperparameters are the same for all schemes: $E=20,K=10$ and $b=64$. The results are shown in Figure (c)c and (d)d.
Our theory renders Scheme I the guarantee of convergence in common federated setting. As expected, Scheme I performs well and stably across most experiments. This also coincides with the findings of Sahu et al. [26]. They noticed that Scheme I performs slightly better than another scheme: server first uniformly samples devices and then averages local models with weight ${p}_{k}/{\sum}_{l\in {S}_{t}}{p}_{l}$. However, our theoretical framework cannot apply to it, since for $t\in \mathcal{I}$, ${\mathbb{E}}_{{S}_{t}}{\overline{\mathbf{w}}}_{t}={\overline{\mathbf{v}}}_{t}$ does not hold in general.
Our theory does not guarantee FedAvg with Scheme II could converge when the training data are unbalanced distributed. Actually, if the number of training samples varies too much among devices, Scheme II may even diverge. To illustrate this point, we have shown the terrible performance on mnist unbalanced dataset in Figure (b)b. In Figure 4, we show additional results of Scheme II on the two synthetic datasets, which are the most unbalanced. We choose $b=24,K=10,E=10$ and ${\eta}_{0}=0.1$ for these experiments. However, transformed Scheme II performs well except that it has a lower convergence rate than Scheme I.