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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.