# 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.

Source: https://www.mlfoundry.in/learn/l-bfgs  
Section: Deep Learning › Optimization Algorithms  
Level: advanced · 13 min read · updated 2026-10-11

**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 $m$ steps, and moves along $d=-H_kg$. It stores only $m$ pairs of vectors, so memory and time per step are $O(md)$ instead of Newton's $O(d^2)$ and $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 $s$ changed the gradient by $y$, then along $s$ the curvature is about $y/s$. BFGS accumulates these measurements into a matrix $H_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:

$$
s_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
$$

- $s_k$: the step actually taken
- $y_k$: the change in gradient it caused. On a quadratic with Hessian $A$, $y_k=As_k$ exactly
- $H_{k+1}$: the new inverse-Hessian estimate. The secant condition demands it map $y_k$ back to $s_k$, as $A^{-1}$ would

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

$$
H_{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}
$$

- $y_k^\top s_k>0$: the **curvature condition**. When it holds, $H_{k+1}$ stays positive definite, so $d=-H_{k+1}g$ is always a descent direction
- $\rho_k s_k s_k^\top$: the term that enforces $H_{k+1}y_k=s_k$

Full BFGS stores the dense $d\times d$ matrix. **L-BFGS** never forms it. It starts each step from a scaled identity $H^0_k=\gamma_kI$ with $\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 $m$ updates implicitly with the **two-loop recursion**.

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

1. $q\leftarrow-g$.
2. For $i=k-1$ down to $k-m$ (newest first): $\alpha_i\leftarrow\rho_i\,s_i^\top q$, then $q\leftarrow q-\alpha_i\,y_i$.
3. $r\leftarrow\gamma_k\,q$ (the initial guess $H^0_k=\gamma_kI$).
4. For $i=k-m$ up to $k-1$ (oldest first): $\beta\leftarrow\rho_i\,y_i^\top r$, then $r\leftarrow r+(\alpha_i-\beta)\,s_i$.
5. Return $d=r$. Cost: $4md$ multiply-adds and $2md$ stored numbers. If $y^\top s$ is not positive for a new pair, skip that pair (PyTorch skips when $y^\top s\le10^{-10}$), which keeps $H_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 $t$ satisfying the **strong Wolfe conditions** (Wolfe, 1969):

$$
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|
$$

- $c_1=10^{-4}$: sufficient decrease (Armijo): the loss must fall at least a little in proportion to the step
- $c_2=0.9$: curvature condition: the slope along d must have flattened. This rules out tiny steps and guarantees yᵀs > 0
- $g^\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 $d$ has risen from $g^\top d<0$ to at least $c_2g^\top d$, then $y^\top s>0$ and the new pair can be used. Once $H_k$ has the curvature roughly right, the unit step $t=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.

> Figure: 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=\tfrac12(x^2+25y^2)$ from the optimizer overview, Hessian $A=\operatorname{diag}(1,25)$, starting at $\theta_0=(-4,\,1.6)$ with $g_0=(-4,\,40)$. Take one gradient step with $\eta=0.05$ to collect a curvature pair, then compute the L-BFGS direction with $m=1$.

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

## The history size m

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

model = torch.nn.Sequential(torch.nn.Linear(1, 64), torch.nn.Tanh(), torch.nn.Linear(64, 1))
x = torch.linspace(-3, 3, 200).unsqueeze(1)
y = torch.sin(2 * x)                                   # small, smooth, full-batch problem

opt = torch.optim.LBFGS(
    model.parameters(),
    lr=1,                          # step length tried first; keep 1 with a line search
    max_iter=20,                   # inner L-BFGS iterations per opt.step()
    history_size=10,               # m; default 100
    tolerance_grad=1e-7, tolerance_change=1e-9,
    line_search_fn="strong_wolfe", # default None = fixed step lr: no safeguard
)

def closure():
    opt.zero_grad()                # the closure is called many times per step:
    loss = torch.nn.functional.mse_loss(model(x), y)
    loss.backward()                # it must recompute loss AND gradients each time
    return loss

for epoch in range(50):
    loss = opt.step(closure)       # returns the loss from the first closure call
print(loss.item())

# Typical PINN / fine-tuning recipe: Adam first (robust far from the optimum),
# 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

> **Do not feed it mini-batches:** L-BFGS assumes the function is the same every time it is evaluated. With a fresh mini-batch inside the closure, $y_k=g_{k+1}-g_k$ mixes curvature with sampling noise, $y^\top s$ can turn negative (pairs get dropped), and the line search compares losses from different batches. Use the full batch, or the same large batch for a whole `step()`. Stochastic quasi-Newton variants exist, but in deep learning they have not displaced Adam. Also note PyTorch's restrictions: one parameter group only, all parameters on one device, and dropout or other randomness in the closure should be off.

> **Where L-BFGS shines:** Problems that are smooth, deterministic and not too large. **Neural style transfer**: Gatys, Ecker and Bethge (2016) optimized the image pixels with L-BFGS. **Physics-informed neural networks**: Raissi, Perdikaris and Karniadakis (2019) trained with L-BFGS, and Adam-then-L-BFGS is a common PINN recipe. Also classical ML: scikit-learn's `LogisticRegression` uses the `lbfgs` solver by default. And fitting small models, calibration parameters (e.g. a temperature) or adversarial inputs, where a few dozen closure calls reach machine precision.

> **Counting cost honestly:** Compare optimizers by function and gradient evaluations, not iterations: one L-BFGS iteration with a line search can call the closure several times. In the figure's Rosenbrock run the 35 iterations cost 44 closure calls; the initial evaluation plus 2 line-search trials went into the first iteration alone, because its trial step $\min(1,1/\|g\|_1)=0.0033$ is a guess made before any curvature is known (the search settled on 0.0008).

Optimizer state per parameter, for d parameters

| method | extra memory | work per step | curvature used |
| --- | --- | --- | --- |
| SGD + momentum | $d$ | $O(d)$ | none |
| Adam | $2d$ | $O(d)$ | diagonal scale from squared gradients |
| L-BFGS | $2md$ (+ line-search copies) | $O(md)$ plus several evaluations | rank-$2m$ correction of $\gamma I$ |
| BFGS | $d^2$ | $O(d^2)$ | dense inverse-Hessian estimate |
| Newton | $d^2$ | $O(d^3)$ | exact Hessian |

**Strengths**

- Superlinear convergence on smooth problems with only gradients
- $O(md)$ memory and time: feasible for millions of parameters
- $H_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

**Limitations**

- 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

**Question:** After a step, an L-BFGS implementation finds yᵀs = −0.3 for the new pair. What should it do?

- A. Use the pair anyway; BFGS corrects itself later
- B. Skip the pair, so the inverse-Hessian estimate stays positive definite
- C. Flip the sign of y
- D. Reset the learning rate to 1

**Answer:** B. Skip the pair, so the inverse-Hessian estimate stays positive definite — The BFGS update keeps $H_k$ positive definite only if $y^\top s>0$. A negative value (negative curvature along the step, or noise) would make $H_k$ indefinite and the next direction possibly uphill. PyTorch skips pairs with $y^\top s\le10^{-10}$; a strong-Wolfe line search makes positive values automatic on smooth functions.

**Question:** Why does torch.optim.LBFGS take a closure while torch.optim.Adam does not need one?

- A. LBFGS must re-evaluate the loss and gradient at trial points during its line search and inner iterations
- B. LBFGS cannot read p.grad
- C. The closure saves memory
- D. Closures are required for second-order derivatives

**Answer:** A. LBFGS must re-evaluate the loss and gradient at trial points during its line search and inner iterations — One `opt.step(closure)` runs up to `max_iter` L-BFGS iterations, and the strong-Wolfe search may try several step lengths per iteration. Each trial needs a fresh loss and gradient, so the optimizer calls your closure as often as it needs.

**Key points**

- Quasi-Newton: learn curvature from gradient changes, enforcing the secant condition $H_{k+1}y_k=s_k$.
- L-BFGS keeps the last $m$ pairs and computes $-H_kg$ with the two-loop recursion in $O(md)$, starting from $\gamma I$, $\gamma=s^\top y/y^\top y$.
- The curvature condition $y^\top s>0$ keeps $H_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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
