Why is Newton's method not widely used in machine learning?

Gradient descent maximizes a function using knowledge of its derivative. Newton's method, a root finding algorithm, maximizes a function using knowledge of its second derivative. That can be faster when the second derivative is known and easy to compute (the Newton-Raphson algorithm is used in logistic regression). However, the analytic expression for the second derivative is often complicated or intractable, requiring a lot of computation. Numerical methods for computing the second derivative also require a lot of computation -- if $N$ values are required to compute the first derivative, $N^2$ are required for the second derivative.

I recently learned this myself - the problem is the proliferation of saddle points in high-dimensional space, that Newton methods want to converge to. See this article: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.

Indeed the ratio of the number of saddle points to local minima increases exponentially with the dimensionality N.

While gradient descent dynamics are repelled away from a saddle point to lower error by following directions of negative curvature, ...the Newton method does not treat saddle points appropriately; as argued below, saddle-points instead become attractive under the Newton dynamics.

More people should be using Newton's method in machine learning*. I say this as someone with a background in numerical optimization, who has dabbled in machine learning over the past couple of years.

Most of the drawbacks in answers here (and even in the literature) are not really an issue if you use Newton's method correctly. Moreover, the drawbacks that do matter also slow down gradient descent the same amount or more, but through less obvious mechanisms.

• Convergence to saddle points is dealt with through linesearch with the Wolfe conditions, or trust regions. A proper gradient descent implementation should be doing this too..

• The whole (dense) Hessian doesn't need to be constructed; the inverse can be applied with iterative methods that only use matrix-vector products (e.g., Krylov methods like conjugate gradient). See, for example, the CG-Steihaug trust region method.

• Hessian matrix-vector products can be computed efficiently through solving two higher order adjoint equations of the same form as the adjoint equation that is already used to compute the gradient (e.g., the work of two backpropagation steps in neural network training).

• Ill conditioning slows the convergence of iterative linear solvers, but it also slows gradient descent equally or worse. Basically the difficulty has been shifted from nonlinear optimization stage (where not much can be done to improve the situation) to the linear algebra stage (where it can be attacked with the entire arsenal of numerical linear algebra preconditioning techniques).

• Also, the computation shifts from "many many cheap steps" to "a few costly steps", opening up more opportunities for parallelism at the sub-step (linear algebra) level.

*Of course, Newton's method will not help you with L1 or other similar compressed sensing/sparsity promoting penalty functions, since they lack the required smoothness.

Gradient descent direction's cheaper to calculate, and performing a line search in that direction is a more reliable, steady source of progress toward an optimum. In short, gradient descent's relatively reliable.

Newton's method is relatively expensive in that you need to calculate the Hessian on the first iteration. Then, on each subsequent iteration, you can either fully recalculate the Hessian (as in Newton's method) or merely "update" the prior iteration's Hessian (in quasi-Newton methods) which is cheaper but less robust.

In the extreme case of a very well-behaved function, especially a perfectly quadratic function, Newton's method is the clear winner. If it's perfectly quadratic, Newton's method will converge in a single iteration.

In the opposite extreme case of a very poorly behaved function, gradient descent will tend to win out. It'll pick a search direction, search down that direction, and ultimately take a small-but-productive step. By contrast, Newton's method will tend to fail in these cases, especially if you try to use the quasi-Newton approximations.

In-between gradient descent and Newton's method, there're methods like Levenberg–Marquardt algorithm (LMA), though I've seen the names confused a bit. The gist is to use more gradient-descent-informed search when things are chaotic and confusing, then switch to a more Newton-method-informed search when things are getting more linear and reliable.

For large dimensions, the Hessian is typically expensive to store and solving $Hd = g$ for a direction can be expensive. It is also more difficult to parallelise.

Newton's method works well when close to a solution, or if the Hessian is slowly varying, but needs some tricks to deal with lack of convergence and lack of definiteness.

Often an improvement is sought, rather than an exact solution, in which case the extra cost of Newton or Newton like methods is not justified.

There are various ways of amelioration the above such as variable metric or trust region methods.

As a side note, in many problems a key issue is scaling and the Hessian provides excellent scaling information, albeit at a cost. If one can approximate the Hessian, it can often improve performance considerably. To some extent, Newton's method provides the 'best' scaling in that it is affine invariant.