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

Question

It seems that, especially for deep learning, there are dominating very simple methods for optimizing SGD convergence like ADAM - nice overview: http://ruder.io/optimizing-gradient-descent/

They trace only single direction - discarding information about the remaining ones, they do not try to estimate distance from near extremum - which is suggested by gradient evolution ($\rightarrow 0$ in extremum), and could help with the crucial choice of step size.

Both these missed opportunities could be exploited by second order methods - trying to locally model parabola in simultaneously multiple directions (not all, just a few), e.g. near saddle attracting in some directions, repulsing in the others. Here are some:

• L-BFGS: http://aria42.com/blog/2014/12/understanding-lbfgs
• TONGA: https://papers.nips.cc/paper/3234-topmoumoute-online-natural-gradient-algorithm
• K-FAC: https://arxiv.org/pdf/1503.05671.pdf
• saddle-free Newton: https://arxiv.org/pdf/1406.2572
• my second order local parametrization: https://arxiv.org/pdf/1901.11457

But still first order methods dominate (?), I have heard opinions that second order just don't work for deep learning (?)

There are mainly 3 challenges (any more?): inverting Hessian, stochasticity of gradients, and handling saddles. All of them should be resolved if locally modelling parametrization as parabolas in a few promising directions (I would like to use): update this parametrization based on calculated gradients, and perform proper step based on this parametrization. This way extrema can be in updated parameters - no Hessian inversion, slow evolution of parametrization allows to accumulate statistical trends from gradients, we can model both curvatures near saddles: correspondingly attract or repulse, with strength depending on modeled distance.

Should we go toward second order methods for deep learning?

Why is it so difficult to make them more successful than simple first order methods - could we identify these challenges ... resolve them?

As there are many ways to realize second order methods, which seems the most promising?

Update: Overview of SGD convergence methods including 2nd order: https://www.dropbox.com/s/54v8cwqyp7uvddk/SGD.pdf

Update: There are criticized huge 2nd order methods, but we can work on the opposite end of cost spectrum: make tiny steps from successful 1st order methods, like just cheap online parabola model in single direction e.g. of momentum method for smarter choice of step size - are there interesting approaches for such 2nd order enhancement of 1st order methods?

Update: 2D example of SGD augmented with 2nd order information from sequence of gradients (github):

Answer 1

Should we go toward second order methods for deep learning?

TL;DR: No, especially now when the pace of innovation is slowing down, and we're seeing less new architectural innovations, and more ways to train what are basically just copies of existing architectures, on larger datasets (see OpenAI's GPT-2).

First, without even getting to second order, it's worth mentioning that in Deep Learning you don't even use (mini-batch) gradient descent to the fullest of its potential (i.e., you don't perform line search), because the optimization step in line search would be very costly.

Second, second order methods are:

• way more complex, i.e., harder to implement without bugs. DL systems are increasingly becoming a small part of huge data processing pipelines. Introducing further complexity and brittleness in a complex system is only wise if the gains largely offset the risks. I'll argue below that they don't.
• harder to optimize for distributed computing on heterogeneous hardware, which is becoming more and more common. See how much work was required in order to make K-FAC work on distributed (non heterogeneous) systems, and performances are still no better than the best first-order methods: https://arxiv.org/pdf/1811.12019.pdf. Instead, if just switching to distributed computing makes my first-order method as fast as, or faster, than second-order methods, I don't see the reason to use a more complicated optimization algorithm.
• way more expensive in terms of iteration cost (not number) and memory occupation, thus they introduce a considerable overhead. Current architectures (GPUs) are more memory-bound that computation-bound. As explained very well here, the increase in iteration cost and memory occupation is steeper, the more high-dimensional the problem is. Optimization in Deep Learning is arguably one of the most high-dimensional optimization problems, so it's not clear that second order methods would have a clear advantage in terms of computational time (not iteration count, which is not what we really care about) wrt first-order methods.
• another issue with Deep Learning optimization are saddle points. It's becoming abundantly clear that "bad" local minima are not an issue in Deep Learning, but saddle points are. Newton's method does have a tendency to be attracted to saddle points. If I remember correctly, Hessian approximating methods such as K-FAC don't have this issue, but I think the proof depends on the type of architecture, making the use of such methods brittle.
• they don't fix the problems which make practitioners waste most of their time. Dead or saturated units are not solved by K-FAC, but by better initialization schemes, so that's what we should focus on, e.g., Fixup: https://arxiv.org/abs/1901.09321
• another issue with second order methods is that for most common loss functions, it's easy to use mini-batches to get an estimator which converges to the actual gradient. It is much more complicated to build a sampling-based estimator for the approximation to the inverse of the Hessian. In other words, second order methods introduce a lot of complexity and extra memory occupation, but stochastic second order methods introduce even more complexity. Contrast that with stochastic first order methods, where the algorithm is just slightly more complicated than that of deterministic first order methods.
• finally, they have a lot of moving parts, which are difficult to tune up in the best way. Your same paper leaves a lot of details to be specified. Do we need even more extra hyperparameters, or do we need robust optimization methods? Keep in mind that in Deep Learning, as explained very well by Shai Shalev-Shwartz, when something goes wrong, it's very difficult to understand how to fix it https://www.youtube.com/watch?v=1nvf_DBnsxo and more hyperparameters don't help in that respect.

Answer 2

This is actually starting to change as recent work are showing the benefit of second order methods specially for NLP problems. Some examples are:

1. "ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning" Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, Michael W. Mahoney

2. "Second Order Optimization Made Practical" Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, Yoram Singer

There has been an incorrect notion that second order methods are impractical because the cost of forming Hessian is $O(N^2)$ or that the cost of Hessian inverse is $O(N^3)$. In fact, you never do any of these explicitly. In practice, randomized linear algebra methods and matrix free approaches are used which can provide good approximations to Hessian in $O(N)$ complexity.

There are actually multiple libraries now for this which enables calculating Hessian spectrum of large models (even billion parameter models) in reasonable times. Below is our implementation:

https://github.com/amirgholami/PyHessian

Update: There was a question about how Newton's method can be used without explicitly forming the Hessian ($O(N^2)$ cost) and explicitly applying its inverse (O(N^3)) cost. The answer is that you can use Conjugate Gradient to compute the Newton step. Let's denote gradient with $g$ and Hessian with $H$. In Newton's method the update to parameters $w$ is as follows:

$w^{new} = w^{old} - H^{-1}g$

The solution to $H^{-1}g$ can be computed by solving:

$H\Delta w = -g$

This is a system of linear equations that can be solved with Conjugate Gradient (for a PSD H). Thankfully, CG does not require $H$ to be explicitly formed to find $\Delta w=-H^{-1}g$. It only requires the application of $H$ to a given vector which can be computed in $O(N)$ complexity. In theory, you will need r CG iterations to exactly solve the above equations (where r is the Hessian rank). However, in practice, a few iterations are often necessary unless machine precision accuracy is needed.

This was elegantly explained in Perlmutter's 1994 paper (see section 5.2):

3. "Fast Exact Multiplication by the Hessian" BA Perlmutter

Also for a more in-depth analysis I suggest reading section 6 the following paper:

4. "Optimization Methods for Large-Scale Machine Learning" Leon Bottou, Frank E. Curtis, Jorge Nocedal