Track trials, findings, and clinical evidence as it lands.
Search papers, labs, and topics across Lattice.
This paper introduces a novel framework for decentralized optimization over graphs by jointly designing agreement constraints, dual variables, and agent clusters for subproblem solving, moving beyond traditional information mixing. The proposed GATE algorithm decomposes the graph into tree blocks, enabling agents to cooperatively optimize edge variables via message passing and local minimizations. A surrogate variant, GATE-S, further enhances efficiency using tractable local models and lightweight message parametrizations, achieving linear convergence with rates dependent on network topology and function properties.
Graph decomposition, not just communication, is the key to unlocking efficient decentralized optimization, enabling algorithms that tear networks into cooperative subproblems.
We study the minimization of sums of smooth strongly convex functions over undirected graphs, with each function held by one agent and communication restricted to neighbors in the graph. Existing decentralized methods, whether based on gossip or on routing over spanning trees, typically use the network to mix or aggregate information to enable {\it prescribed} local optimization updates. What this communication-centered viewpoint lacks is a general framework that uses graph structure to {\it jointly} design the optimization subproblems and the cooperative computation and communication through which agents solve them cooperatively. We develop such a framework from first principles, jointly designing the linear representation of agreement constraints, the blocks of the resulting dual variables (jointly optimized), and connected cluster of agents that cooperatively solve each block subproblem over the assigned subgraph. GATE (Graph-Tearing message passing) is a first instance of this framework: one variable per edge and tree blocks. At each iteration, agents update their assigned edge variables by minimizing the sum of the two endpoint cost-to-go messages and relaxing the result. The messages are updated through local minimizations following the tree recursion. To reduce per-iteration computational and communication costs, we develop GATE-S, a surrogate variant using tractable local models and lightweight message parametrizations. We establish linear convergence with a rate explicit in the interplay among function regularity, network topology, and the chosen partition, revealing the effects of graph decomposition. Numerical experiments are conducted to validate the theoretical results and evaluate the efficiency of our algorithms.