Line-search does not guarantee convergence so how to use it?

Question

Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by performing line-search and finding the appropiate $\gamma$.

This search depends on a 'sufficient descent' criterion.

It can happen that the sufficient descent criterion simply is not going to be satisfied for any reasonable $\gamma$. That is, you are at a part in your search for the optimal point where no matter how small a step-size you take, you are not getting sufficient descent.

Here, line-search would get stuck in an infinite loop (or, a near-infinite loop: the sufficient descent criterion might be satisfied eventually due to numerical errors)

So, how should this be fixed? One option is to omit line-search completely: fixing $\gamma$ to be a constant, you will eventually converge if $\gamma$ is small enough.

A second option is to do line-search for an optimal $\gamma$, but only for a small amount of time (say, 20 iterations). If you haven't found a optimal $\gamma$ by then, then just take any fixed step and hope you get back towards convergence.

What do people do?

Answer 1

First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia article 'Backtracking line search'). This essentially rules out the infinite loop issue.

For example, consider Armijo condition as "the sufficient descent criterion", which is $$ f(\bar{x}+\tau d) \leq f(\bar{x})+\gamma \tau\langle\nabla f(\bar{x}), d\rangle $$ for $\gamma \in (0,1)$ and where $d$ satisfies $\langle\nabla f(\bar{x}), d\rangle < 0$.

If the function is twice differentiable, we can consider its Taylor expansion around the current iterate $x_k$ and show that as $\tau \to 0$, the Armijo condition is satisfied. However the step size could be arbitrarily small, when we consider the backtracking algorithm. To prevent this, we impose additional constraints on the step size, that prevent $\tau$ from being too small, while preserving the guarantee that such a step size still exists. For further details, you can check the Wikipedia article above.

Answer 2

I'm not sure what 'sufficient descent' criterion you have in mind, but you can use gradient descent + line-search even if it doesn't make sufficient progress -- it just might not work very well. Yes, in the worst case, if you have a sufficiently nasty objective function, gradient descent can get stuck in an area where it makes very slow progress; that absolutely can happen. I'm not sure what more there is to say. Gradient descent is a heuristic. There is no claim that it works well on all objective functions.

How should this be fixed? What do people do? That's too broad to answer in general. What to do about it will depend on your specific situation and your particular objective function. If you have an objective function where gradient descent doesn't work well, maybe don't use gradient descent: maybe consider using another optimization method.

I realize this might not be very helpful, but I'm not sure how to be more helpful without looking at a more specific situation.