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 @math ) 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.
Motivated by these considerations, in this work, we focus on implementations that employ gradient approximations and step-sizes. This is driven by the fact that computation of the exact gradients ( J_k( ) ) is generally infeasible in practice because (a) data may be streaming in, making it impossible to compute ( x_k Q_k( ; ) ) in the absence of knowledge about the distribution of the data or (b) the data set, while available as a batch, may be so large that efficient computation of the full gradient is infeasible. As such, the exact gradient will need to be replaced by an approximate gradient, which ends up introducing in a natural manner some form of into the operation of the algorithm; this noise is the difference between the true gradient and its approximation. The gradient noise seeps into the operation of the algorithm continually and becomes coupled with the evolution of the iterates, resulting in perturbations that are neither identically nor independently distributed over time. For instance, the presence of the gradient noise process complicates the dynamics of the iterate evolution relative to the centralized recursions considered in @cite_24 .
@cite_24
1697075315
We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.