Variance-Reduced and Projection-Free Stochastic Optimization

The Frank-Wolfe optimization algorithm has recently regained popularity for machine learning applications due to its projection-free property and its ability to handle structured constraints. However, in the stochastic learning setting, it is still relatively understudied compared to the gradient descent counterpart. In this work, leveraging a recent variance reduction technique, we propose two stochastic Frank-Wolfe variants which substantially improve previous results in terms of the number of stochastic gradient evaluations needed to achieve 1-ε accuracy. For example, we improve from O(frac1ε) to O(lnfrac1ε) if the objective function is smooth and strongly convex, and from O(frac1ε2) to O(frac1ε1.5) if the objective function is smooth and Lipschitz. The theoretical improvement is also observed in experiments on real-world datasets for a multiclass classification application.