Decentralized Optimization with Topology-Independent Communication

Distributed optimization requires nodes to coordinate, yet full synchronization scales poorly. When $n$ nodes collaborate through $m$ pairwise regularizers, standard methods demand $\mathcal{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 $G_j$ depends on a subset $S_j\subseteq \{1,\dots ,n\}$ of nodes. For graph-guided regularizers where $\mathrm{\mid }{S}_j\mathrm{\mid }=2$, expected communication drops to exactly 2 messages per iteration. This method achieves $\tilde{\mathcal{O}}({\epsilon }^{-2})$ iterations for convex objectives and under strong convexity, $\mathcal{O}({\epsilon }^{-1})$ to an $\epsilon$-solution and $\mathcal{O}(\log (1\mathrm{/}\epsilon ))$ to a neighborhood. Replacing the proximal map of the sum ${\sum }_j{G}_j$ with the proximal map of a single randomly selected regularizer $G_j$ preserves convergence while eliminating global coordination. Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.