Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
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})$.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningSimilar Papers 제목 키워드 기반
Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient estimators for such problems is challeng…
Causal InferenceMeta-LearningregressionStochastic OptimizationMulti-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles
We consider stochastic optimization when one only has access to biased stochastic oracles of the objective and the gradient, and obtaining stochastic gradients with low biases comes at high costs. This setting captures v…
Contrastive LearningSchedulingStochastic OptimizationOn the Bias-Variance-Cost Tradeoff of Stochastic Optimization
We consider stochastic optimization when one only has access to biased stochastic oracles of the objective, and obtaining stochastic gradients with low biases comes at high costs. This setting captures a variety of optim…
Bilevel OptimizationStochastic OptimizationStochastic Recursive Variance-Reduced Cubic Regularization Methods
Stochastic Variance-Reduced Cubic regularization (SVRC) algorithms have received increasing attention due to its improved gradient/Hessian complexities (i.e., number of queries to stochastic gradient/Hessian oracles) to …
Glocal Smoothness: Line Search can really help!
Iteration complexities for first-order optimization algorithms are typically stated in terms of a global Lipschitz constant of the gradient, and near-optimal results are achieved using fixed step sizes. But many objectiv…