Federated learning is a new distributed machine learning framework, where a
bunch of heterogeneous clients collaboratively train a model without sharing
training data. In this work, we consider a practical and ubiquitous issue when
deploying federated learning in mobile environments: intermittent client
availability, where the set of eligible clients may change during the training
process. Such intermittent client availability would seriously deteriorate the
performance of the classical Federated Averaging algorithm (FedAvg for short).
Thus, we propose a simple distributed non-convex optimization algorithm, called
Federated Latest Averaging (FedLaAvg for short), which leverages the latest
gradients of all clients, even when the clients are not available, to jointly
update the global model in each iteration. Our theoretical analysis shows that
FedLaAvg attains the convergence rate of $O(E^{1/2}/(N^{1/4} T^{1/2}))$,
achieving a sublinear speedup with respect to the total number of clients. We
implement FedLaAvg along with several baselines and evaluate them over the
benchmarking MNIST and Sentiment140 datasets. The evaluation results
demonstrate that FedLaAvg achieves more stable training than FedAvg in both
convex and non-convex settings and indeed reaches a sublinear speedup.

该研究提出了一种名为 FedLaAvg 的简单分布式非凸优化算法，用于解决在移动环境下采用联邦学习时客户端不连续可用的问题，并证明了其达到了收敛速度为 $ O (E^{1/2}/(N^{1/4} T^{1/2}))$ 的水平。

分布式非凸优化在断断续续的客户端可用性下实现亚线性加速

Distributed Non-Convex Optimization with Sublinear Speedup under  Intermittent Client Availability

Recently, there is a growing interest in the study of median-based algorithms
for distributed non-convex optimization. Two prominent such algorithms include
signSGD with majority vote, an effective approach for communication reduction
via 1-bit compression on the local gradients, and medianSGD, an algorithm
recently proposed to ensure robustness against Byzantine workers. The
convergence analyses for these algorithms critically rely on the assumption
that all the distributed data are drawn iid from the same distribution.
However, in applications such as Federated Learning, the data across different
nodes or machines can be inherently heterogeneous, which violates such an iid
assumption. This work analyzes signSGD and medianSGD in distributed settings
with heterogeneous data. We show that these algorithms are non-convergent
whenever there is some disparity between the expected median and mean over the
local gradients. To overcome this gap, we provide a novel gradient correction
mechanism that perturbs the local gradients with noise, together with a series
results that provable close the gap between mean and median of the gradients.
The proposed methods largely preserve nice properties of these methods, such as
the low per-iteration communication complexity of signSGD, and further enjoy
global convergence to stationary solutions. Our perturbation technique can be
of independent interest when one wishes to estimate mean through a median
estimator.

本文研究介绍了两种分布式非凸优化算法：signSGD 和 medianSGD，并发现它们在数据异构的情况下是不收敛的。作者提出了一种梯度校正机制来消除梯度的平均值和中位数之间的差异，该方法保留了这些方法的良好性质，并实现了全局收敛。此外，该文中所提的梯度校正技术在其他估计平均值的场合也有独立的应用价值。