Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
复制标题
DOI：
10.1109/tac.2017.2713046
复制
发表时间：
2018-01-01
影响因子：
6.8
通讯作者：
Ma, S.
中科院分区：
文献类型：
--
作者：
Aybat, N. S.;Wang, Z.;Ma, S.
给定一个无向图 G = (N, epsilon)，其中代理 N = {1,..., N} 与 epsilon 中的边相连，我们研究如何计算最佳决策，使代理之间达成共识，并最小化特定于代理的私有凸复合函数 {Phi(i)}（i 是 N 的元素）的总和，其中 Phi(i) (sic) xi(i) + f(i) 属于代理 i。假设只有通过边缘连接的代理才能通信，我们提出了一种分布式近端梯度算法（DPGA），用于在未加权和加权静态（无向）通信网络上进行共识优化。在一次迭代中，每个智能体-i 计算 xi(i) 的 prox 图和 fi 的梯度，然后与相邻智能体进行本地通信。我们还研究了它的随机梯度变体 SDPGA，它只能访问每个智能体 i 处的 del f(i) 的噪声估计。该计算模型抽象了分布式传感、机器学习和统计推理中的许多应用。我们展示了 DPGA 和 SDPGA 的次优误差和共识违背的遍历收敛性，速率分别为 O(1/t) 和 O(1/root t)。
Given an undirected graph G = (N, epsilon) of agents N = {1,..., N} connected with edges in epsilon, we study how to compute an optimal decision on which there is consensus among agents and that minimizes the sum of agent-specific private convex composite functions {Phi(i)}(i is an element of N), where Phi(i) (sic) xi(i) + f(i) belongs to agent-i. Assuming only agents connected by an edge can communicate, we propose a distributed proximal gradient algorithm (DPGA) for consensus optimization over both unweighted and weighted static (undirected) communication networks. In one iteration, each agent-i computes the prox map of xi(i) and gradient of fi, and this is followed by local communication with neighboring agents. We also study its stochastic gradient variant, SDPGA, which can only access to noisy estimates of del f(i) at each agent-i. This computational model abstracts a number of applications in distributed sensing, machine learning and statistical inference. We show ergodic convergence in both suboptimality error and consensus violation for the DPGA and SDPGA with rates O(1/t) and O(1/root t), respectively.