arXiv：cs.LG· Kuangyu Ding, Gesualdo Scutari·· 9 小时前AI 评分32
GATE：去中心化优化中基于消息传递的图分解框架
From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
AI 导读
研究者提出 GATE（Graph-Tearing message passing）框架，用图结构联合设计优化子问题与智能体间的协作计算和通信，每条边对应一个变量、以树块划分，并给出轻量代理变体 GATE-S。理论证明该算法具有线性收敛率，收敛速度显式取决于函数正则性、网络拓扑与所选划分之间的相互作用，数值实验验证了理论结果与算法效率。
正文
Abstract: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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.03709 [math.OC] |
| (or arXiv:2610.03709v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03709 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kuangyu Ding [view email]
[v1]
Fri, 2 Oct 2026 17:57:50 UTC (2,823 KB)
来源：arXiv：cs.LG · arxiv.org