Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
This work addresses the challenge of scaling distributed training efficiently for machine learning practitioners by offering the first theoretical guarantee on second-order convergence in asynchronous algorithms, though it is incremental as it builds on existing APSGD methods.
The paper tackles the problem of asynchronous parallel stochastic gradient descent (APSGD) in non-convex optimization by analyzing its second-order convergence near saddle points, providing a theoretical guarantee that linear speedup is achieved when the number of workers is bounded by $\widetilde{O}(K^{1/3}M^{-1/3})$, where $K$ is total steps and $M$ is mini-batch size, ensuring convergence to stationary points with specific gradient and Hessian bounds.
In machine learning, asynchronous parallel stochastic gradient descent (APSGD) is broadly used to speed up the training process through multi-workers. Meanwhile, the time delay of stale gradients in asynchronous algorithms is generally proportional to the total number of workers, which brings additional deviation from the accurate gradient due to using delayed gradients. This may have a negative influence on the convergence of the algorithm. One may ask: How many workers can we use at most to achieve a good convergence and the linear speedup? In this paper, we consider the second-order convergence of asynchronous algorithms in non-convex optimization. We investigate the behaviors of APSGD with consistent read near strictly saddle points and provide a theoretical guarantee that if the total number of workers is bounded by $\widetilde{O}(K^{1/3}M^{-1/3})$ ($K$ is the total steps and $M$ is the mini-batch size), APSGD will converge to good stationary points ($||\nabla f(x)||\leq ε, \nabla^2 f(x)\succeq -\sqrtε\bm{I}, ε^2\leq O(\sqrt{\frac{1}{MK}}) $) and the linear speedup is achieved. Our works give the first theoretical guarantee on the second-order convergence for asynchronous algorithms. The technique we provide can be generalized to analyze other types of asynchronous algorithms to understand the behaviors of asynchronous algorithms in distributed asynchronous parallel training.