Distributed Learning in Non-Convex Environments -- Part II: Polynomial Escape from Saddle-Points
This work addresses the challenge of efficient optimization in distributed non-convex settings, which is incremental relative to existing centralized approaches.
The paper tackles the problem of distributed learning in non-convex environments, showing that the diffusion strategy can escape strict saddle-points in O(1/μ) iterations and find approximately second-order stationary points in polynomial time, with less restrictive gradient noise conditions than prior centralized methods.
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/$μ$) iterations; it is also able to return approximately second-order stationary points in a polynomial number of iterations. Relative to prior works on the polynomial escape from saddle-points, most of which focus on centralized perturbed or stochastic gradient descent, our approach requires less restrictive conditions on the gradient noise process.