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?


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$ – gradstudent Mar 17 '18 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$ – gradstudent Mar 18 '18 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$ – Maziar Sanjabi Mar 19 '18 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$ – gradstudent Mar 19 '18 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$ – Maziar Sanjabi Mar 19 '18 at 3:28

Your Answer

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

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