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 @math convergence rate for Async-SGD and @math 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.
4) Asynchronous SGD for non-convex problems: Similar to their synchronous counterparts, Async-SGD for nonconvex optimization problems also starts to attract some attentions lately. For example, @cite_1 studied the convergence rate of Async-SGD for non-convex optimization problems with bounded delay, where they showed an @math sublinear convergence rate. However, the best convergence rate they provided is highly dependent on the step-size selection strategy, which in turn depends on some a priori iteration threshold value @math . Most recently in , an asynchronous mini-batch SVRG with bounded delay is proposed for solving non-convex optimization problems. They proved that the proposed method converges with an @math convergence rate for non-convex optimization.
@cite_1
778657980
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 @math for both algorithms and prove that the linear speedup is achievable if the number of workers is bounded by @math ( @math is the total number of iterations). Our results generalize and improve existing analysis for convex minimization.