Asynchronous Stochastic Frank-Wolfe Algorithms for Non-Convex Optimization

Asynchronous Stochastic Frank-Wolfe Algorithms for Non-Convex Optimization

Bin Gu, Wenhan Xian, Heng Huang

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 737-743. https://doi.org/10.24963/ijcai.2019/104

Asynchronous parallel stochastic optimization for non-convex  problems  becomes more and more   important in machine learning especially due to the popularity of deep learning. The Frank-Wolfe (a.k.a. conditional gradient) algorithms  has regained much interest  because of  its projection-free property and the ability of handling structured constraints. However,  our understanding of  asynchronous stochastic Frank-Wolfe algorithms is  extremely limited especially in the non-convex setting. To address this challenging problem, in this paper, we propose our  asynchronous stochastic  Frank-Wolfe algorithm (AsySFW) and  its variance reduction version (AsySVFW) for solving the constrained non-convex optimization problems.  More importantly, we  prove the fast convergence rates  of   AsySFW and AsySVFW in the non-convex setting. To the best of our knowledge, AsySFW and AsySVFW  are the first asynchronous parallel stochastic algorithms with convergence guarantees for solving the constrained  non-convex optimization problems. The  experimental  results on real high-dimensional gray-scale images   not only confirm the  fast convergence  of   our algorithms, but also show  a near-linear speedup  on a parallel system with shared memory due to the lock-free implementation.
Keywords:
Computer Vision: Big Data and Large Scale Methods
Machine Learning Applications: Big data ; Scalability