GATE：基于图分解的去中心化优化消息传递框架
From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
一篇去中心化优化的理论论文，提出 GATE 算法，把图拆成树分块来做消息传递，收敛率和图结构直接挂钩，做分布式优化的可以看看。
arXiv 论文提出 GATE（Graph-Tearing message passing），用于在无向图上最小化平滑强凸函数之和，每个函数由一个节点持有，通信仅限邻居。与传统 gossip 或生成树路由方法只做信息混合不同，GATE 从消息传递的第一性原理出发，联合设计一致性约束的线性表示、对偶变量分块和求解每个分块子问题的连通代理集群。GATE 每条边对应一个变量，按树分块递归更新消息；其变体 GATE-S 用可处理的局部模型降低每轮计算和通信开销。论文证明了线性收敛率，其速率显式刻画函数正则性、网络拓扑与图划分之间的相互作用。
From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
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.
