Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
复制标题
DOI：
--
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Artin Spiridonoff;Alexander Olshevsky;I. Paschalidis
中科院分区：
文献类型：
--
作者：
Artin Spiridonoff;Alexander Olshevsky;I. Paschalidis
我们考虑函数和的分布式优化的标准模型F(Z)=∑i=1nfi(Z)，其中网络中的节点i持有函数fi(Z)。我们允许以异步更新、消息延迟、不可预测的消息丢失和节点之间的定向通信为特征的苛刻网络模型。在这种情况下，我们分析了分布式优化的梯度推进法的一种修改，假设(I)节点I能够产生其函数Fi(Z)的梯度，该梯度在每一步都被零均值有界支撑加性噪声破坏，(Ii)F(Z)是强凸的，以及(Iii)每个Fi(Z)都有Lipschitz梯度。我们证明了我们所提出的方法的渐近性能以及在所有函数F1(Z)、…的噪声梯度和的方向上采取步骤的集中梯度下降的最优界每一步，Fn(Z)。
We consider the standard model of distributed optimization of a sum of functions F(z)=∑i=1nfi(z), where node i in a network holds the function fi(z). We allow for a harsh network model characterized by asynchronous updates, message delays, unpredictable message losses, and directed communication among nodes. In this setting, we analyze a modification of the Gradient-Push method for distributed optimization, assuming that (i) node i is capable of generating gradients of its function fi(z) corrupted by zero-mean bounded–support additive noise at each step, (ii) F(z) is strongly convex, and (iii) each fi(z) has Lipschitz gradients. We show that our proposed method asymptotically performs as well as the best bounds on centralized gradient descent that takes steps in the direction of the sum of the noisy gradients of all the functions f1(z), …, fn(z) at each step.