A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent

Abstract

This paper is concerned with minimizing the average of $n$ cost functions over a network in which agents may communicate and exchange information with each other. We consider the setting where only noisy gradient information is available. To solve the problem, we study the distributed stochastic gradient descent (DSGD) method and perform a non-asymptotic convergence analysis. For strongly convex and smooth objective functions, DSGD asymptotically achieves the optimal network independent convergence rate compared to centralized stochastic gradient descent (SGD). Our main contribution is to characterize the transient time needed for DSGD to approach the asymptotic convergence rate, which we show behaves as $K_T=\mathcal{O}\left(\frac{n}{(1-{\rho }_w{)}^2}\right)$, where $1-{\rho }_w$ denotes the spectral gap of the mixing matrix. Moreover, we construct a "hard" optimization problem for which we show the transient time needed for DSGD to approach the asymptotic convergence rate is lower bounded by $\Omega \left(\frac{n}{(1-{\rho }_w{)}^2}\right)$, implying the sharpness of the obtained result. Numerical experiments demonstrate the tightness of the theoretical results.

References in corpus (14)

• Constrained Consensus
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Stochastic Gradient Push for Distributed Deep Learning
• Distributed Recursive Least-Squares: Stability and Performance Analysis
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Supervised Learning Under Distributed Features
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning

Cited by in corpus (20)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Recent theoretical advances in decentralized distributed convex optimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Distributed Stochastic Gradient Tracking Methods
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Rate of Convergence for Distributed Optimization with Uncertain Communications
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• A fast randomized incremental gradient method for decentralized non-convex optimization
• A general framework for decentralized optimization with first-order methods
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
• Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize
• Nested Distributed Gradient Methods with Stochastic Computation Errors