Answers are grounded in this paper and cite their sources.
Decentralized optimization methods with local updates have recently gained attention for their provable ability to communication acceleration. In these methods, nodes perform several iterations of local computations between the communication rounds. Nevertheless, this capability is effective only when the network is sufficiently well-connected and the loss function is smooth. In this paper, we propose a communication-efficient method <tex-math notation="LaTeX">MG-Skip</tex-math> with probabilistic local updates and multi-gossip communications for decentralized composite (smooth + nonsmooth) optimization, whose stepsize is independent of the number of local updates and the network topology. For any undirected and connected networks, <tex-math notation="LaTeX">MG-Skip</tex-math> allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting, while its computation complexity is <tex-math notation="LaTeX">O(κ log 1ε)</tex-math> and communication complexity is only <tex-math notation="LaTeX">O(√κ(1-ρ) log 1ε)</tex-math>, where <tex-math notation="LaTeX">κ</tex-math> is the condition number of the loss function, <tex-math notation="LaTeX">ρ</tex-math> reflects the connectivity of the network topology, and <tex-math notation="LaTeX">ε</tex-math> is the target accuracy. The theoretical results indicate that <tex-math notation="LaTeX">MG-Skip</tex-math> achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting.
No takes yet. Share an insight, caveat, or question.
Guo et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: