Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gradient Descent Optimisation Algorithms

towardsdatascience.com

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Gradient Descent Optimisation Algorithms

#11

Post by _jamesm_ »

It's always useful to see different SGD methods written with a consistent nomenclature. A few thoughts:

1. Is the 1999 Qian paper on momentum really the most appropriate one, given the comparison of the publication date to NAG? As a cursory examination of the paper reveals, momentum has been used for a long time before 1999!

2. Similarly, the original NAG paper isn't about stochastic gradient descent and doesn't really use the equation as written. A more appropriate reference is to the Sutskever, Martens, Dahl and Hinton paper of 2013 http://proceedings.mlr.press/v28/sutskever13.html which is the publication that described/reworked NAG in this way.

3. It's worth noting the caveats about AMSGrad: https://www.fast.ai/2018/07/02/adam-weight-decay/

Re: Gradient Descent Optimisation Algorithms

#12

Post by marcosdumay »

hnuser355 wrote: post #9

And for anyone who wants to know why unmodified gradient descent may be considered a piece of shit in certain circumstances http://wikipedia.org/wiki/Rosenbrock_function Gradient descent with a good line search (Wolfe conditions) applies to the multidimensional case should converge to min, but it might take you thousands of iterations. Newton’s method or something might take But machine learning practitioners will kn…

It's hard to propagate Newton's method over layers on a neural network.

Re: Gradient Descent Optimisation Algorithms

#13

Post by stochastic_monk »

marcosdumay wrote: post #12
hnuser355 wrote: post #9

And for anyone who wants to know why unmodified gradient descent may be considered a piece of shit in certain circumstances http://wikipedia.org/wiki/Rosenbrock_function Gradient descent with a good line search (Wolfe conditions) applies to the multidimensional case should converge to min, but it might take you thousands of iterations. Newton’s method or something might take But machine learning practitioners will kn…

It's hard to propagate Newton's method over layers on a neural network.

There are also a lot of conditions required for Newton’s method to work which you don’t have with neural networks.

Re: Gradient Descent Optimisation Algorithms

#14

Post by marcosdumay »

stochastic_monk wrote: post #13
marcosdumay wrote: post #12

Earlier quoted context omitted.

It's hard to propagate Newton's method over layers on a neural network.

There are also a lot of conditions required for Newton’s method to work which you don’t have with neural networks.

Is there some condition that makes the method not work at all?

I could never find a showstopper (granted that I have thought about this for a few hours when first studying the subject), only stuff that slowed it down so gradient descent became better (and honestly, I am still not sure that can not be fixed).

Re: Gradient Descent Optimisation Algorithms

#15

Post by raibosome »

Riverheart wrote: post #5

For those unfamiliar with the concept, courtesy Wikipedia https://en.m.wikipedia.org/wiki/Gradient_descent The basic intuition behind gradient descent can be illustrated by a hypothetical scenario. A person is stuck in the mountains and is trying to get down (i.e. trying to find the minima). There is heavy fog such that visibility is extremely low. Therefore, the path down the mountain is not visible, so he must use…

Sweet! Another intuition for gradient descent:

Regularly updating your parameters using an educated guess. This educated guess is the gradient value.

Re: Gradient Descent Optimisation Algorithms

#16

Post by raibosome »

_jamesm_ wrote: post #11

It's always useful to see different SGD methods written with a consistent nomenclature. A few thoughts: 1. Is the 1999 Qian paper on momentum really the most appropriate one, given the comparison of the publication date to NAG? As a cursory examination of the paper reveals, momentum has been used for a long time before 1999! 2. Similarly, the original NAG paper isn't about stochastic gradient descent and doesn't real…

Thank you for pointing these out! I have made the necessary edits to the citations for (1) and (2) and republished the article.

For (1), the paper by Sutskever et al., 2013 (http://proceedings.mlr.press/v28/sutskever13.pdf) attributed the classical momentum to Polyak, 1964 (https://www.researchgate.net/publication/243648538_Some_meth...). A Distil article on momentum (https://distill.pub/2017/momentum/) also cited Polyak's paper and also included a much earlier publication in 1959 by Ruttishauser (https://doi.org/10.1007/978-3-0348-7224-9_2), but I will just make reference to Polyak's.

Re: Gradient Descent Optimisation Algorithms

#17

Post by _jamesm_ »

raibosome wrote: post #16
_jamesm_ wrote: post #11

It's always useful to see different SGD methods written with a consistent nomenclature. A few thoughts: 1. Is the 1999 Qian paper on momentum really the most appropriate one, given the comparison of the publication date to NAG? As a cursory examination of the paper reveals, momentum has been used for a long time before 1999! 2. Similarly, the original NAG paper isn't about stochastic gradient descent and doesn't real…

Thank you for pointing these out! I have made the necessary edits to the citations for (1) and (2) and republished the article. For (1), the paper by Sutskever et al., 2013 ( http://proceedings.mlr.press/v28/sutskever13.pdf ) attributed the classical momentum to Polyak, 1964 ( https://www.researchgate.net/publication/243648538_Some_meth... ). A Distil article on momentum ( https://distill.pub/2017/momentum/ ) also ci…

Cool, glad to have helped. It seems I have caused a further minor point of confusion though, so a correction to the correction:

The original Nesterov Accelerated Gradient paper is about gradient descent, it's just not about stochastic gradient descent. It's useful to make the distinction between "traditional" optimization methods like Newton's method, Conjugate Gradient, BFGS and so on, which are all gradient descent methods in the sense they require at least a full gradient calculation per iteration, and a lot of the algorithms mentioned in the article, which are suitable for stochastic gradient descent and originate with the deep learning community (there's nothing to stop them being used elsewhere, it just doesn't seem that common).

Some extra (unnecessary) detail on NAG to put things into a bit more context, if you are so inclined:

Although NAG has received a fair amount of theoretical attention, as far as I know it isn't widely used practically because its convergence properties rely on an exact line search and a rather specific schedule for its momentum-like term.

The Sutskever contribution is interesting because first, it expressed the NAG formula in a way that could be easily understood by machine learning practitioners. Then, by moving the procedure a half step, they showed you could think of it as momentum followed by gradient descent.

Post reply on HN