{"ID":2870092,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.14488","arxiv_id":"2509.14488","title":"Decentralized Optimization with Topology-Independent Communication","abstract":"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,\\ldots,n\\}$ of nodes. For graph-guided regularizers where $|S_j|=2$, expected communication drops to exactly 2 messages per iteration. This method achieves $\\tilde{\\mathcal{O}}(\\varepsilon^{-2})$ iterations for convex objectives and under strong convexity, $\\mathcal{O}(\\varepsilon^{-1})$ to an $\\varepsilon$-solution and $\\mathcal{O}(\\log(1/\\varepsilon))$ 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.","short_abstract":"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 regul...","url_abs":"https://arxiv.org/abs/2509.14488","url_pdf":"https://arxiv.org/pdf/2509.14488v1","authors":"[\"Ying Lin\",\"Yao Kuang\",\"Ahmet Alacaoglu\",\"Michael P. Friedlander\"]","published":"2025-09-17T23:42:57Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.OC\"]","methods":"[]","has_code":false}