A projection-free decentralized algorithm for non-convex optimization
- Resource Type
- Conference
- Authors
- Wai, Hoi-To; Scaglione, Anna; Lafond, Jean; Moulines, Eric
- Source
- 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP) Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on. :475-479 Dec, 2016
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
Signal Processing and Analysis
Optimization
Signal processing algorithms
Algorithm design and analysis
Approximation algorithms
Robustness
Convergence
Prediction algorithms
non-convex optimization
Frank-Wolfe method
decentralized algorithms
gossip algorithms
matrix completion
- Language
This paper considers a decentralized projection free algorithm for non-convex optimization in high dimension. More specifically, we propose a Decentralized Frank-Wolfe (DeFW) algorithm which is suitable when high dimensional optimization constraints are difficult to handle by conventional projection/proximal-based gradient descent methods. We present conditions under which the DeFW algorithm converges to a stationary point and prove that the rate of convergence is as fast as O(l/√T), where T is the iteration number. This paper provides the first convergence guarantee for FrankWolfe methods applied to non-convex decentralized optimization. Utilizing our theoretical findings, we formulate a novel robust matrix completion problem and apply DeFW to give an efficient decentralized solution. Numerical experiments are performed on realistic and synthetic data to support our findings.