Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness,\n and Convergence to Local Minima

In centralized settings, it is well known that stochastic gradient descent\n(SGD) avoids saddle points and converges to local minima in nonconvex problems.\nHowever, similar guarantees are lacking for distributed first-order algorithms.\nThe paper studies distributed stochastic gradient descent (D-SGD)--a simple\nnetwork-based implementation of SGD. Conditions under which D-SGD avoids saddle\npoints and converges to local minima are studied. First, we consider the\nproblem of computing critical points. Assuming loss functions are nonconvex and\npossibly nonsmooth, it is shown that, for each fixed initialization, D-SGD\nconverges to critical points of the loss with probability one. Next, we\nconsider the problem of avoiding saddle points. In this case, we again assume\nthat loss functions may be nonconvex and nonsmooth, but are smooth in a\nneighborhood of a saddle point. It is shown that, for any fixed initialization,\nD-SGD avoids such saddle points with probability one. Results are proved by\nstudying the underlying (distributed) gradient flow, using the ordinary\ndifferential equation (ODE) method of stochastic approximation, and extending\nclassical techniques from dynamical systems theory such as stable manifolds.\nResults are proved in the general context of subspace-constrained optimization,\nof which D-SGD is a special case.\n