<p>Yes, there are some papers. The most relevant one to your question might be: <a href="https://arxiv.org/pdf/1611.00756.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1611.00756.pdf</a></p>

CC BY-SA 3.0
2018-03-17T22:15:00.197Z
Thanks for the link! I was indeed looking at a different paper by the same authors but I didnt see this paper! Thanks :)
gradstudent
CC BY-SA 3.0
2018-03-18T21:02:37.263Z
I am just wondering, isnt the result in your reference better than this more recent paper, https://arxiv.org/abs/1703.00887 ? What am I missing?
gradstudent
CC BY-SA 3.0
2018-03-19T00:49:20.357Z
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.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T02:28:33.367Z
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?
gradstudent
CC BY-SA 3.0
2018-03-19T03:28:18.040Z
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.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T03:38:34.943Z
Take a look at this paper though about the problems with Adam (https://openreview.net/pdf?id=ryQu7f-RZ)
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T04:05:49.927Z
That I know. Infact this new corrected proof also has bugs :D Though these bugs wont change the final answer.
gradstudent
CC BY-SA 3.0
2018-03-19T05:18:37.540Z
Another side question, if you dont mind :D So what is the new point in those Neon, Katyusha, etc. algorithms? Whats the advantage there compared to your link or the one lined to?
gradstudent
CC BY-SA 3.0
2018-03-19T18:35:04.577Z
I have not read their paper, but I am not surprised that there might be bugs. Let's say the review process in most of the ML conferences is not as rigorous as a journal.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T18:39:44.847Z
I do not understand your other question very well. I will try to address what I understand from your question. Let me know if this is not what you were asking. In the general non-convex setting, there is no way you can theoretically do any better than the gradient descent (if you have only access to gradient). This is in contrast with the convex setting, where theoretically, and practically, you can get better results with acceleration. Most of these algorithms are trying to use these ideas from convex optimization to make practically better performing methods.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T18:52:14.553Z
one more thing I want to add is that stochastic GD methods are totally different from the GD methods and using some kind of variance reduction could actually speed them up for minimizing ERMs.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-19T21:43:14.747Z
Yes, I am aware of the general idea of "variance reduction" using which one can get randomized algorithms with better running times than vanilla SGD (which is $O(\frac{1}{\epsilon^4})$) but they cannot beat the GD's running time of $O(\frac{1}{\epsilon^2})$. And that you say is impossible? (..your linked paper or the paper I linked to both are variations of GD and hence are in the $O(\frac{1}{\epsilon^2})$ family..) But I dont know what is the specific advantage of these Neon, Natasha and Katysha proofs.
gradstudent
CC BY-SA 3.0
2018-03-19T22:19:32.733Z
This paper proves that for general non-convex functions with Lipchitz gradient, you cannot beat GD's rate: https://arxiv.org/pdf/1711.00841.pdf. Note that this result is for the general non-convex family of functions. Obviously, you can get better results when you restrict to more specific family of functions.
Maziar Sanjabi
CC BY-SA 3.0
2018-03-17T03:30:23.197Z
2018-03-17T03:30:23.197Z
Maziar Sanjabi
<p>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? </p>

<np-hardness><approximation-algorithms><optimization><machine-learning>
About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective
gradstudent
# About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

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

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?

**Tags:** np-hardness, approximation-algorithms, optimization, machine-learning


---

## 1 answers

### Answer by username_1 on 2018-03-17. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks for the link! I was indeed looking at a different paper by the same authors but I didnt see this paper! Thanks :)  
> **username_0**: I am just wondering, isnt the result in your reference better than this more recent paper, https://arxiv.org/abs/1703.00887 ? What am I missing?  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: Take a look at this paper though about the problems with Adam (https://openreview.net/pdf?id=ryQu7f-RZ)  
> **username_0**: That I know. Infact this new corrected proof also has bugs :D Though these bugs wont change the final answer.  
> **username_0**: Another side question, if you dont mind :D So what is the new point in those Neon, Katyusha, etc. algorithms? Whats the advantage there compared to your link or the one lined to?  
> **username_1**: I have not read their paper, but I am not surprised that there might be bugs. Let's say the review process in most of the ML conferences is not as rigorous as a journal.  
> **username_1**: I do not understand your other question very well. I will try to address what I understand from your question. Let me know if this is not what you were asking. In the general non-convex setting, there is no way you can theoretically do any better than the gradient descent (if you have only access to gradient). This is in contrast with the convex setting, where theoretically, and practically, you can get better results with acceleration. Most of these algorithms are trying to use these ideas from convex optimization to make practically better performing methods.  
> **username_1**: one more thing I want to add is that stochastic GD methods are totally different from the GD methods and using some kind of variance reduction could actually speed them up for minimizing ERMs.  
> **username_0**: Yes, I am aware of the general idea of "variance reduction" using which one can get randomized algorithms with better running times than vanilla SGD (which is $O(\frac{1}{\epsilon^4})$) but they cannot beat the GD's running time of $O(\frac{1}{\epsilon^2})$. And that you say is impossible? (..your linked paper or the paper I linked to both are variations of GD and hence are in the $O(\frac{1}{\epsilon^2})$ family..) But I dont know what is the specific advantage of these Neon, Natasha and Katysha proofs.  
> **username_1**: This paper proves that for general non-convex functions with Lipchitz gradient, you cannot beat GD's rate: https://arxiv.org/pdf/1711.00841.pdf. Note that this result is for the general non-convex family of functions. Obviously, you can get better results when you restrict to more specific family of functions.  

---

