Non-Convex Distributed Optimization
Authors:
- 5 January 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 62 (8) , 3744-3757
Abstract
We study distributed non-convex optimization on a time-varying multi-agent network. Each node has access to its own smooth local cost function, and the collective goal is to minimize the sum of these functions. The perturbed push-sum algorithm was previously used for convex distributed optimization. We generalize the result obtained for the convex case to the case of non-convex functions. Under some additional technical assumptions on the gradients we prove the convergence of the distributed push-sum algorithm to some critical point of the objective function. By utilizing perturbations on the update process, we show the almost sure convergence of the perturbed dynamics to a local minimum of the global objective function, if the objective function has no saddle points. Our analysis shows that this perturbed procedure converges at a rate of O(1/t).Keywords
All Related Versions
Funding Information
- German Research Foundation (DFG)
- GRK 1362 “Cooperative, Adaptive and Responsive Monitoring of Mixed Mode Environments”
- Air Force Office of Scientific Research
- AFOSR-YIP (FA9550-16-1-0400)
This publication has 30 references indexed in Scilit:
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems2015
- Distributed Optimization Over Time-Varying Directed GraphsIEEE Transactions on Automatic Control, 2014
- Non-convex Optimization on Stiefel Manifold and Applications to Machine Learning2012
- Distributed multi-agent optimization with state-dependent communicationMathematical Programming, 2011
- Distributed Stochastic Subgradient Projection Algorithms for Convex OptimizationJournal of Optimization Theory and Applications, 2010
- Gossip-based computation of aggregate information2004
- Simulated AnnealingStatistical Science, 1993
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986
- Strong Convergence of a Stochastic Approximation AlgorithmThe Annals of Statistics, 1978
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951