Back to Search
Start Over
Lower bounds for non-convex stochastic optimization
- Source :
- Mathematical Programming. 199:165-214
- Publication Year :
- 2022
- Publisher :
- Springer Science and Business Media LLC, 2022.
-
Abstract
- We lower bound the complexity of finding $\epsilon$-stationary points (with gradient norm at most $\epsilon$) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least $\epsilon^{-4}$ queries to find an $\epsilon$ stationary point. The lower bound is tight, and establishes that stochastic gradient descent is minimax optimal in this model. In a more restrictive model where the noisy gradient estimates satisfy a mean-squared smoothness property, we prove a lower bound of $\epsilon^{-3}$ queries, establishing the optimality of recently proposed variance reduction techniques.<br />Comment: Correction to hard instance dimensions in Theorem 3
- Subjects :
- FOS: Computer and information sciences
Computer Science - Machine Learning
Statistics - Machine Learning
Optimization and Control (math.OC)
Computer Science - Information Theory
Information Theory (cs.IT)
General Mathematics
MathematicsofComputing_NUMERICALANALYSIS
FOS: Mathematics
Machine Learning (stat.ML)
Mathematics - Optimization and Control
Software
Machine Learning (cs.LG)
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 199
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....b8951f2add66ecff7186919eff152ac2