A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

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.