8
$\begingroup$

More specifically, when training a neural network, what reasons are there for choosing an optimizer from the family consisting of stochastic gradient descent (SGD) and its extensions (RMSProp, Adam, etc.) instead of from the family of Quasi-Newton methods (including limited-memory BFGS, abbreviated as L-BFGS)?

It is clear to me that some of the extensions of SGD, particularly RMSProp and Adam, store gradient information from previous iterates and use it to calculate the update for the next iterate. This is something they have in common with Quasi-Newton methods. However, the motivation behind storing the gradient information in the Adam method, for example, is unclear to me, whereas it is clear that in Quasi-Newton methods the motivation behind storing prior gradient information is to use it to construct an approximation to the Hessian (inverse).

I'm curious to understand:

  • whether there are features of methods like Adam that make them particularly well-suited to machine learning applications;
  • whether these features enable them to outperform more conventional optimization methods like Quasi-Newton methods; and (ideally)
  • what is the general reasoning behind the update rule that these methods use.
$\endgroup$
  • 1
    $\begingroup$ As I understand it, when training a neural network the number of training examples is so vast compared to the number of weights being trained that simply evaluating the gradient is a bottleneck. SGD methods allow you to work with much cheaper approximations of the gradient (typically, summing the contributions of a different small subset of examples at each iteration) instead. $\endgroup$ – Rahul Jan 11 at 12:47
  • $\begingroup$ Right, what separates stochastic gradient descent from regular gradient descent is that, at each iteration, you randomly sample the training data and evaluate the cost/loss function (and its gradient) on just the sample, not all the data. Maybe it's the wrong take, but I interpret it as creating a cheaper surrogate optimization problem at each training iteration. Using a surrogate is a common prescription for a cost function that's too expensive to evaluate. And it works with any optimizer. Surrogate aside, the question stands: why one optimizer over the other? Any thoughts on that point? $\endgroup$ – Jan Kiviaho Jan 11 at 21:01
  • $\begingroup$ I thought I did answer the question. If your surrogate cost function is changing every iteration, can you still reuse the gradient information in a quasi-Newton method? Not as far as I know. $\endgroup$ – Rahul Jan 12 at 3:37
  • $\begingroup$ But that's what Adam is doing. Presumably it is using gradient information from previous iterations when the cost function is changing every iteration. You can do the same with Quasi-Newton methods. That's why it surprises me to find Quasi-Newton methods absent from machine learning libraries like Keras. I wonder if there's a reason for it. Setting aside the random sampling of the training data at every optimization step to create a smaller surrogate problem, are optimizers like Adam better than Quasi-Newton methods? And how so? That's what I'm trying to get at. $\endgroup$ – Jan Kiviaho Jan 12 at 7:26
4
$\begingroup$

This topic has been discussed at some length on Cross Validated (aka stats.stackexchange) and Reddit:

  1. Why is Newton's method not widely used in machine learning? (see in particular Nick Alger's answer)

  2. Why use gradient descent with neural networks?

  3. L-BFGS and neural nets

  4. Why second order SGD convergence methods are unpopular for deep learning?

  5. How does the Adam method of stochastic gradient descent work?

Other relevant references:

  1. Bottou et al., Optimization Methods for Large-Scale Machine Learning (SIAM Review 2018), in particular section 6 on second-order methods.

  2. Ian Goodfellow's Deep learning book, chapter on optimization, section 8.6 (second-order methods).

  3. Quoc Le et al., On optimization methods for deep learning

  4. Dauphin et al., Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

TL;DR: The jury is still out on second-order methods.

$\endgroup$
  • 1
    $\begingroup$ Excellent! Thank you. I had come across the first StackExchange post and was pretty disappointed with most of the replies. But I hadn't discovered the other resources you shared. Seems they outline some significant challenges for second-order methods in the realm of machine learning. And that explanation of the concept of "momentum" in Adam was brilliant. You've given me a lot to dig into. $\endgroup$ – Jan Kiviaho Jan 13 at 16:50
  • $\begingroup$ you're welcome! here's a nice visual explanation of momentum: distill.pub/2017/momentum $\endgroup$ – GoHokies Jan 13 at 18:55

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.