I guess this is a basic question and it has to do with the direction of the gradient itself, but I'm looking for examples where 2nd order methods (e.g. BFGS) are more effective than simple gradient descent.

  • 3
    $\begingroup$ Is it too simplistic to just observe that "find the vertex of a paraboloid" is a much better approximation to the "find a minimum" problem than "find the minimum of this linear function" (which, of course, has no minimum because it's linear)? $\endgroup$
    – user41979
    Apr 8, 2015 at 21:31

4 Answers 4


Here's a common framework for interpreting both gradient descent and Newton's method, which is maybe a useful way to think of the difference as a supplement to @Sycorax's answer. (BFGS approximates Newton's method; I won't talk about it in particular here.)

We're minimizing the function $f$, but we don't know how to do that directly. So, instead, we take a local approximation at our current point $x$ and minimize that.

Newton's method approximates the function using a second-order Taylor expansion: $$ f(y) \approx N_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y - x)^T \, \nabla^2 f(x) \, (y - x) ,$$ where $\nabla f(x)$ denotes the gradient of $f$ at the point $x$ and $\nabla^2 f(x)$ the Hessian at $x$. It then steps to $\arg\min_y N_x(y)$ and repeats.

Gradient descent, only having the gradient and not the Hessian, can't just make a first-order approximation and minimize that, since as @Hurkyl noted it has no minimum. Instead, we define a step size $t$ and step to $x - t \nabla f(x)$. But note that \begin{align} x - t \,\nabla f(x) &= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac{1}{2 t} \lVert y - x \rVert^2\right] \\&= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x)\right] .\end{align} Thus gradient descent minimizes a function $$G_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x).$$

Thus gradient descent is kind of like using Newton's method, but instead of taking the second-order Taylor expansion, we pretend that the Hessian is $\tfrac1t I$. This $G$ is often a substantially worse approximation to $f$ than $N$, and hence gradient descent often takes much worse steps than Newton's method. This is counterbalanced, of course, by each step of gradient descent being so much cheaper to compute than each step of Newton's method. Which is better depends entirely on the nature of the problem, your computational resources, and your accuracy requirements.

Looking at @Sycorax's example of minimizing a quadratic $$ f(x) = \tfrac12 x^T A x + d^T x + c $$ for a moment, it's worth noting that this perspective helps with understanding both methods.

With Newton's method, we'll have $N = f$ so that it terminates with the exact answer (up to floating point accuracy issues) in a single step.

Gradient descent, on the other hand, uses $$ G_x(y) = f(x) + (A x + d)^T y + \tfrac12 (x - y)^T \tfrac1t I (x-y) $$ whose tangent plane at $x$ is correct, but whose curvature is entirely wrong, and indeed throws away the important differences in different directions when the eigenvalues of $A$ vary substantially.

  • 1
    $\begingroup$ This is similar to @Aksakal's answer, but in more depth. $\endgroup$
    – Danica
    Apr 9, 2015 at 3:19
  • 1
    $\begingroup$ (+1) This is a great addition! $\endgroup$
    – Sycorax
    Apr 9, 2015 at 3:22
  • $\begingroup$ I think what I don't understand is why it results in better optimization of $f$ using $N$ (quadratic approximation). Somehow saying $N$ approximates $f$ better feels to vague to really understand why exactly I prefer one vs the other. $\endgroup$ Sep 8, 2020 at 18:02

Essentially, the advantage of a second-derivative method like Newton's method is that it has the quality of quadratic termination. This means that it can minimize a quadratic function in a finite number of steps. A method like gradient descent depends heavily on the learning rate, which can cause optimization to either converge slowly because it's bouncing around the optimum, or to diverge entirely. Stable learning rates can be found... but involve computing the hessian. Even when using a stable learning rate, you can have problems like oscillation around the optimum, i.e. you won't always take a "direct" or "efficient" path towards the minimum. So it can take many iterations to terminate, even if you're relatively close to it. BFGS and Newton's method can converge more quickly even though the computational effort of each step is more expensive.

To your request for examples: Suppose you have the objective function $$ F(x)=\frac{1}{2}x^TAx+d^Tx+c $$ The gradient is $$ \nabla F(x)=Ax+d $$ and putting it into the steepest descent form with constant learning rate $$ x_{k+1}= x_k-\alpha(Ax_k+d) = (I-\alpha A)x_k-\alpha d. $$

This will be stable if the magnitudes of the eigenvalues of $I-\alpha A$ are less than 1. We can use this property to show that a stable learning rate satisfies $$\alpha<\frac{2}{\lambda_{max}},$$ where $\lambda_{max}$ is the largest eigenvalue of $A$. Choosing a learning rate which is too large will overshoot the minimum, and the optimization will diverge.

The steepest descent algorithm's convergence rate is limited by the largest eigenvalue and the routine will converge most quickly in the direction of its corresponding eigenvector. Likewise, it will converge most slowly in directions of the eigenvector of the smallest eigenvalue. When there is a large disparity between large and small eigenvalues for $A$, gradient descent will be slow. Any $A$ with this property will converge slowly using gradient descent.

In the specific context of neural networks, the book Neural Network Design has quite a bit of information on numerical optimization methods. The above discussion is a condensation of section 9-7.

  • $\begingroup$ Great answer! I'm accepting @Dougal 's answer as I think it provides a simpler explanation. $\endgroup$
    – Bar
    Apr 9, 2015 at 9:11
  • $\begingroup$ why do we care about the eigenvectors of $I - \alpha A$? i.e. how does it affect the optimization or even better, each step for getting $x_{k+1}$? $\endgroup$ Sep 8, 2020 at 17:59
  • $\begingroup$ @CharlieParker If the learning rate is too large, the optimization can diverge. If the learning rate is too small, progress towards the minimum will be slow. $\endgroup$
    – Sycorax
    Sep 8, 2020 at 18:29

In convex optimization you are approximating the function as the second degree polynomial in one dimensional case: $$f(x)=c+\beta x + \alpha x^2$$

In this case the the second derivative $$\partial^2 f(x)/\partial x^2=2\alpha$$

If you know the derivatives, then it's easy to get the next guess for the optimum: $$\text{guess}=-\frac{\beta}{2\alpha}$$

The multivariate case is very similar, just use gradients for derivatives.

  • $\begingroup$ is $f$ the approximation or the original function we want to minimize? sorry I find your prose hard to follow. $\endgroup$ Sep 8, 2020 at 18:05

@Dougal already gave a great technical answer.

The no-maths explanation is that while the linear (order 1) approximation provides a “plane” that is tangential to a point on an error surface, the quadratic approximation (order 2) provides a surface that hugs the curvature of the error surface.

The videos on this link do a great job of visualizing this concept. They display order 0, order 1 and order 2 approximations to the function surface, which just intuitively verifies what the other answers present mathematically.

Also, a good blogpost on the topic (applied to neural networks) is here.

  • $\begingroup$ hmmm hugs the original curve? I can imagine an approximation eventually crossing the curve we want to minimize...is that impossible for the approximation we are considering because of convexity? $\endgroup$ Sep 8, 2020 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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