Skip to main content
1 of 6

They aren't popular because they don't work.

Nicol N. Schraudolph spend a few years trying to make Krylov methods work for Machine Learning. I first learned of his work in 2004 Machine Learning summer school in Canberra.

Looking at his later work (A Stochastic Quasi-Newton Method for Online Convex Optimization) you can find the following explanation:

enter image description here

More generally, thousands of people have tried to improve on SGD+momentum in Machine Learning setting, without success. Adam is slightly better on many tasks, but slightly worse on others, like Imagenet training.

Personally I've spent significant time working on ways of improving SGD (contributing to tools like this), and believe that for optimized architectures like Resnet-50, optimally preconditioned direction will only give a modest improvement, perhaps $\approx$ 5x savings in terms of the number of steps needed. This means if your advanced method does more than "5 SGD steps" worth of work per step, it'll lose to SGD. Additionally there's a storage constraint, you can't store more than a few gradients worth of statistics -- models are typically scaled until gradient computation exceeds GPU memory constraint.

General reasons why it's hard to improve on SGD is that typical ML problem is:

  • overparameterized and very high-dimensional. SGD in this setting is already pretty good, converging at an exponential rate -- https://arxiv.org/abs/1811.02564
  • non-stationary. Local curvature statistics get stale quickly after a few of steps.
  • not trained to convergence. Many "advanced methods" are theoretically superior to SGD only in the "tail regime", but we don't get there
  • tailor made for SGD. If SGD fails to achieve good results, this network architecture won't see the light of day. For instance, autoencoder with a bottleneck layer is impossible to train with SGD, but easy with a factored Gauss-Newton method.

An example of method which satisfies these constraints is PSGD which:

  1. stores preconditioner $P$ in a factored form
  2. updates $P$ in an online fashion by taking SGD steps on $P$ to keep $\|I-PH\|^2$ small