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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-10 Page: https://delphi.science/r/arxiv/2608.09004 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…