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

2019/06/06 by Shi Pu, Alex Olshevsky, Pu, Shi +3 · 2 citations
Computer Science · Engineering · #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Parallel #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1906.02702

openalex publication_date 2019/06/06 · openalex created_date 2020/03/13 · openalex updated_date 2026/07/28

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=O((n)/((1-ρ_w)²)), where 1-ρ_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 Ω((n)/((1-ρ_w)²) ), implying the sharpness of the obtained result. Numerical experiments demonstrate the tightness of the theoretical results.

Citations

• A Stochastic Approximation Method
• Stochastic Estimation of the Maximum of a Regression Function
• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• Constrained Consensus and Optimization in Multi-Agent Networks
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Decentralized Stochastic Optimization and Gossip Algorithms with\n Compressed Communication
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• Distributed stochastic gradient tracking methods
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions

Cited by

• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• A fast randomized incremental gradient method for decentralized non-convex optimization

Related

• Improving the Transient Times for Distributed Stochastic Gradient Methods
• Convergence rates for distributed stochastic optimization over random\n networks
• Distributed Stochastic Gradient Tracking Methods
• An Accelerated Distributed Stochastic Gradient Method with Momentum
• Distributed Learning in Non-Convex Environments -- Part I: Agreement at\n a Linear Rate