18
$\begingroup$

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.

$\endgroup$
  • 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 '15 at 21:31
20
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is similar to @Aksakal's answer, but in more depth. $\endgroup$ – Dougal Apr 9 '15 at 3:19
  • 1
    $\begingroup$ (+1) This is a great addition! $\endgroup$ – Reinstate Monica Apr 9 '15 at 3:22
17
$\begingroup$

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 eigenvectors 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$. 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.

$\endgroup$
  • $\begingroup$ Great answer! I'm accepting @Dougal 's answer as I think it provides a simpler explanation. $\endgroup$ – Bar Apr 9 '15 at 9:11
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.