论文标题
在插值样条件下的随机条件梯度方法改善的复杂性
Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
论文作者
论文摘要
我们分析了随机条件梯度方法，用于在过度参数化的机器学习中产生的约束优化问题。我们表明，人们可以利用这种模型满足的类似插值状况来获得改善的甲骨文复杂性。具体来说，当目标函数是凸面时，我们表明条件梯度方法需要$ \ Mathcal {o}（ε^{ - 2}）$调用随机梯度甲骨文来找到$ε$ - optimal的解决方案。此外，通过包括一个梯度滑动步骤，我们表明呼叫的数量减少到$ \ MATHCAL {O}（ε^{ - 1.5}）$。
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})$.
