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

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