In 8th chapter of deep learning book, the following lines are written under Stochastic gradient descent heading:

The asymptotic analysis obscures many advantages that stochastic gradient descent has after a small number of steps. With large datasets, the ability of SGD to make rapid initial progress while evaluating the gradient for very few examples outweighs its slow asymptotic convergence. Most of the algorithms achieve benefits that matter in practice but are lost in the constant factors obscured by the O(1/k) asymptotic analysis.

I do not understand what does it mean to have an asymptotic analysis?


I think it's just a statement about the convergence rate of SGD/GD -- you can prove that after $k$ iterations of gradient descent on a convex, lipschitz continuous function, the difference between the GD solution and the global minimum is $O(1/k)$ (in expectation).

See Big O notation to understand what is meant by asymptotic analysis.


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.