Can one formulate a optimization problem to choose a good step size for gradient descent?

Question

My main goal is to understand how to choose a good step size for gradient descent.

I was trying to understand how to choose a good step size for gradient descent. For this I came across the following (which I will change the notation from the original):

If you want a completely automatic and optimal method, you can just take a derivative with respect to the learning rate, and solve for when it becomes 0. Namely, you want to have some update $w_{t+1}=w_t−\eta ∇L(w_t)$ for your cost/loss function $L$. So what you can do is take $R( \eta)=L(w_t−\eta ∇L(w_t))$ and find the optimal $\eta$ by setting $\frac{ \partial R }{ \partial \eta} = 0$ and solving for $\eta$. If solving is too hard, a line search could do as well.

However, I didn't understand conceptually what the optimization problem $R(\eta)$ is trying to achieve. I understand that one can define such an objective function and optimize it, however, it didn't make sense to me why that optimization problem should yield a good step size to choose for gradient descent.

Can someone explain to me intuitively what optimizing for $R$ is trying to do?

In a summary I'd like to address:

1. Why does $R( \eta)=L(w_t−\eta ∇L(w_t))$ make sense?
2. How does one choose the loss function for the second optimization problem. Why does it have to be the same loss function as the one used in the original problem?

---

To see if I understood this, I tried this on a simple example. The example I will try is Kernel function with the squared loss function. Thus:

$$L(y_n,f(x_n)) = (y_n - f(x_n))^2$$

and

$$ f(x_n) = \sum^{N}_{i=1} c_i K(x_n, x_i) = \langle K_{x_n} , c \rangle = K_{x_n}^Tc$$

However, with these definitions of Loss and function, it didn't quite make sense to simply substitute $w_t−\eta ∇L(w_t)$ into $L$. I guess one could re-write $L$ to be only a function of $c$ as follows:

$$L(c) = (y_n - \langle K_{x_n} , c \rangle)^2$$

then:

$$ L(c) = L(w_t−\eta ∇L(w_t)) = (y_n - \langle K_{x_n} , w_t−\eta ∇L(w_t) \rangle)^2 $$

However, this formulation seemed a bit strange and wasn't sure if it was correct.

Answer 1

The book that I learned gradient descent from (Numerical Analysis by Burden and Faires) describes this as the method for finding the learning rate, so it seems odd to me when people describe other ways of finding a learning rate, such as keeping it constant.

Anyways, the idea is that you are taking a step in the direction of the derivative, i.e.

$w_{t+1} = w_{t} + \alpha ∇L(w_t)$

The question is how to chose the scalar value $\alpha$. Well, the point is that we can just see the choice of $\alpha$ as an optimization problem and chose the value of $\alpha$ that maximizes (or at least increase) $L(w_t + \alpha ∇L(w_t)$).

Note that if $w_{t+1} = w_{t} + \alpha ∇L(w_t)$, and $\alpha$ is the value that maximizes $L(w_t + \alpha ∇L(w_t))$, then clearly $L(w_{t+1}) \geq L(w_t)$.

I think what may seem circular is that it seems really backwards to say "the way we figure out how to do this step of the optimization problem is to see it as another optimization problem". But the key is that we see it as a much simpler optimization problem. It is generally much easier to optimize a scalar problem (i.e. find optimal choice of $\alpha$) than to optimize the multivariate problem (i.e. find optimal choice of $w_{t+1}$, where $w$ is high dimensional). As they state, worst come to worst, you can use a simple line search to find an optimal value of $\alpha$, which is clearly less computationally intense than a high dimensional grid search to find an optimal value of $w$.

Answer 2

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 address the following points:

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?

My Response:

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

5. 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)}$.

Answer 3

A no-nonsense answer that works is:

Try setting it to something big, like 1. If the optimization works, celebrate, else try for instance 0.5. Again, if it works, great, else try 0.25 and so on. In practice you get faster convergence with bigger values of $\eta$, when they work. If they are too big, the optimization diverges, so you need to try a smaller one. Monitor the target function value and see if it drops steadily (minimization). All the nice theory comes down to something simple like this in the end.