Linear Convergence of Stochastic Frank Wolfe Variants


Donald Goldfarb, Garud Iyengar, Chaoxu Zhou ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1066-1074, 2017.


In this paper, we show that the Away-step Stochastic Frank-Wolfe (ASFW) and Pairwise Stochastic Frank-Wolfe (PSFW) algorithms 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. As far as we know, this technique has not been used previously 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.

Related Material