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 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.