From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this paradigm. We introduce a {\it graph decomposition framework} that uses the network to design the method, not merely execute it. It jointly determines how agreement is imposed, which variables are optimized jointly (blocks), and which connected subgraphs host the agents solving each block. The convergence an...
| Authors | Kuangyu Ding, Gesualdo Scutari |
|---|---|
| Primary category | math.OC |
| Published | 2 October 2026 |
| Last updated at source | 14 October 2026 |
Popularity, last 2 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.