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

Abstract

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})$.

References in corpus (19)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Understanding deep learning requires rethinking generalization
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Empirical Risk Minimization under Fairness Constraints
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• On exponential convergence of SGD in non-convex over-parametrized learning
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Structured Evolution with Compact Architectures for Scalable Policy Optimization
• SGD: General Analysis and Improved Rates
• Deep Frank-Wolfe For Neural Network Optimization
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Towards Gradient Free and Projection Free Stochastic Optimization
• Stochastic Conditional Gradient++
• One Sample Stochastic Frank-Wolfe
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation