Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
This provides theoretical support for widely used asynchronous parallel methods in deep learning, addressing a gap in understanding for nonconvex problems.
The paper tackles the lack of theoretical convergence guarantees for asynchronous parallel stochastic gradient methods in nonconvex optimization, establishing an ergodic convergence rate of O(1/√K) and proving linear speedup under certain conditions.
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.