From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

Kuangyu Ding, Gesualdo Scutari

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 analysis quantifies the trade-offs among these choices. GATE (Graph-Tearing message passing) instantiates the framework by assigning one dual variable per edge and partitioning the edges into trees. Agents interleave edge updates with local message passing recursions that summarize optimization within each tree (block). Its surrogate variant, GATE-S, uses tractable local models and compact messages to reduce computation and communication. We establish linear convergence and show that the…