# Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions

arXiv: https://arxiv.org/abs/2006.08167 · HTML: https://mlsanity.com/paper/2006.08167/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 2 of 2)

- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)

## Abstract (arXiv)

We analyze stochastic conditional gradient methods for constrained optimization problems arising in over-parametrized machine learning. We show that one could leverage the interpolation-like conditions satisfied by such models to obtain improved oracle complexities. Specifically, when the objective function is convex, we show that the conditional gradient method requires O(ε-2) calls to the stochastic gradient oracle to find an ε-optimal solution. Furthermore, by including a gradient sliding step, we show that the number of calls reduces to O(ε-1.5).