1
$\begingroup$

I'm trying to implement L-BFGS but I can't quite figure out how to do step sizes. I tried small fixed step sizes, but for some reason the iterates always explode whenever memory < variable size (which is kind of the whole point). So I thought I'd try some back tracking line search.

My issue is, I don't want to re-evaluate the function or gradient, because those are the most expensive steps. I have all the current iterates $g$ gradient, $s=x-x_{prev}$, $y=g-g_{pref}$, $H^{-1} y$, $H^{-1} g$ etc available, and I can do operations of order of the variable size.

Are there any line search methods that can be used especially for this purpose, that basically don't require recomputing any function, gradient, or hessian for the intermediate points?

Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm far from expert on L-BFGS, but my impression is that normally it is implemented with a line search and the line search involves evaluating the function at different points along a line. (But no recomputation of any gradient or hessian.) $\endgroup$ – D.W.♦ Mar 26 '17 at 22:31
  • $\begingroup$ Yes that's my impression too. Unfortunately for my application, evaluating the function and gradient are the pain points to begin with (requires constantly gathering data from distributed sources) so I was hoping there was any alternative. I would think in deep learning applications, this would be an issue but I can't seem to find much literature on the subject. Thank you for your answer! $\endgroup$ – Y. S. Mar 27 '17 at 16:31
  • $\begingroup$ In that situation, L-BFGS might not be the best algorithm. For instance, maybe an algorithm that does more computation and fewer evaluations of the function might be more effective; L-BFGS isn't really tuned for that point in the tradeoff space. Perhaps you might consider asking a separate question that describes your particular situation. As for deep learning, in deep learning, evaluating the function and the gradient aren't hard; and deep learning doesn't use L-BFGS. $\endgroup$ – D.W.♦ Mar 27 '17 at 16:53
  • $\begingroup$ So, the problem is actually to investigate L-BFGS in distributed deep learning. I think computing the function and gradient is unavoidable for each choice of step size, and will be annoying. (Though as I am typing this I realize if we use MSE, this might be avoidable with clever linear algebra since the search direction does not change... it certainly won't generalize though.) But your point is well taken that this might simply be a key weakness of L-BFGS. $\endgroup$ – Y. S. Mar 27 '17 at 17:02

Your Answer

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

Browse other questions tagged or ask your own question.