Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
This work addresses optimization efficiency for over-parametrized models, offering incremental improvements in complexity bounds for researchers in machine learning optimization.
The paper tackles the problem of constrained optimization in over-parametrized machine learning by leveraging interpolation-like conditions to improve oracle complexities for stochastic conditional gradient methods. The results show that the conditional gradient method requires O(ε^{-2}) calls to find an ε-optimal solution for convex objectives, which reduces to O(ε^{-1.5}) with a gradient sliding step.
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 $\mathcal{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 $\mathcal{O}(ε^{-1.5})$.