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!