Distributed Learning in Non-Convex Environments -- Part II: Polynomial Escape from Saddle-Points

The diffusion strategy for distributed learning from streaming data employs\nlocal stochastic gradient updates along with exchange of iterates over\nneighborhoods. In Part I [2] of this work we established that agents cluster\naround a network centroid and proceeded to study the dynamics of this point. We\nestablished expected descent in non-convex environments in the large-gradient\nregime and introduced a short-term model to examine the dynamics over\nfinite-time horizons. Using this model, we establish in this work that the\ndiffusion strategy is able to escape from strict saddle-points in O(1/$\\mu$)\niterations; it is also able to return approximately second-order stationary\npoints in a polynomial number of iterations. Relative to prior works on the\npolynomial escape from saddle-points, most of which focus on centralized\nperturbed or stochastic gradient descent, our approach requires less\nrestrictive conditions on the gradient noise process.\n