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 $\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 \(\eps\). This matches the standard upper bound and resolves the question raised by Arjevani et al. 2023 of whether almost-surely bounded oracle error permits a better rate than bounded variance.