Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks

Abstract

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/\epsilon ))$ gradient evaluations and $\mathcal{O}(\kappa \log (1/\epsilon ))$ communications to converge to the same fixed point with the non-accelerated variant where $\kappa$ is the condition number and $\epsilon$ 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.

References in corpus (13)

• Federated Learning: Strategies for Improving Communication Efficiency
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Communication-Efficient Distributed Dual Coordinate Ascent
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• From Averaging to Acceleration, There is Only a Step-size
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method

Cited by in corpus (10)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Recent theoretical advances in decentralized distributed convex optimization
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
• Optimal Gradient Tracking for Decentralized Optimization
• Heavy-Tail Phenomenon in Decentralized SGD
• Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize