Conditional Gradient Methods via Stochastic Path-Integrated Differential Estimator
Alp Yurtsever · Suvrit Sra · Volkan Cevher

Tue Jun 11th 04:35 -- 04:40 PM @ Grand Ballroom

We 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 known FW variants 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. Our numerical evidence supports our theoretical findings, and demonstrates the superiority of SPIDER-FW and SPIDER-CGS.

Author Information

Alp Yurtsever (EPFL)
Suvrit Sra (MIT)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors