Improving the Transient Times for Distributed Stochastic Gradient Methods

Abstract

We consider the distributed optimization problem where $n$ agents each possessing a local cost function, collaboratively minimize the average of the $n$ cost functions over a connected network. Assuming stochastic gradient information is available, we study a distributed stochastic gradient algorithm, called exact diffusion with adaptive stepsizes (EDAS) adapted from the Exact Diffusion method and NIDS and perform a non-asymptotic convergence analysis. We not only show that EDAS asymptotically achieves the same network independent convergence rate as centralized stochastic gradient descent (SGD) for minimizing strongly convex and smooth objective functions, but also characterize the transient time needed for the algorithm to approach the asymptotic convergence rate, which behaves as $K_T=\mathcal{O}\left(\frac{n}{1-{\lambda }_2}\right)$, where $1-{\lambda }_2$ stands for the spectral gap of the mixing matrix. To the best of our knowledge, EDAS achieves the shortest transient time when the average of the $n$ cost functions is strongly convex and each cost function is smooth. Numerical simulations further corroborate and strengthen the obtained theoretical results.

References in corpus (8)

• Constrained Consensus
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions

Cited by in corpus (4)

• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency