# A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization

arXiv: https://arxiv.org/abs/2312.11861 · HTML: https://mlsanity.com/paper/2312.11861/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 21 of 21)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates](https://mlsanity.com/paper/2207.12891/) (2022)
- [Local Exact-Diffusion for Decentralized Optimization and Learning](https://mlsanity.com/paper/2302.00620/) (2023)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020)
- [Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2009.04373/) (2020)
- [PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction](https://mlsanity.com/paper/2012.15010/) (2020)
- [DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization](https://mlsanity.com/paper/2209.01850/) (2022)
- [Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization](https://mlsanity.com/paper/2302.03238/) (2023)

## Built on by (most cited first, 2 of 2)

- [A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks](https://mlsanity.com/paper/2508.20645/) (2025)
- [Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration](https://mlsanity.com/paper/2602.16148/) (2026)

## Abstract (arXiv)

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 MG-Skip 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, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting, while its computation complexity is Oleft(kappa log frac1εright) and communication complexity is only Oleft(√frackappa(1-ρ) log frac1εright), where kappa is the condition number of the loss function, ρ reflects the connectivity of the network topology, and ε is the target accuracy. The theoretical results indicate that MG-Skip achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting.