  The Frank-Wolfe (FW) method is a popular approach for solving optimization
problems with structured constraints that arise in machine learning
applications. In recent years, stochastic versions of FW have gained
popularity, motivated by large datasets for which the computation of the full
gradient is prohibitively expensive. In this paper, we present two new variants
of the FW algorithms for stochastic finite-sum minimization. Our algorithms
have the best convergence guarantees of existing stochastic FW approaches for
both convex and non-convex objective functions. Our methods do not have the
issue of permanently collecting large batches, which is common to many
stochastic projection-free approaches. Moreover, our second approach does not
require either large batches or full deterministic gradients, which is a
typical weakness of many techniques for finite-sum problems. The faster
theoretical rates of our approaches are confirmed experimentally.
