L-BFGS

A quasi-Newton method: it learns curvature from the last m gradient differences and applies an approximate inverse Hessian in O(md) time via the two-loop recursion. With a strong-Wolfe line search it excels on smooth, full-batch problems, but mini-batch noise breaks it.

13 min read1019 wordsadvanced0 viewsupdated 2026-10-11

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 mm steps, and moves along d=−Hkgd=-H_kg. It stores only mm pairs of vectors, so memory and time per step are O(md)O(md) instead of Newton's O(d2)O(d^2) and O(d3)O(d^3).

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 ss changed the gradient by yy, then along ss the curvature is about y/sy/s. BFGS accumulates these measurements into a matrix Hk≈∇2L−1H_k\approx\nabla^2L^{-1}, 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:

sk=θk+1−θk,yk=gk+1−gk,secant condition: Hk+1 yk=sks_k=\theta_{k+1}-\theta_k,\qquad y_k=g_{k+1}-g_k,\qquad\text{secant condition: } H_{k+1}\,y_k=s_k
sks_k
the step actually taken
yky_k
the change in gradient it caused. On a quadratic with Hessian AA, yk=Asky_k=As_k exactly
Hk+1H_{k+1}
the new inverse-Hessian estimate. The secant condition demands it map yky_k back to sks_k, as A−1A^{-1} would

The secant condition gives dd equations for a symmetric matrix with d(d+1)/2d(d+1)/2 unknowns, so many updates satisfy it. BFGS picks the one closest to the previous HkH_k (in a weighted norm), which gives a rank-two correction:

Hk+1=(I−ρkskyk⊤) Hk (I−ρkyksk⊤)+ρksksk⊤,ρk=1yk⊤skH_{k+1}=\big(I-\rho_k s_k y_k^\top\big)\,H_k\,\big(I-\rho_k y_k s_k^\top\big)+\rho_k s_k s_k^\top,\qquad \rho_k=\frac{1}{y_k^\top s_k}
yk⊤sk>0y_k^\top s_k>0
the curvature condition. When it holds, Hk+1H_{k+1} stays positive definite, so d=−Hk+1gd=-H_{k+1}g is always a descent direction
ρksksk⊤\rho_k s_k s_k^\top
the term that enforces Hk+1yk=skH_{k+1}y_k=s_k

Full BFGS stores the dense d×dd\times d matrix. L-BFGS never forms it. It starts each step from a scaled identity Hk0=γkIH^0_k=\gamma_kI with γk=sk−1⊤yk−1yk−1⊤yk−1\gamma_k=\frac{s_{k-1}^\top y_{k-1}}{y_{k-1}^\top y_{k-1}} (an estimate of the inverse curvature along the latest step) and applies the last mm updates implicitly with the two-loop recursion.

Two-loop recursion: compute d = −H_k g from the m stored pairs

  1. 1q←−gq\leftarrow-g.
  2. 2For i=k−1i=k-1 down to k−mk-m (newest first): αi←ρi si⊤q\alpha_i\leftarrow\rho_i\,s_i^\top q, then q←q−αi yiq\leftarrow q-\alpha_i\,y_i.
  3. 3r←γk qr\leftarrow\gamma_k\,q (the initial guess Hk0=γkIH^0_k=\gamma_kI).
  4. 4For i=k−mi=k-m up to k−1k-1 (oldest first): β←ρi yi⊤r\beta\leftarrow\rho_i\,y_i^\top r, then r←r+(αi−β) sir\leftarrow r+(\alpha_i-\beta)\,s_i.
  5. 5Return d=rd=r. Cost: 4md4md multiply-adds and 2md2md stored numbers. If y⊤sy^\top s is not positive for a new pair, skip that pair (PyTorch skips when y⊤s≤10−10y^\top s\le10^{-10}), which keeps HkH_k 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 tt satisfying the strong Wolfe conditions (Wolfe, 1969):

L(θ+td)≤L(θ)+c1 t g⊤dand∣∇L(θ+td)⊤d∣≤c2 ∣g⊤d∣L(\theta+t d)\le L(\theta)+c_1\,t\,g^\top d\qquad\text{and}\qquad\big|\nabla L(\theta+t d)^\top d\big|\le c_2\,\big|g^\top d\big|
c1=10−4c_1=10^{-4}
sufficient decrease (Armijo): the loss must fall at least a little in proportion to the step
c2=0.9c_2=0.9
curvature condition: the slope along d must have flattened. This rules out tiny steps and guarantees yᵀs > 0
g⊤d<0g^\top d<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 dd has risen from g⊤d<0g^\top d<0 to at least c2g⊤dc_2g^\top d, then y⊤s>0y^\top s>0 and the new pair can be used. Once HkH_k has the curvature roughly right, the unit step t=1t=1 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.

f = Rosenbrock (1−x)² + 100(y−x²)²×directions: → −g → L-BFGS −H_k g ⇢ Newton −H⁻¹g━ L-BFGS (m = 10, strong Wolfe) ━ GD lr = 0.001f (log) vs iteration1e-121e-81e-4102040100-D quadratic, κ = 1000:iters to 1e-8·f₀ vs m (GD: 3932)11020124history m
k = 0|
L-BFGS f 24.200 · closure calls 1 · pairs stored 0 · step t 0.001 · f < 1e-8 at iteration 35
GD f 24.200 after 0 steps (1 gradient calls)
cos(d, Newton) 0.437 · min eig(H) 23.633
fig.A port of torch.optim.LBFGS (same two-loop recursion, same γ scaling, same first step min(1, 1/‖g‖₁), same strong-Wolfe search with c₁ = 1e-4, c₂ = 0.9) against gradient descent. On Rosenbrock with m = 10 and strong Wolfe, L-BFGS reaches f < 1e-8 at iteration 35 after 44 closure calls, while GD at lr 0.001 is still at f = 4.0 after 40 steps. Arrows at the current iterate show −g, the L-BFGS direction and the true Newton direction; at 27 of the 35 iterates the last two nearly coincide (cosine > 0.98). At 5 iterates (1, 2, 3, 17 and 23) the true Hessian is indefinite (at iteration 17 its smallest eigenvalue is −5.07): there the Newton direction points uphill (at iteration 17 its cosine with the L-BFGS direction is −0.98), while L-BFGS, whose H_k is positive definite, still descends. Switch the line search off (fixed step lr = 1, PyTorch's default) and after 40 iterations f is still 0.64. The bars show why m matters in high dimension: on a 100-D quadratic with κ = 1000, L-BFGS needs 178 iterations with m = 1, 124 with m = 10 and 116 with m = 20; GD at its best fixed step needs 3932.

Worked example: one secant pair

Take the valley f=12(x2+25y2)f=\tfrac12(x^2+25y^2) from the optimizer overview, Hessian A=diag⁡(1,25)A=\operatorname{diag}(1,25), starting at θ0=(−4, 1.6)\theta_0=(-4,\,1.6) with g0=(−4, 40)g_0=(-4,\,40). Take one gradient step with η=0.05\eta=0.05 to collect a curvature pair, then compute the L-BFGS direction with m=1m=1.

  1. 1Step: θ1=(−3.8, −0.4)\theta_1=(-3.8,\,-0.4), g1=(−3.8, −10)g_1=(-3.8,\,-10), ff falls from 40 to 9.22. So s0=(0.2, −2)s_0=(0.2,\,-2) and y0=g1−g0=(0.2, −50)y_0=g_1-g_0=(0.2,\,-50), which is exactly As0As_0.
  2. 2y⊤s=0.04+100=100.04>0y^\top s=0.04+100=100.04>0, so the pair is kept: ρ=1/100.04=0.009996\rho=1/100.04=0.009996. y⊤y=2500.04y^\top y=2500.04, so γ=100.04/2500.04=0.0400\gamma=100.04/2500.04=0.0400, close to 1/251/25: the step was mostly along the steep axis, so the scale is the steep curvature's inverse.
  3. 3First loop: q=−g1=(3.8, 10)q=-g_1=(3.8,\,10), α=ρ s⊤q=−0.1923\alpha=\rho\,s^\top q=-0.1923, q←q−αy=(3.8385, 0.3838)q\leftarrow q-\alpha y=(3.8385,\,0.3838).
  4. 4Scale: r=γq=(0.1536, 0.01536)r=\gamma q=(0.1536,\,0.01536). Second loop: β=ρ y⊤r=−0.00737\beta=\rho\,y^\top r=-0.00737, r←r+(α−β)s=(0.1166, 0.3853)r\leftarrow r+(\alpha-\beta)s=(0.1166,\,0.3853).
  5. 5Check the secant condition: applying the same H1H_1 to y0y_0 returns (0.2, −2)=s0(0.2,\,-2)=s_0 exactly. Compare with Newton, −A−1g1=(3.8, 0.4)-A^{-1}g_1=(3.8,\,0.4): the steep yy-component is already almost right (0.385 vs 0.4), the flat xx-component is still only γ\gamma times the gradient. A second pair along xx would fix it; on a dd-dimensional quadratic with exact line searches, BFGS recovers A−1A^{-1} after dd steps.

The history size m

Each pair contributes one curvature measurement along one direction. With mm pairs, HkH_k is the scaled identity corrected in an mm-dimensional subspace, so larger mm captures more of the spectrum at 2md2md extra memory. Typical values are 3 to 20; returns diminish quickly, as the figure's sweep shows (178 → 124 iterations from m=1m=1 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.

python
1import torch
2
3model = 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 problem
6
7opt = torch.optim.LBFGS(
8 model.parameters(),
9 lr=1, # step length tried first; keep 1 with a line search
10 max_iter=20, # inner L-BFGS iterations per opt.step()
11 history_size=10, # m; default 100
12 tolerance_grad=1e-7, tolerance_change=1e-9,
13 line_search_fn="strong_wolfe", # default None = fixed step lr: no safeguard
14)
15
16def 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 time
20 return loss
21
22for epoch in range(50):
23 loss = opt.step(closure) # returns the loss from the first closure call
24print(loss.item())
25
26# 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.
torch.optim.LBFGS needs a closure, because the line search evaluates the loss several times per step
methodextra memorywork per stepcurvature used
SGD + momentumddO(d)O(d)none
Adam2d2dO(d)O(d)diagonal scale from squared gradients
L-BFGS2md2md (+ line-search copies)O(md)O(md) plus several evaluationsrank-2m2m correction of γI\gamma I
BFGSd2d^2O(d2)O(d^2)dense inverse-Hessian estimate
Newtond2d^2O(d3)O(d^3)exact Hessian
Optimizer state per parameter, for d parameters

Use when

  • +Superlinear convergence on smooth problems with only gradients
  • +O(md)O(md) memory and time: feasible for millions of parameters
  • +HkH_k 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 Hk+1yk=skH_{k+1}y_k=s_k.
  • ✓L-BFGS keeps the last mm pairs and computes −Hkg-H_kg with the two-loop recursion in O(md)O(md), starting from γI\gamma I, γ=s⊤y/y⊤y\gamma=s^\top y/y^\top y.
  • ✓The curvature condition y⊤s>0y^\top s>0 keeps HkH_k positive definite; a strong-Wolfe line search guarantees it on smooth functions.
  • ✓In PyTorch: LBFGS(params, line_search_fn="strong_wolfe") and opt.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.
← back to Deep Learning roadmap