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

Understand

The diffusion strategy for distributed learning from streaming data employs local stochastic gradient updates along with exchange of iterates over neighborhoods.

• In Part I [2] of this work we established that agents cluster around a network centroid and proceeded to study the dynamics of this point.
• We established expected descent in non-convex environments in the large-gradient regime and introduced a short-term model to examine the dynamics over finite-time horizons.
• Using this model, we establish in this work that the diffusion strategy is able to escape from strict saddle-points in O(1/$\mu$) iterations; it is also able to return approximately second-order stationary points in a polynomial number of iterations.