# What is the fastest gradient based algorithm to get to criticality of a “nice” non-convex function?

I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$,

(a) Let there be a $\sigma >0$ s.t the norm of the gradient of the function is bounded by $\sigma$.

(b) Let the function's value itself be upper and lower bounded.

(c) Let the function be "L-smooth" as in for any two points, $x$ and $y$ in the domain lets say we have, $f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac {L}{2} \Vert y - x \Vert ^2$

Under these conditions whats the fastest gradient based algorithm known to get to a point $x_*$ s.t $\Vert \nabla f(x_*) \Vert \leq \epsilon$ ?

• I checked the old results I am aware of and the new papers that I know of but I am unable to locate any result which can exploit all these properties.

• I am not sure if there is any implicit constraint between $\sigma, L$ and the bounds on the function value. Kindly let me know if something like that is getting implied!

• See Nesterov's method: web.stanford.edu/class/msande318/notes/… – Erik M Mar 14 '18 at 19:44
• Yeah. Can you point to any specific theorem there which you have in mind? AFAIK there is no version of Nestrov's method which can exploit either this $\sigma$ or the upperbound of the function. They never get better than $O(\frac {L(f(x_{initial})-f(x_{global min}))}{\epsilon^2})$ Please correct me if I am wrong! – gradstudent Mar 14 '18 at 19:52