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

<p>(a) Let there be a $\sigma &gt;0$ s.t the norm of the gradient of the function is bounded by $\sigma$.</p>

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

<p>(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$</p>

<p>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$ ? </p>

<hr>

<ul>
<li><p>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. </p></li>
<li><p>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! </p></li>
</ul>

CC BY-SA 3.0
2018-03-14T19:44:45.960Z
See Nesterov's method: http://web.stanford.edu/class/msande318/notes/notes-first-order-smooth.pdf
Erik M
CC BY-SA 3.0
2018-03-14T19:52:43.273Z
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
<ds.algorithms><reference-request><approximation-algorithms>
What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?
gradstudent
# What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?

(Asked by: username_0 on 2018-03-14)

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!

**Tags:** ds.algorithms, reference-request, approximation-algorithms

> **Comments:**
> **username_1**: See Nesterov's method: http://web.stanford.edu/class/msande318/notes/notes-first-order-smooth.pdf  
> **username_0**: 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!  

---

## 0 answers

