On the O(1/k)𝑂1𝑘O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers∗
Ermin Wei† and Asuman Ozdaglar† †Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
Abstract
We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with $O(1/\sqrt{k})$ rate of convergence (where $k$ is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate $O\left(1/k\right)$ .
中文速览
分布式多智能体网络中，各节点只掌握自己的局部目标函数，却需要协同求解一个带线性耦合约束的全局优化问题，现有方法要么收敛慢（基于次梯度的方法仅达到 O(1/√k)），要么必须依赖同步时钟和全局已知的节点顺序（同步 ADMM），难以在真实去中心化场景中落地。本文提出一种异步 ADMM（Alternating Direction Method of Multipliers）分布式算法：每次迭代随机激活一部分约束，只让涉及这些约束的智能体更新各自的原变量，再统一更新对偶变量，完全无需全局时钟或固定更新顺序。理论上证明了算法几乎必然收敛到最优解，并在约束集紧致的条件下建立了 O(1/k) 的收敛速率——目标函数值与最优值之差以及约束违反量均以此速率趋于零。这一结果在收敛速度上优于现有异步分布式优化方法，为大规模机器学习、资源分配等实际网络应用提供了理论更扎实、工程更易实现的算法框架。
原文 arXiv:1307.8254;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1307.8254v1