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 centralized methods.
Annealing for Distributed Global Optimization
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
The paper proves convergence to global optima for a class of distributed algorithms for nonconvex optimization in network-based multi-agent settings. Agents are permitted to communicate over a time-varying undirected graph. Each agent is assumed to possess a local objective function (assumed to be smooth, but possibly nonconvex). The paper considers algorithms for optimizing the sum function. A distributed algorithm of the consensus+innovations type is proposed which relies on first-order information at the agent level. Under appropriate conditions on network connectivity and the cost objective, convergence to the set of global optima is achieved by an annealing-type approach, with decaying Gaussian noise independently added into each agent's update step. It is shown that the proposed algorithm converges in probability to the set of global minima of the sum function.
years
2019 3verdicts
UNVERDICTED 3representative citing papers
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.
Diffusion learning achieves linear-rate agreement around the network centroid in stochastic non-convex distributed optimization.
citing papers explorer
-
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 centralized methods.
-
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.