How to avoid"Line search failed"?

[duhd1993]

I'm trying FullBatchLBFGS with wolfe line search on a fitting task of a small dataset.

1. Levenbert-Marquardt is giving me fairly accuracy. Can I expect LBFGS provide similar accuracy as LM? Say, for a synthesized dataset, y=1/x
2. I'm getting lots of "Line search failed; curvature pair update skipped". How could I avoid this?
3. I noticed that the result is stochastic. Where does randomness come from since I'm using a full batch training (no shuffling).

Thanks!

[hjmshi]

Hi,

Thanks for trying out the implementation! To answer your questions:

1. Levenberg-Marquardt is a different optimization algorithm. If your least squares problem is non-convex (which likely is the case if the response variable is nonlinear with respect to the predictor variables), then L-BFGS may converge to a different minimizer than LM. That being said, the minimizer may not be worse than the one gotten by LM, it really depends on the problem.

2. If the line search is failing, I would first try increasing the number of trial points. To do this, within the options, set max_ls to a higher number, i.e. options = {'max_ls': 30}, for example (or potentially higher). Let me know if this helps.

3. The result will be influenced by numerical error if in-place operations are used (which require less memory). This is turned on by default; I would suggest turning it off by modifying the option 'inplace' and setting it to False.

Please let me know if this helps.

[duhd1993]

Thanks a lot for your reply! It appears fullbatch with wolfe line search works for me.

1. I'm having trouble getting comparable accuracy with Levenberg-Marquardt. The MSE is 3 magnitude smaller with LM.
   Could you give it a try if you had time:
   https://colab.research.google.com/drive/1vlzyCZKvaaZuWRQ5j8AT1pkq0pBTk18J

2. Thanks for the suggestions. It helps somehow. But Armijo line search is not working for me, it's not learning at all. I'm not sure what's wrong. All other settings is the same as Wolfe line search.

3. Thanks for pointing out. Actually, adding some randomness turns out to be a good thing for synthesized dataset without noises. When 'inplace' set to false, it converges to a local minimum pretty fast.

[hjmshi]

Glad to hear the suggestions help!

I haven't had the chance to take a closer look at your problem, but based on some of the initial settings, have you tried using an initial learning rate/steplength of 1? This is typical in (quasi-)Newton based methods.

There a few possible reasons as to why Levenberg-Marquardt may work better. If I may ask, what LM optimizer are you trying? One possibility is that LM converges to a different, potentially better minimizer. This could occur because you have a non-convex problem; note that not all local minima are equal. Another possibility is that the LM optimizer you are using operates in double precision. This L-BFGS implementation for PyTorch operates only in single precision, which may restrict the amount of accuracy you may be able to attain for your problem.

I can look into the Armijo line search. It's not clear to me why it would not work, although the Wolfe line search should be much more effective in the non-convex setting as it allows you to "move forward" to ensure the step you're taking is not too small and you're seeing sufficient change in curvature.