在分布式优化中,局部更新可加速收敛,且两次更新即达最优效果。
Local Updates in Distributed Optimization: Provable Acceleration and Topology Effects
- 基于PEP分析DIGing算法,证明局部更新能有效加速优化
- 仅需两次局部更新即可达到最大加速,额外更新无益
- 网络拓扑影响加速效果,稀疏图提升有限
受联邦学习中通信间隔内执行多次局部优化步骤成功的启发,将此类局部更新引入分布式优化近年来受到广泛关注。然而,与联邦学习中因小批量设置下降低梯度估计误差而受益不同,在精确梯度可用时,这种优势是否仍存在尚不明确。此外,现有理论通常要求在使用多步局部更新时减小步长,这可能完全抵消额外更新的潜在收益。本文聚焦经典DIGing算法,利用性能估计问题(PEP)提供的紧致性能界,证明引入局部更新确实能加速分布式优化。据我们所知,这是对一大类目标函数首次严格的加速证明。分析进一步表明,在合适步长下,仅需两次局部更新即可实现最大可能改进,更多更新不再带来增益。由于更多更新会增加计算成本,这些发现为高效实现提供了实用指导。我们还发现,这些加速效果高度依赖网络结构,更稀疏或连接度更低的图(由混合矩阵的谱特性表征)带来的提升较小。在合成与真实数据集上的大量实验验证了理论结果。
原文摘要 · Abstract (English)
Inspired by the success of performing multiple local optimization steps between communication rounds in federated learning, incorporating such local updates into distributed optimization has recently attracted growing interest. However, unlike federated learning, where local updates can accelerate training by reducing gradient estimation error under minibatch settings, it remains unclear whether similar benefits persist when exact gradients are available. Moreover, existing theoretical results typically require reducing the step size when multiple local updates are employed, which can entirely offset any potential benefit of these additional local updates. In this paper, we focus on the classic DIGing algorithm and leverage the tight performance bounds provided by Performance Estimation Problems (PEP) to show that incorporating local updates can indeed accelerate distributed optimization. To the best of our knowledge, this is the first rigorous demonstration of such acceleration for a broad class of objective functions. Our analysis further reveals that, under an appropriate step size, performing only two local updates is sufficient to achieve the maximal possible improvement, and that additional local updates provide no further gains. Because more updates increase computational cost, these findings offer practical guidance for efficient implementation. We also show that these speed gains depend critically on the network structure, with sparser or less connected graphs, characterized by the spectral properties of the mixing matrix, yielding smaller improvements. Extensive experiments on both synthetic and real-world datasets corroborate the theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。