Abstract: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.
| Subjects: | Systems and Control (eess.SY); Machine Learning (cs.LG) |
| Cite as: | arXiv:2601.03442 [eess.SY] |
| (or arXiv:2601.03442v4 [eess.SY] for this version) | |
| https://doi.org/10.48550/arXiv.2601.03442 arXiv-issued DOI via DataCite |
From: Zuang Wang [view email]
[v1]
Tue, 6 Jan 2026 22:10:11 UTC (289 KB)
[v2]
Wed, 14 Jan 2026 18:40:59 UTC (289 KB)
[v3]
Mon, 9 Mar 2026 21:12:53 UTC (289 KB)
[v4]
Tue, 21 Apr 2026 17:52:21 UTC (518 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。