# On the complexity of finding stationary points of smooth functions in one dimension

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2022.

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

- [Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2406.04592/) (2024)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [The Computational Complexity of Finding Stationary Points in Non-Convex Optimization](https://mlsanity.com/paper/2310.09157/) (2023)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [On Approximate Computation of Critical Points](https://mlsanity.com/paper/2601.21917/) (2026)
- [Complexity of Non-Log-Concave Sampling in Fisher Information](https://mlsanity.com/paper/2605.15859/) (2026)
- [Towards Serverless Semi-Decentralized Federated Learning with Heterogeneous Optimizers](https://mlsanity.com/paper/2606.06687/) (2026)

## Abstract (arXiv)

We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms under consideration are deterministic or randomized, and whether the oracle outputs 1rm st-order or both 0rm th- and 1rm st-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or 0rm th-order information. Our results also show that, for every dimension d ≥ 1, gradient descent is optimal among deterministic algorithms using 1rm st-order queries only.