13
$\begingroup$

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\nabla F(a)$ implies that $F(b) \leq F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal $\gamma$ at each step. In my book, in order to do this, one should minimize $G(\gamma)=$ $F(x-\gamma\nabla F(x))$ for $\gamma$. It also says that it should be minimized via a line search. Why can't this function be minimized by simple calculus?

I am unsure what it means to perform a line search on this function. I am also unsure why we want to minimize this function to find the optimal step size.

$\endgroup$
30
$\begingroup$

You are already using calculus when you are performing gradient search in the first place. At some point, you have to stop calculating derivatives and start descending! :-)

In all seriousness, though: what you are describing is exact line search. That is, you actually want to find the minimizing value of $\gamma$, $$\gamma_{\text{best}} = \mathop{\textrm{arg min}}_\gamma F(a+\gamma v), \quad v = -\nabla F(a).$$ It is a very rare, and probably manufactured, case that allows you to efficiently compute $\gamma_{\text{best}}$ analytically. It is far more likely that you will have to perform some sort of gradient or Newton descent on $\gamma$ itself to find $\gamma_{\text{best}}$.

The problem is, if you do the math on this, you will end up having to compute the gradient $\nabla F$ at every iteration of this line search. After all: $$\frac{d}{d\gamma} F(a+\gamma v) = \langle \nabla F(a+\gamma v), v \rangle$$ Look carefully: the gradient $\nabla F$ has to be evaluated at each value of $\gamma$ you try.

That's an inefficient use of what is likely to be the most expensive computation in your algorithm! If you're computing the gradient anyway, the best thing to do is use it to move in the direction it tells you to move---not stay stuck along a line.

What you want in practice is a cheap way to compute an acceptable $\gamma$. The common way to do this is a backtracking line search. With this strategy, you start with an initial step size $\gamma$---usually a small increase on the last step size you settled on. Then you check to see if that point $a+\gamma v$ is of good quality. A common test is the Armijo-Goldstein condition $$F(a+\gamma v) \leq F(a) - c \gamma \|\nabla F(a)\|_2^2$$ for some $c<1$. If the step passes this test, go ahead and take it---don't waste any time trying to tweak your step size further. If the step is too large---for instance, if $F(a+\gamma v)>F(a)$---then this test will fail, and you should cut your step size down (say, in half) and try again.

This is generally a lot cheaper than doing an exact line search.

I have encountered a couple of specific cases where an exact line search could be computed more cheaply than what is described above. This involved constructing a simplified formula for $F(a+\gamma v)$ , allowing the derivatives $\tfrac{d}{d\gamma}F(a+\gamma v)$ to be computed more cheaply than the full gradient $\nabla F$. One specific instance is when computing the analytic center of a linear matrix inequality. But even in that case, it was generally better overall to just do backtracking.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, a couple of typos in there. I think I've squashed 'em but please don't hesitate to point out more. $\endgroup$ – Michael Grant Apr 26 '13 at 21:40
  • $\begingroup$ What exactly is meant by $\|\nabla F(a)\|_2^2$ ? $\endgroup$ – user314782 Feb 17 '16 at 0:48
  • $\begingroup$ @user314782 It is standard notation for the norm of a vector. Typically we deal with multi-dimensional problem, so $a$ is a vector and so is the gradient of $F$ wrt to $a$. $\endgroup$ – Ant Nov 12 '17 at 12:16
  • $\begingroup$ You are right, but couldn't we, for instnace, take a few preselected steps and pick the best one of them, rather than just sticking to the before-hand selected one? $\endgroup$ – David Jul 18 '19 at 10:37
  • $\begingroup$ @David it's not clear to me why that would be better. After all, what if none of those preselected steps meets the fitness criteria? But sure, it might be worth somehow trying a couple of additional steps. $\endgroup$ – Michael Grant Jul 20 '19 at 2:41
2
$\begingroup$

There is a good discussion of this in chapter 10 of Numerical Recipes. Old versions are free online.

You are right that if you have $F$ in a simple enough form, you can minimize over $\gamma$ by calculus. You might even be able to find the minimum directly, without iteration. Often you don't have it in that form. $x$ and $\bigtriangledown F(x)$ are both vectors and it may not be feasible to compute $\bigtriangledown F(x)$ analytically but you can search for a minimum.

What it means to perform a line search is hidden in the symbolism. The value of $G(\gamma)$ is precisely the value of $F$ along a line from the current point $x$ in the direction $\bigtriangledown F(x)$. It should remind you of a parameterized line in three dimensions: a point plus a variable times a direction vector. The reason you do this is because this is the best point along that line. You expect that the value will decrease along that direction (because you have chosen the gradient, which is the direction of greatest decrease) but if you go too far it will start to increase again. Why not stop at the bottom of the valley and try again?

Some of the methods in Numerical Recipes don't need any computations of the gradient at all. They come up with directions to minimize over in other ways.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Not your question, but an adaptive step size can beat a constant $\gamma$, and a $\gamma_i$ per component can beat a single $\gamma$ for all components. See RmsProp , rmsprop.py
and Zeiler, ADADELTA: An adaptive learning rate method, 2012, 6p.
But be careful with recursive / IIR filters !

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "and a γi per component can beat a single γ for all components." can you please supply me with a reference for this? $\endgroup$ – Lindon Feb 22 '15 at 0:07
  • $\begingroup$ @Lindon, "Per-dimension first order methods" in Zeiler's paper; also Notes on AdaGrad by C. Dyer (CMU), 2011, 3p. Could you describe your problem, or point to similar problems on the web ? $\endgroup$ – denis Feb 22 '15 at 14:18

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.