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

arXiv: https://arxiv.org/abs/2608.09004 · HTML: https://mlsanity.com/paper/2608.09004/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 7 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2406.04592/) (2024)
- [Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2512.18713/) (2025)

## Built on by (most cited first, 1 of 1)

- [Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness](https://mlsanity.com/paper/2609.00045/) (2026)

## Abstract (arXiv)

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 Omegaleft( fracDelta Lε2 + fracDelta 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 Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.