# Why are second-order derivatives useful in convex optimization?

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.

• 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)? – user41979 Apr 8 '15 at 21:31

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.

• This is similar to @Aksakal's answer, but in more depth. – djs Apr 9 '15 at 3:19
• (+1) This is a great addition! – Sycorax Apr 9 '15 at 3:22
• 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. – Charlie Parker Sep 8 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.

• Great answer! I'm accepting @Dougal 's answer as I think it provides a simpler explanation. – Bar Apr 9 '15 at 9:11
• 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}$? – Charlie Parker Sep 8 at 17:59
• @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. – Sycorax Sep 8 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.

• is $f$ the approximation or the original function we want to minimize? sorry I find your prose hard to follow. – Charlie Parker Sep 8 at 18:05