On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization
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(ε+…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.19553
curl -X POST /api/v1/records/arxiv/2606.19553/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.19553/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'