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