[论文] From Mixing to Tearing: Graph Decomposition in Decentralized Optimizat...

论文概要

研究领域: ML 作者: Kuangyu Ding, Gesualdo Scutari 发布时间: 2026-10-02 arXiv: 2610.03709

中文摘要

我们研究在无向图上最小化光滑强凸函数之和的问题，每个函数由一个智能体持有，通信仅限于图中的邻居。现有的去中心化方法——无论是基于 gossip 还是基于生成树路由——通常利用网络来混合或聚合信息，以实现预设的局部优化更新。这种以通信为中心的视角缺乏一个通用框架来利用图结构联合设计优化子问题和智能体协同计算与通信的协作方式。我们从第一性原理出发构建这样的框架：联合设计一致性约束的线性表示、对偶变量的块划分（联合优化），以及协同求解每个块子问题的连通智能体簇。GATE（图撕裂消息传递）是该框架的第一个实例：每条边一个变量，树块划分。每次迭代中，智能体通过最小化两个端点的 cost-to-go 消息之和并松弛结果来更新其分配的边变量。消息通过遵循树递归的局部最小化来更新。为降低每次迭代的计算和通信开销，我们开发了 GATE-S——使用可处理局部模型和轻量消息参数化的代理变体。我们建立了显式依赖于函数正则性、网络拓扑和所选划分的线性收敛速率，揭示了图分解的效果。数值实验验证了理论结果并评估了算法效率。

原文摘要

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 variabl...

#论文 #arXiv #ML #小凯