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

This is something that has been bugging me for a while, and I couldn't find any satisfactory answers online, so here goes:

After reviewing a set of lectures on convex optimization, Newton's method seems to be a far superior algorithm than gradient descent to find globally optimal solutions, because Newton's method can provide a guarantee for its solution, it's affine invariant, and most of all it converges in far fewer steps. Why is second-order optimization algorithms, such as Newton's method not as widely used as stochastic gradient descent in machine learning problems?

• For neural networks, deeplearningbook.org Section "8.6 Approximate Second-Order Methods" gives a nice overview. In summary "Beyond the challenges created by certain features of the objective function, such as saddle points, the application of Newton’s method for training large neural networks is limited by the significant computational burden it imposes." There exist alternatives that attempt to gain some of the advantages of Newton’s method while side-stepping the computational hurdles, but they have their own issues. Dec 29, 2016 at 2:56
• see this related question and comments, stats.stackexchange.com/questions/232305/… Dec 29, 2016 at 3:10
• Note that the other comments have some wider applicability to machine learning beyond just "deep learning". However while all ML problems can tend to be "big data", not all ML problems are necessarily "big features" (i.e. many parameters to tune), though deep learning invariably is. Dec 29, 2016 at 3:49
• It's worth noting that in machine learning outside of deep learning, L-BFGS (which, roughly speaking, approximates Newton's method) is a fairly common optimization algorithm. Jan 3, 2017 at 22:16
• Newton's method assumes convexity, modern ML problems (neutral nets) are not likely anywhere near convex, though admittedly an area of open research there. Hence Newton's method is probably as bad an estimator as linear anywhere but near the point of calculation. You'll probably gain very little for a quadratic increase in computation. That said, a recent conference at Berkeley had a presenter continuing to show progress in using 2nd order methods, so it's not dead by any means. Jan 11, 2017 at 1:40

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.

• Worth noting that (things based on) the Gauss-Newton method are probably more common. This is a specialization of Newton to nonlinear least squares. Dec 29, 2016 at 1:26
• I wouldn't call Gauss-Newton a specialization of Newton to nonlinear least squares. I'd call it a bastardized approximation of Newton for nonlinear least squares, which uses a more inaccurate Hessian approximation, the larger the residuals in the fitted equations, and accordingly, the further the argument is from optimality. Dec 29, 2016 at 4:12
• @MarkL.Stone fair point, I was trying to not get into technicalities :) It is true that Gauss-Newton style methods try to "fake" 2nd order w/only 1st order info. Personally I have never used Newton methods for optimization, just Gauss-Newton (or LM, or ~similar UKF) or DFO-SQP methods (e.g. BOBYQA). "Optimality" is a tricky question I would say ... for a ML problem, vs. say an engineering design-optimization problem, the reliability/informativeness of a "local Hessian" can be dubious. Perhaps non-local DFO-SQP is ~"stochastic Newton"? (e.g. "online") Dec 29, 2016 at 5:26
• On second thought, DFO-SQP approaches tend to be nonlocal in the parameter space, rather than data batches. The UKF may be the closest in flavor to "stochastic Newton" as it is online w/limited memory ... but it effectively assumes a positive-definite Hessian (i.e. Gaussian approx.). Dec 29, 2016 at 5:34
• Actually that is misleading reason since there are second order methods like CG that doesn't require computing the hessian. k iterations of CG will cost only kN. It is correct that CG would theoretically match Newton only at k=N, but really you dont need so many iterations. Oct 6, 2017 at 14:22

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.

The drawbacks in answers here (and even in the literature) are not 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.

• Using linesearch with the Wolfe conditions or using or trust regions prevents convergence to saddle points. A proper gradient descent implementation should be doing this too. The paper referenced in Cam.Davidson.Pilon's answer points out problems with "Newton's method" in the presence of saddle points, but the fix they advocate is also a Newton method.

• Using Newton's method does not require constructing the whole (dense) Hessian; you can apply the inverse of the Hessian to a vector 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.

• You can compute Hessian matrix-vector products efficiently by 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. Using Newton's method instead of gradient descent shifts the difficulty from the nonlinear optimization stage (where not much can be done to improve the situation) to the linear algebra stage (where we can attack it 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.

For background information about these concepts, I recommend the book "Numerical Optimization" by Nocedal and Wright.

*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.

• I think we're in violent agreement with each other, not with everyone else. Dec 30, 2016 at 14:43
• @MarkL.Stone It seems a conversation happened here and was deleted while I was away. Anyways, I think you're right that we agree with each other and no one else. I guess this is to be expected based on our background as compared to the other people here. As you probably expect I don't think very much of the linked paper. On the other hand, I do think that Riemannian manifold Newton's method, where one shoots a geodesic trajectory in a Newton search direction, is a technique with a lot of promise for very hard problems. Dec 30, 2016 at 22:15
• Could you provide links to the more technical terms you use by chance? (Wolfe conditions, CG-Steihaug trust region method, conjugate gradient, adjoint equation, ...). It seems like you know a lot, but I can't understand it and I wish I could. Jan 2, 2017 at 7:52
• How would you deal with a large training set? If you have e.g. 1 million training samples, then just evaluating the current optimization objective requires testing 1 million samples. And you need to do that multiple times during a line search. So by the time you've done 1 Newton step, Stochastic Gradient Descent will have done a few million updates. Jan 2, 2017 at 9:20
• Nick and @MarkL.Stone: Are you talking about essentially this approach? This is something that was briefly popular in deep learning, especially for recurrent nets, but has since fallen out of favor I assume because it just didn't empirically work that much better than adaptive gradient methods. If they were just doing something wrong, and you fix whatever it is and show it generally outperforms the current standard SGD variant Adam, you might make a big impact: the Adam paper has had 1345 citations in two years.... Jan 3, 2017 at 22:14

A combination of two reasons:

• Newton method attracts to saddle points;
• saddle points are common in machine learning, or in fact any multivariable optimization.

Look at the function $$f=x^2-y^2$$ If you apply multivariate Newton method, you get the following. $$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

Let's get the Hessian: $$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

Invert it: $$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

Get the gradient: $$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

Get the final equation: $$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

So, you see how the Newton method led you to the saddle point at $x=0,y=0$.

In contrast, the gradient descent method will not lead to the saddle point. The gradient is zero at the saddle point, but a tiny step out would pull the optimization away as you can see from the gradient above - its gradient on y-variable is negative.

• Thanks to you I actually understood how this method works from A to Z, so thank you very much for this clear example! Sep 19, 2017 at 18:02
• What would be the the favourite point here?
– Ben
Aug 12, 2019 at 11:48
• @SimplyBeautifulArt the next sentence explains clarifies the statement. the saddle point is not stable in gradient descent, any tiny step will push you away from it Apr 14, 2021 at 18:00
• Let me be more precise with my previous statement. Although it is the case that gradient should eventually leave a first order saddle point, it may have to get very very close to it to do so. Gradient Descent Can Take Exponential Time to Escape Saddle Points figure 1 provides a good example. Apr 14, 2021 at 18:43
• Although the saddle point is unstable for gradient descent, it's also worth noting that because the gradient is zero at the saddle point, gradient descent isn't leaving quickly. In practice, this can lead to "convergence" to the saddle point, if one is not careful. Apr 14, 2021 at 18:44

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.

• Could you add some explanation to why this is so? In theory, Newton's method preforms a weighted gradient descent with "optimal" weights for each of the eigenvectors. Dec 29, 2016 at 17:15
• What that article says about Newton methods "wanting to" converge to saddle points is only true for garbage implementations of Newton's method. Dec 30, 2016 at 4:16
• The paper reparameterizes the problem in terms of eigenvalues and eigenvectors, and uses that to show that gradient descent moves away from a saddle point: it moves towards the saddle point in the direction of negative e-vectors, but it moves away in the direction of positive e-vectors, so it ultimately leaves the saddle point. Newton, on the other hand, has no such guarantee. Jan 3, 2017 at 20:18
• The new algorithm they advocate for in this paper is (a variant of) Newton's method though. it is basically Newton's method for the directions of positive curvature and negative Newton's method for the directions of negative curvature. Jan 5, 2017 at 7:44
• The linked paper introduces saddle-free Newton methods able to handle this issue: by changing sign of step in negative curvature directions - this problem can be resolved by controlling Hessian eigenvalues. Dec 6, 2020 at 7:56

You asked two questions: Why don't more people use Newton's method, and why do so many people use stochastic gradient descent? These questions have different answers, because there are many algorithms that lessen the computational burden of Newton's method but often work better than SGD.

First: Newton's Method takes a long time per iteration and is memory-intensive. As jwimberley points out, Newton's Method requires computing the second derivative, $H$, which is $O(N^2)$, where $N$ is the number of features, while computing the gradient, $g$, is only $O(N)$. But the next step is $H^{-1} g$, which is $O(N^3)$ to compute. So while computing the Hessian is expensive, inverting it or solving least squares is often even worse. (If you have sparse features, the asymptotics look better, but other methods also perform better, so sparsity doesn't make Newton relatively more appealing.)

Second, many methods, not just gradient descent, are used more often than Newton; they are often knockoffs of Newton's method, in the sense that they approximate a Newton step at a lower computational cost per step but take more iterations to converge. Some examples:

• Because of the expense of inverting the Hessian, quasi-Newton" methods like BFGS approximate the inverse Hessian, $H^{-1}$, by looking at how the gradient has changed over the last few steps.

• BFGS is still very memory-intensive in high-dimensional settings because it requires storing the entire $O(N^2)$ approximate inverse Hessian. Limited memory BFGS (L-BFGS) calculates the next step direction as the approximate inverse Hessian times the gradient, but it only requires storing the last several gradient updates; it doesn't explicitly store the approximate inverse Hessian.

• When you don't want to deal with approximating second derivatives at all, gradient descent is appealing because it only uses only first-order information. Gradient descent is implicitly approximating the inverse Hessian as the learning rate times the identity matrix. I, personally, rarely use gradient descent: L-BFGS is just as easy to implement, since it only requires specifying the objective function and gradient; it has a better inverse Hessian approximation than gradient descent; and because gradient descent requires tuning the learning rate.

• Sometimes you have a very large number of observations (data points), but you could learn almost as well from a smaller number of observations. When that is the case, you can use "batch methods", like stochastic gradient descent, that cycle through using subsets of the observations.

• (+1) It's worth noting that L-BFGS is of the same order of complexity as gradient descent in regards to the number of parameters. This is not the case for BFGS. So it's not just the limited memory part of L-BFGS that makes it attractive. Mar 16, 2019 at 18:18
• Sure using full Hessian is rather impractical for NN training, but we can e.g. restrict to "locally interesting subspace" - like spanned by top 10 Hessian eigenvectors suggested by arxiv.org/pdf/1812.04754 ... which can be practically traced with methods like online PCA ( cs-www.cs.yale.edu/homes/el327/papers/opca.pdf ). Dec 6, 2020 at 8:01
• This answer could use more upvotes. For large problems, N^2 memory and N^3 computation are prohibitive and the suggested alternatives are the more practical alternatives. Sep 12, 2022 at 15:54

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.

• Boy, you must use terrible implementations of Newton and Quasi-Newton. If using either with a non positive definite Hessian, then either use trust regions or do line search along direction(s) of negative curvature. If so, they are MORE reliable than steepest descent (i.e, gradient descent with line search or trust region). In short, gradiewnt descent is much less reliable than a properly implemented Quasi-Newton method, which is less reliable than a properly implemented Newton method. Computation time and memory requirements per iteration are a different matter however. Dec 29, 2016 at 12:41
• I think you mean perfectly quadratic function. That is, Newton's method converges in a single iteration with a quadratic objective function, which has a linear gradient. Dec 29, 2016 at 22:22
• @ElizabethSantorella: Yup, you're right! I updated the answer.
– Nat
Dec 30, 2016 at 3:38
• The advantage of a well-implemented and safeguarded Newton method over steepest descent increases the nastier, more ill-condtioned, more non-convex the function is. If you are minimizing the best-behaved quadratic function there is, having a $1/2 x^Tx$ quadratic term, i.e., Hessian = Identity matrix, then steepest descent is just fine, and is the same as Newton's method. Dec 30, 2016 at 4:06
• I've made my case. if you want to think steepest descent, gradient descent are wonderful, especially on poorly behaved functions, that's your business. Knock yourself out. Dec 30, 2016 at 4:31

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 ameliorating 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.

There are many difficulties regarding the use of Newton's method for SGD, especially:

• it requires to know local Hessian matrix - how to estimate Hessian e.g. from noisy gradients with a sufficient precision at a reasonable cost?

• full Hessian is too costly - we rather need some its restriction, e.g. to a linear subspace (like its top eigenspace),

• it needs inverted Hessian $$H^{-1}$$, what is costly and very unstable for noisy estimation - can be statistically blurred around $$\lambda=0$$ eigenvalues which invert to infinity,

• Newton's method directly attracts to close point with zero gradient ... which is usually a saddle here. How to avoid this saddle attraction e.g. repelling them instead? For example saddle-free Newton reverses negative curvature directions, but it requires controlling signs of eigenvalues,

• it would be good to do it online - instead of performing a lot of computation in a single point, try to split it into many small steps to exploit local information about the landscape.

We can go from 1st order to 2nd order in small steps, e.g. adding update of just 3 averages to momentum method we can simultaneously MSE fit parabola in its direction for smarter choice of step size. ps. I have prepared SGD overview lecture focused on 2nd order methods: slides: https://www.dropbox.com/s/54v8cwqyp7uvddk/SGD.pdf, video: https://youtu.be/ZSnYtPINcug

1. First order methods have very well theoretical guarantee about convergence and avoidance of saddle points, see Backtracking GD and modifications.
2. Backtracking GD can be implemented in DNN, with very good performance.
3. Backtracking GD allows big learning rates, can be of the size of inverse of the size of gradient, when the gradient is small. This is very handy when you converge to a degenerate critical point.

References:

https://github.com/hank-nguyen/MBT-optimizer

https://arxiv.org/abs/2007.03618 (Here you also find a heuristic argument, that backtracking gd has correct unit, in the sense of Zeiler in his adadelta paper)

Concerning Newton’s method: with a correct modification, you can avoid saddle points, as several previous comments pointed out. Here is a rigorous proof, where we also give a simple way to proceed if the hessian is singular

https://arxiv.org/abs/2006.01512