# First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2020.

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

- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)

## Abstract (arXiv)

Machine learning algorithms typically perform optimization over a class of non-convex functions. In this work, we provide bounds on the fundamental hardness of identifying the global minimizer of a non convex function. Specifically, we design a family of parametrized non-convex functions and employ statistical lower bounds for parameter estimation. We show that the parameter estimation problem is equivalent to the problem of function identification in the given family. We then claim that non convex optimization is at least as hard as function identification. Jointly, we prove that any first order method can take exponential time to converge to a global minimizer.