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

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?

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.