FedAvg Converges to Zero Training Loss Linearly: The Power of Overparameterized Multi-Layer Neural Networks
Authors: Bingqing Song
Prashant Khanduri
Xinwei Zhang
Jinfeng Yi
Mingyi Hong
Venue: Submitted to ICLR 2023 (2023)
Keywords: Overparameterized Neural Network
FedAvg

Abstract: Federated Learning (FL) is a distributed learning paradigm that allows multiple clients to learn a joint model by utilizing privately held data at each client. Significant research efforts have been devoted to develop advanced algorithms that deal with the situation where the data at individual clients have different distributions (i.e., the data heterogeneity issue). In this work, we show that data heterogeneity can be dealt from a different perspective. That is, by utilizing a certain overparameterized multi-layer neural network at each client, even the vanilla FedAvg (a.k.a. the Local SGD) algorithm can accurately optimize the training problem. Specifically, when each client has a neural network with one wide layer of size $N$ (where $N$ is the number of total training samples), followed by layers of smaller widths, FedAvg converges linearly to a solution that achieves (almost) zero training loss, without requiring any assumptions on the data distributions at each client. To our knowledge, this is the first work that demonstrates such resilience to data heterogeneity
for FedAvg when trained on multi-layer neural networks. Our experiments also confirm that, neural network of large size can achieve better and more stable performance for FL problems.

Under review as a conference paper at ICLR 2023
FEDAVG CONVERGES TO ZERO TRAINING Loss LINEARLY FOR OVERPARAMETERIZED MULTI-LAYER NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Learning (FL) is a distributed learning paradigm that allows multiple clients to learn a joint model by utilizing privately held data at each client. Sig- nificant research efforts have been devoted to develop advanced algorithms that deal with the situation where the data at individual clients have heterogeneous distributions. In this work, we show that data heterogeneity can be dealt from a different perspective. That is, by utilizing a certain overparameterized multi-layer neural network at each client, even the vanilla FedAvg (a.k.. the Local SGD) algorithm can accurately optimize the training problem: When each client has a neural network with one wide layer of size N (where N is the number of total training samples), followed by layers of smaller widths, FedAvg converges lin- early to solution that achieves (almost) zero training loss, without requiring any assumptions on the clients' data distributions. To our knowledge, this is the first work that demonstrates such resilience to data heterogeneity for FedAvg when trained on multi-layer neural networks. Our experiments also confirm that, neu- ral networks of large size can achieve better and more stable performance for FL problems.
INTRODUCTION
In Federated Learning (FL), multiple clients collaborate with the help of server to learn joint model McMMhan et al. (017)). The privacy guarantees of FL has made it a popular distributed learning paradigm,
each client holds a private data set and aims to learn a global model without leaking its data to other nodes or the server. The performance of FL algorithms is known to degrade when training data at individual nodes originates from different distributions, referred to the heterogeneous data setting Yu et al. (2019a): Woodworth et al. (2020a). In the past few years, substantial research effort has been devoted towards developing large number of algorithms that can better deal with data heterogeneity, KKrimireddy et al. (2020b); Zhang et al. (021)): Li et al. (2018); Acar et al.] (2020); Khanduri et (2021). However, practice it has been observed by number of recent works, that in spite of the data heterogeneity, the simple vanilla FedAvg algorithm (a.k.a. the Local SGD) still offers competitive performance comparison to the oatte-of-the-are For example, see Table 2 in KKarimreedy et al. (2020a), Table I in Reddi et al. (2020), and Table 2 in Yang et al. 202I for performance comparison FedAvg on popular FL tasks.
Motivated by these observations, ask: Is it possible to handle the the data heterogeneity issue from a different perspective, without modifying the vanilla FedAvg algorithm? To answer this ques- tion, in this work we show that FedAvg can indeed perform very well regardless of the heterogeneity conditions, if the models to be learned are nice enough. Specifically, FedAvg finds solutions that achieve almost zero training loss (or almost global optimal solution) very quickly (i.e., linearly), when the FL model to be trained is certain overparameterized multi-layer neural network. To the best of our ledgl this is the first result that shows (linear) convergence of FedAvg in the over- parameterized regime for training multilayer neural networks. The major contributions of our work are listed below.
Under certain assumptions on the neural network architecture, we prove some key properties of the clients' (stochastic) gradients during the training phase Lemmas[aand] 2). These results allow us to establish convergence of FedAvg for training overparameterized neural networks without imposing restrictive heterogeneity assumptions on the gradients of the local loss functions.

---

Under review as a conference paper at ICLR 2023
We design special initialization strategy for training the network using FedAvg. The initialization is designed such that the singular values of the model parameters and the outputs of the first layer of local and aggregated model parameters stay positive definite during the training. This property combined with overparameterization enables FedAvg to converge linearly to a (near) optimal solution.
We conduct experiments on CIFAR-IO and MNIST datasets in both i.idd and heterogeneous data settings to compare the performance of FedAvg on various network architectures of different sizes. To our knowledge, this is the first work that shows the linear convergence of FedAvg (both SGD and GD versions) the optimal solution when training overparameterized multi-layer neural networks.
Related Work: Federated Learning (FL). FL algorithms were first proposed in McMahan et al. (017)) where within each communication round the clients utilize their private data update the model parameters using multiple SGD steps. Earlier works analyzed the performance of FedAvg for the case of homogeneous data setting Zhou and Cong (2018); Stich (2018); Lin al. (2020); Woodworth et al. (2000b); Wang and Joshi (2021). i.c., when the local data at each client follows the same underlying distribution. Motivated by practical applications, recent works have analyzed
FedAvg for heterogeneous client data distributions Yu et al. (20T9h [Hadaadpour and Mahdavi (2019); Woodworth et al.] (2020a) and it was observed that the performance of FedAvg degrades as the data heterogeneity increases. To address the data heterogeneity issue among clients, many works have focused on developing sophisticated algorithms Karimireddy et al. (2020b); /Zhang et al.
(2021) Acar et al. (2020): Li al. (2018); Khanduri et al. (2021): Karimirddyy et al. (2020a): Das ct al. (2020).
O overparameterized Neural Networks. The surprising performance of overparameterized neural networks has raised sigmificant research interest in the ML community to analyze the phenomenon of overparameterization [Belkin et al.] (2019). Consequently, many works have analyzed the per- formance of centralized (stochastic) gradient descent GS) on overparameterized neural network architectures under different settings Jacot et al. (2018); ; Li and Liang (2018); Arooa al. (2019)
Du et al. 20188 2019); Allen-Zhu et al. (2019); Zou and Gu (2019); guyen and Mondelli 2020
Nguyen 2021))
However, there are only a handful of works that have attempted to analyze the performance of overparameterized neural networks in the distributed setting [Li et al. (202T): Huang al. (202T); Deng and Mahdavi (202T). The works most closely related to our work are Huang et al. (2021) and
Deng and Mahdavi (202T). [Huang et al. (202T) analyzed the performance of FedAvg on a single hidden-layer neural network for the case when each client utilizes GD for the local updates. The authors established linear convergence of FedAvg using the NTK parameterization and showed that it suffices to design the neural network of width ((NN4) to achieve this performance (where N is the number of training samples). Similarly, Deng and Mahdavi (202T) analyzed the performance of FedAvg on a ReLU neural network but when each client utilizes SGD (or GD) for the local updates. The authors proved convergence of FedAvg under the standard parameterization while requiring the very large network width of 1(N18). Note that since individual clients be devices with limited computational capabilities, in realistic settings it is undesirable to have networks of such large widths. In contrast both these works, we focus on the more practical setting of multi-layer neural network Nguyen and Mondelli (2020) and establish linear convergence of FedAvg even for the case when each client utilizes SGD for the local updates. Importantly, we show that with proper initialization, it only requires a network of width N at each client, which is much smaller compared to the unrealistic requirements of Huang et al. (202T); Deng and Mahdavi (202T).
PROBLEM SETUP
In this section, we define the multi-laye neural network and formalize the problem we aim to solve. We consider a distributed system of K clients with each client having access a privately held data set. We assume that each client l: E [l,.... KJ has N₂ training samples denoted as {(xx, Vx)), with X E Xdd and Y. E Nedaut Note that each row of X2 and Y1 represents the feature vector and its corresponding label, and di and dout denote the feature (input) and label (output) dimensions, respectively. We further denote N = E as the total samples across all clients.
A model is generally referred to as overparameterized if the number of (trainable) parameters are more than the number of training samples N.
2

---

Under review as a conference paper at ICLR 2023
Suppose each client trains fully-connected neural network with L layers, and with activation function Ø IR + R. We denote the vectorized parameters at each node h E {I...., ...,.K K} as & = |vec (W1 1.) ................................ vec (WI,s)] E R., where Wi, E R 1xx represents the weight matrix of each layer E (1....,L.) and ny represents the width of each layer. Note that each layer inputs a (feature) vector of dimension n4-1 and outputs (feature) vector of dimension ny. For simplicity, define no = din and n2 = dout. as the input and the output dimensions of the neural network. We define Fi, the local output of each layer at client k then using the above notations, we have
Xx o (FI-LAWEN)
1= 0
Fi,
lE (1,22..... 1= T.
(1)
FL
We further define the vectorized output of each layer and the labels at each client as ft,k vec(Fi,x) E Ne and yk = vec(Yi) E NNa2,
Similar to the above setup, also define the notations to describe single network, with the full data (X, Y) with X xd and Y E xxout as input. This "centralized" network will be useful later perform the analysis. Then given parameter 6 [vee (W1) ,.... vec (WL)), the output at each layer of the network is defined as
X R= = o (P- Fi-1WL
1=0
1E (1,,....., L]
[= L
Next, we define the local and global loss functions. First, each client & E {l...., K} has local loss function given by: & (0) पλę. + yo l2. where || |l2 denotes the standard mo-m Then the global loss function is the sum of weighted local loss functions, given by:
N N
(00)
(x)
(() Ull
2N
Additionally, define the gradient of 3 = [vec( V w, (())...... vec( Ww, (())), which is the
stacked gradient of the loss w.r.t. the 1st 7 layer's parameters; define the gradient of the losses at each client & E [K] as: gk I9 KL, KL with øt,k vec Vw.. (()) for all E [4].
Next, we define the optimality criteria to solve using an overparameterized neural network.
Definition 1 (e-optimal solution). Consider an overparameterizell problem ming (()), where there exist 8 such that ((0") = O. A solution 0 is called an c-optimal solution if it satisfies ((0) I e. Moreover, i is random variable, then we use E[ S denote an e-optimal solution, where the expectation is taken w.r.t. the randomness of x.
THE FEDAVG ALGORITTM
A classical algorithm to solve problem is the FedAvg McMahan al. 2017 In FedAvg, each client performs multiple local updates before sharing their updated parameters with the server. We refer the algorithm as redAvg-SGD (resp. FedAvg-GD) if the clients employ SGD (resp. GD) for the local updates.
The detailed steps to implement FedAvg-SGD are listed in Algorithm [ for a total of T communication rounds, within each communication round every client performs r local updates. In each communication round / the server aggregates the local parameters and constructs @rt from each client's local parameters 0rt+* and shares it with the clients. The clients use the aggregated parameter, 0rt+r, as the initial parameter value for computing the next round of local updates. For each v E (0, 1......., 1}, to update the local parameters the clients compute the (unbiased) stochastic gradient using m-samples drawn form their private data set (XR, Y.). We denote the random sample drawn ,h local step in the 7hh communication round (xrt+v , yrrt+)). Using the stochastic gradient estimate, the clients update their parameters locally by employing the SGD step. After local SGD steps, each client shares its updated parameters with the server and gets back the aggregated parameters before starting the next round of updates. Note that if we choose the Ng, for all (1....,K)) K), FedAvg-SSe SGD becomes FedAvg-Gi
We execute the algorithm
batch size
3

---

Under review as a conference paper at ICLR 2023
Algorithm The FedAvg-SGD Algorithm
Initialize: Parameters 0% 0%, Step-size n, of communication rounds, local updates T,, r for t 0, ........2 T 1 do
Algorithm summarizes the above descrip- tion. For each communication round t E {0, . 1} and local step v r- (0.., we define the vector 0f
for each client k E (1,..., K} do Set 0/ = Ht
[vec (vec(W..k)) "....,, vec(WW,t+") v.. For FedAvg- SGD, define 1.k and fi. as the output and the vectorized output of each hidden layer respectively, when the input to the client k's local network is the stochastic (mini-batch) samples (Xrt+v yrett). Using the notation Tg grt+o = vec as the vectorized labels of the stochastic samples at each local step, define the mini-batch stochastic loss as:
for w= 0, r0....111111111 do r- Sample mini-batch of size (X y yxrtt)
m,
Compute stochastic gradient gh t us- ing (5)
n + Update: 0% grt+u+1 gm
19
K
Aggregation: @r((+1) = Σ
Ne
grttr
N
Return: Parameters, G k=1
D (0 ==
(4)
2m
and the stochastic gradient as grt+" := 10,, w.r.t. the 1th layer of the network evaluated at the hthh client:
IL,k where Th,k grt+ is the stochastic gradient
gL. vec (ve. (0((tt
E 1
(5)
For each communication round, let us define the aggregated parameters as: K
gr = [vvo(WTTT) vec(WE)) WT
Nu N
WTL.
(6)
For FedAvg-GI, we denote gx rt+e == lor ........... rt as the full gradient of 1hth client's loss function, where similar to () 91,k defines the gradient of the loss function w.r.t. the 1hh layer's parameters. Throughout, we make the following standard assumption Ghadimi and Lan 2013)
Assumption 1. The stochastic gradients at each client are unbiased, i.e., we have R. Rigg 9k Vk E [K].
Next, we analyze the performance of the FedAvg for an overparameterized neural network.
4 CONVERGENCE ANALYSIS
We present the convergence guarantees of FedAvg when training an overparameterized neural net- work. We first present set of assumptions on the network architecture, and activation functions.
Assumption 2. The width of each hidden layer satisfies: nı 2 N, n2 2 n& ... 2 n, 2 1.
Assumption 3. The activation function a(-) in [ satisfies the following: 1) d'xx) E
[7; 2) [x(x) < |æ];; V E IR; 3) o' is 3-Lipschitz, with 7 E (0, and 3 0.
Remark 1. Assumptions 2 andd 3 play an important role in our analysis. They help ensure that the local and global loss functions and their (stochastic) gradients are well behaved. Note that As- sumption 2 only requires the first layer to be wide while the rest of the layers can be of constant width. Assumption [ is required to establish a PL like property for the global and local loss func- tions Nguyen and Hein (2018); Nguyen and Mondelli (2020). Assumption 3 is also standard in the anilysis of overparameterized neural networks. Similar assumptions activation functions have been made in the past Jacot et al. (2018); Du et al. (2019); Nguuyen and Mondelli (2020); Huang and Yau (2020) and are utilized to manage the behavior of the gradients of the loss functions. Importantly, note that as demonstrated in Nguyen and Mondelli (2020) activa- tion functions satisfying Assumption 3 can be utilized to uniformly approximate the ReLU function to arbitrary accuracy.
the smoothness of the
Remark 2. We do not impose any assumptions on the distribution of individual clients' local data sets. In contrast, majority of works on FL impose restrictive assumptions the gradients (and/or the Hessians) of each client's 's local loss functions to guarantee algorithm convergence Yu et al.
2019b); Li et al. (2018) : Yu et al. (019a): Karimireddy et al. (2020a). Below, we list two most
4

---

Under review as a conference paper at ICLR 2023
popular heterogeneity assumptions (from Yu al. (2019a) and Koloskova al. 2020) respec- rively):
- v S - v0, R. Ak [K], for some ò >> 0.
1 K
[ = +2 Y for some ò1 82 0.
(8)
Both conditions impose strong restrictions on the gradients of the local clients, and they do not hold for even simple quadratic loss Khaled al. (2019): Zhang et al. (2027). We will see shortly that, our results will indicate that as long as the neural network is large enough, then the local (stochastic) gradients will be well-behaved, thereby eliminating the need to impose any additional assumptions on the data distributions.
In the following, we show the convergence guarantees achieved by FedAvg. Our analysis roughly
follows the four steps presented below:
[Step 1] We first show key result, that the ratio of the local stochastic gradients and the local full gradients stays bounded (Lemma JT. This result crucial for the FedAvg-SGD analysis, as allows us to work with the full local gradients directly, and it helps to bound the gradient drift across local updates within each communication round.
[Step 2] Using the result of Step 1, we bound the summation of (stochastic) gradients and the gradient drift during the local updates within each communication round (Lemma 2 This result ensures that irrespective of the data heterogeneity, the gradients size will not change too much from their initial values at the beginning of each round.
(Step 3] We then show that adopted network architecture allows us derive bounds the size of the gradients and ensure the loss function to be PL during the each communication round (Lemma) Utilizing this and the results derived in Steps 1 and we show that the expected loss converges linearly to zero (Proposition] D]
[Step 4] Finally, we find special initialization strategy so that all the conditions imposed on the network properties are satisfied during the entire training process.
Next, let us begin with Step 1. We need the following definition.
Definition 2. Given parameter 0r define the following quantity for each k E [K], t (0, 1o......TTTT........
T - 1} and (0,1,
1}: p( 10 1lart-
"12//111// *1
Clearly, p(0) measures the ratio of the norm of stochastic and full gradients of the local loss functions. In the following, we show that if the model parameters at each client satisfy certain conditions, then p(0r(+") uniformly bounded. Define m-ax(-)) and m-in()) as the largest and smallest singular value of a matrix, respectively.
Lemma 1. Let Assumptions [ holld Suppose in any iteration rt + u, V E {0,1, , 1}, for ort+v [vee (rec(Witt") ")... ),-.., vco veo(Wrkt (Wrtt))) there exists constant Nr A, AF > such that the singular values of Wit+ and Fri+o satisfy
T mmax Benxx(WTT (Wrl+") S Åo, lE [L], E [K],
Tmin FWirl (Wrt+e)
A,, lE [3...., .,. LJ, E [K],
mmin (prtt)) Ap, k [K].
where λر- = II X for given layer-wise parameter d then: p(0 my
AAp
As discussed earlier in Step 1, this lemma crucial to our analysis as it allows us to work with full gradients of individual clients. Before proceeding to Step 2, we need the following definitions:
K
K
No rtte and 5 jot+o =
No -rttv N 9k
N 9k
Here get++ and Jet+t are the weighted averages the full and stochastic gradients, respectively.
Next, in Step (Lemma 2 first bound the size of the sum of frtto over the local updates within each communication round. Then we bound the change in grt+o from v = 0 to any o e (0, 1.....r-- 1). Note that this quantity measures the drift in the averaged gradients from the start of each communication round.
5

---

Under review as a conference paper at ICLR 2023
Lemma 2. For BedAvg-SGDD given step size n > 0, E {0.1,...,--1 and {0, 1..1., 1}.
Suppose there exists constants År, p. and A such that the following conditions hold:
A 2 sup maxx
P z sup (0% kE(K] K]
$x(00 & A $x(00'), h E [K].
kE]K]
Then we have
pL [X] F
3
11 (lfz((0)) 3112.
Σ
9
grtt9
(10)
N
VĀ-1
min
A
Q=0
LE[L]
Further, for all ls [K]. 3Qx O, such that have
- 5- MoL
AL
A
K & v112-
(11)
N min A VA [E
Next, we show Step 3, that the averaged parameter 8r defined in 6 after tth communication round, will have good performance. Towards this end, define the full gradient given parameter f as
ge = [vec Ww, F(0")), vec(Vw, $(0*)))
(12)
Lemma 3. Let Assumptions
2 andd 3 hold. At each communication round rt, suppose there exists
constant 94, Q2, 2p, such that
mmax (W??) S Q2 E [L].
Omin (WT') 2 2, 1 (3...., L..
(13)
Omin (Fi()")) Sp
where Ort and Wirt are defined in (6) Then have
-/-1
lla(0*))22 ver (Vw, + (0
N 22 ) -100 -vll
(14)
PI-LL (0+)) - -wl12-
11900"))la 112 N min S4
(15)
LE(T]
Remark 3. Note that (14) is a PL.ttyp inequality Karimi et al. (2016), and requires the special
structure of the network that satisfies Assumption 2 Nguyen and Hein (2018); Nguyen and Mondelli 22020) Also, (15) can be proven using Assumption
Now, we utilize the results of Steps 1- and Lemma 3 to derive the convergence of FedAvg.
Proposition 1. Use Algorithm to minimize for each iteration rt v. E (0, 1.......
3 Suppose Assumptions 7 and 3 are satisfied, and
0x satisfies the conditions in Lemmas 1 and 2
and for each communication round rt, gr satisfies conditions in Lemmal 3 then 3 0 such that
E (0 (1 N1-
TT) 2 2(L
2 21
+ (00)
(16)
Remark 4. Proposition 7 above shows that, if the conditions in Lemmas 7 and 3 are satisfied,
ie.. we have well-behaved gradients (Lemmas] 7 and 2 and PL. condition (Lemma we achieve
linear convergence of expected loss function for solving with FedAvg-SGD.
We outline the major steps in the proof of Proposition Proof Sketch. Consider the tth communication round, and suppose the singular values the param- eters satisfy (13), then it is easy to show that ((0*)) is Lipschitz smooth with some constant > 0.
Then using the Lipschitz smoothness of /b (("),, we get
jre+r-1) + - 115m +... -
(0+(+)1)) < ((0rt) - 17 (g" 1 9
Taking expectation both sides and conditioning Tht and the past, get the following

---

Under review as a conference paper at ICLR 2023
1( & F ((00) "'0""""" g + +.... .g
Q
5 +.... + -3
2
= = (0 77 (g" rggh) 7100 Σ grete g-h +
Q "
$ 5 (00)) y/r 11 1 + nll 1|l
9 no 101l2
Q
1 +
(17)
Now we bound each term in using Lemmas and 3 We first use the upper and lower bounds in Lemma to bound the gradient norm. First, to bound the second term the right hand side (rhs) of 17 we use the PL-inequality in (14) of Lemma]
1--1 N 22 [I - u1l2-
1g 112
(18)
We bound gradient norm in the third term using the upper bound of gradient in (15) of Lemma
L 121+1 [l
1
2/12 := Ti
(19)
N min f2 [E
Additionally, we use 11 in Lemma
to bound the gradient drift in the third term, we get
g gr 8-112 PL ALL
A
Σ Q (x el12 == T2 (20)
N min [E(L]
VA-
Next, using (0) in Lemma 2 to bound fourth term the rhs, the sum of stochastic gradient as
pL|| A #
7 |1((rr)) -yl2 == TT--
1 ......... 3rltr-111 11,
VA
min A
[E
Finally, plugging the bounds for each term in
17 using the.definition of loss function Φ
(0rt) y v12 along with the choice of step-size 1)
N2 2
we get
(( - (1 (1- N 2 2
2 22 22
E((((*)))
(21)
Using the above inequality recursively, we get the statement of Proposition
Now Step 3 is complete and we move to define the initialization strategy of Step 4. It is important all of which impose some conditions on the singular
to note that Proposition[ [utilized Lemmas]] | 3
values of the model parameters and the outputs of the first layer at each client during the entire training phase. Next, we define the initialization strategy that ensures that the conditions of Lemmas satisfied almost surely.
Next, we go to Step 4, and discuss the initialization strategy. Define X == Omin (W?) and
A (1 + maax (W?)), for / E {1,2}, (mmax((())
(22)
for E [3.....
We also define the largest and smallest singular values of the output of the first layer at initialization for each client as Co,k = Juin (o (Xx#W,x)) Similarly, for the centralized setting when all the clients share the same parameter and full data, we define 2. o (a (XWP)).
Initialization Strategy: Given any < 4100), we initialize the model weights such that for some constants M,, M2, M3 0, the following are satisfied
Mi min X [E[C]
(
1/2, LE f3...., 1}.
(23)
|
1, 1E (1,2)
M2 min A (E(M]
2
An
< min
Co:
min Co.k kE[K]
Madg-r00 2
(24)
min X
[E(L)

---

Under review as a conference paper at ICLR 2023
To satisfy the required initialization, we follow the initialization strategy of Nguyen and Mondelli 2020). First, randomly initialize [WT],; ~ NNO,, 1/df,). Broadcast [Wilkt to each client and collect Fi,e. which is the output of the first layer of each client, as well as the norm of local data || ll. With Fi.s. On and &n can be computed. For (23). since we have nn >N, Gg and Co. are strictly positive. Then it is easy to verify that given
0, (23) and the second relation in (24)
will be satisfied if we choose large enough
X1-L This can be realized by choosing arbitrarily large min À :E]G]
X1, E [3, ................................ .... In order to satisfy the first relation in (4 we need to make X and 2 close L
to each other. Intuitively, one way to construct (W:9)== such that X X <>>>>> 1, where Ç
can be chosen to be any large number such that (23) and the second relation in (24) are satisfied.
We also need to upper bound + (00). This can be done by choosing small W2. Randomly initialize
Wy such that [W2],, aj _NO0, s)). We can set x to be arbitrarily small, then (00) is bounded by
N llvll2 with high probability (see (10) in Nguyen and Mondelli (222 Note that the desired error e is another key constant in the initialization. When we expect the error to be small, (23 and the second relation in (24) will be more strict. But this is not issue since we can choose larger such that the initial conditions are satisfied. The detailed initialization strategy that ensures that the conditions of Lemmas I 2 and are satisfied is given in the Appendix B.22
Next, let us state our main result, which indicates the linear convergence of local SGD to any 6- optimal solution (see Definition [ The proof is attached in Appendix [B.]]
Theorem 1. Using FedAvg-SGD to minimize
) with Algorithm 7 Suppose Assumptions 7 2 and
are satisfied, then there exists an initialization strategy such that for any e < ((0"), there exists 2(1-1)
step-size 1j > 0 such that we have (where p¹
2N 2(L-)) (1) (4)2((-1) 22 and np² 1)
E( D) (1
T -1-110 -''))" (00)), tE (0 1
Theorem [ shows that, for any E we can always find an initialization, such that FedAvg- SG achieves an accuracy within O (log(²)) rounds of communication. Notice that there is no heterogeneity assumption on the data (see Remark 2, and no assumption on the Lipschitz gradient of the loss function.
We comment on the key novelties this work compared to Nguyen and Mondelli (020). (1) Our work requires careful analysis to deal with multiple local updates at each client. Note that in contrast to Nguyyn and Mondelli (2020). for our algorithm there is no guarantee that the overall objective will always decrease during local updates. In fact, our analysis demonstrates that the overall objective can increase after each local iteration, we show that this increase will be compensated by the descent in the objective value between each communication round.
Remark 5.
(2) Our algorithm and analysis can deal with the stochastic gradients for conducting local updates, while Nguyen and Mondelli (2020) only considered gradient descent in a centralized setting. A key step in our analysis is to characterize the relationship between the stochastic and full gradient updates, which is illustrated in Lemma
Remark 6. We comment on the choice of parameters and the convergence rate. As will be shown in Appendix B.3 by utilizing our initialization strategy. we can choose c/p' for some constant
c E (0,1) (independent of This implies that μ'r c <, which further implies that we have (1 - p'm) < 1 in Theorem [ ensuring linear convergence of FedAvg-SGI)
Finally, we present the convergence guarantees for the case when FedAvg-GD- is utilized.
Corollary 1. Using FedAvg-GD to minimize 3 with Algorithm ! Suppose Assumptions 2 and are satisfied, then there exists an initialization strategy and step-size 1) > O, such that we have
T ((0r((+1)) S (1- - p'n)² ((0)), 1L E , T
(25)
Remark 7. Corollary
I implies that FedAvg-GD achieves linear convergence when optimizing We note that the result of Corollary is much stronger compared to Theorem 7
as the initialization
for FedAvg-GD GD is independent of compared to the one for FedAvg-SGD (shown in Appendix (B2)
NUMERICAL EXPERIMENTS
In this section, we analyze the effect of increasing the network sizes on popular image classification tasks with MNIST, Fashion MNIST and CIFAR-10 data sets. We compare the performance of
8

---

Under review as a conference paper at ICLR 2023
FedAvg in both homogeneous (i.id.)) and heterogeneous (non-ii.d.) data settings. Through experiments we establish that larger sized networks uniformly outperform smaller networks under different settings. Next, discuss the data and the model setting for experiments.
Cifer10
with
Cifarlo Test Accuracy with CNN
CNN
0.7
1d smail
800
6.6
noniid smail
Tainngg Uosz
0.
C.
500
id.smal
0.3
62:
nonidd ymal
0:2
nomiid jarge moniid_smal
6.1
nomid
50
100
150
200
250
300
50
100
150
200
250
300
30 60 90 120 150 100 240 270 300 Trariing Epochs
Traniing Epocrs
Training Eoochs
Figure I: CIFAR-I0 with CNN: FedAvg-SGD SGD on large and small size CNN.
Cifar10 Training Loss with
Cifar10 lest Accuracy with ResNet
Nonii Cifar ResNet
1000
Is res18
0.8-
MW
0.0
idd re150
Tainng Lobe
norlid, res18 namiid,
C.6
Text icc
6.0
reures3
resre
6.2
nonid_res18
0.7
ronid res50
nonid, nonild_re550 res50
ronid res18
20
40
00
80
100
0
20
40
60
80
100
30
00 100 Training Epoaer
40
50
60
70
80
manning Epochs
Iraiming Epocths
Figure 2: CIFAR-10 with ResNet: Comparison of FedAvg- SGD on ResNet18 and ResNet50.
MNIST Test Accuracy
Fashion Test Accuracy
0.0
nonid
nonid
nonid In
ronid_in In
20
40
60
100
20
40
60
80
100
Training Epocits
Traiiin Boochs
Figure 3: Test accuracy for MNIST (left) and Fashion MNIST (right) datasets. We compare the per- formance with (standard) random initialization and the proposed initialization strategy for both iid and noniid settings. Legends 'jid ini' and 'noniid ini' represent the proposed initialization strategy.
Data set: For MNIST, Fashion MNIST and CIFAR-10 data sets, split the data set among K = 100 clients. For the homogeneous (i.i.d) setting, we randomly distribute the complete data set with 60, 000 samples to each client. To model the heterogeneous (non i.i.d.) setting, we split the clients into two sets. One set of clients receive randomly drawn samples while the second set of clients |abels|McMahar
receive data from only two out of ten labels McMahan et al. (2017). For our experiments on MNIST
and Fashion MNIST data, 70% of the users receive non-i.i.d samples, while for CIFAR- 10 data, the fraction is 20%.
Results and Discussion For each setting, we compare the training loss and testing accuracy of Fe- dAvg on smaller and larger sized networks. To analyze the effect of network sizes on the stability of FedAvg, we also plot the performance of FedAvg averaged over 10 iterations for non-i.i.d. client data setting for all the network architectures. From our experiments, we make a few observations. First, we observe from Figures mance (lower variance) than non-i.i.d setting. Second, we note that the larger network uniformly outperforms the smaller network under all the settings. Third, we note from the box plots in Figures and 2 that the performance of the larger networks have lower variance, hence more stable per- formance compared with what can be achieved by the smaller networks. Finally, compare the random initialization with special initialization strategy which satisfies (23). (24) We can conclude from Figure that these two initialization similar in test performance.
in all the cases, the i.i.d setting has more stable perfor-

---

Under review as a conference paper at ICLR 2023
REFERENCES
D. A. E. Acar, Y. Zhao, R. Matas, M. Mattina, P. Whatmough, and V. Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2020.
Z. Allen-Zhu, Y. Li, and Song. A convergence theory for deep learning via over-parameeterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
M. Belkin, D. Hsu, Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15849 15854, 2019.
R. Das, A. Acharya, A. Hashemi, S. Sanghavi, S. Dhillon, and Topeu. Faster non-convex federated learning via global and local momentum. arXiv preprint arXiv:2012.04061 2020.
Y. Deng and M. Mahdavi. Local sgd optimizes overparameterized neural networks in polynomial time. arXiv preprint arXiv:2107 2021.
Du, Lee, H. Li, L. Wang, and Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
S. S. Du, X. Zhai, B, Poczos, and A. Singh. Gradient descent provably optimizes werrparamettrizee neural networks. arXiv preprint 1x1..0/810.0205:: 2018.
Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint 1910. 1911..140.5 2019.
B. Huang, X. Li, Z. Song, and X. Yang. Fl-ntk: neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning, pages 4423 4434. PMLR, 2021.
Huang and H.-T. Yau. Dynamics of deep neural networks and neural tangent hierarchy, In International Conference on Machine Learning, pages 4542-4551. PMLR, 2020.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. S. Bengio, Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and moximal-gradient meth- ods under the polyak-lojasiewicz condition. In Joini European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-88 811. Springer, 2016.
Karimireddy, M. Jaggi, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.088 03606, 2020a.
P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pages 5132-514 5143. PMLR, 2020b.
A. Khaled, K. Mishchenko, and P. Richtárik. First analysis of local gd on heterogencous data. arXiv preprint arxiv 1009009999007700 15, 2019.
P. Khanduri, P. Sharma, H. Yang, M. Hong, J. Liu, K. Rajawat, and P. K. Varshney. Stem: A stochastic two-sided momentum algorithm achieving oear-optimal sample and communication complexities for federated learning. arXiv preprint arXiv: 106. 10435, 2021.
10

---

Under review as a conference paper at ICLR 2023
A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi. and S. Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in 2018.
heterogeneous networks. arXiv preprint
X. Li, M. Jiang, X. Zhang, M. Kamp, and Q. Dou. Fedbn: Federated learning on non-iid features via local batch normalization. arXiv preprint arXiv:2102.07623, 2021.
Y. Li and Y. Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data, arXiv preprint 0r80v11808.01244, 2018.
T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi. Don't t use large mini-batches, use local sgd. In International Conference on Learning Representations, 2020.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communccation-fffciienn learning of deep networks from decentralized data. In Artificial intelligence and statisties, pages 1273-1282. PMLR, 2017.
Q. Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprint arXiv:2101.09611 2021.
Q Nguyen and M. Hein. Optimization landscape and expressivity of deep cnns. In International conference on machine learning, pages 3730-3739, PMIR, 2018
Q Nguyen and M. Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. arXiv preprint arXiv:2002.0786; 2020.
S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.0029: 2020.
U. Stich. Local sgd converges fast and communicates little. arXiv preprint 1XXX::180550977 2018.
J. Wang and G. Joshi. Cooperative sgd: A unified framework for the design and analysis of local- update sgd algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021.
B. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local sgd for heterogeneous distributed learning, arXiv preprint arXiv:2006. 04735, 2020a.
B. Woodworth, K. K. Patel, S. U. Stich, Z. Dai, B. Bullins, H. B. McMahan, O. Shamir, and N. Sre- bro. Is local sgd better than minibatch sgd? arXiv preprint arXiv:2002.0783) 2020b.
H. Yang, M. Fang, and J. Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101. 11203, 2021.
H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 1184-7193, PMLR, 2019a.
H. Yu, S. Yang, and Zhu. Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019b.
X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu. Fedpd: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing, pages 1-1, 2021. doi: 10. 10..100991P22221.1115522.
Zhou and G. Cong. On the convergence properties of a k-step averaging stochastic gradient de- scent algorithm for nonconvex optimization. In Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 3219-3227, 2018.
D. Zou and Q Gu. An improved analysis of training over parammttettr deep neural networks. arXiv preprint arXiv: 1906006688. 2019.
11

---

Under review as a conference paper at ICLR 2023
APPENDIX
A RELATED WORK
Overparameterized Neural Networks. The surprising performance of overparameterized neural networks has raised significant research interest in the ML community to analyze the phenomenon of overparameterization Belkin et al. (2019). Consequently, number of works have analyzed the per- formance of centralized (stochastic) gradient descent (S)GD on overparameterized neural network architectures under different settings Jacot et al. (2018); Li and Liang (2018); |Arora al. (2019);
Du et al. 2018 2019); Allen-Zhu et al. (2019); Zou and Gu (gg1)) and Mondelli 22000;
Nguyen 2021 The authors in Jacot al. (2018). showed that infinite width neural network
when trained using gradient descent (GD) behaves like a kernel method with the kernel defined as neural tangent kernel (NTK). Using this NTK parameterization Li and Liang (2018) showed that deep neural networks trained using GD require (2(N*) width to find the global optimal. This re- sult was later improved S2(N3) in Huang and Yau (020). The authors in Du et al. (2018) and Du et al. (2019) also analyze the performance of GD on overparameterized neural networks under different settings. Under standard parameterization, the work Allen-Zhu et al. (2019) studied the convergence of SGD and showed that network width of (2(224) suffices to guarantee linear conver- gence. Recently, Nguyen and Mondelli (2020) and Nguyynn (202I) have improved the dependence on the width and have shown that GD requires only (2(N) width to achieve linear convergence. All the works mentioned above focus on the centralized setting, and therefore, do not deal with data heterogeneity problem.
B PROOF OF MAIN RESULT
B. PROOF OF LEMMAS
We define some additional notations before we state some lemmas which are needed in the proof. Let & denote the Kronecker product, and denote En == diag [vec (o' (Fi-1Wi)]] e R.N.miNNe and E
ΣLe = diag [vec (o' (F,-1,:W,..)) E
diag vee (o'(Fr-LAWE)))) ))] E Rmm: Define Sr (Ortt)); St' == ST,(0')), FL Sr == (ec(F
SI,,(0 LLK
F (0rtt)); Lemma 4. Nguyen and Mondelli (2020) Suppose Assumptions and Assumption 3 are satisfied. Then for I [L] the following holds:
J. II
1
1. g1,k = Nx
(Im, 8 F(
Ep-L (Wn, & INx) (FI. - yk), p=1+1
(26)
0fLK
L-1-1 II (WI-pk INc) EL-1-1 (Irr & F1 D=o
2.
(27)
i @vec(Wi.))
3. 11922112 2 Omin (Fi.)) II
minn (Ep-1.)) amin (Wpr)) |fr, 22 2
(28)
Nx
p=3
4. [Finll < |
mma (W
(29)
p=1
5. VWn Px &xl1F
I N₂
||
II
mmx Wo,k) llfr. Vull2
(30)
Tmax (W1,))
X||Xx|| |
6. |1 -
max (E/-1,6) llfz.k Mell2
(31)
N
min o maax (Wi,))
[E
1=2
12

---

Under review as a conference paper at ICLR 2023
Furthermore, given with og and 8% if A 2 max (Amax (Wit)) max (W?x)) for some scalars
N1. Let R = II max (1, Then, for E [L]. pm1
A
FÝ.k - Fi.all S VII|x
[=1
1 01:112
min A, [E(Z]
(32)
0fl (0t) vec (W(+) a vec (W7)
0fr (0%)
8.
5 &VI|X&||RR111 Lo) | 02112
(33)
The above Lemma follows Lemma 4.1 Nguyen and Mondelli (2020)
26 gives the expression of
the vectorized gradient; (27) provides the vectorized Jacobian matrix of the output of the network;
28) gives lower bound on the norm of the gradient, which holds under Assumption 2 (29
provides an upper bound on the norm of output of each layer while (30) gives an upper bound on the
norm of gradient of each layer; 32 derives the Lipschitz constant of the networks and (33) provides
the Lipschitz constant for the Jacobian of each layer. Similar results can be derived in centralized optimization problem,
do not include the results here.
Lemma 5. (Nguyen and Mondelli x, E Rn be given, and assume that V (=) V5(x)]l s C|I - 22l12 for every 2 = x + lly x)
2020
Lemma 4.3) Let f R" - R be C² function. Let
with E [0, 1]. Then,
C |a y/1
[()) S f(x) (VI(x), x)
Lemma 6. For constant C.p.p. i + we have
lim 7-00
+ 3pCr lox pcn e 3p
(34)
log )/e
Furthermore, given e < 400)), let =
1
then there exists constant &, such that
log' -
(VI+ +1++ppm 3pCr)"
(80
sup O<nymmint de )
(35)
where& & e constant dependent on and μ.
Proof. Take logarithm on both sides, we get
log V1 3pCn lns --ccn
log( /1 3pCr) log(1 (Cn)
1 log(1 + 3pCm)
(36)
log(1 pCn)
Now let 17 0, by I. L''ôpitta'ss rule, take derivative over 7), have
lim 1 log(1 + 3pCn) lim 7-0 2 log(1 - ( 7- μc 1+ 3pCn
3pC 1 nOn
3p
(37)
24
Next, if we can show the function of n, which is VI T- has a limit when
min( pC ) then by the continuity, it has an upper bound in (0, (0.iin( pc = denote it as &. easy to derive that
lim m-+min 20 p
VI + +3pC' los I-pen
lim
+ 3pm
lox 2m
2
p > μ
mim
1.
P S p.
13

---

Under review as a conference paper at ICLR 2023
Then by the continuity the function, (v1 + +3p0p) Then can derive
is bounded by some constant &.
lox (116
sup nE (O, minl pc )
V1 + 3pCn
lim / 1 + 3pm y-+0
1og 1-20
3u 2M
((60))
(38)
then we have there exists some constant f 2 e 600 such that
< (09) <
sup ne (0, 7 mr))
V1 1 + 3pC'
(39)
E
Lemma 7. Let Assumption and Assumption Ap such that and
hold. For Os, suppose there exists constant Nr, Ar.
max (WI,)) I Ar, E [L], E [K], miin (Wi,k) 2 A, LE {3....,LI L,), k [K],
(40)
mmin (Fi,k) Ap, k [K].
then we have
ALck LN
min A (E
p(0x)
(41)
my
LFF
Proof. By definition, we have
p(0)) 1g 12
|
(42)
11yx 1
11 112
Since by 31 and 28 in Lemma 4 we have
Lll A1-L 1l, - -5l12,
1 2 <
(43)
min A [E(L]
1
1102,112 2
7 1- 2 A vll.
(44)
N₂
where Xg. is the sampled data at 0g. So we can derive
&|
min A: (() [
Â
uoll2 LN |N|X||
m
min Ar
p(0k)= <
A AF IL Uk 12 S m 2gg--2Ag-0 AA..1.AFF"
(45)
No
where the last inequality is because | S ||||| and Ilfr,, Dnll2 (f),, yk 212-
Lemma 8. For the FedAvg-SGI algorithm, given step size r) 0, E {0, 1.. 1) and
q E (0, I,..,, v - 1}. Suppose the following conditions hold:
1.A, 2 sup maxx (Wittt)
RE(K]
(46)
2.p > sup p (0) kE[K]
(47)
3. (0 < A T (0't), &o E (K].
(48)
then have
X |l A = AT
< Σ
|
<
v112-
(49)
N
VA
min A [E[L]
9=0
14

---

Under review as a conference paper at ICLR 2023
Further, there exists constant Qs, such that Ak [K] we have
9h
rttg+1_
9k 2
rttg
S pQu
2
(50)
and
v-1
mpL, A1 A = -1
K
-g -
| - grtto|12 1
o
|
11
v1l2.
N
min As VA 1
9=0
[E|L]
Amm
(51)
Proof. First, let us show (49.
(#)
K
N N
(26)
K
Nu
guttll
1
1|2
S
19
+
(52)
N
9=0
9=0 k=
k=
((r) pL
K
A
X
11 - -ll2
(53)
min A [E[4]
q=0
pL.
|x&l F
Σ
uxll2
(54)
N
[E[L]
k=
9=0
PL
K -
K || FF
Σ
A 11 - y1sl22
(55)
N min A
[E[L]
k=1
9=0
p0 Á A 1
K Σ
||
wall2
(56)
N min A VA
[
(0i) PL A A -
K 15
117
(57)
N min Ai VA
[E[L]
A=1
k=1
pL||X Â A A
115t
vll2.
(58)
N min À VĀ - 1
[E[4]
So we can derive
(49
Next, we show 550).
Let us
denote J J
afrll"
afr!!*
By triangle inequality, we have
Vec W1.))
vee
r++++1
rt+g
JSL. Jrrttg+1
( yk)
JSLI (filt -at--yj uK) -ua)
Ok
gk
2
$
f2 prttat1 - SE.
|| | 112 + | - -S(tt 1
| yb
(59)
Now we find the bound for each term in (59). Since max (Amaxx (Wiztoot) Tmax (WIAtte)
))
A₁, by (32) in Lemma we get
Art+g-1
LL
fi 11, S VL
10
(60)
min A LE[L]
Further, by 27 we have
aJ aJslttat1 Ivec (W
A min Ai [E[L]
|
<
< L
(61)
1=1
15

---

Under review as a conference paper at ICLR 2023
Using 33 in Lemma
we have
OJ f f
|J [J
- 1|2
Ōvec (W1,s)
b vec (W1,+)
S I |1lll R' (1
LB||Xx R()
(62)
2
where R' = -17 max (1, Ar). So plug the above bounds into 59 Set Lipschitz constant
LVL No
1
LVL +1 | R¹) R' || - ykl12:
Qx =
+
||
(63)
min A7 N₁ [E(2]
then we derive
9k
+++t+1
Ok
rttg
S -u Qull0rttott
06--911-
(64)
Now 50
proved. Last, we prove 51 We have
ggrit
8-111 5
| g
grttol/
r++++1
rfto
94
9k
N
0=0==
No
Qk
1ortttt1
gritg
Nk Qk 17 1
9=0 kmmm
K
Qk
AI+L
L
x|
|| - 8kl12
N
min A [E[L]
Q= km
(6r) 1TL1 A -
K
m-1
Qs ||lll
Σ
A || 11
min A [E[L]
k=1
9=0
nL Â A 2
K Σ
1
Qx ||
|| - -1al1
N min A VA
[E[L]
k=
(0) nL ÅI= A =
K
K
Q &
Σ 11sttta - vx
N min A VA
[E[L]
1=1
n À 1 A A -1
K
Σ
O
1 -15T
vll2.
N min At VA-
[E[T]
where (i) uses triangle inequality: (ii) uses the Lipschitz gradient assumption in condition 2; (iii) comes from (31 in Lemma 4 (iv) uses condition 3; (v) is from Cauchy- Schwarr inequality.
16

---

Under review as a conference paper at ICLR 2023
B.2 INITIALIZATION STRATEGY
Detailed Initialization for FedAvg-SGD: Denote
L|
7
L-1
P:
(2" - 1):
N
3
1-11
X2 11+
C: PL|XX|
(65)
2
min X7
[E)
LN|| ||
|7
p:=
(66)
my L- 22 1-+ min
Co
min Co.k KE(K]
p 2 2( (62-) (
2(1-1) 1) 1لLة
(67)
Suppose given any small such that < ((0)), the initialized weights satisfies the following con- ditions:
2N 2
(8()))
12, lE (3...., , le [1,2}.
2 (40)
I
(68)
X ( ) 3--1
min
kE(M)
2N
($0)
(20
S 2
min
Co
min Co.k kE(K]
(69)
-(2)--1
D x
min A
where < 2 e is some constant dependent on and j..
Now we provide detailed way realize the above initialization condition. To satisfy the required initialization, we follow the initialization strategy of Nguyen and Mondelli (2020). First, randomly initialize [WT],,
N0, 1/d(.). Broadcast [WP]k] to each client and collect Fi,A, which is the output of the first layer of each client, as well as the norm of local data [|xx|| and norm of local
label l|well2. With Fi.k. Zn and Gg. be computed. For (23), since have nı > N, On and
ao.k are strictly positive with probability 1. Then easy to verify that given e > 0, (23 and
the second relation in (24) will be satisfied if choose large enough AL=t. This can be realized min X (EIL)
by choosing arbitrarily large Às E (3. (3....,,4 L}. However, notice that by Lemma 6 the constant
3p which is defined in (39). is only dependent on and μ and > e So if we can fix P and as some constants, is a bounded constant. Notice in (66) and (67). for I E {3, L). if we can make λr and X, close to each other, then and f are also close, so 2μ
30 is not large. This is
equivalent to the first relation in (24) in main text. In order to satisfy the above conditions, one way to construct (W7) I. 1-3 in such way that X Xr <> 1, where can be chosen be any large number such that (23) and the second relation in (4) are satisfied. Specifically, we can utilize the following construction: Initialize W/ such that its top block is a scaled identity matrix and rest of entries are zero
C. Inc 0
W0
1= 1= 3....,,
(70)
We also need upper bound & (00). This be done by choosing small W Randomly initialize
w such that [W?],, AO0 k). We can set to be arbitrarily small, similar to (10) in Nguyen
17

---

Under review as a conference paper at ICLR 2023
and Mondelli 2020), find bound for ((0)) with high probability:
(00 = || - y|lr
(71)
$ llv1l2 + F2 (0") 1F
llvlla + II o max |
2|yl||
(72)
Then the loss function at initialization can be bounded by constant /2N - 211v|12-
Initialization for FedAvg-GD: The initialized weight matrices satisfy the following conditions:
2. (3) 4-1 + +2 - 1)) |X1| d
{ 1 f3. (3....... D
S
(73)
m7((1-2) (z) 2(2-1112 3-11 og
(1,2)
(()) 4-1 2 1)) ||
2N
1
1 L Gg-
(74)
ry 2) (2)
2(1 1)2 22 1.
The initialization strategy is similar to FedAvg-SGD, so we omit the discussion here.
B.3 PROOF OF THEOREM 1
Theorem 1. Using FedAvg-SCi SGDA to minimize with Algorithm 7 Suppose Assumptions L and are satisfied, then there exists an initialization strategy such that for any c $(f"), there exists step-size 1j > 0 such that we have
E(0(0)(()))] (1- p'n)* (00)) te "O....,T-11.
(75)
where p 2 (1) 2(-1) 23
Proof. First, we provide structure of our proof. We will show the following recursively at each communication round: The averaged weights are bounded at each communication round; 2) The divergence of loss function (3) is bounded at each communication round; 3) The expected loss function (3) decreases linearly at each communication round. Further, we will show that each local epoch within fixed communication round, we have: 1) The weights of each client are bounded; 2) The divergence of loss function &y of each client is bounded.
log( (og(4<(0)/e) //e)
Now let us set T
If we can show
75 holds for 1 = 0,..., T. then it is easy
log
pem
to show that
F( < (1 (1-nCm)² (00)) Se.
We prove Theorem
I by induction. Define
p prtt
p(0r+99)
sup kE[K]
Lm || |
A
min A KE(L]
No - min
Cgp min Co.k
ke
(76)
18

---

Under review as a conference paper at ICLR 2023
We show that Vt Σ T, we have
mmax
[
3 d u E {O.... th, E [L],
2
mmin
(Wrr)
> zd1 u E (o....,, ... E (3....,44 L}:
Omin
(FI")
aag u to.
min 1,k
f. e (o...., .t. k E [K],
(77)
p² S p,
+ (Gr))
$ (1 + 3pCn)) 1 (8%) u E {0.............. .0. - (1 - _Cn))* (0"), u u (O.
E ② (6r))
where de is defined in (2 and X, is the smallest eigen value of the weight matrix, C, p. p defined in B.2 and μC = y¹.
The above recursive equation describes the weight matrix and loss function in cach communication round. To prove (77,, we decompose the recursive equation into two steps, follows
Step1: For a fixed f and u E [r - 1], given
Omax (Wi < I u {0, (0,....,.]).........
0. E [b],
Mmin
(WiT)) > 211 e to,.....t..........
t), E [4]
(PT)) > 200: E (4.......
min
p
pi
(rr
I (1+3pCr))00 " (09) E (0
E
O (C(1= (0)) u E {0. , .t]
(78)
(Dntto
(1+ 3p(+) (0)) 1 E (0.....v 1-11), 1), k E [K].
Wrih
s 77,, E (0. U 1), E [T], E [K],
max
S t21 E U-,,,, E [4], k [K],
mmin
1,k
Omin
Ert4g 1,K
2 ta q t0,....uu 1}. & E [K],
p p
Spp
aim to show
WrLto
1 77. E uU, le [4], k [K].
Tmax
Omiu
1,k
2 2 q E (o.....,u), v), 1E [Z]. ke [K],
Omin
preta
to g E (o,
[K]
(79)
rrtte S P,
2 (o
< (1 + 3pC" n) (0%) gE E l,.,,,.,,u k E [K].
2
x
where C² maxk
N₂
min X7
Step 2: Given
(8) and
79
we show
mmax (Wi"") < 2 57, E ++...,,,+++,, le [4].
Umin
(W,"") > 1 2.1 u (0....,.+1),,
1 1e
[Z].
Umin
(FT") > ap. u 1011
o Tmin
(Fi.x) 2 2 200
mE f0...., 1}, E [K].
8
(80)
pr(t-1)
S.
T (@ra) 5 (1 + 3pCr) (80)
u E (0, 1o..... t t+ 1), E S (frl) < (1 - p (00) u (0. (0.....t . + 1}.
Now we show Step I first. (1) We first show
WrL+ Wrb+g
< F7., E (0......), 1 E [T], & e [K].
mmax
(81)
> tdi E u), 1 E [4], k e [K]
Umin
19

---

Under review as a conference paper at ICLR 2023
We have
Writh - W17
-
Wrtt
Lik
In
Σ
91.k
9k
2
(8)
S
np
1
9
rt+
rt+4
11
9=0
9-0
(82)
(180
nph N₂
||xille (/0-1
x1 T.
ykk
(83)
min X
[E(T]
npL 7 |
d1=
Σ 7=0
(1
+ 3pC'))) 1|E
yk
(84)
NB
min A
[E[L]
where (i) is because the norm of concentated gradient is no smaller than norm of one-layer gradient; (ii) results from Lemma [ (iii) comes from (31) in Lemma 4 (iv) is because of the induction assumption. Let 77 < per we have
Wiit W7
P
not N2
4
2
min X
p- dI
Σ 33 [| - 8xl12
(85)
[E[4]
9=0
npL
7
1-1
-1-
v-1
|xillE
Σ
2"
| - -2kll2
Nk
min X [E(2]
4=0
(18)
mpb
1-1
AI-
w-1
|X*lls
2a || - =ull2
Nk
4
min À [E[L]]
q=0
npL(2"
-1)
7
T.-1
11=
1|llll F
l1 vll2
(86)
NR
min X
LE|L)
mpL[(2r - -1)
|| F
7
L-1
l1 1112(1 + 3pCn) 2
Nk
4
min du
LE(L)
mpL(2" -1) N₂
7
L-1
X1
EN (80)
||A1llF
11
2112
4
min X
[E[L]
T 2 1 (3..... L},
1 E (1
where (i) uses < pC (ii) is because II.E.t - yklla S 1 vlla: the last inequality holds if we choose small enough 17. To be more specific, we can choose
min
min [E(T]]
A
1) <
(87)
| (2)
X 2
11/2- - -yl12" (09)
N2.
mineel
By Weyl's inequality, we have
Tmin
Wrr+++1]
Wi.
mmin
WTr
1,k
1 1. LE (3...., L}, k E [K],
mmax
1++++++
< 0 max
(
+ 1/xx < [7. lE (3.....1) L}. k = [K]
(88)
0 Umax
Wrr
F
+ 1
[WT < 77, k [K],
T mmax
2,
G
+ 1
[ - f7.. ke []].
(2) We next show that
0 Omin
Frt+o 1,k
> 4
a E fo..... o}. k E [K].
(89)
20

---

Under review as a conference paper at ICLR 2023
is sufficient to show min
FFttt) 1,k
3 2 j0 & E [K].
Fr.
FT,
o
X Wrr - (xaWilts) 1r
(90)
F
max
(Xx)
WT
(91)
(6) max (Xa)
m0(2" -1) |xxllr (1)
1--1
X1
5 (0")
[1 - y112
(92)
min X [E[L]
where (i) results from the Lipschitz gradient of a in Assumption and (ii) comes from (6). If we choose small enough 7), which satisfies
1 No
<
(93)
max (xx)p(2" 1) [| (3)
(-1
X1- 11 y112. 54.(00)
min
EE(
then we have
| -FTh F 1 2
<
(94)
(3) Next, we show that
1= S.p
(95)
Since have already shown in
81 that max (W S 7T,, minn (W7L+*) 2 1 and we have
shown in 89 that miin (F)
N 7 ao By lemma we have
(9)-1 LN X
AI=L
min A [E(L)
p(0 S G)-- my 1-- 2gg min ao.k
S p.
(96)
kE[K]
(4) Next, we prove
Du (0%tt) < (1 + ()) (0%*), a E (O,...,,u, Ee [K].
(97)
We show
Dx (0 (1 + 3pC'n)) Dx (0%')
(98)
First, we need to show dy has Lipschitz gradient within [ort+e-1, ort+y.. This is similar to the proof
of (50p in Lemma 8 So we don't include the details here. It is easy show that, for ort 1,5
or grtte-1 + s(Or+v 0% 0 ), there is max (mmax (WItte-I,e)
mmax (WLk
(witte-1) ))
S 77.. So
similarly we can derive the Lipschitz constant
LVL.
2(L--1)
XL
LVL Nx
Qx- =
| 1
+
R') R' [|22 yk 11
Nx
4
min Xi EE(L)
(99)
such that Vs E [0, 1).
9k
+ 1.s
9k
S Qul10
0xt--1111 1/2.
(100)
2
With Lipschitz gradient within [0rito-1 grttt) by Lcmma 5 we have
2 (0r+ty) < 4 (0)+t=1) + (v (0rtov-) 0.tt0 0rt+o) +
Qs
grt+v-
0
|
2
2
(101)
2b (0)++=11) + (gf r -
199
+
Qx
|
aor--r- 1 112
(102)
Qx
ty (0rt+n-1) 1) + 17 119% 1-ttt-11
||2
11
||2
17
2
9
-rr+to1
(103)
< D. (0r++0-1) + upp 10 +
11,-
Qk 2
p²
rttu-1
(104)
2
21

---

Under review as a conference paper at ICLR 2023
Let 17 Qep
T we have the above inequality
4 (0 S 4b (0 + no 11% --+--11
112 +
Qk " p²
19
2
(105)
2
tb (0
+ pm 11%
1 1
(106)
3.
7
2(1--1)
< 2 (DRtto)
L 2 (0rt+U-1).
(107)
N₂
4
min X
tE(T.)
where the third inequality comes from 31 in Lemma
Recall C² == max( 1
No (7)
2(2-1)
x
min (E
we have
D (O s th (ON+*) (1 3pC'n).
(108)
Now Step 1 is proved. Next we show Step 2. (1) Show
max (WT")
2 Nr uE (0, 1t..,,+++]]] 1E [4]
(109)
min (WT")
A E (0,1,...(+1] le (3. (3....,, L}
Define (00)) be the stochastic gradient over layer of each client. Denote zirlto
K
Dx We have No
N
[ wP 1)
+ 9 grrut + ..... -.rttr-111
(110)
1)
g1.u+t11 2|
(111)
5raio
2
(112)
w=0
we have pr+ S p. So by definition of p we have llg l| S 011 1|2. Then easy to verify that the assumptions in Lemma
By Step we know for v E {0, 1o..,,,...r--. 1-
8 are satisfied,
where A Ar.. Q+ is defined in (63) and A = 1 3pC'n. Then by Lemma 8 if n p we have
X ||
(7)
1-1
À d1
En
(2"
1)
11 2ll2
(113)
N
4
min
v=
u=0
IE L
Using the definition of P
X| e
(I) 1-1 (2" - 1), we have
N
pL||X| IE
7
L-1
2
(2 1)
11 v1l2
(114)
N
4
min
v=
w=0
LE 4)
S mpp
Σ
|| 2l122
(115)
min A
[E[L]
u=0
À -
S npp
Σ
(1 3pCm) $152 2112,
(116)
min X x==
[E[1]
(117)
22

---

Under review as a conference paper at ICLR 2023
where the last inequality comes from the induction assumption. Now let s v1 + 3pCn, if we choose 17 < pC we get
dI-LL
g gr 12 S npp
Σ(1 3pC 2ll2
min X
M=O o=0
a=0 (E(L]
= -pp X1
1-112 ff - y112
min À1 x=0 [E|L]
S npp λ1= ST+1
(S + 1)1ssh 51l2
min X 52 [E[L]
npp XI-L ST+1 .3
min A 3pCn 1 - y [E|4
(118)
By Lemma we have ST S (0)
Additionally, S S 2, therefore, we have
71--I 25T 3 11 yl12
2 S npp
(119)
min d iE[r]]
3pCn
4=0 v=0
1 P d
25 (89)
11 vl12
C
min A
e
[E[L]
ς (89)
1152 v/12
(120)
L|| |F (2)
L-1
min A
SEI
x 2/d \.. 1 (3.
L).
1, E [1,2}.
where the last inequality is from 688. So by Weyl's 's ineuality, we have
(r((t1)
(WTT) _/ 1.2m. L (....., L},, k E [K],
Tmin
Gmin
Wr((t+1) S Fmax
(W:+)) + 1 < 3T LE (3..... LL.. k E [K].
Tmax
(121)
WPy) S 1 + max
(Wit)= I 3d., KE [K],
Omax
Wh') S 1 + o max
With) S 3 27,, k E [K].
0 mmax
(2) Show
1
0 mmin (FT") >
7ap u E +0.. l [1].
(122)
Similarly, we have
p p2(++2)_ r2 = -110 (XWr(tt) - -a (XW.)) |
(123)
mmax (X) [Pr(et1) - -
(124)
2
< (00)
(x)
11 vll2
(125)
|| (2)
L-1
min
1E(2)
2
< (80)
< |||||
152 v112
(126)
L|| || (3)
A
min A
1012)
(10)
<
(127)
2
23

---

Under review as a conference paper at ICLR 2023
where (i) is because is 1 L-Lisschitz; (ii) comes from 120)), and (iii) is because 69 in B.2 So
similarly by Weyl's inequality, we have minn (M7(+)))
min (1T)) Cuu 2
20
(3) Show
1 2
Mmin
(FT
2 2
u (0,....6+11] 1 [L]
(128)
Similarly, we have
1,6
(((()))
FL,
10 (Xali)( (xxm9))
(129)
[ -
mmax mmax(Xs)
(130)
ạ (0))
max (Xx)
|1 v1l2
(131)
L||X| || (2)
2-1
min A IE
E (80)
[1 1/12
(132)
|| (2)
1-1
X
min X
(c]4)
(66)
(133)
where (i) is because a is 1 L-pisschiz: (ii) comes from 120), and (iii) is because 66 in
B.2 So
similarly by Weyl's inequality, we have miin (F1(+1) a (FI,)) Go. 200.
200.
(3) Show
((++)) Sp.
(134)
Since we have already shown in 8 that max (wr(ht)) have shown
3 A1, min
(Wi(ttt)
2
2
1 22, and we
(89 that Gmin (FT" (1+1))
ap. By Lemma
we have
XI=L 3 1- LN
min A
p+(++)) <
(2) my b )g b
16)2)
min do kE[K]
< p.
(135)
(4) Show
① (0ru)
& 3pCn) " (0"), u ,++.,,,,,,1,, 1E [4].
First, similar to the proof of 50). we can derive
LVL
3
2(L-1)
X2 min X N
LVL
Q =
X
+
(1+ RIJ2 - -vl2, (136)
N
2
[E[L]
T.
where R =
II
max (1, 7))) such that Vîrt, = Ort + s(rr((+)) - -rr), E [0, 1]. we have
p=1
- S <0/
0rd -rr
(137)
2
Then by Lemma
we have
(or(++1)
(ōrt 11"
n9 x
Q
+ (0rl) 17 (9 ,9 ... gr
+
"
9
grt
+
9
(138)
2
+ (0 + 17 |19 11 + - ||,
Q 2
Erd
+
5rl
+
||
2
24

---

Under review as a conference paper at ICLR 2023
By 49 in Lemma 8 if n
pa:
have A = 2, and we have
pL||X|a
7
L-1
11-
mt + + 1
g 122 2
(2"
1)
|1
y112 - pp
11
y112.
N
4
min [E[L]
min
[
(139)
Then we have
+ +n|19"|| ① (or(422) 5 =0(0')+nll0""
12 + gr
Q 2 5 +...+ - ?
(140)
X2 1
$ x0 + =1110*112 pp
15 u1l2 + " 1|
p2
11
v1l
min X [E|L]
min X
[E|L]
(141)
Q 2 2
X2
2 (0
n 1110*1112 pp
| 112 +
p2
||
-111
min X
min
X
[E|L]
[E|4]
(142)
L| X
3
X 1ー
Q 1 2113
X
+ (0')) +
U
p2
1
v1
N
2
min Xp
2
min
X?
iE(L]
(143)
Let -1x 19)2-1
where (i) comes from 31 in Lemma 4
QpPN Qp(2r-1) we get
(gr((t)) s 1 (0rt) + mpPL||XI
X
11
v11 + - "| 22pppp2
Q
X
lIft
v112
N
min X?
2
min [E(L)
X?
(E(L]
(144)
npPL||X|
X|I
(3)
L-1
X2
$ + (0Tt)
+
-
1 v11
2
N
2
min X?
(E(T)
3
X2
2 (0
1 ++3
2
min X2
[E[4]
Recall C' = -PL|XX |r (3)
X
then we have
min X7 EE
+ ( 1 <1+330C7)
3pCm) 1 (0"t)
(145)
(5) Show
[[((0((1) ( wCn)" (0%) u (0, 1, 1,...,++1)
By 138 have
Q +....4 15ttr-1) + 112
(0-((1)) < < (0
Ert
+
(146)
2
25

---

Under review as a conference paper at ICLR 2023
Given 0*t, take expectation of the stochastic gradient on both sides conditioned on H and the past, we get
Q
X
} s (0"t) - -n " gg +... +....0 ggtht--)
p p2
|
v
min X [E[4]
1-1
Q
X -
I E (8 - 17 rgg"t) - n TM
9 uu -g"")
p p2
1 0122
2 1|
min X? [E[L]
==1
Q
X
I E (0rl) و + nlll" x
grhto 9"d 12 +
11 p2
2
p2
1=
|1 - v1
min
X7
1=1
[E[4]
(147)
Now is easy to verify the assumptions in Lemma are satisfied. Let A, = 77., Q defined in (36
A = 1 + 3pC'n S 2, by (51) in Lemma we have
12L(22
71--I. min X EE[L
Σ g gtt grd
Q 1I vlla
(148)
N
4
Plug (48) into 147). we get:
Q 2
X
E ((((0(()))
< E + (0rl) 1111"" +
nlll 112 x || Σ grtto 3-1112 +
2
2
p2
|
-13
min LELL]
Xi
v=
< E 1 (ōrl) - 1r 11110"111 + 11 x npL(2" - -1]|| F
7
L-1
K Σ
o x
N
4
A=1
|1 - 2ll2 + Q
x
/² p² p2
|1 2112
min A
2
min X?
[E[L]
[E
(1)
$ E + (#"t) - np 1|
- -1)||
21
2
Q II
x
N2
8
x
X
||
v112 +
Q
2
p2
Xz
11
min X?
min
X
[E[L]
[E
(41)
2(b-1)
E
+ (r
77 N2
2(1-2)
r
11
-11
2
:=p'
K Σ
L22(22 - 1)[[
1 (2)) /--1
Q
2 p2
X
x
I
-112
N2
2
min X [E(L)
B
where (i) uses (3] to provide an upperbound for ||g I]. (ii) uses 28 to provide a lower bound for
[|. Let 1) < 28. we have
E ((
}
< E Φ (0"t) - ' v1l2 + BISE -v12]
(149)
< E D (0rt) (1 nnp'']
(150)
1 2(1-1)
= El (#rt)
1 17 N
g ((1-
X2 22.0
(151)
2
26

---

Under review as a conference paper at ICLR 2023
(1) 123111112 11 22 20.
Let μ
we have
E B[ (C1-pCn) ( El (8')),
(152)
where pC pl.
Now we summarize the choice of it should be smaller than all the following quantities:
1
1
1
min {mingg]) 7 6
pC pmax((ux
pC μc' -112--1)
X (3) 2-1
1 11.2 - vl1 E0100)
Nu
minrett] Ài
1 Nu
(153)
maxx ((2) &lll (3)
A1 mingel: d
JL,k
(00
Remark To satisfy the initialization assumptions defined in (69) and (68), we initialize the neural network coefficients such that we have Å1-L O(1/e). Note from the definition of p' in (152) that this implies yl O(22.1.)
(11/e). Also, note from the choice of step-size in 153) that, we have 1 O(e x 1/A1 - = (c)²). Note that this follows from the fact that is smaller than each quantity defined (153) above. Thus, we have p'm = (1) and we can always choose 7 c/pl for some (0, 1), which guarantees linear convergence of the objective in each communication round (see Theorem
C EXPERIMENT SETTING AND RESULT
C.I MODEL AND PARAMETER SETTINGS:
To analyze the performance of FedAvg-SGr SGD the MNIST data set, fully-comnetted neural network (MLP) with ReLU activation. We set the hidden-layer size to be 32 (resp. 1, 000) for the small (resp. large) network. We choose the mini-batch size m 10 and choose the number of local steps to be r 10. Using the above network, we also compare the random initialization with the special initialization strategy (23), (24g with MNIST and Fashion MNIST dataset. For the CIFAR-1O data set, we analyze the performance of FedAvg-SGD on two network architectures convolutional neural network (CNN) and ResNet. We design the smaller CNN using two 5 X 5 convolutional layers followed by 2 X 2 max pooling, each has 6 and 16 channels, connected by fullly-onnected layers with 120 and 84 hidden neurons. For larger CNN, we use three 3 x 3 convolutional layers each with 128 channels followed by 2 x 2 max pooling. The ReLU activation function is used after each hidden layer for smalVlarge CNN. For ResNet, we compare the performance on ResNet18 8 with ResNet50 architectures. For both the CNN and ResNet, = 5. We randomly sample 10
single hidden-layer
we use a mini-batch size of m = 32 and number of local steps to be r rer=b clients in each epoch and perform FedAvg-SCr SGD for more efficient training.
C.2 EXPERIMENT RESULT FOR MNIST
1200
MNIST Training Loss
MNSST Test
1.0
Boxplot Nonild
id_32
1000
1000
0.8
noniid_32
Teet Arrurey
800
nonid. 1000
0.6
nonlid 32
nonid, 1000
nonlid_1000
nonidd332
6.0
20
40
60
80
100
0
20
40
60
80
100
10
20
30
40
50
60)
70
80
00 100
Traning Epocho
Thsining Epochs
Thiining Epocrs
Figure MNIST with MLP: Comparison of FedAvg on large and small size MLP.
27

---

Under review as a conference paper at ICLR 2023
MNIST Training Loss
Citar10 Training Lass with CNN
Cifar10 Training Loss with ResNet
Thiining loss
MMM
Monnnnn www
3.5
Treniing
5.0
4.5
4.0
60
100
Epochs
Training
Figure 5: Log-scale loss.
28


Reviews:
[{"review_id": "m0kuj1HQmW", "reviewer": "Reviewer_Er5f", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of federated learning when optimizing with overparameterized multi-layer neural networks. More specifically, the author shows that with a specialized initialization, FedAvg has a linear convergence rate when solving the federated learning problem with overparameterized multi-layer neural networks.", "summary_of_the_review": "The problem, i.e., how the overparameterization will affect the performance of FedAvg, considered in this paper seems to be interesting. However, the results provided in the current paper are not strong enough. The main question I have is whether the FedAvg can outperform the naive mini-batch baseline in this setting. In addition, what is the generalization guarantee of the proposed method?", "strength_and_weaknesses": "The strength of the paper:\n1. It shows a linear convergence rate of FedAvg under certain conditions.\n2. Experiments validate the effectiveness of theoretical guarantees.\n\nThe Weaknesses of the paper:\n1. The presentation is not clear. There are lots of unclear definitions, which makes the paper hard to follow. (see detailed comments in next section)\n2. Assumption 3 seems to be a strong assumption on the activation functions. What are specific examples of this kind of activation function?\n3. It is unclear whether FedAvg is better than the naive mini-batch SGD baseline in this setting. For example, if we do not perform local updates and instead compute $r$ stochastic gradients at the same point and send the mini-batch gradients to the server and then update the model, whether FedAvg can outperform this mini-batch SGD baseline? According to Lemma 1, such a procedure can reduce $\\rho$, and it will also avoid the error introduced by local updates as in Lemma 2.\n4. The paper only shows the convergence guarantee of FedAvg. Therefore, it is unclear the generalization performance of FedAvg using overparameterized multi-layer neural networks. Note that most of the existing works consider a stochastic problem, and thus their convergence guarantees of FedAvg can serve as the generalization guarantees.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fjOZQ4WSYUa", "reviewer": "Reviewer_vggk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an interesting solution for overcoming the data heterogeneity of FedAvg algorithm. The theoretical result indicates that for a specific structure of neural network, FedAvg can achieve nearly zero loss at a linear convergence rate without making any additional assumptions on data distribution. The empirical result further validates this result. ", "summary_of_the_review": "This paper fills in the blank of applying overparameterized model to FedAvg algorithms and achieves the expected result: linear convergence rate. But I have two major concerns: (1) the unclear definition of data heterogeneity; this paper may fall into an existing scoop of federated learning research. (2) the uncommon constraint on the step size; the theoretical result doesn't match some existing overparameterized models research.  From these two reasons, I tend to reject.", "strength_and_weaknesses": "***Strength***\n* It is the first convergence analysis of FedAvg over multi-layer neural network. And it is interesting to see it achieves linear convergence rate without additional requirements on data distribution.  \n\n***Weaknesses***\n* I feel that the linear convergence of overparameterized model in the federated learning scenario is trivial. See the following two references. The data heterogeneity is characterized by the gap between global minimum and average of client minimum [Li2019] or the gradient noise at the global minimizer [Khaled2019]. For overparameterized model, both of those value are zero. It generally says that for overparameterized model there is no \"data heterogeneity\". I would be expecting to hear how data heterogeneity is defined in this paper and how it is different from those existing definitions. \n\n*[Li2019] Li, X., Huang, K., Yang, W., Wang, S., & Zhang, Z. (2019, September). On the Convergence of FedAvg on Non-IID Data. In International Conference on Learning Representations.*\n\n*[Khaled2019] Khaled, A., Mishchenko, K., & Richtárik, P. (2019). First analysis of local gd on heterogeneous data. arXiv preprint arXiv:1909.04715.*\n\n\n* I agree that Theorem 1 indicates that FedAvg-SG attains a linear rate. But according to Remark 8 in the appendix, it appears that the choice of learning rate is very sensitive, it must be of the order $\\Theta(\\epsilon^2)$. If it is smaller, for example, $\\eta =  \\Theta(\\epsilon^3)$, then the rate cannot be linear; and if $\\eta =  \\Theta(\\epsilon)$, the convergence is not guaranteed. I don't think this result is satisfactory. For other research on overparameterized models, the following two references [Du2018] and [Ma2018] show the linear convergence rate can be achieved with a step size independent w.r.t. $\\epsilon$. It is not clearly clarified in this paper why there is such uncommon constraints on the learning rate.\n\n*[Du2018] Du, S. S., Zhai, X., Poczos, B., & Singh, A. (2018). Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054.*\n\n*[Ma2018] Ma, S., Bassily, R., & Belkin, M. (2018, July). The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In International Conference on Machine Learning (pp. 3325-3334). PMLR.* \n\n\n===================================\n\nUpdates after Rebuttal:\n\nI have read other reviews and the author's responses. I still tend to reject this paper. (1) As stated by the author in the rebuttal, this work uses a different definition of the data heterogeneity from [Li2019] and [Khaled2019]. So I don't think this result solves the standard heterogeneity issue in the federated learning. (2) Also, compared to prior over-parameterized model studies, this paper has non-standard constraints on the learning rate. I agree that multiple local updates will make -level learning rate invalid but it makes this paper meaningless: I can always run one-step local update at each edge device with a constant learning rate then applying [Du2018] and [Ma2018] to standard SGD with mini-batches; it also has a linear convergence rate. (3) Besides both above, I agree with Reviewer Er5f: there exists solid theoretical results showing that the minibatch SGD is always not worse than the federated averaging approach, so the motivation of sololy studying FedAvg is weak.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "bn6ptYTYah", "reviewer": "Reviewer_3BVM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence performance of FedAvg for training (pyramidal topology) overparameterized deep networks. Specifically, under certain assumptions, the authors design a special initialization strategy for FedAvg and prove linear convergence rate of FedAvg on training such overparameterized models without making assumptions on data heterogeneity. The authors also provide experimental results on MNIST and CIFAR10 under different data heterogeneous settings to study the effect of model size in FedAvg training.", "summary_of_the_review": "This paper studies an important problem in FL optimization (convergence rate of FedAvg under overparameterized regime) and obtains interesting theoretical results, I would recommend acceptance.", "strength_and_weaknesses": "Strength:\n\n1. Given FedAvg is a widely used algorithm in FL and the interpolation regime is an interesting regime in FL. Built on the previous results on overparameterized models with pyramidal topology [NM2020], this paper makes important contributions to provide linear convergence rates of FedAvg in this setting.\n\n2. The theoretical results are derived without assuming heterogeneity conditions.\n\nWeaknesses:\n\n1. The setup of experiments in Section 5 do not align with the theoretical results. I agree it is interesting to investigate the convergence performance of FedAvg under the settings in Sec 5. I would like to see the empirical performance of FedAvg with the specified initialization strategy for solving a problem where all the assumptions (network architecture and activation), which could better corroborate the theoretical results. Moreover, this could be helpful for examining the tightness of the convergence analysis (e.g., the theoretical linear convergence rate v.s. the actual linear convergence rate).\n\n2. [minor] The non-iid setting considered in Sec 5 is not very challenging, it might be interesting to study the performance of FedAvg under more extreme data heterogeneity conditions, e.g., settings in Table III in [LDC+2021].\n\nQuestions:\n\n1. The training loss is pretty large in Figure 2 and Figure 3, is the training loss in those plot the summed loss or averaged loss? Also, it might be helpful to visualize the training loss in log scale to study the linear convergence of FedAvg.\n\n\nReferences\n\n[NM2020] Global convergence of deep networks with one wide layer followed by pyramidal topology. Q. Nguyen and M. Mondelli. NeurIPS 2020.\n\n[LDC+2021] Federated Learning on Non-IID Data Silos: An Experimental Study. Qinbin Li, Yiqun Diao, Quan Chen, Bingsheng He. https://arxiv.org/abs/2102.02079. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b5VJkecblJF", "reviewer": "Reviewer_oX5J", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves under certain assumptions, FedAvg can converge linearly to the optimal solution even under heterogeneous clients. The convergence relies on specific network architectures and parameter initialization.", "summary_of_the_review": "Due to the lack of technical novelty, I recommend rejection.", "strength_and_weaknesses": "Strength:\n1. A global and linear convergence result for FedAvg. In this sense, the result is new and interesting.\n\nWeakness:\n1. Compared with the result for centralized training (Nguyen and Mondelli, 2020), the technical contribution of this paper is questionable. The network architecture, the initialization, as well as most of the proof, are from Nguyen and Mondelli (2020). While in Remark 5, the technical novelty compared with it is discussed, either extending to federated training or dealing with stochastic gradient is not significant or novel enough.\n\n2. The analysis of federated training is likely to be superficial or unrealistic in that, the total update length within each communication round, decreases as the local training steps increases. In particular, the step size $\\eta \\asymp A^{-r}$ ($A > 1$) where $r$ is the number of local steps so in total, $\\eta r$ decreases exponentially. For one thing, this is never the real world case. Usually, each local client will train for several steps with constant step size and then aggregate on the server side. More locally training steps makes the averaging step harder, while in this paper's configuration, more local steps mean the total change of the parameter becomes even smaller, thus averaging also become easier. This lead to the theoretical aspect: this kind of configuration makes the total local updates within $r$ steps so small, that the first-order approximation is precise enough. This makes the $r$-step update FedAvg no harder than the $1$-step update FedSGD. It is then trivial to show that FedSGD indeed can handle arbitrary heterogeneity in the clients.\n\n3. The presentation needs further polishing. I found several typos and notation inconsistencies in the equations. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject