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 Omegaleft( fracDelta Lε2 + fracDelta 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.