Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Alireza Fallah;Mert Gurbuzbalaban;A. Ozdaglar;Umut Simsekli;Lingjiong Zhu
中科院分区：
文献类型：
--
作者：
Alireza Fallah;Mert Gurbuzbalaban;A. Ozdaglar;Umut Simsekli;Lingjiong Zhu
研究了分布式随机梯度（D-SG）方法及其加速变体（D-ASG），用于求解分散强凸随机优化问题，其中目标函数分布在一个固定但任意连通的通信图上的多个计算单元上，受局部通信约束，其中梯度的噪声估计是可用的.我们开发了一个框架，允许选择这些算法的步长和动量参数的方式来优化性能，系统地权衡的偏见，方差，鲁棒性梯度噪声和依赖网络效应。当梯度不包含噪声时，我们还证明了分布式加速方法可以实现加速，要求$\mathcal{O}（\kappa \log（1/\varepsilon））$梯度评估和$\mathcal{O}（\kappa \log（1/\varepsilon））$通信收敛到与非加速变量相同的不动点，其中$\kappa$是条件数，$\varepsilon$是目标精度。据我们所知，这是第一个加速结果，其中迭代复杂度与条件数的平方根成比例，在\n {primal}分布式不精确一阶方法的上下文中。对于二次函数，我们还提供了更精细的性能界限，这些界限对于偏差和方差项来说是严格的。最后，我们研究了一个多阶段版本的D-ASG的参数仔细变化的阶段，以确保准确的$\mathcal{O}（-k/\sqrt{\kappa}）$线性衰减的偏差项，以及最佳的$\mathcal{O}（\sigma^2/k）$的方差项。我们通过数值实验说明，我们的方法在实际的算法，是强大的梯度噪声，可以优于现有的方法。
We study distributed stochastic gradient (D-SG) method and its accelerated variant (D-ASG) for solving decentralized strongly convex stochastic optimization problems where the objective function is distributed over several computational units, lying on a fixed but arbitrary connected communication graph, subject to local communication constraints where noisy estimates of the gradients are available. We develop a framework which allows to choose the stepsize and the momentum parameters of these algorithms in a way to optimize performance by systematically trading off the bias, variance, robustness to gradient noise and dependence to network effects. When gradients do not contain noise, we also prove that distributed accelerated methods can \emph{achieve acceleration}, requiring $\mathcal{O}(\kappa \log(1/\varepsilon))$ gradient evaluations and $\mathcal{O}(\kappa \log(1/\varepsilon))$ communications to converge to the same fixed point with the non-accelerated variant where $\kappa$ is the condition number and $\varepsilon$ is the target accuracy. To our knowledge, this is the first acceleration result where the iteration complexity scales with the square root of the condition number in the context of \emph{primal} distributed inexact first-order methods. For quadratic functions, we also provide finer performance bounds that are tight with respect to bias and variance terms. Finally, we study a multistage version of D-ASG with parameters carefully varied over stages to ensure exact $\mathcal{O}(-k/\sqrt{\kappa})$ linear decay in the bias term as well as optimal $\mathcal{O}(\sigma^2/k)$ in the variance term. We illustrate through numerical experiments that our approach results in practical algorithms that are robust to gradient noise and that can outperform existing methods.