Clearly we cannot hope to find a global minimum,
but, under a mild smoothness assumption (see Remark REF ), there is a useful and total local solution concept: (approximate) fixed points of the gradient descent dynamics (“KKT points”).
By a simple potential argument, gradient descent itself always converges to such \(\epsilon \) -approximate fixed point in \((1/\epsilon )\)  iterations.
But in some cases, e.g. when \(f\)  is also convex, algorithms like the center of gravity method converge in \((n,\log (1/\epsilon ))\)  iterations [1]}.
For what nonconvex functions can we achieve exponentially fast (in \(1/\epsilon \) ) convergence?
(Indeed, accelerated methods make it possible for some nonconvex functions, e.g. [2]}.)
