Linear Speedup in Saddle-Point Escape for Decentralized Non-Convex Optimization
This work addresses the challenge of efficient decentralized optimization for non-convex problems, which is incremental by extending prior results from first-order to second-order stationary points.
The paper tackles the problem of achieving linear speedup in saddle-point escape time for decentralized non-convex optimization, showing that symmetric combination policies enable linear speedup proportional to the number of agents, with potential improvements using asymmetric weights.
Under appropriate cooperation protocols and parameter choices, fully decentralized solutions for stochastic optimization have been shown to match the performance of centralized solutions and result in linear speedup (in the number of agents) relative to non-cooperative approaches in the strongly-convex setting. More recently, these results have been extended to the pursuit of first-order stationary points in non-convex environments. In this work, we examine in detail the dependence of second-order convergence guarantees on the spectral properties of the combination policy for non-convex multi agent optimization. We establish linear speedup in saddle-point escape time in the number of agents for symmetric combination policies and study the potential for further improvement by employing asymmetric combination weights. The results imply that a linear speedup can be expected in the pursuit of second-order stationary points, which exclude local maxima as well as strict saddle-points and correspond to local or even global minima in many important learning settings.