Are Quasi-Newton methods computationally impractical?

Question

I was reading a book by Simon Haykin on neural networks when I came across the following strong statement (on the pdf's page 188):

"However, we still have a computational complexity that is $\mathcal{O}(W^2)$, where $W$ is the size of weight vector $\mathbf{w}$. Quasi-Newton methods are therefore computationally impractical, except for in the training of very small-scale neural networks"

It made me confused since I always thought that Quasi-Newton methods are feasible implementations of the Newton's method.

I would like to understand the feasibility of Quasi-Newton methods.

Answer 1

I'm guessing you're referring to the discussion on pages 188-189 of that book. The author doesn't give much detail on quasi-Newton methods or substantiate the $\mathscr O(W^2)$ complexity estimate. To me, the discussion there is pretty unsatisfying.

Probably the archetypal quasi-Newton method is the Broyden-Fletcher-Goldgarb-Shanno or BFGS algorithm. If you can't actually calculate the Hessian, the BFGS algorithm does the next best thing which is to estimate it based on the value of the gradient at previous iterations. I think what Haykin is seizing on is that the BFGS algorithm as originally published uses the full iteration history to come up with a curvature estimate, and that really is quadratic in the dimension of the problem. But it's a lot more common in applications to use the limited memory variant of BFGS, which only uses the last $k$ iterations where $k \ll W$. The complexity of each iteration is $\mathscr{O}(kW)$ for limited-memory BFGS. On top of that, the limited-memory variant can outperform the full BFGS algorithm because the early iterates are so far off that they don't contribute to a good curvature estimate. You're better off forgetting them and using only the last 10 or 20 iterations.

I'd also take issue with some of the statements made in the same section about using second-order methods. The full Newton method can be impractical for many realistic problems because the second derivative is not always feasible to compute and, when it is, it may be indefinite. There is, however, a very good approximation to the second derivative that is strictly positive-definite, easily computable, and offers better than first-order convergence rates called the Gauss-Newton approximation. It's a very general trick but unfortunately many resources only describe it as applied to least-squares problems -- it works for any convex-composite problem. In the machine learning literature, you'll also see second-order methods based on the Gauss-Newton approximation referred to as natural gradient descent. Their use of the term "natural gradient" alludes to some fairly deep connections to statistics; if you want to read more you can look up the information metric. Haykin's book does talk about natural gradient descent but that's in chapter 10.

I don't do ML as such, so take this with a grain of salt, but I have used gradient descent, BFGS, and Gauss-Newton for Bayesian inverse problems in geophysics. For those problems, BFGS usually outperformed gradient descent by at least factor of 10. Gauss-Newton would beat BFGS by a further factor of 10 and sometimes 50 on some standard test problems. Again, different domain so your mileage may vary.

Answer 2

Traditional quasi-newton methods like BFGS require $O(n^{2})$ storage for a potentially fully dense quasi-Hessian matrix and $O(n^{2})$ work in each iteration to update the factorized quasi-Hessian matrix (or its inverse.)

For small neural network models with no more than a few thousand parameters, this is not at all unreasonable. However, deep neural network models often have tens of millions of weights. Storing a matrix of this size is completely impractical.

In practice, various methods in the family of stochastic gradient descent (SGD) are used for training large-scale deep neural networks.