Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
Xiangru Lian, Yijun Huang, Yuncheng Li et al. · arXiv (Cornell University) · 2015
Asynchronous parallel implementations of stochastic gradient (SG) have been broadly used in solving deep neural network and received many successes in practice recently. However, existing theories cannot explain their convergence and speedup properties, mainly due to the nonconvexity of most deep learning formulations and the asynchronous parallel mechanism. To fill the gaps in theory and provide theoretical supports, this paper studies two asynchronous parallel implementations of SG: one is on the computer network and the other is on the shared memory system. We establish an ergodic convergence rate $O(1/\sqrt{K})$ for both algorithms and prove that the linear speedup is achievable if the number of workers is bounded by $\sqrt{K}$ ($K$ is the total number of iterations). Our results generalize and improve existing analysis for convex minimization.
Cited by 324 works. doi:10.48550/arxiv.1506.08272 Open-access PDF
Authors
References
- ImageNet classification with deep convolutional neural networks
- Learning Multiple Layers of Features from Tiny Images
- Caffe
- 10.1162/153244303322533223
- Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Online Passive-Aggressive Algorithms
- Robust Stochastic Approximation Approach to Stochastic Programming
- Parallelized Stochastic Gradient Descent
- Scaling distributed machine learning with the parameter server