# Are Quasi-Newton methods computationally impractical?

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.

• In stochastic gradient descent, the gradient is sampled randomly in batches defined by random number generator seeds. Each gradient evaluation uses a different batch of seeds. The BFGS method doesn't work when evaluating noisy gradients, just like finite differences doesn't work with noisy function evaluations. There are some recent works looking at LBFGS approaches, but the standard BFGS scheme simply will not work with stochastic gradient descent. Commented Oct 28, 2022 at 17:39

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.

• I think another important point here is that for neural network applications we typically care whether we get an accurate least squares solution- anything reasonably close to a local minimum might be perfectly adequate in terms of predictive mean square error. Commented Oct 27, 2022 at 0:42
• "unfortunately many resources only describe it as applied to least-squares problems" - As far as I known, the Gauss-Newton approximation is only applicable when the objective function is the sum of error squares, right? Commented Oct 28, 2022 at 9:27
• @RubemPacelli consider reading the link with text "convex-composite" in the above post. Commented Oct 28, 2022 at 14:10
• @RubemPacelli It would be very easy to come to that conclusion but there's actually a little more to the story. Briefly, the idea is to take the second derivative of the composition of $f : X \to \mathbb{R}$ with $g : Q \to X$, where $f$ is convex and $Q$, $X$ are Banach spaces. The second derivative consists of two terms. One term is symmetric, positive definite, and easy to compute. The second term is neither definite nor easy. The approximation is to keep only the nice part. Commented Oct 28, 2022 at 16:22

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.

• What about, limited-memory variants of the BFGS, are they feasible for dense deep neural networks? Commented Oct 28, 2022 at 9:31