Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?


1 Answer 1


Yes, there are some papers. The most relevant one to your question might be: https://arxiv.org/pdf/1611.00756.pdf

  • $\begingroup$ Thanks for the link! I was indeed looking at a different paper by the same authors but I didnt see this paper! Thanks :) $\endgroup$ Commented Mar 17, 2018 at 22:15
  • $\begingroup$ I am just wondering, isnt the result in your reference better than this more recent paper, arxiv.org/abs/1703.00887 ? What am I missing? $\endgroup$ Commented Mar 18, 2018 at 21:02
  • $\begingroup$ The difference is in the algorithm. The paper I posted uses hessian gradient products and not just the gradient which is used in practice. So their algorithm is only realizable if you have access to an efficient hessian vector product oracle. In that case you can get a better result than just perturbing the gradient descent. In other words you can escape saddle points in less iterations. $\endgroup$ Commented Mar 19, 2018 at 0:49
  • $\begingroup$ Right. Somehow in your linked paper it never seems to be clearly stated as to what all they really expect the Oracle to provide! Can you point to anywhere in the paper where its clearly stated? BTW, a side question : do you know if there is any understanding of RMSProp/ADAM for non-convex settings? $\endgroup$ Commented Mar 19, 2018 at 2:28
  • $\begingroup$ they casually mention it on page 2 right below the first formula on that page. But you are right. They do not emphasize on it. About ADAM and RMSProp, I don't know of any analysis of those methods for the non-convex optimization. $\endgroup$ Commented Mar 19, 2018 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.