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:

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? enter image description here

  • $\begingroup$ Related: stats.stackexchange.com/questions/253632/… $\endgroup$ – Sycorax Apr 22 '19 at 15:43
  • $\begingroup$ @Sycorax, thanks, the answer below is about K-FAC problems, pure Newton has its own (like Hessian size, its estimation and inversion, saddle attraction), but there are also cheap possibilities for 2nd order methods, like just momentum method plus 3 additional updated averages to model parabola in its single direction for smarter choice of step size: stats.stackexchange.com/questions/404545/… $\endgroup$ – Jarek Duda Apr 23 '19 at 8:09

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.
| cite | improve this answer | |
  • 2
    $\begingroup$ You are wise... (+1) More seriously, the point you raise about memory bottlenecks in GPU is substantial and often overlooked. NVIDIA realised this issue early so it immediately served cuBLAS and then (as DL gain traction) cuDNN exactly so be practice for using GPU resources is available. The early days of pure CUDA (and OpenCL 1.x) were marred with such problems; they have been partially hidden from the user's attention with the aforementioned tools but their shadow remains. $\endgroup$ – usεr11852 Feb 24 '19 at 12:13
  • 1
    $\begingroup$ Thanks for materials, I will have to read. However, there is a large spectrum of 2nd order methods, starting with considering single direction but additionally trying to estimate distance to extremum in this direction to choose step size. Considering simultaneously two directions wouldn't add much cost, but could allow to handle problematic saddles you mentioned: attract in one direction, repulse in second. K-FAC uses relatively huge blocks - is on the opposite side of this spectrum - close to full Hessian, but maybe the low cost end deserves some more exploration - small steps from 1st order? $\endgroup$ – Jarek Duda Feb 24 '19 at 13:17
  • $\begingroup$ @JarekDuda not sure how choosing only two directions out of $10^6-10^9$ would help - there is still a fairly large chance that they're both increasing, even if in a saddle. But probably your proof makes use of stochasticity to fix that? Concerning K-FAC being on the opposite side of the spectrum, it's interesting that you should say that, because Roger Grosse actually sells it as a cheap approach, b/c of the Kronecker factorization. I personally agree with you, though. Well, best of luck with your research! Keep us updated. $\endgroup$ – DeltaIV Feb 24 '19 at 20:03
  • $\begingroup$ @DeltaIV, much better two than one e.g. of Adam, especially around saddle: with attractive and repulsive directions, which should be extractable from recent statistical trends of gradient sequence, but proper optimization of their choice is a difficult question. Cost of K-FAC is still ~dimension^2, while tracing a few directions costs dimension times a few. Without help I will realistically have time to really focus on it during the summer break. $\endgroup$ – Jarek Duda Feb 24 '19 at 20:24
  • $\begingroup$ @JarekDuda "Cost of K-FAC is still ~dimension^2, while tracing a few directions costs dimension times a few". Not at all. It's $d^2$, where $d$ is the (typical) number of units in a single layer. This can be much less that the dimensionality of the NN, if it's a deep net like a ResNet. Please don't advertise my answer as a criticism of K-FAC, because it's not. I also added a small modification to the answer. $\endgroup$ – DeltaIV Feb 26 '19 at 10:52

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:


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):

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

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

  1. "Optimization Methods for Large-Scale Machine Learning" Leon Bottou, Frank E. Curtis, Jorge Nocedal
| cite | improve this answer | |
  • $\begingroup$ I think this answer would be improved if you distinguished between the more efficient $O(N)$ methods that you espouse and things like Newton's method. The reason is that (1) Newton's method is a second order method and (2) it does use an inverse of the Hessian. The claim that "you never do any of these [forming and inverting a Hessian]" is flatly false when you consider all second-order methods, but the claim is true for the particular methods which you outline. $\endgroup$ – Sycorax Aug 21 at 21:26
  • $\begingroup$ @Sycorax You actually never explicitly do any of these (forming the Hessian and computing its inverse). I have updated the answer with a clarification and references. $\endgroup$ – Amir Gholami Aug 23 at 1:26

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.