# The Computational Complexity of Finding Stationary Points in Non-Convex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 13 Oct 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [On the complexity of finding stationary points of smooth functions in one dimension](https://mlsanity.com/paper/2209.07513/) (2022)
- [How to trap a gradient flow](https://mlsanity.com/paper/2001.02968/) (2020)

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

- [Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?](https://mlsanity.com/paper/2505.16736/) (2025)
- [On Approximate Computation of Critical Points](https://mlsanity.com/paper/2601.21917/) (2026)

## Abstract (arXiv)

Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results: 1. The problem of finding approximate stationary points over unrestricted domains is PLS-complete. 2. For d = 2, we provide a zero-order algorithm for finding varepsilon-approximate stationary points that requires at most O(1/varepsilon) value queries to the objective function. 3. We show that any algorithm needs at least Omega(1/varepsilon) queries to the objective function and/or its gradient to find varepsilon-approximate stationary points when d=2. Combined with the above, this characterizes the query complexity of this problem to be Theta(1/varepsilon). 4. For d = 2, we provide a zero-order algorithm for finding varepsilon-KKT points in constrained optimization problems that requires at most O(1/√varepsilon) value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be Theta(1/√varepsilon). 5. Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.