134
$\begingroup$

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?

$\endgroup$
  • 25
    $\begingroup$ 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. $\endgroup$ – Franck Dernoncourt Dec 29 '16 at 2:56
  • 1
    $\begingroup$ see this related question and comments, stats.stackexchange.com/questions/232305/… $\endgroup$ – Haitao Du Dec 29 '16 at 3:10
  • 1
    $\begingroup$ 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. $\endgroup$ – GeoMatt22 Dec 29 '16 at 3:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Dougal Jan 3 '17 at 22:16
  • 2
    $\begingroup$ 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. $\endgroup$ – David Parks Jan 11 '17 at 1:40
96
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Worth noting that (things based on) the Gauss-Newton method are probably more common. This is a specialization of Newton to nonlinear least squares. $\endgroup$ – GeoMatt22 Dec 29 '16 at 1:26
  • 4
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Dec 29 '16 at 4:12
  • 1
    $\begingroup$ @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") $\endgroup$ – GeoMatt22 Dec 29 '16 at 5:26
  • 1
    $\begingroup$ 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.). $\endgroup$ – GeoMatt22 Dec 29 '16 at 5:34
  • 1
    $\begingroup$ 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. $\endgroup$ – user25322 Oct 6 '17 at 14:22
41
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think we're in violent agreement with each other, not with everyone else. $\endgroup$ – Mark L. Stone Dec 30 '16 at 14:43
  • 1
    $\begingroup$ Tell me what you think of this paper link.springer.com/article/10.1007/s11081-016-9323-4 ? Line search Newton method applied to very non-convex problems w/no adjustment to Hessian or searching along directions of negative curvature. No wonder he thinks Quasi-Newton (probably BFGS) is more robust than Newton. The author claims he used a simple version of Newton's method so as to have an apples to apples comparison between Euclidean and Riemannian Newton's method. (continued in next comment) $\endgroup$ – Mark L. Stone Dec 30 '16 at 14:52
  • 3
    $\begingroup$ @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. $\endgroup$ – Nick Alger Dec 30 '16 at 22:15
  • 2
    $\begingroup$ 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. $\endgroup$ – nikie Jan 2 '17 at 9:20
  • 2
    $\begingroup$ 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.... $\endgroup$ – Dougal Jan 3 '17 at 22:14
33
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – nbubis Dec 29 '16 at 17:15
  • 4
    $\begingroup$ What that article says about Newton methods "wanting to" converge to saddle points is only true for garbage implementations of Newton's method. $\endgroup$ – Mark L. Stone Dec 30 '16 at 4:16
  • $\begingroup$ 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. $\endgroup$ – Elizabeth Santorella Jan 3 '17 at 20:18
  • $\begingroup$ 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. $\endgroup$ – Nick Alger Jan 5 '17 at 7:44
26
$\begingroup$

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$$ enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks to you I actually understood how this method works from A to Z, so thank you very much for this clear example! $\endgroup$ – greenoldman Sep 19 '17 at 18:02
  • $\begingroup$ What would be the the favourite point here? $\endgroup$ – Ben Aug 12 at 11:48
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+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. $\endgroup$ – Cliff AB Mar 16 at 18:18
12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Dec 29 '16 at 12:41
  • 4
    $\begingroup$ 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. $\endgroup$ – Elizabeth Santorella Dec 29 '16 at 22:22
  • 1
    $\begingroup$ @ElizabethSantorella: Yup, you're right! I updated the answer. $\endgroup$ – Nat Dec 30 '16 at 3:38
  • 3
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Dec 30 '16 at 4:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Dec 30 '16 at 4:31
7
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

  • it needs Hessian matrix - how to estimate it e.g. from noisy gradients with a sufficient precision in a reasonable cost?

  • full Hessian is too costly - we rather need some its restriction, e.g. to a subspace (which subspace?),

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

  • Newton's method directly attracts to close point with zero gradient ... which is usually a saddle here. How to repel them instead? E.g. saddled-free Newton reverses negative curvature directions, but it requires controlling signs of eigenvalues,

  • it would be good to do it online - instead of doing a lot of computations in a single point, try to split it into many small steps exploiting more local information.

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 ... 2nd order modeling in a low dimensional subspace we can can still use the remaining coordinates for simultaneous gradient descent.

$\endgroup$

protected by kjetil b halvorsen Feb 20 at 22:26

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.