L-BFGS: On the Limited Memory BFGS Method for Large Scale Optimization

Dong C. Liu and Jorge Nocedal (Northwestern University), Mathematical Programming 45 (1989), pp. 503–528. Read from the authors' PDF on Nocedal's Northwestern page. This is the paper that gave L-BFGS its name and its standard form, and it is the first quasi-Newton source this spoke holds. Before it, the deterministic side of the spoke was gradient-descent and nothing else.

What the method is

BFGS builds an approximation to the inverse Hessian from the gradient changes it observes. Stored as a dense matrix, that costs n² memory, which is impossible at thousands of variables. The limited-memory version keeps only the last m pairs of step and gradient-change vectors and rebuilds the product with the inverse Hessian from them on each iteration. Storage and per-iteration cost then grow with m·n, and the user picks m. The authors frame it two ways: as conjugate gradient with extra storage spent on faster convergence, or as quasi-Newton with storage capped. It needs only function and gradient values, nothing about sparsity or separability. The idea predates the paper (Perry 1977, Shanno 1978, Nocedal 1980); this paper is the large-scale comparison and the convergence proof.

What the authors measured

• L-BFGS beats the Buckley–LeNir method (cycles of BFGS steps and conjugate-direction steps) and makes better use of extra storage.
• A cheap dynamic scaling of the starting matrix speeds it up a lot. Of the four scalings tested with m = 5, the one that rescales by a scalar every iteration (M3) did best on most of the problems in their Table 11. On problem 1 at n = 1000, for example, iterations fell from 34 unscaled to 26.
• Partitioned quasi-Newton (Griewank and Toint) wins when you can feed it structure, especially when each element function depends on fewer than 4 or 5 variables. L-BFGS can be faster when the element functions depend on more than 3 or 4 variables, when the Hessian is not very sparse, or when the separability is hard to obtain.
• Against conjugate gradient, scaled L-BFGS beat CONMIN and standard CG except in one case: on large problems with cheap function evaluations, CG was competitive.
• Theory: global convergence on uniformly convex problems.

How far this reaches

The comparison is the authors' own, run on a SUN 3/60 against test problems most of which have cheap function evaluations. That is the same shape this spoke keeps recording: the method's authors pick the problems and score the method (synthesis, "the comparisons are run by the people who wrote the algorithm"). What the paper does not touch is the use L-BFGS sees most often now, as the default smooth optimizer in scientific libraries, which rests on later practice and not on this paper.

Related

gradient-descent · stochastic-gradient-descent · adam-optimizer · adamw · highs