Optimal Stochastic Optimization with Bounded Gradient Noise

Lower bounds for stochastic optimization usually rely on oracles that occasionally return very large gradient errors, so it is unclear whether they remain valid when the noise is uniformly bounded, a setting arjevani2023 left open. We show that bounding the noise does not make optimization easier. For smooth nonconvex, Polyak–Lojasiewicz (PL), strongly convex, and convex objectives, we prove matching upper and lower bounds under almost-surely bounded gradient noise. In particular, finding an $ϵ$-stationary point requires $\Theta (\Delta L{\sigma }^2{ϵ}^{-4})$ stochastic gradients in the noise-dominated regime, and $\Theta (\Delta H\sigma {ϵ}^{-3})$ when the centered noise is $H$-Lipschitz, so stochastic gradient descent and variance reduction remain optimal. We also find a separation between PL and strongly convex objectives: in the noise-dominated regime, PL objectives require $\kappa {\sigma }^2/(\mu \eta )$ samples rather than ${\sigma }^2/(\mu \eta )$. Further results cover additive noise, finite sums, relative noise, higher-order smoothness, and limits on sample reuse. Our lower bounds hold for arbitrary randomized algorithms that may re-evaluate samples adaptively and observe exact function values. They rest on bounded observations drawn from the Poisson kernel on the sphere, together with an information argument that controls all responses from reused samples.