Definition
L-BFGS (limited-memory Broyden–Fletcher–Goldfarb–Shanno) is a quasi-Newton optimizer. Instead of computing the Hessian, it estimates the inverse Hessian from how the gradient changed over the last steps, and moves along . It stores only pairs of vectors, so memory and time per step are instead of Newton's and .
Newton's method converges in a handful of steps, but it needs the Hessian. Gradient descent needs only gradients, but it crawls on ill-conditioned problems. Quasi-Newton methods sit in between. Every step you take tells you something about curvature for free: if a step changed the gradient by , then along the curvature is about . BFGS accumulates these measurements into a matrix , and L-BFGS keeps only the most recent ones.
Quasi-Newton methods started with Davidon (1959), refined by Fletcher and Powell (1963) into the DFP method. The BFGS update was published independently in 1970 by Broyden, Fletcher, Goldfarb and Shanno, and is still the most robust quasi-Newton formula. Nocedal (1980) showed how to apply it with limited storage, and Liu and Nocedal (1989) established L-BFGS as the method of choice for large smooth problems. PyTorch's torch.optim.LBFGS is, in its own words, heavily inspired by Mark Schmidt's MATLAB package minFunc.
The secant condition and the BFGS update
After a step, record the parameter change and the gradient change:
- the step actually taken
- the change in gradient it caused. On a quadratic with Hessian , exactly
- the new inverse-Hessian estimate. The secant condition demands it map back to , as would
The secant condition gives equations for a symmetric matrix with unknowns, so many updates satisfy it. BFGS picks the one closest to the previous (in a weighted norm), which gives a rank-two correction:
- the curvature condition. When it holds, stays positive definite, so is always a descent direction
- the term that enforces
Full BFGS stores the dense matrix. L-BFGS never forms it. It starts each step from a scaled identity with (an estimate of the inverse curvature along the latest step) and applies the last updates implicitly with the two-loop recursion.
Two-loop recursion: compute d = −H_k g from the m stored pairs
- 1.
- 2For down to (newest first): , then .
- 3 (the initial guess ).
- 4For up to (oldest first): , then .
- 5Return . Cost: multiply-adds and stored numbers. If is not positive for a new pair, skip that pair (PyTorch skips when ), which keeps positive definite.
The line search: strong Wolfe
L-BFGS computes a direction; a line search picks how far to go along it. The standard choice is a step satisfying the strong Wolfe conditions (Wolfe, 1969):
- sufficient decrease (Armijo): the loss must fall at least a little in proportion to the step
- curvature condition: the slope along d must have flattened. This rules out tiny steps and guarantees yᵀs > 0
- d is a descent direction, which positive-definite H_k guarantees
The second condition is what makes the line search and the update work together: if the slope along has risen from to at least , then and the new pair can be used. Once has the curvature roughly right, the unit step satisfies both conditions and the search costs a single evaluation. Without a line search, nothing stops an overshooting step or a pair that has to be discarded.
Worked example: one secant pair
Take the valley from the optimizer overview, Hessian , starting at with . Take one gradient step with to collect a curvature pair, then compute the L-BFGS direction with .
- 1Step: , , falls from 40 to 9.22. So and , which is exactly .
- 2, so the pair is kept: . , so , close to : the step was mostly along the steep axis, so the scale is the steep curvature's inverse.
- 3First loop: , , .
- 4Scale: . Second loop: , .
- 5Check the secant condition: applying the same to returns exactly. Compare with Newton, : the steep -component is already almost right (0.385 vs 0.4), the flat -component is still only times the gradient. A second pair along would fix it; on a -dimensional quadratic with exact line searches, BFGS recovers after steps.
The history size m
Each pair contributes one curvature measurement along one direction. With pairs, is the scaled identity corrected in an -dimensional subspace, so larger captures more of the spectrum at extra memory. Typical values are 3 to 20; returns diminish quickly, as the figure's sweep shows (178 → 124 iterations from to 10, then only 116 at 20). PyTorch's default is history_size=100, and the documentation warns that the optimizer needs param_bytes * (history_size + 1) bytes of extra memory.
1import torch23model = torch.nn.Sequential(torch.nn.Linear(1, 64), torch.nn.Tanh(), torch.nn.Linear(64, 1))4x = torch.linspace(-3, 3, 200).unsqueeze(1)5y = torch.sin(2 * x) # small, smooth, full-batch problem67opt = torch.optim.LBFGS(8 model.parameters(),9 lr=1, # step length tried first; keep 1 with a line search10 max_iter=20, # inner L-BFGS iterations per opt.step()11 history_size=10, # m; default 10012 tolerance_grad=1e-7, tolerance_change=1e-9,13 line_search_fn="strong_wolfe", # default None = fixed step lr: no safeguard14)1516def closure():17 opt.zero_grad() # the closure is called many times per step:18 loss = torch.nn.functional.mse_loss(model(x), y)19 loss.backward() # it must recompute loss AND gradients each time20 return loss2122for epoch in range(50):23 loss = opt.step(closure) # returns the loss from the first closure call24print(loss.item())2526# Typical PINN / fine-tuning recipe: Adam first (robust far from the optimum),27# then switch to L-BFGS for the last digits on the full batch.| method | extra memory | work per step | curvature used |
|---|---|---|---|
| SGD + momentum | none | ||
| Adam | diagonal scale from squared gradients | ||
| L-BFGS | (+ line-search copies) | plus several evaluations | rank- correction of |
| BFGS | dense inverse-Hessian estimate | ||
| Newton | exact Hessian |
Use when
- +Superlinear convergence on smooth problems with only gradients
- + memory and time: feasible for millions of parameters
- + stays positive definite (curvature condition), so every direction descends, even where the true Hessian is indefinite
- +With strong Wolfe, the unit step is usually accepted and almost no tuning is needed
Avoid when
- −Breaks down with mini-batch noise: needs full-batch or fixed-batch evaluation
- −Several closure calls per step; memory grows with m
- −No per-parameter options in PyTorch; one parameter group, one device
- −Can stall at saddles or in non-smooth regions (ReLU kinks, max-pooling) where curvature pairs are unreliable
Check yourself
After a step, an L-BFGS implementation finds yᵀs = −0.3 for the new pair. What should it do?
Check yourself
Why does torch.optim.LBFGS take a closure while torch.optim.Adam does not need one?
Remember
- ✓Quasi-Newton: learn curvature from gradient changes, enforcing the secant condition .
- ✓L-BFGS keeps the last pairs and computes with the two-loop recursion in , starting from , .
- ✓The curvature condition keeps positive definite; a strong-Wolfe line search guarantees it on smooth functions.
- ✓In PyTorch:
LBFGS(params, line_search_fn="strong_wolfe")andopt.step(closure), where the closure zeroes grads, computes the loss and calls backward. - ✓Use it for smooth, full-batch problems (style transfer, PINNs, small models, logistic regression), not for noisy mini-batch training.