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}(\epsilon^{-2})$ calls to the stochastic gradient oracle to find an $\epsilon$-optimal solution. Furthermore, by including a gradient sliding step, we show that the number of calls reduces to $\mathcal{O}(\epsilon^{-1.5})$.
翻译：我们分析过度平衡的机器学习中产生的限制优化问题的随机有条件梯度方法。 我们显示, 可以利用这些模型所满足的内推性条件来获得更佳的神器复杂性。 具体地说, 当目标功能是二次曲线时, 我们显示, 有条件梯度方法需要$\ mathcal{O}(\\ epsilon}%-2}) $ 来给随机梯度梯度或极佳的解答。 此外, 通过加入一个梯度滑动步骤, 我们显示, 调用数量会下降到$\ mathcal{O}(\ epsilon}- 1. 5} $ 。
相关内容
微信扫码咨询专知VIP会员