{"id":"arxiv/2608.09004","url":"https://arxiv.org/abs/2608.09004","tags":["math.OC","cs.CC","cs.LG"],"score":0,"title":"A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise","domain":"math.OC","source":"arxiv","authors":["Jikai Jin"],"reviews":0,"subject":"math.OC","summary":"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 $$Ω\\left( \\frac{ΔL}{ε^2} + \\frac{Δ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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}