5
$\begingroup$

tl;dr: When is gradient descent with exact line search preferred over Newton's method?


I simply don't understand why exact line search is ever useful, and here's my reasoning.

Let's say I have a function $f$ that I want to minimize. Gradient descent performs the updates:

$$\vec{x} \gets \vec{x} - t \vec{\nabla}f(\vec{x})$$

The optimal step size $t$ must satisfy:

$$\frac{d}{d t} f(\vec{x} - t\vec{h}) = 0$$

To solve this, I approximate $f$ with its Taylor polynomial:

$$f(\vec{x} - t\vec{h}) \approx f(\vec{x}) - t\vec{h}^\top \vec{\nabla}f(\vec{x}) + \frac{t^2}{2}\vec{h}^\top \vec{\nabla}^2f(\vec{x})\ \vec{h} + \ldots$$

...and then differentiate it with respect to $t$ and set it equal to $0$:

$$\frac{d}{d t} f(\vec{x} - t\vec{h}) \approx -\vec{h}^\top \vec{\nabla}f(\vec{x}) + t\vec{h}^\top \vec{\nabla}^2f(\vec{x})\ \vec{h} = 0$$

$$t = \frac{\vec{h}^\top \vec{\nabla}f(\vec{x})}{\vec{h}^\top \vec{\nabla}^2f(\vec{x})\ \vec{h}}$$

Since $\vec{h} = \vec{\nabla} f(\vec{x})$, we have:

$$t = \frac{\vec{\nabla}f(\vec{x})^\top \vec{\nabla}f(\vec{x})}{\vec{\nabla}f(\vec{x})^\top \vec{\nabla}^2f(\vec{x})\ \vec{\nabla}f(\vec{x})}$$

This is great, except that we can see that computing $t$ requires the Hessian $\vec{\nabla}^2f$ (expensive)!
But if I could really compute the Hessian, then wouldn't I be using Newton's method instead?

Why would I ever choose to do exact line search?

$\endgroup$
10
  • $\begingroup$ Note that the choice of exact line search is discutable in itself: math.stackexchange.com/questions/770622/… $\endgroup$
    – Surb
    Feb 17, 2015 at 21:56
  • 1
    $\begingroup$ Exact line search is usually not used in practical algorithms. Other line search strategies are used. $\endgroup$
    – littleO
    Feb 17, 2015 at 22:08
  • $\begingroup$ @littleO: When you say "usually" do you have exceptions in mind? Or is that just to avoid using superlatives? $\endgroup$
    – user541686
    Feb 17, 2015 at 22:20
  • $\begingroup$ I only say "usually" because there is probably some counterexample out there that I'm not aware of. In the conjugate gradient method for solving $Ax = b$, an exact line search is used, but in that case we are only minimizing a quadratic function. $\endgroup$
    – littleO
    Feb 17, 2015 at 22:46
  • $\begingroup$ @littleO: Hmm, I guess my question applies just as well to the conjugate gradient case -- i.e. why would you ever use exact line search for conjugate gradient descent instead of Newton's method? What's the benefit? $\endgroup$
    – user541686
    Feb 17, 2015 at 22:49

2 Answers 2

8
$\begingroup$

Since I seem to be the only one who thinks this is a duplicate, I will accept the wisdom of the masses :-) and attempt to turn my comments into an answer.

Here's the TL;DR version:

  • what you have described is not an exact line search.
  • a proper exact line search does not need to use the Hessian (though it can).
  • a backtracking line search is generally preferred in practice, because it makes more efficient use of the gradients and (when applicable) Hessian computations, which are often expensive. (EDIT: coordinate descend methods often use exact line search.)
  • when properly constructed, the line search should have no impact on your choice between gradient descent and Newton's method.

An exact line search is one that solves the following scalar minimization exactly---or, at least, to a high precision: $$t = \mathop{\textrm{argmin}}_{\bar{t}} f( x - \bar{t} h ) \tag{1}$$ where $f$ is the function of interest, $x$ is the current point, and $h$ is the current search direction. For gradient descent, $h=\nabla f(x)$; for Newton descent, $h=(\nabla^2 f(x))^{-1}\nabla f(x)$. The key concept, of course, is that you have temporarily reduced a multidimensional optimization problem down to a single dimension. But to call it an exact line search, you still have to determine a near-exact solution to $(1)$.

You haven't done this. Instead, you've taken a single Newton step in $t$. This is an approximate line search, not an exact one. To turn your approach into an exact line search you need to iterate: $$t_0=0, \quad t_{k+1} = f(x-t_k h) - \alpha_k\left(\left.\frac{d^2}{dt^2} f(x-t h) \right|_{t=t_k}\right)^{-1}\left.\frac{d}{dt} f(x-t h) \right|_{t=t_k}, \quad k=1,2,\dots$$ where $\alpha_k$ is a step size that you must select to ensure convergence. (We will talk about a good way to select $\alpha_k$ later.)

As you have seen, computing even one of these iterates requires the computation of the Hessian $\nabla^2 f(x-t_k h)$. And you are right to say that this makes no sense! If you are going to use the Hessian in the line search, you should use it in the outer descent steps. Granted, you don't have to invert the Hessian in the scalar case, so it might be slightly less expensive, but still, the point stands.

Your second mistake, then, is assuming that an exact line search must use the Hessian. This is not the case: any numerical method for solving $(1)$ will do; and for gradient descent, it makes sense to use the gradient alone for an exact line search. That is: $$t_0=0, \quad t_{k+1} = f(x-t_k h) - \alpha_k \left.\frac{d}{dt} f(x-t h) \right|_{t=t_k} \quad k=0,1,\dots$$ Again, $\alpha_k$ is a step size chosen to ensure convergence.

Even with this reduced complexity, an exact line search rarely makes sense. This is the point I made in the other question. After all, $$\left.\frac{d}{dt} f(x-t h) \right|_{t=t_k} = \langle \nabla f(x-th), h \rangle = \langle \nabla f\left(x-t\nabla f(x)\right), \nabla f(x)\rangle$$ Each step of the line search requires computing the full gradient at the new candidate point. If you're going to go through the trouble of computing the gradient, why should you limit yourself to moving in the direction of the old gradient?

EDIT: If evaluating $f$ alone is significantly less expensive than evaluating $\nabla f$, then one option is to use bisection to perform the exact line search. I will leave this as an exercise for the reader.

In practice, one rarely does exact line search. Instead, one does something called backtracking line search. In effect, a backtracking line search does only the first step of a numerical line search, and takes care to make sure that the step size $\alpha_1$ guarantees a sufficient reduction in the objective function. Since we're only taking one step, I'll drop the subscript and just call the step size $\alpha$. There are many ways to go about this, but here's what I do.

  1. Select constants $c_1>1$, $0<c_2,c_3<1$, and an initial step size; say $\alpha=1$.
  2. Select an initial guess of $\alpha\leftarrow c_1\alpha$. The idea is that for each step of your outer iteration (gradient or Newton), you're going to try a slightly larger step size so that you can converge faster.
  3. Check to see if $f(x-\alpha h) \leq f(x) - c_2\alpha\langle \nabla f(x),h \rangle$. This is called the Armijo-Goldstein condition.
  4. If that condition is satisfied, STOP. $\alpha$ is your step size, and $x-\alpha h$ is your new iterate.
  5. If that condition is not satisfied, reduce the step size with $\alpha\leftarrow c_3\alpha$, and repeat steps 3-5.

If you're doing a Newton iteration, you might change step 2 so that the maximum value of $\alpha$ is 1. That's because once you've reached the region of quadratic convergence, there really isn't going to be any benefit to having $\alpha>1$.

EDIT: I just attended a lecture yesterday where it was stated that exact line search is often employed in coordinate descent methods. This makes sense if the cost of descending on one variable is significantly cheaper than a full gradient descent.

$\endgroup$
3
  • $\begingroup$ What if we like to search for the best step-size among both positive and negative values of $\alpha$ ? $\endgroup$
    – Bob
    Mar 7, 2017 at 22:12
  • $\begingroup$ Under what circumstances would a negative alpha occur? $\endgroup$ Mar 8, 2017 at 1:11
  • $\begingroup$ Actually I want to do SQP, and there you first find the best direction based on a subproblem, and then doing a line search to minimize a merit function in that direction . The fact is that the found direction is not the gradient of the merit function so it can happen to be minimized by a negative alpha! $\endgroup$
    – Bob
    Mar 10, 2017 at 11:25
0
$\begingroup$

It's still different since you are not required to calculate the inverse of hessian in the exact line search, which is a very computationally expensive step.

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