Linear Convergence of Stochastic Frank Wolfe Variants

arXiv1703.07269MaRDI QIDQ6284636FDOQ6284636

Authors: Donald Goldfarb, G. Iyengar, Chaoxu Zhou 

Publication date: 21 March 2017

Abstract: In this paper, we show that the Away-step Stochastic Frank-Wolfe Algorithm (ASFW) and Pairwise Stochastic Frank-Wolfe algorithm (PSFW) converge linearly in expectation. We also show that if an algorithm convergences linearly in expectation then it converges linearly almost surely. In order to prove these results, we develop a novel proof technique based on concepts of empirical processes and concentration inequalities. Such a technique has rarely been used to derive the convergence rates of stochastic optimization algorithms. In large-scale numerical experiments, ASFW and PSFW perform as well as or better than their stochastic competitors in actual CPU time.

This page was built for publication: Linear Convergence of Stochastic Frank Wolfe Variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284636)