Primal-dual stochastic distributed algorithm for constrained convex optimization
Primal-dual stochastic distributed algorithm for constrained convex optimization
复制标题
约束凸优化的原对偶随机分布式算法
DOI：
10.1016/j.jfranklin.2019.07.018
复制
发表时间：
2019-11-01
影响因子：
4.1
通讯作者：
Li, Huaqing
中科院分区：
文献类型：
--
作者：
Niu, Youcheng;Wang, Haijing;Li, Huaqing
本文研究了无向连通网络上的分布式凸优化问题，其中每个节点的变量都位于一个私有的约束凸集内，所有节点的目标是使所有局部目标函数的和共同最小。考虑到大规模训练集分布到多个自治节点的机器学习问题中的各种应用，进一步将每个局部目标函数设计为中等个数的局部瞬时函数的平均值。每个局部目标函数和约束集不能与其他人共享。提出了一种解决分布式凸优化问题的原始-对偶随机算法，其中每个节点通过在其私有约束集上利用无偏随机平均梯度和投影来更新其状态。在每次迭代中，对每个节点随机选择的一个局部瞬时函数的梯度进行评估，并使用最近随机梯度的平均值来逼近真实的局部梯度。在约束条件下，证明了在局部瞬时函数的强凸性和梯度的Lipschitz连续性的条件下，算法几乎必然收敛于全局最优解。在无约束情况下，给出了算法的显式线性收敛速度。数值实验验证了理论结果的正确性。(C)2019年富兰克林研究所。爱思唯尔有限公司出版。保留所有权利。
This paper investigates distributed convex optimization problems over an undirected and connected network, where each node's variable lies in a private constrained convex set, and overall nodes aim at collectively minimizing the sum of all local objective functions. Motivated by a variety of applications in machine learning problems with large-scale training sets distributed to multiple autonomous nodes, each local objective function is further designed as the average of moderate number of local instantaneous functions. Each local objective function and constrained set cannot be shared with others. A primal-dual stochastic algorithm is presented to address the distributed convex optimization problems, where each node updates its state by resorting to unbiased stochastic averaging gradients and projects on its private constrained set. At each iteration, for each node the gradient of one local instantaneous function selected randomly is evaluated and the average of the most recent stochastic gradients is used to approximate the true local gradient. In the constrained case, we show that with strong-convexity of the local instantaneous function and Lipschitz continuity of its gradient, the algorithm converges to the global optimization solution almost surely. In the unconstrained case, an explicit linear convergence rate of the algorithm is provided. Numerical experiments are presented to demonstrate correctness of the theoretical results. (C) 2019 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.