# About gradient descent on non-convex functions

There is this "folklore" result that gradient descent on a non-convex function takes $O(\frac n {\epsilon^2})$ steps to get to a point whose gradient norm is below $\epsilon$ and with SGD this takes $O(\frac {1}{\epsilon^4})$ steps.

• Can someone share a reference where this is proven?

I am aware of the recent references where these numbers have been improved. But I am not able to locate a pedagogic presentation of these older results.

• What are you assuming about the function? If nothing, take your favorite function and then for each $m \in \mathbb{N}$, pick a starting point, run gradient descent from that point for $m \cdot \frac{n}{\varepsilon^2}$ iterations, then modify the function to make the gradient get steep there. – Reinstate Monica Mar 8 '18 at 1:16
• I dont know as to what is the condition under which the stated result is true. I havent seen more details about it! – gradstudent Mar 9 '18 at 20:41
• @Solomonoff'sSecret For example see the footnote 2 at the bottom of page 2 of this paper, arxiv.org/pdf/1603.05643.pdf What is this "trivial SGD" that they are referring to? – gradstudent Mar 11 '18 at 21:05
• I will try to review that paper later. Trivial SGD is going through a training set one example at a time and performing gradient descent on that example. That is, not using momentum or any other technique beyond gradient descent. – Reinstate Monica Mar 12 '18 at 13:56