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

Abstract

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 topology-aware design acts as a \emph{preconditioner}: the rate depends {\it jointly} on topology and function geometry through the coupling between subproblems defined on the selected subgraphs, whereas consensus-based optimization methods pay the worst case of each separately, the centralized condition number times the inverse spectral gap. On tree-dominant graphs, convergence is provably faster: the rate scales with the tree {\it diameter}, linearly in the number of agents on rings and barbells against quadratically for non-accelerated consensus-optimization methods. Experiments support the predicted scaling and savings in iterations and communication.