From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
GATE introduces a graph-tearing message passing framework that jointly designs subproblems and communication for decentralized optimization over agent clusters.
The paper studies minimizing sums of smooth strongly convex functions over undirected graphs with neighbor-only communication, moving beyond gossip or spanning-tree routing. GATE (Graph-Tearing message passing) assigns one variable per edge with tree blocks, updating edge variables from endpoint cost-to-go messages, while GATE-S uses tractable local surrogate models and lightweight message parametrizations to cut per-iteration cost. The authors prove linear convergence with rates explicit in function regularity, network topology, and the chosen partition, validated numerically.
15