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 projectionfree 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 con-
firm 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