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

DOI10.1016/J.ORL.2022.01.015MaRDI QIDQ6342916arXivFDO

Authors Tesi Xiao, Krishnakumar Balasubramanian, Saeed Ghadimi

Publication date 15 June 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2022.01.015

Mathematics Subject Classification ID

Stochastic programming (90C15) Methods of reduced gradient type (90C52)

arXiv classification

cs.LGmath.OCstat.ML

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 $mathcalO(epsilo{n}^{-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 $mathcalO(epsilo{n}^{-1.5})$.

This page was built for publication: Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342916)