1

In my optimization class we are using the Boyd and Vandenberghe Convex Optimization textbook, which gives the following stopping criterion for backtracking line search (p. 464):

$$f(x + t \Delta x) \leq f(x) + \alpha t \nabla f(x)^T \Delta x$$

Here $\alpha$ is a parameter on $(0, 1/2)$. These bounds are used when proving the following fact related to gradient descent: If $0 \leq t \leq 1/M$ and $\alpha \lt 1/2$, then

$$f(x - t \nabla f(x)) \leq f(x) - \alpha t || \nabla f(x) ||^2$$

The proof given is

$$\begin{align} f(x - t \nabla f(x)) & \leq f(x) - t || \nabla f(x) ||^2 + \frac{Mt^2}{2} || \nabla f(x) ||^2 &\text{(Taylor's theorem)}\\ & \leq f(x) - \frac{t}{2} || \nabla f(x) ||^2 & (\text{because} -t + Mt^2/2 \leq -t/2)\\ & \leq f(x) - \alpha t || \nabla f(x) ||^2 \end{align}$$

But considering the geometry of the method, it seems to me like it should be "safe" to pick any $\alpha \lt 1$. And this more general limit is mentioned on Wikipedia and this wiki.

Beyond the simplicity of the proof above, is there a deeper reason for restricting $\alpha$ to $(0, 1/2)$?

Max
  • 1,257
  • I think this is a very good question. I believe there's a good reason for the $1/2$ upper bound. Will post an answer in about 30 minutes when I get home. – f10w Dec 02 '20 at 21:42

2 Answers2

2

First, for gradient descent (or steepest descent in general), $\alpha\in (0,1)$ is enough. It is easy to adapt the proof presented in the book to this case. I show below such a proof for gradient descent, but for steepest descent it is similar.

We will show that for $0\le t\le \frac{2(1-\alpha)}{M}$ and $\alpha\in (0,1)$ we have $$f(x - t \nabla f(x)) \leq f(x) - \alpha t \| \nabla f(x) \|_2^2.$$ Indeed, \begin{align} f(x - t \nabla f(x)) & \leq f(x) - t \| \nabla f(x) \|_2^2 + \frac{Mt^2}{2} \| \nabla f(x) \|_2^2\\ & = f(x) - \left(1 - \frac{Mt}{2} \right)t \|\nabla f(x) \|^2 \\ & \leq f(x) - \alpha t || \nabla f(x) ||^2. \end{align} Now the proof proceeds as presented in the book. Update for clarification: You should replace accordingly the values in the remaining part of the proof. For example, instead of "Therefore the backtracking line search terminates either with $t = 1$ or with a value $t\ge \beta/M$", it should now reads "Therefore the backtracking line search terminates either with $t = 1$ or with a value $t\ge 2(1-\alpha)\beta/M$". And so on.

Second, and more interestingly:

Beyond the simplicity of the proof above, is there a deeper reason for restricting $\alpha$ to $(0,1/2)$.

The reason why the authors restricted $\alpha \in (0,1/2)$ is, apparently, because they want to use the same bounds of $\alpha$ for all the methods presented in that chapter of the book. The tricky part here is that the analysis of the damped Newton method requires $\alpha < 1/2$ (pages 490-491, and later on page 505 for self-concordant functions). For the other ones, $(0,1)$ is enough (but the authors took advantage of their assumption $\alpha < 1/2$ to simplify expressions, so their proofs need to be adapted to the $(0,1)$ case).

A better presentation would have been using $(0,1)$ for the general case, and restricting to $(0,1/2)$ when necessary. (Or at least making it clear when $(0,1/2)$ is necessary instead of "The reason for requiring $\alpha$ to be smaller than $0.5$ will become clear later.")

f10w
  • 4,509
  • 15
  • 22
  • How do you justify the less-restrictive bounds on $t$? – Max Dec 03 '20 at 01:18
  • @Max The answer is in the proof (last inequality). – f10w Dec 03 '20 at 01:25
  • What I mean is, how do you know that the $t$ you get from inexact line search satisfies $0 \leq t \leq \frac{2(1-\alpha)}{M}$? I only know how to show $0 \leq t \leq 1/M$, which guarantees $0 \leq t \leq \frac{2(1-\alpha)}{M}$ only for $\alpha \leq 1/2$. Basically, your proof only weakens the constraint on $\alpha$ by tightening the constraint on $t$, which begs the question. – Max Dec 03 '20 at 01:36
  • Ah, I see now. $2(1 - \alpha)/ M$ is in fact looser than $1/M$. – Max Dec 03 '20 at 01:40
  • 1
    @Max Great. I've added some clarification that should make it easier for you to complete the proof. If you want to fully understand it, you should start from the beginning (in the book), and replace the part in your question (and everything after that) with what I have presented. It should be straightforward enough. – f10w Dec 03 '20 at 01:48
  • @Max My added clarification should show clearly why line search will produce $t$ that satisfies $0 \leq t \leq \frac{2(1-\alpha)}{M}$. – f10w Dec 03 '20 at 01:52
  • @Max I'm going to sleep now so just in case it's still not clear for you: Try to fully understand the proof presented in the book for $(0,1/2)$ first, then you'll see that the above extension to $(0,1)$ is straightforward. Good luck! – f10w Dec 03 '20 at 01:56
0

To prove convergence of steepest descent, $\alpha\in(0,1)$ is enough. Additional restrictions on $\alpha$ are required in order to prove additional results as, e.g.,

  • existence of step-sizes for Wolfe-Powell step-size strategy
  • convergence of nonlinear CG
  • acceptance of full step-size $t=1$ in globalized Newton
daw
  • 49,113
  • 2
  • 38
  • 76
  • How do you prove convergence of gradient descent with alpha up to 1? The proof we learned relies on the fact above. – Max Dec 02 '20 at 12:32
  • This is a different question ;) The proof above is certainly not optimal. – daw Dec 02 '20 at 14:01