We consider the problem of finding second-order stationary points of heterogeneous federated learning (FL). Previous works in FL mostly focus on first-order convergence guarantees, which do not rule out the scenario of unstable saddle points. Meanwhile, it is a key bottleneck of FL to achieve communication efficiency without compensating the learning accuracy, especially when local data are highly heterogeneous across different clients. Given this, we propose a novel algorithm Power-EF that only communicates compressed information via a novel error-feedback scheme. To our knowledge, Power-EF is the first distributed and compressed SGD algorithm that provably escapes saddle points in heterogeneous FL without any data homogeneity assumptions. In particular, Power-EF improves to second-order stationary points after visiting first-order (possibly saddle) points, using additional gradient queries and communication rounds only of almost the same order required by first-order convergence, and the convergence rate exhibits a linear speedup in terms of the number of workers. Our theory improves/recovers previous results, while extending to much more tolerant settings on the local data. Numerical experiments are provided to complement the theory.

我们提出了一种名为Power-EF的算法，通过一种新颖的误差反馈方案，只传递经过压缩的信息，实现异构联邦学习中逃离鞍点的分布式和压缩的SGD算法，无需任何数据均匀性假设，并且在访问一阶（可能是鞍点）点之后，仅使用几乎与一阶收敛所需相同数量的梯度查询和通信轮次进一步提高到二阶稳定点，其收敛速度以工作器数量的线性加速度变化。

通过通信压缩的分布式随机梯度下降在异构联邦学习中逃离鞍点