Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression
Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression
复制标题
DOI：
10.48550/arxiv.2310.19059
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Sijin Chen;Zhize Li;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Sijin Chen;Zhize Li;Yuejie Chi
研究了异质联邦学习(FL)的二阶平稳点的寻找问题。前人的工作大多集中在一阶收敛保证上，不排除鞍点不稳定的情况。同时，在不补偿学习精度的情况下获得通信效率是FL的一个关键瓶颈，特别是当本地数据跨不同客户端高度异构性时。有鉴于此，我们提出了一种新的算法Power-EF，该算法只通过一种新的差错反馈方案来传递压缩信息。据我们所知，Power-EF是第一个分布式和压缩的SGD算法，可以证明在不需要任何数据同质性假设的情况下避开了异质FL中的鞍点。特别地，在访问一阶(可能是鞍点)点后，Power-EF改进为二阶驻点，使用额外的梯度查询和几乎与一阶收敛所需的相同阶的通信轮次，并且收敛速度表现出与工作者数目的线性加速比。我们的理论改进/恢复了以前的结果，同时扩展到对本地数据的更宽容的设置。数值实验是对理论的补充。
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.