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

arXiv:2608.09004v1 Announce Type: cross 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 $Omegaleft( frac{Delta L}{epsilon^2} + frac{Delta Lsigma^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.

Source: arXiv cs.LG | 2026-08-11