Yurtsever, AlpSra, SuvritCevher, Volkan2019-05-072019-05-072019-05-072019https://infoscience.epfl.ch/handle/20.500.14299/156285We propose a class of novel variance-reduced stochastic conditional gradient methods. By adopting the recent stochastic path-integrated differential estimator technique (SPIDER) of Fang et al. (2018) for the classical Frank-Wolfe (FW) method, we introduce SPIDER-FW for finite-sum minimization as well as the more general expectation minimization problems. SPIDER-FW enjoys superior complexity guarantees in the non-convex setting while matching the best FW variants in the literature in the convex case. We also extend our framework `a la conditional gradient sliding (CGS) of Lan & Zhou (2016) and propose SPIDER-CGS to further reduce the stochastic first-order oracle complexity.ml-aitext::conference output::conference proceedings::conference paper