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 @math accuracy. For example, we improve from @math to @math if the objective function is smooth and strongly convex, and from @math to @math 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.
@cite_1: In this paper, we present a new conditional gradient type method for convex optimization by calling a linear optimization ( @math ) oracle to minimize a series of linear functions over the feasible set. Different from the classic conditional gradient method, the conditional gradient sliding (CGS) algorithm developed herein can skip the computation of gradients from time to time and, as a result, can achieve the optimal complexity bounds in terms of not only the number of calls to the @math oracle but also the number of gradient evaluations. More specifically, we show that the CGS method requires @math and @math gradient evaluations, respectively, for solving smooth and strongly convex problems, while still maintaining the optimal @math bound on the number of calls to the @math oracle. We also develop variants of the CGS method which can achieve the optimal complexity bounds for solving stochastic optimization problems and an important class...
Stochastic Condition Gradient Sliding (SCGS), recently proposed by @cite_1 , uses Nesterov's acceleration technique to speed up Frank-Wolfe. Without strong convexity, SCGS needs @math stochastic gradients, improving SFW. With strong convexity, this number can even be improved to @math . In both cases, the number of linear optimization steps is @math . The key idea of our algorithms is to combine the variance reduction technique proposed in with some of the above-mentioned algorithms. For example, our algorithm SVRF combines this technique with SFW, also improving the number of stochastic gradients from @math to @math , but without any extra conditions (such as Lipschitzness required for SCGS). More importantly, despite having seemingly same convergence rate, SVRF substantially outperforms SCGS empirically (see ).