1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.