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

2020/06/15 by Tesi Xiao, Krishnakumar Balasubramanian, Xiao, Tesi +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.08167

openalex publication_date 2020/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 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 O(ε^-1.5).

Citations

• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Constrained Deep Learning using Conditional Gradient and Applications in\n Computer Vision
• Structured Evolution with Compact Architectures for Scalable Policy\n Optimization
• On exponential convergence of SGD in non-convex over-parametrized learning
• The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy
• Stochastic Conditional Gradient++
• Understanding deep learning requires rethinking generalization
• One Sample Stochastic Frank-Wolfe
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems

Related

• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Aiming towards the minimizers: fast convergence of SGD for overparametrized problems
• Geometry, Computation, and Optimality in Stochastic Optimization
• Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization
• Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles