On the Convergence of Federated Averaging under Partial Participation
  for Over-parameterized Neural Networks
Federated learning (FL) is a widely employed distributed paradigm for
collaboratively training machine learning models from multiple clients without
sharing local data. In practice, FL encounters challenges in dealing with
partial client participation due to the limited bandwidth, intermittent
connection and strict synchronized delay. Simultaneously, there exist few
theoretical convergence guarantees in this practical setting, especially when
associated with the non-convex optimization of neural networks. To bridge this
gap, we focus on the training problem of federated averaging (FedAvg) method
for two canonical models: a deep linear network and a two-layer ReLU network.
Under the over-parameterized assumption, we provably show that FedAvg converges
to a global minimum at a linear rate $\mathcal{O}\left((1-\frac{min_{i \in
[t]}|S_i|}{N^2})^t\right)$ after $t$ iterations, where $N$ is the number of
clients and $|S_i|$ is the number of the participated clients in the $i$-th
iteration. Experimental evaluations confirm our theoretical results.
Xin Liu, Wei li, Dazhi Zhan, Yu Pan, Xin Ma, Yu Ding, Zhisong Pan
# A Neural Tangent Kernel View on Federated Averaging for Deep Linear Neural Network

###### Abstract

Federated averaging (FedAvg) is a widely employed paradigm for collaboratively training models from distributed clients without sharing data. Nowadays, the neural network has achieved remarkable success due to its extraordinary performance, which makes it a preferred choice as the model in FedAvg. However, the optimization problem of the neural network is often non-convex even non-smooth. Furthermore, FedAvg always involves multiple clients and local updates, which results in an inaccurate updating direction. These properties bring difficulties in analyzing the convergence of FedAvg in training neural networks. Recently, neural tangent kernel (NTK) theory has been proposed towards understanding the convergence of first-order methods in tackling the non-convex problem of neural networks. The deep linear neural network is a classical model in theoretical subject due to its simple formulation. Nevertheless, there exists no theoretical result for the convergence of FedAvg in training the deep linear neural network. By applying NTK theory, we make a further step to provide the first theoretical guarantee for the global convergence of FedAvg in training deep linear neural networks. Specifically, we prove FedAvg converges to the global minimum at a linear rate \(\mathcal{O}\big{(}(1-\eta K/N)^{t}\big{)}\), where \(t\) is the number of iterations, \(\eta\) is the learning rate, \(N\) is the number of clients and \(K\) is the number of local updates. Finally, experimental evaluations on two benchmark datasets are conducted to empirically validate the correctness of our theoretical findings.

 Federated learning, Deep linear neural network, Neural tangent kernel

## I Introduction

Federated learning (FL) is an efficient and privacy-preserving distributed learning scheme. In the framework of the centralized distributed learning, there exists a server node for communication with distributed clients. In general, the server updates the global model through collecting local data from clients. However, this approach has several drawbacks. Firstly, it is not suitable for the scenarios with high privacy requirements. For instance, the diagnosis data of the patient can not be shared and collected due to the regulation [1], which prevents data collection from clients. Secondly, some distributed devices are sensitive to the communication and energy costs, such as the wireless sensor which has limited battery capacity and large latency in the network. As a result, it is difficult to support frequent communication between the server and clients. To address these problems, McMahan _et al._[2] proposed the Federated Averaging (FedAvg) algorithm, in which the updating of the model is conducted on clients to prevent transmitting private informations. Meanwhile, each client performs multiple training processes on the local dataset before uploading the local model to the server, which reduces the communication burden.

With the widespread practice of FedAvg, there is a growing interest in providing theoretical guarantees for its convergence. Under convex and smooth assumptions, previous work [3, 4] has proven the convergence of FedAvg based on gradient descent (GD) and stochastic gradient descent (SGD). Nowadays, the neural network has achieved great success due to its extraordinary performance, which makes it a preferred model choice in FedAvg. Recently, progress has been obtained in analyzing the convergence of gradient-based methods for training over-parameterized neural networks [5, 6, 7, 8, 9, 10], whose number of parameters is significantly larger than that of the training samples. For the federated learning, researchers extended these theoretical results to consider the optimization problem of FedAvg in training the two-layer ReLU neural network [11] and the deep ReLU neural network [12, 13]. However, there is no guarantee for the convergence rate of FedAvg in training the deep linear neural network. Despite the simplicity of its framework, the deep linear neural network has attracted considerable attention due to its hierarchical structure similar to non-linear networks, as well as its high-dimensional and non-convex objective function. which makes it a representative model in theoretical community [14, 15, 16, 10].

In this paper, we focus on the optimization problem of FedAvg with GD in training the deep fully-connected linear neural network. Specifically, our contributions are as follows

* We first establish the recursive formulation of the residual error of the FedAvg in training the deep linear neural network, which is closely related to an asymmetric coefficient matrix. Based on the over-parameterized assumption, the spectrum of the coefficient matrix is derived using NTK theory.
* Then, we provide the first theoretical guarantee for the global convergence of FedAvg by analyzing its residual error. Specifically, FedAvg can converge to a global minimum at a non-asymptotic linear rate \(\mathcal{O}\big{(}(1-\eta K/N)^{t}\big{)}\), where \(t\) is the number of iterations, \(\eta\) is the learning rate, \(N\) is the number of clients and \(K\) is the number of local updates. Moreover, the required network width only has
a linear dependence on the network depth.
* Finally, we conduct experiments on two benchmark datasets to empirically validate our theoretical findings. The result shows the correctness of our theoretical findings.

## II Related works

### _Federated learning_

The server node uses the collected client-side model to update the global model, thereby enabling the acquisition of a global model without accessing private data. To further reduce communication costs, [17] exploited model sparsification and quantization compression while minimising the impact on model performance. To address the problem of limited communication and computational resources, [18] proposed an adaptive approach that makes a balance between the number of local update rounds and communications. [19, 20] proposed gradient compression methods to reduce the upload of server data on client nodes. To address security concerns in federated learning,[21] considered a secure aggregation approach. [22, 23] exploited differential privacy (DP) by adding noise. [11] investigated the convergence of FedAvg algorithm when training an over-parameterised two-layer ReLU neural network, which demonstrates that the algorithm can converge to a global minimum at a linear rate. Furthermore, [12] analysed FedAvg in training a deep ReLU fully connected neural network, which establishing its convergence rates.

### _Deep linear networks_

The deep linear networks is only linear maps between input and output space, which leads to a simple formulation of the optimization problem. However, its loss landscape is non-convex due to the existence of the layered structure. Recent works mainly focus on investigating its characteristics to promote the understanding of practical non-linear networks. One line of researches analyzed the properties of critical points (e.g., the gradient is zero). In 1989, Baldi _et al._[24] conjectured that all local minimums (e.g., the gradient is zero and the Hessian is positive semidefinite) of deep linear networks are global minima. Kawaguchi [25] was the first to prove this conjecture by extracting the second-order information from the local minimum. Subsequent work extended this result to different settings, such as few assumptions [26] and arbitrary loss functions [27]. However, the above results are insufficient to provide convergence guarantees for gradient-based optimization methods.

To establish the theoretical convergence result for the deep linear network, some work considered the trajectory induced by gradient-based methods. Shamir [28] showed that GD converges with at least \(exp\big{(}\Omega(L)\big{)}\) iterations for a \(L\)-layer linear network, where all layers have a width of 1 and the initialization scheme uses the standard Gaussian. However, this result only fits for narrow networks. Later, Du _et al._[29] proved that GD exhibits a linear convergence to the global optimum for a wide deep linear network, but the lower bound of the width scales linearly in the depth. Hu _et al._[30] analyzed the effect of the orthogonal initialization in the deep linear network, showing that the required width is independent of the depth. Zou _et al._[14] provided the convergence analysis for both GD and stochastic GD in the training of deep linear ResNets.

## III Problem Setting

### _Notations_

We use lowercase, lowercase boldface and uppercase boldface letters to denote scalars, vectors and matrices, respectively. The other notations are introduced in the Table I.

### _Preliminaries_

The FedAvg involves the following four steps:

1. In the \(t\)-th global round, the server broadcasts the global model to each client.
2. Each client \(c\) initializes its local model with the global model and updates using GD for \(K\) local steps.
3. After all local updates finish, each client sends its local model to the server.
4. Finally, the server averages all local parameters to derive a new global model.

FedAvg repeats the above procedures with \(T\) global rounds. The framework of the algorithm is provided in Fig 1.

For the architecture of the model, we consider a \(L\)-layer fully-connected linear neural network \(f:\mathbb{R}^{d_{in}}\rightarrow\mathbb{R}^{d_{out}}\)

\[f(\mathbf{W}^{1},\cdots\mathbf{W}^{L};\mathbf{x}):=\frac{1}{\sqrt{m^{L-1}d_{out}}}\mathbf{W} ^{L}\cdots\mathbf{W}^{1}\mathbf{x}, \tag{1}\]

\begin{table}
\begin{tabular}{|c|l|} \hline
**Notation** & **Meaning** \\ \hline \(\otimes\) & The Kronecker product. \\ \(\|\cdot\|\) & The \(\ell_{2}\) norm of the vector or the spectral norm of the matrix. \\ \(\|\cdot\|_{F}\) & The Frobenius norm of the matrix. \\ \(\operatorname{vec}(\cdot)\) & The vectorization of the matrix in the column-first order. \\ \(rank(\cdot)\) & The rank of the matrix. \\ \(\lambda_{max}(\cdot)\), \(\lambda_{min}(\cdot)\) & Largest and smallest eigenvalues of the matrix. \\ \(\sigma_{max}(\cdot)\), \(\sigma_{min}(\cdot)\) & Largest and smallest singular values of the matrix. \\ \(\kappa(\cdot)\), & The condition number of the matrix. \\ \(\mathcal{N}(0,1)\) & The standard gaussian distribution. \\ \(N\) & The number of the clients. \\ \(c\) & The index of the client. \\ \(T\) & The number of the communication rounds. \\ \(t\) & The index of the communication round. \\ \(K\) & The number of the local update steps. \\ \(k\) & The index of the local update step. \\ \(\mathbf{X},\mathbf{Y}\) & The feature matrix and the ground truth. \\ \(\mathbf{X}_{c},\mathbf{Y}_{c}\) & The feature matrix and the ground truth on the \(c\)-th client. \\ \(\mathbf{W}^{i}_{k,c}(t)\) & The parameter of the \(i\)-th layer of the \(c\)-th client in \\  & \(k\)-th local step of \(t\)-th global round. \\ \(\overline{\mathbf{W}}^{i}(t)\) & The \(i\)-th layer of the global model in the \(t\)-th global round. \\ \(\overline{\mathbf{U}}(t)\) & Outputs of the server model in \(t\)-th global round. \\ \(\overline{\mathbf{U}}_{c}(t)\) & Outputs of the server model on \(\mathbf{X}_{c}\) in \(t\)-th global round. \\ \(\mathbf{U}_{k,c}(t)\) & Outputs of the \(c\)-th client in \(k\)-th local step of the \(t\)-th global round. \\ \(\mathbf{U}_{k}(t)\) & The concatenation of the outputs of all clients in \\  & \(k\)-th local step of \(t\)-th global round. \\ \(\overline{\mathbf{\xi}}(t)\), \(\overline{\mathbf{\xi}}_{k}(t)\) & The residual error of the global model \(\overline{\mathbf{\xi}}(t)=\overline{\mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\). \\ \(\mathbf{\xi}_{k,c}(t)\), \(\mathbf{\xi}_{k}(t)\) & The residual error of the local model \(\mathbf{\xi}_{k,c}(t)=\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\) and \(\mathbf{\xi}_{k}(t)=\mathbf{U}_{k}(t)-\mathbf{Y}\). \\ \hline \end{tabular}
\end{table} TABLE I: Summary of notations
where \(\mathbf{x}\in\mathbb{R}^{d_{in}}\) denotes the feature, \(\mathbf{W}^{1}\in\mathbb{R}^{m\times d_{in}}\), \(\mathbf{W}^{L}\in\mathbb{R}^{d_{out}\times m}\) and \(\mathbf{W}^{i}\in\mathbb{R}^{m\times m}\) (\(1<i<L\)) denote the parameters of the network for each layer, respectively. Each entry of \(\mathbf{W}^{i}\) is identically independent initialized with the standard gaussian distribution \(\mathcal{N}(0,1)\). It is noted that the coefficient \(\frac{1}{\sqrt{m^{L-1}d_{y}}}\) in Eq.(1) is a scaling factor according to [8].

Under federated learning setting, we aim to minimize the sum of loss \(\mathcal{L}\) over all clients

\[\min_{\mathbf{W}^{L},\cdots,\mathbf{W}^{1}}\mathcal{L}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1}). \tag{2}\]

For the loss function, we use the square loss

\[\mathcal{L}_{j}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1}) :=\!\frac{1}{2}\!\sum_{i\in S_{j}}(f(\mathbf{W}^{L}\!,\!\cdots\!,\mathbf{W }^{1};\mathbf{x}_{i})\!-\!\mathbf{y}_{i})^{2}, \tag{3}\] \[\mathcal{L}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1}) :=\frac{1}{N}\sum_{j=1}^{N}L_{j}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1}), \tag{4}\]

where \(\mathbf{x}_{i}\) and \(\mathbf{y}_{i}\) denote the feature and the label of the \(i\)-th training instance. For brevity, we denote the outputs of the neural network \(f\) on \(\mathbf{X}\) as

\[\mathbf{U}=\frac{1}{\sqrt{m^{L-1}d_{out}}}\mathbf{W}^{L:1}\mathbf{X}\in\mathbb{R}^{d_{y} \times n}, \tag{5}\]

where \(\mathbf{W}^{L:1}=\mathbf{W}^{L}\mathbf{W}^{L-1}\cdots\mathbf{W}^{1}\).

Based on (1) and (3), the gradient \(\frac{\partial\mathcal{L}_{c}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1})}{\mathbf{W}^{1}}\) on each client \(c\) has the following form

\[\frac{\partial\mathcal{L}_{c}(\mathbf{W}^{L},\cdots\mathbf{W}^{1})}{\partial\mathbf{W}^{i }} \!\!\!=\!\!\frac{1}{\sqrt{m^{L-1}d_{out}}}\!\mathbf{W}^{L:i\!+\!1}\!\left[\! \mathbf{U}_{c}\!-\!\mathbf{Y}_{\!\!\mathbf{\lambda}}(\mathbf{W}^{l-1:1}\mathbf{X}_{c})^{\top}\! \right.\!\!. \tag{6}\]

According to the procedures of FedAvg, the optimization of the deep linear neural network involves local update and global update.

**Local update**. For each client \(c\), the local parameter \(\mathbf{W}^{i}_{k,c}(t)\) of each layer \(i\) for local iteration \(k\) at the global iteration \(t\) is updated by GD as:

\[\mathbf{W}^{i}_{k+1,c}(t)=\mathbf{W}^{i}_{k,c}(t)-\eta\frac{\partial\mathcal{L}_{c}( \mathbf{W}^{L},\cdots,\mathbf{W}^{1})}{\partial\mathbf{W}^{i}_{k,c}(t)}, \tag{7}\]

where \(\eta>0\) is the learning rate.

**Global update**. In the server side, it updates the global parameter by averaging all local parameters from clients as

\[\overline{\mathbf{W}}^{i}(t+1)= \sum_{c=1}^{N}\mathbf{W}^{i}_{K,c}(t)/N. \tag{8}\]

## IV Theoretical Results

In this section, we provide a detailed convergence analysis of FedAvg for training the deep fully-connected linear network. Our proof is composed of two parts: 1) Establishing the connection between two consecutive residual errors. 2) Deriving the closed-form of the residual error to provide a recursive bound.

### _The dynamics of the residual error_

At the \(t+1\) global iteration, the global parameter \(\overline{\mathbf{W}}^{i}(t+1)\) of each layer \(i\) can be expanded as

\[\overline{\mathbf{W}}^{i}(t+1)= \sum_{c=1}^{N}\mathbf{W}^{i}_{K,c}(t)/N\] \[= \overline{\mathbf{W}}^{i}(t)\!-\!\frac{\eta}{N}\sum_{c=1}^{N}\sum_{k=0 }^{K-1}\frac{\partial\mathcal{L}_{c}(\mathbf{W}^{L},\cdots,\mathbf{W}^{1})}{\partial \mathbf{W}^{i}_{k,c}(t)}. \tag{9}\]

For brevity, we denote the accumulated gradient as \(\frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}}^{i}(t)}=\frac{1}{N}\sum_{c= 1}^{N}\sum_{k=0}^{K-1}\frac{\partial\mathcal{L}_{c}(\mathbf{W}^{L},\cdots,\mathbf{W}^{ 1})}{\partial\mathbf{W}^{i}_{k,c}(t)}\).

Thus, the multiplication of the global parameters of \(L\) layers has

\[\overline{\mathbf{W}}^{L:1}(t+1)=\prod\left(\overline{\mathbf{W}}^{i}(t)- \eta\frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}}^{i}(t)}\right)\] \[= \overline{\mathbf{W}}^{L:1}(t)-\eta\sum_{i=1}^{L}\overline{\mathbf{W}}^{L:i +1}(t)\frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}}^{i}(t)}\overline{ \mathbf{W}}^{i-1:1}(t)+\mathbf{E}(t), \tag{10}\]

where the second term contains first-order items with respect to \(\eta\) and \(\mathbf{E}(t)\) contains all high-order items. When multiplying \(\frac{1}{\sqrt{m^{L-1}d_{out}}}\mathbf{X}\) on both sides of Eq.(10), it has the corresponding outputs of the global model as

\[\overline{\mathbf{U}}(t+1)\!=\!\overline{\mathbf{U}}(t)\!-\!\frac{\eta}{ \sqrt{m^{L-1}d_{out}}}\!\sum_{i=1}^{L}\!\!\left(\!\overline{\mathbf{W}}^{L:i+1}(t) \frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}}^{i}(t)}\overline{\mathbf{W}}^{i -1:1}(t)\mathbf{X}\!\right)\] \[\qquad+\frac{1}{\sqrt{m^{L-1}d_{out}}}\mathbf{E}(t)\mathbf{X}. \tag{11}\]

Fig. 1: The framework of FedAvg, in which the solid line represents the upload of the local model, the dashed line denotes the download of the global model and the circles correspond to the procedures of FedAvg.
Taking the vectorization of the second term on the right side of Eq.(11), it has

\[\text{vec}\left(\frac{\eta}{\sqrt{m^{L-1}d_{out}}}\sum_{i=1}^{L}( \overline{\mathbf{W}}^{L:i+1}(t)\frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}} ^{i}(t)}\overline{\mathbf{W}}^{i-1:1}(t)\mathbf{X})\right)\] \[= \frac{\eta}{Nm^{L-1}d_{out}}\sum_{i=1}^{L}\sum_{c=1}^{N}\sum_{k=0 }^{K-1}\text{vec}(\mathbf{T}_{k,c}^{i}), \tag{12}\]

where the first equality uses the gradient Eq.(6) and \(\mathbf{T}_{k,c}^{i}=\overline{\mathbf{W}}^{L:i+1}(t)\mathbf{W}_{k,c}^{i+1}(t)^{\top}(\mathbf{ U}_{k,c}(t)-\mathbf{Y}_{c})(\mathbf{W}_{k,c}^{i-1:1}(t)\mathbf{X}_{c})^{\top}\overline{\mathbf{W}} ^{i-1:1}(t)\mathbf{X}\).

For simplicity, we denote \(\mathbf{M}_{k,c}^{i}=\text{vec}(\mathbf{T}_{k,c}^{i})\). Using \(\text{vec}(\mathbf{ACB})=(\mathbf{B}^{\top}\otimes\mathbf{A})\text{vec}(\mathbf{C})\), it has

\[\mathbf{M}_{k,c}^{i} = \big{(}\overline{\mathbf{W}}^{i-1:1}(t)\mathbf{X}\big{)}^{\top}(\mathbf{W}_{k,c}^{i-1:1}(t)\mathbf{X}_{c})\otimes\overline{\mathbf{W}}^{L:i+1}(t)\mathbf{W}_{k,c}^{L:i +1}(t)^{\top}\big{)} \tag{13}\] \[\ast\text{vec}(\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}).\]

For centralized training setting, the analysis in [8] mainly depends on the spectral properties of a symmetric gram matrix defined by

\[\mathbf{P}(t)=\frac{1}{m^{L-1}d_{out}}\sum_{i=1}^{L} \big{(}(\mathbf{W}^{i-1:1}(t)\mathbf{X})^{\top}(\mathbf{W}^{i-1:1}(t)\mathbf{X})\] \[\otimes\mathbf{W}^{L:i+1}(t)\mathbf{W}^{L:i+1}(t)^{\top}\big{)}, \tag{14}\]

where the eigenvalues of the time-varying \(\mathbf{P}(t)\) can be bounded by applying perturbation analysis.

In light of [8, 11], we abuse the notation \(\mathbf{P}\) to define a similar matrix.

**Definition IV.1**.: _For any \(t\in[0,T],k\in[0,K],c\in[1,N]\), we define a matrix \(P(t,k,c)\) as_

\[\mathbf{P}(t,k,c):=\frac{1}{m^{L-1}d_{out}}\sum_{i=1}^{L} \big{(}(\overline{\mathbf{W}}^{i-1:1}(t)\mathbf{X})^{\top}(\mathbf{W}_{k,c}^ {i-1:1}(t)\mathbf{X}_{c})\] \[\otimes\overline{\mathbf{W}}^{L:i+1}(t)\mathbf{W}_{k,c}^{L:i+1}(t)^{\top }\big{)}. \tag{15}\]

Compared to Eq.(14), the matrix \(\mathbf{P}(t,k)=[\mathbf{P}(t,k,1),\cdots,\mathbf{P}(t,k,N)]\) is an asymmetric matrix, which is non-trivial to directly derive its eigenvalues. Instead, we turn to present the bounds of its eigenvalues by bounding the distance between \(\mathbf{P}(t,k)\) and \(\mathbf{P}(0)\) according to [11].

Along with \(\mathbf{P}(t,k)\), taking the vectorization of both sides of Eq.(11), it has

\[\text{vec}(\overline{\mathbf{U}}(t+1))= \text{vec}(\overline{\mathbf{U}}(t))-\frac{\eta}{N}\sum_{c=1}^{N}\sum_ {k=0}^{K-1}\mathbf{P}(t,k,c)\text{vec}(\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c})\] \[+\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})\] \[= \text{vec}(\overline{\mathbf{U}}(t))-\frac{\eta}{N}\sum_{k=0}^{K-1}\bm {P}(t,k)\text{vec}(\mathbf{U}_{k}(t)-\mathbf{Y})\] \[+\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X}), \tag{16}\]

where the first equality uses Eq.(12) and Eq.(15). For simplifying notations, we use \(\overline{\mathbf{\xi}}(t)=\text{vec}(\overline{\mathbf{U}}(t)-\mathbf{Y})\) and \(\mathbf{\xi}_{k}(t)=\text{vec}(\mathbf{U}_{k}(t)-\mathbf{Y})\) as the vectorizations of the global residual error and the local residual error, respectively. Then, it has

\[\overline{\mathbf{\xi}}(t+1)\] \[= \overline{\mathbf{\xi}}(t)-\frac{\eta}{N}\sum_{k=0}^{K-1}\mathbf{P}(t,k) \mathbf{\xi}_{k}(t)+\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})\] \[= \overline{\mathbf{\xi}}(t)-\frac{\eta}{N}\sum_{k=0}^{K-1}(\mathbf{P}(t,k) -\mathbf{P}(0))\mathbf{\xi}_{k}(t)-\frac{\eta}{N}\sum_{k=0}^{K-1}\mathbf{P}(0)\overline{\bm {\xi}}(t)\] \[-\frac{\eta}{N}\sum_{k=0}^{K-1}\mathbf{P}(0)\text{vec}(\mathbf{U}_{k}(t)- \overline{\mathbf{U}}(t))+\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})\] \[= \underbrace{(I-\frac{\eta}{N}\sum_{k=0}^{K-1}\mathbf{P}(0))\overline{ \mathbf{\xi}}(t)}_{\text{fit term}}\underbrace{-\frac{\eta}{N}\sum_{k=0}^{K-1}(\mathbf{P}(t,k) -\mathbf{P}(0))\mathbf{\xi}_{k}(t)}_{\text{second term}}\] \[\underbrace{-\frac{\eta}{N}\sum_{k=0}^{K-1}\mathbf{P}(0)\text{vec}( \mathbf{U}_{k}(t)-\overline{\mathbf{U}}(t))}_{\text{third term}}+\underbrace{\frac{1}{ \sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})}_{\text{fourth term}}. \tag{17}\]

Then we can obtain the bound of \(\|\overline{\mathbf{\xi}}(t+1)\|_{F}\) through analyzing the four terms in Eq.(17).

### _Theoretical Results_

**Theorem IV.2**.: _Suppose \(r=rank(\mathbf{X})\),\(\kappa=\frac{\sigma_{max}^{2}(\mathbf{X})}{\sigma_{min}^{2}(\mathbf{X})}\), \(\eta=\mathcal{O}(\frac{d_{out}}{L\kappa L\|\mathbf{X}\|^{2}})\) and \(m=\Omega(L\max\{r\kappa^{4}N^{2}d_{out}(1+\|\mathbf{W}^{*}\|^{2}),r\kappa^{4}N^{2} \log(\frac{r}{2}),\log L\})\). With the probability at least \(1-\delta\), for any \(t\geq 0\), FedAvg has the following bound of the training loss for updating the randomly initialized deep linear neural network_

\[\mathcal{L}(t)\leq(1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})^{t}\mathcal{L}(0). \tag{18}\]

**Remarks**. From above theorem, we show that FedAvg is capable of attain the global optimum at a \((1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})^{t}\) rate in optimizing the deep fully-connected linear neural network after \(t\) training iterations. In addition, the increasing of the number of clients slows down the convergence of FedAvg. On the contrary, FedAvg converges faster with the increasing of the local updates. Besides, it is noted that the convergence rate of FedAvg is determined by the ratio \(K/N\). Therefore, the convergence of FedAvg stays in a similar manner when \(K/N\) is fixed.

Now, we turn to introduce the details of the proof. Firstly, we make following three inductive hypothesis.

1. \(\mathcal{A}(\tau)\): \(\mathcal{L}(\tau)\leq\rho^{\tau}\mathcal{L}(0)\), where \(\rho=1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N}\) for brevity.
2. \(\mathcal{B}(\tau)\): \[\sigma_{max}(\overline{\mathbf{W}}^{L:i}(\tau))\leq 1.25m^{\frac{L-i+1}{2}},\quad\forall 1<i\leq L\] \[\sigma_{min}(\overline{\mathbf{W}}^{L:i}(\tau))\geq 0.75m^{\frac{L-i+1}{2}},\quad\forall 1<i\leq L\] \[\sigma_{max}(\overline{\mathbf{W}}^{i:1}(\tau)\mathbf{X})\leq 1.25m^{\frac{L}{2}}\|\mathbf{X}\|,\quad\forall 1\leq i<L\] \[\sigma_{min}(\overline{\mathbf{W}}^{i:1}(\tau)\mathbf{X})\geq 0.75m^{\frac{L}{2}}\sigma_{min}(\mathbf{X}),\quad\forall 1\leq i<L\] \[\|\overline{\mathbf{W}}^{j:i}(\tau)\|\leq \mathcal{O}(\sqrt{L}m^{\frac{j-i+1}{2}}),\forall 1<i\leq j<L.\]
3. \(\mathcal{C}(\tau)\): For any
\[\mathcal{O}(\max\{1,\log(\frac{r}{s})/d_{out},\|\mathbf{W}^{*}\|^{2}\})\| \mathbf{X}\|_{F}^{2}.\]

The derivation of the bound of \(\mathcal{L}(0)\) can be found in [8].

Noted that \(\mathcal{A}(\tau)\) provides the convergence result of FedAvg for training deep fully-connected linear networks, which is also the main part of the Theorem IV.2. \(\mathcal{B}(\tau)\) establishes the bounds for the singular values of the multiplication of consecutive \(\overline{\mathbf{W}}^{i}\). \(\mathcal{C}(\tau)\) ensures the parameter of each layer always stays in a norm ball, where the center is the initial parameter.

Next, we prove the three hypothesis by induction. Specifically, assuming \(\mathcal{A}(\tau)\), \(\mathcal{B}(\tau)\) and \(\mathcal{C}(\tau)\) hold for \(\tau\leq t\), it needs to prove them hold for \(\tau=t+1\). To start with, we consider \(\mathcal{C}(t+1)\) using the hypothesis \(\mathcal{A}(\tau)\) for \(\tau\leq t\).

#### Iv-A1 \(\mathcal{C}(t+1)\)

Before proving \(\mathcal{C}\), we first provide the bound of the accumulated gradient. Note that the distance between \(\overline{\mathbf{W}}^{i}(t+1)\) and \(\overline{\mathbf{W}}^{i}(0)\) involves the gradients from initial to the \(t\)-th iteration. Hence, we bound the gradient as

\[\|\frac{\partial\mathcal{L}}{\partial\overline{\mathbf{W}}^{i}(t)}\|_ {F}= \|\frac{1}{N}\sum_{c=1}^{N}\sum_{k=0}^{K-1}\frac{\partial\mathcal{ L}_{c}(\mathbf{W}^{L},\cdots,\mathbf{W}^{i})}{\partial\mathbf{W}^{i}_{k,c}(t)}\|_{F}\] \[\stackrel{{(a)}}{{\leq}} C_{1}\sum_{c=1}^{N}\sum_{k=0}^{K-1}\|\mathbf{W}^{i-1:1}_{k,c}(t)\mathbf{X}_{c}\|\| \mathbf{\xi}_{k,c}(t)\|_{F}\|\mathbf{W}^{L:i+1}_{k,c}(t)\|\] \[\stackrel{{(b)}}{{\leq}} C_{1}\sum_{c=1}^{N}\sum_{k=0}^{K-1}1.26^{2}m^{(L-1)/2}\|\mathbf{\xi}_{k,c}(t)\|_{F}\| \mathbf{X}_{c}\|\] \[\stackrel{{(c)}}{{\leq}} \frac{8\|\mathbf{X}\|}{5N\sqrt{d_{out}}}\sum_{c=1}^{N}\sum_{k=0}^{K-1} \rho^{k}\|\overline{\mathbf{\xi}}_{c}(t)\|_{F}\] \[\stackrel{{(d)}}{{\leq}} \frac{8\|\mathbf{X}\|}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(t)\|_{F}, \tag{19}\]

where (a) uses Eq.(6) and \(C_{1}=\frac{1}{N\sqrt{m^{L-1}d_{out}}}\), (b) uses \(\mathcal{B}(t)\), Eq.(34) and Eq.(35) that

\[\|\mathbf{W}^{i-1:1}_{k,c}(t)\mathbf{X}_{c}\|\] \[\leq \|\mathbf{W}^{i-1:1}_{k,c}(t)\mathbf{X}_{c}-\overline{\mathbf{W}}^{i-1:1}(t) \mathbf{X}_{c}\|+\|\overline{\mathbf{W}}^{i-1:1}(t)\mathbf{X}_{c}\|\] \[\leq \frac{0.01}{\kappa\sqrt{N}}m^{\frac{i-1}{2}}\|\mathbf{X}_{c}\|+1.25m ^{\frac{i-1}{2}}\|\mathbf{X}_{c}\|\leq 1.26m^{\frac{i-1}{2}}\|\mathbf{X}_{c}\|\]

and

\[\|\mathbf{W}^{L:i+1}_{k,c}(t)\|\leq \|\mathbf{W}^{L:i+1}_{k,c}(t)-\overline{\mathbf{W}}^{L:i+1}(t)\|+\| \overline{\mathbf{W}}^{L:i+1}(t)\|\] \[\leq 1.26m^{\frac{L-i}{2}},\]

(c) uses Lemma (VII.4) with \(\sqrt{1-\frac{\eta L\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})}{4d_{out}}}\leq 1\) and (d) uses \(\sum_{c\in[N]}\|\overline{\mathbf{\xi}}_{c}(t)\|_{F}\leq\sqrt{N}\|\overline{\mathbf{ \xi}}(t)\|_{F}\) according to Cauchy-Schwartz inequality and \(\eta\leq\frac{d_{out}}{50L\kappa R\|\mathbf{X}\|^{2}}\).

Thus, it has

\[\|\overline{\mathbf{W}}^{i}(t+1)-\overline{\mathbf{W}}^{i}(0)\|_{F} \stackrel{{(a)}}{{\leq}}\sum_{s=0}^{t}\|\overline{\mathbf{W}}^{i}(s+ 1)-\overline{\mathbf{W}}^{i}(s)\|_{F}\] \[\leq \eta\sum_{s=0}^{t}\|\frac{\partial L}{\partial\overline{\mathbf{W}} ^{i}(s)}\|_{F}\stackrel{{(b)}}{{\leq}}\eta\sum_{s=0}^{t}\frac{8\| \mathbf{X}\|K}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(s)\|\stackrel{{ (c)}}{{\leq}}\frac{16\sqrt{Bd_{out}}N\|\mathbf{X}\|}{L\sigma_{min}^{2}(\mathbf{X})}\]

where (a) uses the triangular inequality of norm, (b) uses (19) and (c) uses \(\mathcal{A}(\tau)\) for \(\tau\leq t\), \(\sqrt{1-x}\leq 1-x/2\) for \(0\leq x\leq 1\), \(\eta=\mathcal{O}(\frac{d_{out}}{L\kappa R\|X\|^{2}})\) and following bound of \(\lambda_{min}(\mathbf{P}(0))\)

\[\lambda_{min}(\mathbf{P}(0))\geq \frac{1}{m^{L-1}d_{out}}L(0.8)^{4}m^{L-1}\sigma_{min}^{2}(\mathbf{X})\] \[= \frac{0.8^{4}L\sigma_{min}^{2}(\mathbf{X})}{d_{out}}, \tag{20}\]

which is according to Lemma VII.1 and the definition of \(\mathbf{P}(0)\) in Eq.(14). This completes the proof. Then we turn to prove assumption \(\mathcal{B}\) holds at \(t+1\).

#### Iv-A2 \(\mathcal{B}(t+1)\)

Note that \(\overline{\mathbf{W}}^{L:i}(t+1)=(\overline{\mathbf{W}}^{L}(0)+\Delta^{L}(t+1))\cdots( \overline{\mathbf{W}}^{i}(0)+\Delta^{i}(t+1))\) for \(\Delta^{i}(t+1)=\overline{\mathbf{W}}^{i}(t+1)-\overline{\mathbf{W}}^{i}(0)\), it has

\[\|\overline{\mathbf{W}}^{L:i}(t+1)-\overline{\mathbf{W}}^{L:i}(0)\|\] \[\stackrel{{(a)}}{{\leq}} \sum_{s=1}^{L-i+1}\binom{L-i+1}{s}R^{*}(\mathcal{O}(\sqrt{L}))^{ *}1.2m^{\frac{L-i+1-s}{2}}\] \[\stackrel{{(b)}}{{\leq}} \sum_{s=1}^{L-i+1}L^{s}R^{*}(\mathcal{O}(\sqrt{L}))^{*}1.2m^{\frac{L- i+1-s}{2}}\] \[\leq 1.2m^{\frac{L-i+1}{2}}\sum_{s=1}^{L-i+1}(\frac{\mathcal{O}(L^{3/ 2}R)}{\sqrt{m}})^{s}\] \[\leq 1.2m^{\frac{L-i+1}{2}}\frac{\mathcal{O}(L^{3/2}R)}{\sqrt{m}}\sum_{ s=1}^{L-i+1}(\frac{\mathcal{O}(L^{3/2}R)}{\sqrt{m}})^{s-1}\] \[\stackrel{{(c)}}{{\leq}} \frac{0.01}{\kappa\sqrt{N}}m^{\frac{L-i+1}{2}}, \tag{21}\]

where (a) uses \(\mathcal{C}(t+1)\) and Lemma VII.1, (b) uses \(\binom{L-i+1}{s}\leq L^{s}\) and (c) uses \(m=\Omega\left((L^{3/2}R\kappa\sqrt{N})^{2}\right)\). Combining the bound of the initial parameter in Lemma VII.1, it has

\[\sigma_{max}(\overline{\mathbf{W}}^{L:i}(t+1))\] \[= \max_{\|\mathbf{z}\|=1}\|\overline{\mathbf{W}}^{L:i}(t+1)\mathbf{z}\|\] \[\leq \max_{\|\mathbf{z}\|=1}\|(\overline{\mathbf{W}}^{L:i}(t+1)-\overline{\mathbf{W}} ^{L:i}(0))\mathbf{z}\|+\max_{\|\mathbf{z}\|=1}\|\overline{\mathbf{W}}^{L:i}(0)\mathbf{z}\|\] \[\leq \frac{0.01}{\kappa\sqrt{N}}m^{\frac{L-i+1}{2}}+1.2m^{\frac{L-i+1}{2 }}\leq 1.25m^{\frac{L-i+1}{2}},\]

and

\[\sigma_{min}(\overline{\mathbf{W}}^{L:i}(t+1))\] \[= \min_{\|\mathbf{z}\|=1}\|\overline{\mathbf{W}}^{L:i}(t+1)\mathbf{z}\|\] \[= \min_{\|\mathbf{z}\|=1}\|(\overline{\
Then, it can derive the upper bound of \(\|\overline{\mathbf{W}}^{j:i}(t+1)\|\) by applying the above analysis and it completes the proof of \(\mathcal{B}(t+1)\).

#### Iv-B3 \(\mathcal{A}(t+1)\)

Finally, we focus on analyzing Eq.(17) to derive the convergence rate of FedAvg in training deep fully-connected linear networks.

**1. The bound of the first term**: According to Eq.(20), it has

\[\|(I\!-\!\frac{\eta}{N}\sum_{k\in[K]}\mathbf{P}(0))\overline{\mathbf{\xi}}( t)\|_{2}\] \[\leq(1\!-\!\frac{\eta\lambda_{min}(\mathbf{P}(0))K}{N})\|\overline{ \mathbf{\xi}}(t)\|_{F}, \tag{23}\]

where the last inequality uses \(\eta\leq\frac{d_{out}}{50L\kappa K\|\mathbf{X}\|^{2}}\).

**2. The bound of the second term**:

\[\|\frac{\eta}{N}\sum_{k\in[K]}(\mathbf{P}(t,k)-\mathbf{P}(0))\mathbf{\xi}_{k}( t)\|_{2}\] \[\leq \frac{\eta}{N}\sum_{k\in[K]}\|\mathbf{P}(t,k)-\mathbf{P}(0)\|\|\mathbf{\xi}_{ k}(t)\|_{F}\] \[\leq K\frac{\eta}{N}\|\overline{\mathbf{\xi}}(t)\|_{F}\frac{0.109L}{d_{ out}\kappa}\|\mathbf{X}\|^{2}\leq\frac{0.109K\eta\lambda_{min}(\mathbf{P}(0))}{0.8^{4}N}. \tag{24}\]

where the second inequality uses Lemma VII.5 the last inequality uses Eq.(31), Eq.(36) and \(\eta\leq\frac{d_{out}}{50L\kappa K\|\mathbf{X}\|^{2}}\).

**3. The bound of the third term**:

\[\|\frac{\eta}{N}\sum_{k\in[K]}\mathbf{P}(0)\text{vec}(\mathbf{U}_{k}(t)- \overline{\mathbf{U}}(t))\|\] \[\leq \frac{\eta\lambda_{max}(\mathbf{P}(0))}{N}\|\sum_{k\in[K]}\text{vec} (\mathbf{U}_{k}(t)-\overline{\mathbf{U}}(t))\|\] \[\leq \frac{\eta\lambda_{max}(\mathbf{P}(0))}{N}\frac{\eta 57K^{2}\sigma_{max}^{2}( \mathbf{X})}{20d_{out}}\|\overline{\mathbf{\xi}}(t)\|_{F}\] \[\leq \frac{\eta\lambda_{min}(\mathbf{P}(0))K}{5N}. \tag{25}\]

where the first inequality uses Lemma VII.7, the second inequality uses Lemma VII.1 and \(\mathcal{B}(t)\) that \(\lambda_{max}(\mathbf{P}(0))\leq\frac{1.2^{t}L\sigma_{max}^{2}(\mathbf{X})}{d_{out}}\) and the last inequality uses \(\eta=\mathcal{O}(\frac{d_{out}}{K\kappa K\|\mathbf{X}\|^{2}})\).

**4. The bound of the fourth term**:

From Eq.(10), we know that \(\mathbf{E}(t)\) contains high-order items in terms of \(\eta\). Moreover, it has \(\|\frac{\partial\mathcal{C}}{\partial\overline{\mathbf{W}}^{0}(t)}\|\leq\frac{8 \|\mathbf{X}\|K}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(t)\|_{F}\) according to Eq.(19). Thus, it has

\[\|\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})\|\] \[\leq \frac{1}{\sqrt{\mathcal{C}_{2}}}\sum_{s=2}^{L}\left(\frac{L}{s} \right)\left(\eta\frac{8\|\mathbf{X}\|K}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(t )\|_{F}\right)^{s}(\mathcal{O}(\sqrt{L}))^{s-1}m^{\frac{L-s}{2}}\|\mathbf{X}\|\] \[\leq \frac{1}{\sqrt{d_{out}}}\sum_{s=2}^{L}L^{s}\left(\eta\frac{8\| \mathbf{X}\|K}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(t)\|_{F}\right)^{s}(\mathcal{ O}(\sqrt{L}))^{s-1}m^{\frac{1-s}{2}}\|\mathbf{X}\|\] \[\leq \frac{1}{\sqrt{d_{out}}}\sum_{s=2}^{L}\left(\mathcal{O}(L^{3/2} \eta\frac{8\|\mathbf{X}\|K}{5\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}(t)\|_{F})\right) ^{s}L^{-1/2}m^{\frac{1-s}{2}}\|\mathbf{X}\|\] \[\leq L\eta\frac{\|\mathbf{X}\|^{2}K}{\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}}( t)\|_{F}\sum_{s=2}^{L}\left(\mathcal{O}(L^{3/2}\eta\frac{8\|\mathbf{X}\|K}{5\sqrt{N \sqrt{md_{out}}}}\|\overline{\mathbf{\xi}}(t)\|_{F})\right)^{s-1}.\]

where the second inequality uses \(\binom{L}{s}\leq L^{s}\).

In addition, it has

\[\mathcal{O}(L^{3/2}\eta\frac{\|\mathbf{X}\|K}{5\sqrt{N}\sqrt{md_{out}}}\|\overline{ \mathbf{\xi}}(t)\|_{F})\leq\frac{1}{2},\]

where \(m=\Omega(\frac{Ld_{out}}{\kappa^{2}N\|\mathbf{X}\|^{2}}\|\overline{\mathbf{\xi}}(0)\|_{F }^{2})\) and \(\eta=\mathcal{O}(\frac{d_{out}}{L\kappa K\|\mathbf{X}\|^{2}})\).

\[L\eta\frac{\|\mathbf{X}\|^{2}K}{\sqrt{Nd_{out}}}\|\overline{\mathbf{\xi}} (t)\|_{F}(L^{3/2}\eta\frac{\|\mathbf{X}\|K}{\sqrt{N}\sqrt{md_{out}}}\|\overline{\mathbf{ \xi}}(t)\|_{F})*2\] \[\leq \frac{\eta\lambda_{min}(\mathbf{P}(0))K}{10N} \tag{26}\]

where \(m=\Omega(\frac{Ld_{out}}{\|\mathbf{X}\|^{2}}\|\overline{\mathbf{\xi}}(0)\|_{F}^{2})\) and \(\eta=\mathcal{O}(\frac{d_{out}}{L\kappa K\|\mathbf{X}\|^{2}})\).

Finally, combining Eq.(23), Eq.(24), Eq.(25) and Eq.(26), it has

\[\|\overline{\mathbf{\xi}}(t+1)\|\] \[= \|(I\!-\!\frac{\eta}{N}\sum_{k\in[K]}\mathbf{P}(0))\text{vec}(\overline {\mathbf{\xi}}(t))\!-\!\frac{\eta}{N}\sum_{k\in[K]}(\mathbf{P}(t,k)\!-\!\mathbf{P}(0))\mathbf{ \xi}_{k}(t)\] \[-\frac{\eta}{N}\sum_{k\in[K]}\mathbf{P}(0)\text{vec}(\mathbf{U}_{k}(t)\!- \!\overline{\mathbf{U}}(t))+\frac{1}{\sqrt{m^{L-1}d_{out}}}\text{vec}(\mathbf{E}(t)\mathbf{X})\|\] \[\leq (1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{N}+\frac{0.109\eta K\lambda _{min}(\mathbf{P}(0))}{0.8^{4}N}+\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{5N}\] \[+\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{10N})\|\overline{\mathbf{\xi}}(t )\|_{F}\] \[\leq (1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})\|\overline{\mathbf{\xi}}( t)\|_{F}\] \[\leq (1-\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})\|\overline{\mathbf{\xi}}( t)).\]

Thus, it has

\[\mathcal{L}(t\!+\!1)\!=\!\|\overline{\mathbf{\xi}}(t\!+\!1)\|_{F}^{2}\] \[\leq (1\!-\!\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})^{2}\mathcal{L}( t)\leq(1\!-\!\frac{\eta K\lambda_{min}(\mathbf{P}(0))}{2N})\mathcal{L}(t).\]

Finally, based on \(m=\Omega(L^{3}R^{2}\kappa^{2}N)\) and the requirement of \(m\) in Lemma VII.6, it can derive the condition on \(m\) with \(R\) defined in assumption \(\mathcal{C}\).

## V Experimental evaluation

### _Experimental Setup_

In the experiment, we consider two widely used datasets: MNIST [31] and FMNIST [32], where each dataset contains 60,000 samples. For the architecture of the network, the deep linear network is evaluated for 10 classification task, where the initialization uses the scheme in Section III-B. The network depth is set to 3 and the width is 500. In addition, we set the learning rate to 0.0005 for both datasets. For evaluating the impacts of the local update \(K\) and the number of local clients \(N\), we perform \(K\in\{1,5,10\}\) and \(N\in\{40,80,160\}\). In addition, we test the influence of the ratio \(K/N\) on the convergence by setting \(K/N\in\{1/8,1/16\}\). According to the training setting in [33, 11], we use two schemes to distribute the dataset to clients: independent and identically distributed (i.i.d) and non-i.i.d. For the non-iid scheme, each client only randomly accesses two classes of the dataset. To assess the impact of the global aggregation
### _Experimental Result_

**The impact of \(N\)**: As shown in Fig.2, it can be observed that FedAvg requires more rounds to achieve the same training loss along with the increasing of clients on both i.i.d and non-i.i.d schemes, which is consistent with our theoretical findings that the convergence rate is inversely proportional to \(N\).

**The impact of \(K\)**: Furthermore, the experimental result depicted in Fig.3 shows that FedAvg converges faster as the number of local iterations increases. This also verifies the correctness of our theoretical findings that the increasing of \(K\) can speed up the convergence of FedAvg.

**The impact of \(K/N\)**: According to Theorem IV.2, the convergence rate of FedAvg is actually influenced by the ratio of \(K/N\). As depicted in Fig.4, it can be observed that the curves of the training loss stay similarly for \(\{N=80,K=5\}\) and \(\{N=160,K=10\}\), which also holds on \(\{N=40,K=5\}\) and \(\{N=80,K=10\}\). These observations are in accordance with our theoretical convergence rate \(\mathcal{O}\left(1-\frac{\eta K}{N})^{t}\right)\) for FedAvg.

## VI Conclusion

FedAvg is widely used in training neural networks from distributed clients without sharing data. However, the corresponding optimization problem is often non-convex. Moreover, FedAvg include multiple clients and local updates, which results in an inaccurate gradient-descent direction. In this paper, we provide the first theoretical guarantee for the global convergence of FedAvg in training the deep linear neural network, where the convergence rate is \(\mathcal{O}\big{(}(1-\eta K/N)^{t}\big{)}\). In the experiment, we empirical justify the correctness of our theoretical results by evaluate the effects of \(K\) and \(N\) on the convergence speed.

In the future work, the convergence of FedAvg in training other commonly used architectures of neural networks would be interesting to explore. Furthermore, the partial participant of clients is commonly used in the real scenario, thereby deserving its impact on the convergence of FedAvg in the non-convex optimization problem of neural networks.

## VII Supporting Lemma

**Lemma VII.1**.: _([8]) With probability at least \(1-\delta\), it has_

\[\left\{\begin{array}{l}\sigma_{max}(\overline{\mathbf{W}}^{L:i}(0))\leq 1.2m ^{\frac{L-i+1}{2}},\\ \sigma_{min}(\overline{\mathbf{W}}^{Li:i}(0))\geq 0.8m^{\frac{L-i+1}{2}}, \end{array}\right.\forall 1<i\leq L\]

\[\left\{\begin{array}{l}\sigma_{max}(\overline{\mathbf{W}}^{j:1}(0)\mathbf{X})\leq 1.2m^{\frac{j}{2}}\sigma_{max}(\mathbf{X}),\\ \sigma_{min}(\overline{\mathbf{W}}^{j:1}(0)\mathbf{X})\geq 0.8m^{\frac{j}{2}} \sigma_{min}(\mathbf{X}),\end{array}\right.\forall 1\leq j<L\]

\[\|\overline{\mathbf{W}}^{j:i}(0)\|\leq\mathcal{O}(\sqrt{L}m^{\frac{i-i+1}{2}}), \ \forall 1<i\leq j<L\]

\[\frac{1}{2}\|\overline{\mathbf{\xi}}(0)\|_{F}^{2}\leq B^{2}=\mathcal{O}(\max\{1, \frac{\log(r/\delta)}{d_{out}},\|\mathbf{W}^{*}\|^{2}\})\|\mathbf{X}\|_{F}^{2},\]

_where the requirement of the width satisfies \(m=\Omega(\frac{L\|\mathbf{X}\|^{4}d_{out}B}{\sigma_{min}^{2}(\mathbf{X})})=\Omega( \frac{Le^{2}d_{out}B}{\sigma_{min}^{2}(\mathbf{X})})\)_

**Lemma VII.2**.: _For a matrix \(\mathbf{A}=[\mathbf{A}_{0},\cdots,\mathbf{A}_{N-1}]\), then it has the bound_

\[\|\mathbf{A}\|_{2}\leq\sqrt{\sum_{c\in[N]}\|\mathbf{A}_{c}\|_{2}^{2}}.\]

The above lemma can be proved by applying triangle inequality.

**Lemma VII.3**.: _([35]) For any matrix \(\mathbf{A}\) and \(\mathbf{B}\), then it has_

\[\|\mathbf{A}\otimes\mathbf{B}\|_{2}=\|\mathbf{A}\|_{2}\|\mathbf{B}\|_{2}.\]

**Lemma VII.4**.: _(Theorem 4.1 in [8]) With \(\eta=\frac{d_{out}}{3L\|\mathbf{X}^{\top}\mathbf{X}\|}\leq\frac{d_{out}}{3L\|\mathbf{X}^{ \top}\mathbf{X}_{c}\|}\), it has_

\[\|\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\|_{2}^{2}\leq (1-\frac{\eta L\lambda_{min}(\mathbf{X}_{c}^{\top}\mathbf{X}_{c})}{4d_{out }})^{k}\|\mathbf{U}_{0,c}(t)-\mathbf{Y}_{c}\|_{2}^{2}\] \[\leq (1-\frac{\eta L\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})}{4d_{out}})^{k} \|\mathbf{U}_{0,c}(t)-\mathbf{Y}_{c}\|_{2}^{2}.\]

It is noted that \(\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})\leq\lambda_{min}(\mathbf{X}_{c}^{\top}\mathbf{X}_{c})\) and \(\lambda_{max}(\mathbf{X}^{\top}\mathbf{X})\geq\lambda_{max}(\mathbf{X}_{c}^{\top}\mathbf{X}_ {c})\), then \(\kappa=\frac{\lambda_{max}(\mathbf{X}^{\top}\mathbf{X})}{\lambda_{min}(\mathbf{X}^{\top} \mathbf{X})}>\kappa_{c}=\frac{\lambda_{max}(\mathbf{X}^{\top}\mathbf{X}_{c})}{\lambda_{ min}(\mathbf{X}^{\top}\mathbf{X}_{c})}\). As a result, it has

\[1-\eta L\frac{\lambda_{min}(\mathbf{X}_{c}^{\top}\mathbf{X}_{c})}{4d_{out}}\leq 1-\eta L \frac{\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})}{4d_{out}}. \tag{27}\]

**Lemma VII.5**.: _Based on the inductive hypothesis for \(\tau\leq t\) in, with \(m=\Omega(L^{3}R^{2}\kappa^{2}N)\), it has_

\[\|\mathbf{P}(t,k)-\mathbf{P}(0)\|\leq\frac{0.109L}{d_{out}\mathcal{K}}\|\mathbf{X}\|^{2}.\]

Proof.: Denote \(\Delta_{1}(t)=\overline{\mathbf{W}}^{l-1:1}(t)X-\overline{\mathbf{W}}^{i-1:1}(0)X\), \(\Delta_{2}(t)=\mathbf{W}_{k,c}^{l-1:1}(t)\mathbf{X}_{c}-\overline{\mathbf{W}}^{i-1:1}(0) \mathbf{X}_{c}\), \(\Delta_{3}(t)=\overline{\mathbf{W}}^{L:i+1}(t)-\overline{\mathbf{W}}^{L:i+1}(0)\) and \(\Delta_{4}(t)=\mathbf{W}_{k,c}^{L:i+1}(t)-\overline{\mathbf{W}}^{L:i+1}(0)\).

It has

\[\|\Delta_{1}(t)\|\leq \frac{0.01}{\kappa\sqrt{N}}m^{\frac{i-1}{2}}\|\mathbf{X}\|,\|\Delta_{3} (t)\|\leq\frac{0.01}{\kappa\sqrt{N}}m^{\frac{L-i}{2}}, \tag{28}\]

according to Eq.(21) and Eq.(22).

Moreover, based on Eq.(34) and Eq.(22), it has

\[\|\Delta_{2}(t)\|=\|\mathbf{W}_{k,c}^{i-1:1}(t)\mathbf{X}_{c}-\overline{\bm {W}}^{i-1:1}(0)\mathbf{X}_{c}\|\] \[\leq \|\mathbf{W}_{k,c}^{i+1:1}(t)\mathbf{X}_{c}-\overline{\mathbf{W}}^{i-1:1}(t) \mathbf{X}_{c}\|+\|\overline{\mathbf{W}}^{i-1:1}(t)\mathbf{X}_{c}-\overline{\mathbf{W}}^{i-1:1}(0) \mathbf{X}_{c}\|\] \[\leq \frac{0.02}{\kappa\sqrt{N}}m^{\frac{i-1}{2}}\mathbf{X}_{c}. \tag{29}\]

Similarly, it has

\[\|\Delta_{4}(t)\|_{2}\leq \frac{0.02}{\kappa\sqrt{N}}m^{\frac{L-i}{2}}. \tag{30}\]

Considering \(\mathbf{P}(0)=[\mathbf{P}(0,1),\cdots\mathbf{P}(0,N)]\) with \(\mathbf{P}(0,c)=\frac{1}{m^{\frac{L-1}{L-d_{out}}}}((\overline{\mathbf{W}}^{i-1:1}(0)X)^{ \top}(\overline{\mathbf{W}}^{i-1:1}(0)\mathbf{X}_{c})\otimes\overline{\mathbf{W}}^{Li +1}(0)\overline{\mathbf{W}}^{Li+1}(0)^{\top})\) for \(1\leq c\leq N\) and \(C_{2}=\frac{1}{m^{t-1}d_{out}}\), it has

\[\|\mathbf{P}(t,k)-\mathbf{P}(0)\|\leq \sqrt{\sum_{c\in[N]}\|\mathbf{P}(t,k,c)-\mathbf{P}(0,c)\|^{2}}\]
\[= \sqrt{\sum_{c\in[N]}(\frac{0.109L}{d_{out}\kappa\sqrt{N}}\|\mathbf{X}\|^{2 })^{2}}\leq\frac{0.109L}{d_{out}\kappa}\|\mathbf{X}\|^{2}. +\Delta_{3}(t)\overline{\mathbf{W}}^{L:i+1}(0)^{\top}+\Delta_{3}(t) \Delta_{4}(t)^{\top})+((\overline{\mathbf{W}}^{i-1:1}(0)\mathbf{X})^{\top}\Delta_{2}(t)\] \[+\Delta_{1}(t)^{\top}\overline{\mathbf{W}}^{i-1:1}(0)\mathbf{X}_{c}+ \Delta_{1}(t)^{\top}\Delta_{2}(t)\otimes\overline{\mathbf{W}}^{L:i+1}(t)\mathbf{W}_{k, c}^{L:i+1}(t)^{\top}\|\] \[\leq LC_{2}(1.2^{2}m^{i-1}\|\mathbf{X}\|^{2}(1.2*\frac{0.02}{\kappa\sqrt{N }}+1.2*\frac{0.01}{\kappa\sqrt{N}}+\frac{2*10^{-4}}{\kappa^{2}N})m^{L-i}\] \[+1.25^{2}m^{L-i}(1.2*\frac{0.02}{\kappa\sqrt{N}}+\frac{0.01}{ \kappa\sqrt{N}}*1.2+\frac{2*10^{-4}}{\kappa^{2}N})m^{i-1}\|\mathbf{X}\|^{2})\] \[\leq \frac{0.109L}{d_{out}\kappa\sqrt{N}}\|\mathbf{X}\|^{2}.\]

**Lemma VII.6**.: _(Claim 7.1, 7.2 and 7.3 in [8]) With probability at least \(1-\delta\) over the random initialization, the following inequalities hold for all \(k\in[K]\), \(c\in[N]\) and \(r\in[m]\) in local iteration \(k\) with \(m=\Omega(L\max\{r\kappa^{3}d_{out}(1+\|\mathbf{W}^{*}\|^{2}),r\kappa^{3}\log\frac{ \delta}{\delta},\log L\})\)\(\|\mathbf{W}^{*}\|^{2}),r\kappa^{3}\log\frac{\delta}{\delta},\log L\}\)\(\|\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\|_{F}^{2}\leq(1-\eta L\frac{\lambda_{min}(\mathbf{X}_{c}^{ \top}\mathbf{X}_{c})}{4d_{out}})^{k}\|\overline{\mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\|_{F}^{2},\)\(\|\mathbf{W}_{k,c}^{L:i}(t)-\overline{\mathbf{W}}^{j:i}(t)\|\leq\)\(\mathcal{O}(\sqrt{L})\!\!\sum_{s=1}^{j-i+1}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
\[\|(\mathbf{W}_{k,c}^{i:1}(t)-\overline{\mathbf{W}}^{i:1}(t))\mathbf{X}\|\leq \frac{5}{4}m^{\frac{i}{2}}\sum_{s=1}^{i}(\frac{\mathcal{O}(L^{3/2}R)}{\sqrt{m}} )^{s}\|\mathbf{X}\|,1\leq i<L\] \[\|\mathbf{W}_{k,c}^{i}(t)-\overline{\mathbf{W}}^{i}(t)\|\leq R:=\frac{24 \sqrt{d_{out}}\|\mathbf{X}_{c}\|}{L\sigma_{min}^{2}(\mathbf{X}_{c})}\|\overline{\mathbf{U} }_{c}(t)-\mathbf{Y}_{c}\|_{F} \tag{32}\]

In addition, according to [8], it has

\[\|\operatorname{vec}(\mathbf{U}_{k+1,c}(t+1)-\mathbf{U}_{k,c}(t))\|\] \[\leq \eta\lambda_{max}(\mathbf{P}^{k+1,c}(t))\|\mathbf{\xi}_{k,c}(t)\|_{F}+ \frac{\eta\lambda_{min}(\mathbf{P}^{k+1,c}(t))}{6}\|\overline{\mathbf{\xi}}(t)\|_{F}\] \[\leq \frac{7\eta\lambda_{max}(\mathbf{P}^{k+1,c}(t))}{6}\|\mathbf{\xi}_{k,c}(t )\|_{F}\leq\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}\|\mathbf{\xi}_{k,c }(t)\|_{F}, \tag{33}\]

where \(\mathbf{P}^{k+1,c}(t)\) denotes the centralized gram matrix calculated on client \(c\), the last inequality uses the upper bound of the largest eigenvalue of \(\mathbf{P}^{k+1,c}(t)\leq 1.25^{4}L\sigma_{max}^{2}(\mathbf{X}_{c})/d_{out}\) as proved in [8].

Based on Lemma VII.6 and \(m=\Omega(L^{3}R^{2}\kappa^{2}N)\), it has

\[\|(\mathbf{W}_{k,c}^{i:1}(t)-\overline{\mathbf{W}}^{i:1}(t))\mathbf{X}\|\leq \frac{5}{4}m^{\frac{i}{2}}\sum_{s=1}^{i}(\frac{\mathcal{O}(L^{3/ 2}R)}{\sqrt{m}})^{s}\|\mathbf{X}\|\] \[\leq \frac{0.01}{\kappa\sqrt{N}}m^{\frac{i}{2}}\|\mathbf{X}\|. \tag{34}\]

Similarly, it has

\[\|\mathbf{W}_{k,c}^{L:i}(t)-\overline{\mathbf{W}}^{L:i}(t)\|\leq \frac{5}{4}m^{\frac{L-i+1}{2}}\sum_{s=1}^{L-i+1}(\frac{\mathcal{ O}(L^{3/2}R)}{\sqrt{m}})^{s}\] \[\leq \frac{0.01}{\kappa\sqrt{N}}m^{\frac{L-i+1}{2}}. \tag{35}\]

According to Eq.(21) and Lemma VII.6, it has

\[\|\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\|_{F}^{2}\leq(1-\eta L\frac{\lambda_{min}(\mathbf{X} ^{\top}\mathbf{X})}{4d_{out}})^{k}\|\overline{\mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\|_{F}^{2}\]

As a result, it has

\[\|\mathbf{U}_{k}(t)-\mathbf{Y}\|_{F}^{2}= \sum_{c\in|N|}\|\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\|_{F}^{2}\] \[\leq (1-\eta L\frac{\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})}{4d_{out}})^{k} \|\overline{\mathbf{U}}(t)-\mathbf{Y}\|_{F}^{2}, \tag{36}\] \[\|\mathbf{U}_{k}(t)-\mathbf{Y}\|_{F}\leq (1-\frac{\eta L\lambda_{min}(\mathbf{X}^{\top}\mathbf{X})}{8d_{out}})^{k} \|\overline{\mathbf{U}}(t)-\mathbf{Y}\|_{F}, \tag{37}\]

according to \(\sqrt{1-x}\leq 1-x/2\) for \(0\leq x\leq 1\)

We then prove a Lemma that controls the updates in local steps.

Fig. 3: The impact of \(K\) on the convergence of FedAvg.
**Lemma VII.7**.: _In the \(t\)-th global update, for all \(k\in[K],c\in[N]\), it has_

\[\|\overline{\mathbf{U}}_{c}(t)-\mathbf{U}_{k,c}(t)\|_{F}\leq\frac{57\eta \sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}\|\overline{\mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\|_ {F},\] \[\|\mathbf{U}_{k}(t)-\overline{\mathbf{U}}(t)\|_{F}^{2}\leq (\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}})^{2}\| \overline{\mathbf{U}}(t)-\mathbf{Y}\|_{F}^{2}.\]

Proof.: From Eq.(33), it has

\[\|\mathbf{U}_{k,c}(t)-\mathbf{Y}_{c}\|_{F}\leq \|\mathbf{U}_{k,c}(t)-\mathbf{U}_{k-1,c}(t)\|_{F}+\|\mathbf{U}_{k-1,c}(t)-\mathbf{Y }_{c}\|_{F}\] \[\leq (\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}+1)\|\mathbf{U} _{k-1,c}(t)-\mathbf{Y}_{c}\|_{F}\] \[\leq (\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}+1)^{k}\| \overline{\mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\|_{F}.\]

In turn, it has

\[\|\overline{\mathbf{U}}_{c}(t)-\mathbf{U}_{k,c}(t)\|_{F}\leq\sum_{i=1}^{k }\|\mathbf{U}_{i,c}(t)-\mathbf{U}_{i-1,c}(t)\|_{F}\] \[\leq \sum_{i=1}^{k}\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out} }\|\mathbf{U}_{i-1,c}(t)-\mathbf{Y}_{c}\|_{F}\] \[\leq \sum_{i=1}^{k}\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out} }(\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}+1)^{i-1}\|\overline{\bm {U}}_{c}(t)-\mathbf{Y}_{c}\|_{F}\] \[\leq \frac{57k\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{10d_{out}}\|\overline{ \mathbf{U}}_{c}(t)-\mathbf{Y}_{c}\|_{F},\]

where the last inequality applies

\[\sum_{i=1}^{k}(x+1)^{i-1}\leq\sum_{i=1}^{k}(x+1)^{K}\leq 2k, \tag{38}\]

which is according to

\[(\frac{57\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{20d_{out}}+1)^{K}\leq (\frac{7}{100\kappa K}+1)^{K}\leq e^{\frac{7}{100\kappa}}\leq 2\]

Therefore, it has

\[\|\mathbf{U}_{k}(t)-\overline{\mathbf{U}}(t)\|_{F}^{2}= \sum_{c\in[N]}\|\mathbf{U}_{k,c}(t)-\overline{\mathbf{U}}_{c}(t)\|_{F}^{2}\] \[\leq (\frac{57k\eta\sigma_{max}^{2}(\mathbf{X}_{c})}{10d_{out}})^{2}\| \overline{\mathbf{U}}(t)-\mathbf{Y}\|_{F}^{2} \tag{39}\]
