Distributed stochastic optimization with gradient tracking over strongly-connected networks
Distributed stochastic optimization with gradient tracking over strongly-connected networks
复制标题
DOI：
10.1109/cdc40024.2019.9029217
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Ran Xin;Anit Kumar Sahu;U. Khan;S. Kar
中科院分区：
文献类型：
--
作者：
Ran Xin;Anit Kumar Sahu;U. Khan;S. Kar
在这篇文章中，我们研究了分布式随机优化问题，以最小化在强连通图上通信的代理网络上的光滑和强凸局部代价函数的和。假设每个智能体都可以访问一个随机的一阶预言$\Left({\Mathcal{S}\Mathcal{F}\Mathcal{O}}\Right)$，我们提出了一种新的分布式方法，称为$\Mathcal{S}-\Mathcal{A}\Mathcal{B}$，其中每个智能体使用一个辅助变量来渐近跟踪期望中全局费用的梯度。$\Mathcal{S}-\Mathcal{A}\Mathcal{B}$算法同时使用行和列随机权重来确保一致性和最优性。由于不使用双随机权，因此$\Mathcal{S}-\Mathcal{A}\Mathcal{B}$适用于任意强连通图。我们证明了在一个足够小的恒定步长下，$\数学{S}-\数学{A}\数学{B}$在期望均方意义下线性收敛到全局极小点的一个邻域。我们给出了基于真实世界数据集的数值模拟来说明理论结果。
In this paper, we study distributed stochastic optimization to minimize a sum of smooth and strongly-convex local cost functions over a network of agents, communicating over a strongly-connected graph. Assuming that each agent has access to a stochastic first-order oracle $\left( {\mathcal{S}\mathcal{F}\mathcal{O}} \right)$, we propose a novel distributed method, called $\mathcal{S} - \mathcal{A}\mathcal{B}$, where each agent uses an auxiliary variable to asymptotically track the gradient of the global cost in expectation. The $\mathcal{S} - \mathcal{A}\mathcal{B}$ algorithm employs rowand column-stochastic weights simultaneously to ensure both consensus and optimality. Since doubly-stochastic weights are not used, $\mathcal{S} - \mathcal{A}\mathcal{B}$ is applicable to arbitrary strongly-connected graphs. We show that under a sufficiently small constant step-size, $\mathcal{S} - \mathcal{A}\mathcal{B}$ converges linearly (in expected mean-square sense) to a neighborhood of the global minimizer. We present numerical simulations based on real-world data sets to illustrate the theoretical results.