Asynchronous Stochastic Frank-Wolfe Algorithms for Non-Convex Optimization

Abstract

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.