A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
2026-08-10 • Computational Complexity
Computational ComplexityMachine Learning
AI summaryⓘ
The authors proved a clear lower limit on how fast algorithms can solve a certain kind of problem where the function is smooth but not necessarily convex, and the noise in gradients is limited. They show that any algorithm must make at least a certain number of queries to find a solution with a small expected gradient, matching known upper bounds. Their result answers a previous question about whether having uniformly bounded error allows faster methods, finding that it does not. The proof was assisted by an AI model, with the human mainly checking and refining the work.
stochastic optimizationnonconvex optimizationgradient noiseoracle complexityexpected gradient normlower boundsmooth functionsadaptive algorithmsbounded variancealgorithmic complexity
Authors
Jikai Jin
Abstract
We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.