Second-order Guarantees of Distributed Gradient Algorithms
read the original abstract
We consider distributed smooth nonconvex unconstrained optimization over networks, modeled as a connected graph. We examine the behavior of distributed gradient-based algorithms near strict saddle points. Specifically, we establish that (i) the renowned Distributed Gradient Descent (DGD) algorithm likely converges to a neighborhood of a Second-order Stationary (SoS) solution; and (ii) the more recent class of distributed algorithms based on gradient tracking--implementable also over digraphs--likely converges to exact SoS solutions, thus avoiding (strict) saddle-points. Furthermore, new convergence rate results to first-order critical points is established for the latter class of algorithms.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Distributed Learning in Non-Convex Environments -- Part II: Polynomial Escape from Saddle-Points
Diffusion strategy for distributed learning escapes saddle points in O(1/μ) iterations and returns approximate second-order stationary points in polynomial iterations with less restrictive noise assumptions than centr...
-
Distributed Global Optimization by Annealing
A consensus + innovations algorithm with decaying additive Gaussian noise converges to the global minima of nonconvex functions under technical assumptions, with verification methods and a target-localization example.
-
Distributed Learning in Non-Convex Environments -- Part I: Agreement at a Linear Rate
Diffusion learning achieves linear-rate agreement around the network centroid in stochastic non-convex distributed optimization.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.