# How does one choose the step size for steepest descent?

Consider finding the minimal value for any function $g$ from $\mathbb{R}^n$ to $\mathbb{R}$. The method of steepest descent for finding a local minimum for an arbitrary function $g$ from from $\mathbb{R}^n$ to $\mathbb{R}$ can be intuitively described as follows:

1. Evaluate $g$ at an initial approximation $x^{(0)} = (x^{(0)}_{1}, ..., x^{(0)}_{D})^t$
2. Determine a direction from $x^{(0)}$ that results in a decrease in the value of $g$ (or the greatest decrease by using $\bigtriangledown g(x)$, the gradient of $g$, as in gradient descent)
3. Move an appropriate amount in this direction and call the new value $x^{(1)}$.
4. Repeat steps 1 through 3 with $x^{(0)}$ replaced by $x^{(1)}$.

Usually step 3 is implemented as follow (since the object is to reduce $g(x)$ to its minial value):

$$x^{(1)} = x^{(0)} - \alpha \bigtriangledown g(x^{(0)} )$$

for some constant $\alpha > 0$.

However, to us that descent equation one has to choose an appropriate value of $\alpha$ so that $g(x^{(1)} )$ is less that $g(x^{(0)} )$. According to the textbook numerical analysis book by Burden and Faires to determine an appropriate choice for the value of $\alpha$, we consider the single-variable function:

$$h(\alpha) = g(x^{(0)} - \alpha \bigtriangledown g( x^{(0)} )$$

according to them, the value of $\alpha$ that minimizes $h$ is the value needed for the gradient descent equation.

What I don't understand is;

1. why is that the optimal value of $\alpha$? ( i.e. the solution to the minimization of $h( \alpha )$?)
2. How is "optimality" value of alpha even mean in this case and why does minimizing $h( \alpha)$ capture this definition of optimality? Maybe that is the choice of alpha that gives the biggest step size possible given the computed gradient?
3. What is the proof or the rigorous justification that this equation is the right one to optimize to choose the step size? Why is that the correct equation and not something else? Is there a rigorous why to explain why that is the best alpha?
4. What type of guarantee's does that choice of $\alpha$ give us? If we choose that $alpha$, are we guaranteed that if we keep doing iterations of steepest descent, that we will never overshoot? Will it be in an infinite number of iterations or finite iterations?
5. Does this mean that we choose a new step size for every step of Steepest descent?

Notice that, by definition

$$h(\alpha) \equiv g\left(x^{(0)} - \alpha \nabla g\left( x^{(0)} \right)\right) = g\left( x^{(1)} \right).$$

Since the goal is to choose the step with the deepest descent, this can be achieved by choosing $\alpha$ to minimize $h(\alpha)$. This is equivalent to solving

$$\min_\alpha g\left( x^{(1)} \right),\;\;\;\text{ subject to}\;\; x^{(1)}=x^{(0)} - \alpha \nabla g\left( x^{(0)} \right).$$

• descending the deepest would mean to me that you descent and reach the local minimum in one single step (since you can't descend lower, at least not locally). But we choose this step size for more than 1 iterations. So it isn't choosing the deepest descent, since it doesn't achieve that. Or do we have different definitions of deepest? It's still not clear to me. Commented Dec 2, 2015 at 0:13
• @CharlieParker, the constraint in the minimization I wrote down is important. You have to choose the step based only on what you know about the function, i.e $x^{(0)}$ and $\nabla g\left( x^{(0)} \right)$. If you knew where the minimum is it would, in fact, be the deepest descent to go straight there. The problem is exactly that you don't know where that is though.
– mzp
Commented Dec 2, 2015 at 0:47
• @CharlieParker , did this clear up your confusion?
– mzp
Commented Dec 2, 2015 at 17:08
• yes, your comment did clear up my confusion. Though, I find your answer not to reveal everything that is going on. With a few more details I'd be good. Commented Dec 2, 2015 at 19:09
• @CharlieParker For me to help you, it would be better if you could clarify what you mean by that...
– mzp
Commented Dec 2, 2015 at 19:23

Notice that the goal is to reach to some minim of $g(x)$. i.e. we want:

$$\min_{x \in R^n} g(x)$$

notice that $x$ might be a multivariable vector.

Since we have no better way to reach a minimum, lets follow the direction of greatest change towards some minimum. Thus the update rule:

$$x^{(1)} := x^{(0)} - \alpha \nabla g(x^{(0)})$$

However, now we are left with choosing a good step size $\alpha$. Unfortunately, at any point of this algorithm there are only two things that we know, our current guess $g(x^{(0)})$ and the direction of greatest change $\nabla g(x^{(0)})$. If we could, we'd want to choose $x^{(1)}$ such that it corresponds to a minimum i.e. it would be nice to have:

$$\min_{x \in R^n} g(x) = \min_{x^{(1)} \in X^{(1)} } g(x^{(1)})$$

where $X^{(1)}$ denotes the set of candidate $x^{(1)}$ that we could potentially choose (based on the two things that we know). It would be awesome if we could reach the minimum like this because it means that we choose a new $x^{(1)}$ such that its at the (local) minimum that we are looking for. Unfortunately, we are restricted to the previous estimate ( i.e. $x^{(0)}$) that we had. So in reality, we have:

$$\min_{x^{(1)} \in X^{(1)} } g(x^{(1)}) \iff \min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

Thus these two optimization problems are equivalent!

At this point the key aspect to note is that our original problem is $\min_{x \in R^n} g(x)$ and we replaced it by choosing a multivariable vector in a restricted set. How is it restricted? We are only allowed to choose $x^{(1)}$ based on the gradient and our previous estimate. So it makes sense to choose $\alpha$ (and hence $x^{(1)}$ such that we minimize $g(x)$ as much as possible. Since, that was our goal the whole time anyway! Our goal is to choose the smallest $g(x)$, so at each step, we are making sure that we choose an $\alpha$ such that we minimize our original goal $g(x)$ as much as possible.

Let's to address the bullet points in the original question:

1. The reason that $min_{\alpha} h(\alpha)$ is the optimal value of $\alpha$ is because, we are choosing the step size that makes sure we minimize our objective $g(x)$ as much as possible, given that we only know our previous estimate of the minimum and the direction greatest change. So we choose an alpha such that $min g(x^{(1)})$ is satisfied.
2. Optimality in this case means that we choose a step size such that we decrease our function as much as possible (given the information that we have, i.e. we only know its previous estimate and the direction of steepest change).
3. The justification is that given the restrictions to the problem, we cannot do better than choose the next $x^{(1)}$ as close to our real objective $min g(x)$ as possible.
4. If you notice $\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$ is of the same form as our real objective $min g(x)$. Thus, a solution to $\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$ will only aim to minimize the original objective function $g$ subject to the constraints. The really nice property of this is that if the optimal solution $x^*$ is ever in the restricted set $X^{(1)}$, the solution will be chosen. Also notice that we are choosing a new step size based on our previous estimate. So we will only choose a step size that minimizes our current guess....why? Because thats how we set up the problem, look:

$$\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

Choose a step size only if it improves our current solution, is a way of re-phrasing. So its key that in this second optimization problem that we choose the same objective function to optimize over $x^{(1)}$. If we choose some other $g'$ we would have:

$$\min_{\alpha \in R } g'(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

which doesn't necessarily improve our real objective of minimizing $g$.

1. Yes, you need to choose a new step size and solve the optimization problem at each step of the algorithm.

I never quite explicitly said this but:

$$X^{(1)} = \{ x^{(1)} \in R^n \mid x^{(0)} - \alpha \nabla g(x^{(0)}), \alpha \in R \}$$

so we are only considering points in the hyperplane described by the vector $\nabla g(x^{(0)})$ and the point to "reach" the plane $x^{(0)}$.

I don't think all questions are phrased entirely correct:

1. The textbook does not state, that the choice for $\alpha$ is optimal, they only find it appropriate. It is optimal for the first step, because it minimizes $g(x^{(1)})$ by design, but there is no reason why it should be optimal in the subsequent steps. In fact, you can find an example with a diverging gradient descent having $\alpha$ set according to Burden and Fairs.
2. An optimal $\alpha$ would be one that guarantees conversion with the minimum number of steps.
3. According to the definition of $h(\alpha)$, we know that $$\min_{\alpha}h(\alpha) = \min_{x\in X^{(1)}}g(x),$$ $$X^{(1)} = \{ g(x^{(0)}) - \alpha \nabla g(x^{(0)})\}$$ Note, that $X^{(1)}$ is the set of all the possible values for $x^{(1)}$. Therefore, if we find an $\alpha$ that minimizes $h(\alpha)$, we have also found an $x \in X^{(1)}$, that minimizes $g(x)$ using that $\alpha$, i.e. our $\alpha$ is the best choice for finding $x^{(1)}$ as defined by gradient descent.
4. This choice of $\alpha$ guarantees that the first iteration gives us the best possible solution.
5. No, this would be completely impractical. It is even impractical to choose an $\alpha$ by really minimizing $h(\alpha)$ in the first place. It just expresses a simple idea: Let's take an $\alpha$ that minimizes our target function optimal in the first step. But this leads to another minimization problem. So, for one-dimensional $g(x)$ for example, knowing an optimal $\alpha$ is about as good as knowing an $x$ that minimizes $g(x)$.