1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ See Nesterov's method: web.stanford.edu/class/msande318/notes/… $\endgroup$ – Erik M Mar 14 '18 at 19:44
  • $\begingroup$ 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! $\endgroup$ – gradstudent Mar 14 '18 at 19:52

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.