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

Jikai Jin

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 algori…