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.

使用 NTK 理论进一步提供对联邦平均（FedAvg）在训练深度线性神经网络方面全局收敛的第一个理论保证，通过实验评估验证了理论发现的正确性。

深度线性神经网络联邦平均的神经切线核视角

A Neural Tangent Kernel View on Federated Averaging for Deep Linear  Neural Network

We analyze speed of convergence to global optimum for gradient descent
training a deep linear neural network (parameterized as $x \mapsto W_N W_{N-1}
\cdots W_1 x$) by minimizing the $\ell_2$ loss over whitened data. Convergence
at a linear rate is guaranteed when the following hold: (i) dimensions of
hidden layers are at least the minimum of the input and output dimensions; (ii)
weight matrices at initialization are approximately balanced; and (iii) the
initial loss is smaller than the loss of any rank-deficient solution. The
assumptions on initialization (conditions (ii) and (iii)) are necessary, in the
sense that violating any one of them may lead to convergence failure. Moreover,
in the important case of output dimension 1, i.e. scalar regression, they are
met, and thus convergence to global optimum holds, with constant probability
under a random initialization scheme. Our results significantly extend previous
analyses, e.g., of deep linear residual networks (Bartlett et al., 2018).

本文研究在白化数据上，通过梯度下降来训练深度线性神经网络收敛到全局最优点的速度。当隐藏层数的维度不小于输入输出维度的最小值，并且初始化的权重矩阵大致平衡且初始损失小于任何秩缺失解时，可保证线性收敛。此外，在输出维度为 1 的情况下，即标量回归，这些条件是满足的，并且在随机初始化方案下具有恒定的概率达到全局最优解。