Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning

Abstract

Understanding the convergence performance of asynchronous stochastic gradient descent method (Async-SGD) has received increasing attention in recent years due to their foundational role in machine learning. To date, however, most of the existing works are restricted to either bounded gradient delays or convex settings. In this paper, we focus on Async-SGD and its variant Async-SGDI (which uses increasing batch size) for non-convex optimization problems with unbounded gradient delays. We prove $o(1/\sqrt{k})$ convergence rate for Async-SGD and $o(1/k)$ for Async-SGDI. Also, a unifying sufficient condition for Async-SGD's convergence is established, which includes two major gradient delay models in the literature as special cases and yields a new delay model not considered thus far.

2020 IEEE 59th Conference on Decision and Control (CDC)

References in corpus (6)

• Stochastic Variance Reduction for Nonconvex Optimization
• Asynchronous Stochastic Gradient Descent with Delay Compensation
• Parallel training of DNNs with Natural Gradient and Parameter Averaging
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Asynchronous Coordinate Descent under More Realistic Assumptions
• On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

Cited by in corpus (4)

• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Fast Federated Learning in the Presence of Arbitrary Device Unavailability
• Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?