{"id":"arxiv/2606.19553","url":"https://arxiv.org/abs/2606.19553","tags":["math.OC"],"score":0,"title":"On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization","domain":"math.OC","source":"arxiv","authors":["Anant Shyam","Brian Bullins"],"reviews":0,"subject":"math.OC","summary":"We consider the problem of finding $δ$-stationary points for $δ> 0$, i.e., $x \\in \\mathbb{R}^d$ such that $||\\nabla F(x)|| \\le δ$, for smooth, non-convex objectives, where the derivative oracles are not only stochastic but also biased. In the first-order setting, we provide tight lower bounds for finding an $O((ε+ B^2)^{1/2})$-stationary point, for $ε> 0$ and where $B$ is a bound on the gradient bias, matching the upper bounds of Ajalloeian and Stich (2020). We then establish bias-dependent lower bounds for algorithms that use higher-order derivative information for finding $O(ε+…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-17","reactions":{}}