# Decentralized Optimization with Topology-Independent Communication

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 67 references that are in the map.
- First posted on arXiv 17 Sep 2025.

## Builds on (most cited first, 30 of 33)

- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [An Efficient Framework for Clustered Federated Learning](https://mlsanity.com/paper/2006.04088/) (2020)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Towards Personalized Federated Learning](https://mlsanity.com/paper/2103.00710/) (2021)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning](https://mlsanity.com/paper/2107.13892/) (2021)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning](https://mlsanity.com/paper/1909.00047/) (2019)
- [RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates](https://mlsanity.com/paper/2207.12891/) (2022)
- [Optimal Gradient Tracking for Decentralized Optimization](https://mlsanity.com/paper/2110.05282/) (2021)
- [Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning](https://mlsanity.com/paper/1910.10453/) (2019)
- [Proximity Without Consensus in Online Multi-Agent Optimization](https://mlsanity.com/paper/1606.05578/) (2016)
- [Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives](https://mlsanity.com/paper/1810.02660/) (2018)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Distributed Mirror Descent for Online Composite Optimization](https://mlsanity.com/paper/2004.00837/) (2020)
- [A Compressed Gradient Tracking Method for Decentralized Optimization with Linear Convergence](https://mlsanity.com/paper/2205.12623/) (2022)
- [DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization](https://mlsanity.com/paper/2209.01850/) (2022)
- [An Enhanced Gradient-Tracking Bound for Distributed Online Stochastic Convex Optimization](https://mlsanity.com/paper/2301.02855/) (2023)
- [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021)
- [The Stochastic Multi-Proximal Method for Nonsmooth Optimization](https://mlsanity.com/paper/2505.12409/) (2025)

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

- [Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms](https://mlsanity.com/paper/2602.05489/) (2026)

## Abstract (arXiv)

Distributed optimization requires nodes to coordinate, yet full synchronization scales poorly. When n nodes collaborate through m pairwise regularizers, standard methods demand O(m) communications per iteration. This paper proposes randomized local coordination: each node independently samples one regularizer uniformly and coordinates only with nodes sharing that term. This exploits partial separability, where each regularizer Gj depends on a subset Sj subseteq 1,ldots,n of nodes. For graph-guided regularizers where |Sj|=2, expected communication drops to exactly 2 messages per iteration. This method achieves tildeO(varepsilon-2) iterations for convex objectives and under strong convexity, O(varepsilon-1) to an varepsilon-solution and O(log(1/varepsilon)) to a neighborhood. Replacing the proximal map of the sum sumj Gj with the proximal map of a single randomly selected regularizer Gj preserves convergence while eliminating global coordination. Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.