When does L-BFGS outperform GD?

Question

In practice, L-BFGS is frequently held comparably to other inexact QN methods, and it provides a middle ground of sorts between Hestenes–Stiefel CG and BFGS as memory goes from zero to infinity (Numerical Optimization Ch. 7). Lots of empirical results show L-BFGS outperforms GD, at least in certain large classes of settings, like very strongly convex and smooth functions.

Liu and Nocedal 1989 prove that the L-BFGS descent direction angle with the gradient at the $k$-th iterate, $\theta_k$, satisfies the lower bound $\cos^2\theta_k\ge \delta>0$ eventually, which under moderate smoothness ensures GD-like convergence properties: since the descent agrees with GD enough, under line search satisfying Wolfe conditions, we get global eventual convergence and for smooth and strongly convex functions we achieve linear convergence.

However, the $\cos^2\theta_k\ge \delta$ result, the local and global convergence properties come from general theorems about any descent method with Wolfe conditions met. There's nothing special about L-BFGS. In fact, the inequalities used for the $\cos^2\theta_k\ge \delta$ result seem to get weaker as memory increases.

The linear local rate with worse constants is counter-intuitive and feels like a gap between theory and practice.

Are any theoretical results known where L-BFGS improves on GD's linear rate (or even its smoothness constants) in sufficiently regular settings, ideally in a way monotonically improving with memory use?

Answer 1

(Not exactly an answer to my question, but some empirical experiments which might give guidance to what a worst-case analysis of the L-BFGS iteration of a quadratic function should result in). I tested directly translated algorithm pseudocode implementations of GD and L-BFGS. See the code and all my experiments here. Even in the nicest setting you can think of, a quadratic function with moderate condition number, L-BFGS exhibits no superlinearity. Generally speaking, it seems like L-BFGS behaves basically like a better-conditioned version of GD.

Here are some rapid-fire takeaways:

• L-BFGS convergence order looks linear regardless of memory
• L-BFGS, unsurprisingly, dominates GD in well-conditioned quadratic settings, owing to a much better linear rate.
• Interestingly, in my vanilla implementation, high-memory L-BFGS is unstable.
• Increases in memory seems to linearly improve the effective linear rate.
• The condition number exhibits the same $(1-\kappa^{-1})$-like behavior for the linear convergence rate for both L-BFGS and GD.

Edit to answer Brian's question from the comments: With very high $\kappa=10^5$, scipy's inexact Wolfe line search fails to terminate for both GD and L-BFGS ($m=5$). Switching to Armijo I got noisy descents, so I resampled several different least squares problems with the same log-spaced singular values and geometrically averaged the resulting descent curves. The same pattern holds (eventually linear, L-BFGS dominates), but with much worse rates for everyone.