# On Approximate Computation of Critical Points

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 29 Jan 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [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)
- [On the complexity of finding a local minimizer of a quadratic function over a polytope](https://mlsanity.com/paper/2008.05558/) (2020)
- [Almost-Linear Planted Cliques Elude the Metropolis Process](https://mlsanity.com/paper/2204.01911/) (2022)
- [DC Decomposition of Nonconvex Polynomials with Algebraic Techniques](https://mlsanity.com/paper/1510.01518/) (2015)
- [Complexity aspects of local minima and related notions](https://mlsanity.com/paper/2008.06148/) (2020)
- [The Complexity of Computing KKT Solutions of Quadratic Programs](https://mlsanity.com/paper/2311.13738/) (2023)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Third-Order Newton Methods with Semidefinite Programming](https://mlsanity.com/paper/2209.10051/) (2022)
- [The Computational Complexity of Finding Stationary Points in Non-Convex Optimization](https://mlsanity.com/paper/2310.09157/) (2023)
- [Hesse's Redemption: Efficient Convex Polynomial Programming](https://mlsanity.com/paper/2511.03440/) (2025)
- [On Polynomial Optimization over Non-compact Semi-algebraic Sets](https://mlsanity.com/paper/1304.4552/) (2013)

## Abstract (arXiv)

We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in n variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm at most 2n whenever the polynomial has a critical point, then P=NP. The algorithm is permitted to return an arbitrary point when no critical point exists. We also prove hardness results for approximate computation of critical points under additional structural assumptions, including settings in which existence and uniqueness of a critical point are guaranteed, the function is lower bounded, and approximation is measured in terms of distance to a critical point. Overall, our results stand in contrast to the commonly-held belief that, in nonconvex optimization, approximate computation of critical points is a tractable task.