A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
TL;DR
A sharp lower bound is proved for smooth nonconvex stochastic optimization with uniformly bounded gradient noise with uniformly bounded gradient noise and resolves the question raised by whether almost-surely bounded oracle error permits a better rate than bounded variance.
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 $$\Omega\left( \frac{\Delta L}{\epsilon^2} + \frac{\Delta L\sigma^2}{\epsilon^4} \right)$$ queries to find a point with expected gradient norm at most \(\epsilon\). 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.