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.

  • $\begingroup$ 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. $\endgroup$ – Solomonoff's Secret Mar 8 '18 at 1:16
  • $\begingroup$ I dont know as to what is the condition under which the stated result is true. I havent seen more details about it! $\endgroup$ – gradstudent Mar 9 '18 at 20:41
  • $\begingroup$ @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? $\endgroup$ – gradstudent Mar 11 '18 at 21:05
  • $\begingroup$ 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. $\endgroup$ – Solomonoff's Secret Mar 12 '18 at 13:56

Your Answer

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

Browse other questions tagged or ask your own question.