Back to the on-screen lesson ·
Curvature estimated from successive gradients, the secant condition, and why limited memory is what scales.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute a secant estimate of curvature from two gradients, state the secant condition, and explain where a quasi-Newton method's curvature information comes from and why it costs nothing extra. You will also be able to compare gradient descent, quasi-Newton, limited-memory quasi-Newton and Newton on storage, work per iteration and convergence rate, and to choose between them for a problem by doing arithmetic about the number of variables.
Gradient descent, which uses no curvature and is slow when the problem is stretched. Newton, which uses exact curvature and pays $n^2$ storage and $n^3$ work per iteration for it. This lesson is the space between them, and it is where most real smooth optimization actually happens.
The observation the whole family rests on: two successive gradients contain curvature information. If the gradient changed by $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$ over a step $s_k = x_{k+1} - x_k$, then along that direction the curvature is about $y_k / s_k$. In several variables this is the secant condition
$$B_{k+1}\, s_k = y_k,$$
asking the approximate Hessian $B_{k+1}$ to reproduce the change that was just observed.
One step gives one direction's worth of information, and the condition does not determine $B$ on its own. BFGS — the standard choice — fills the gap by taking the update closest to the previous estimate, in a suitable sense, that satisfies the secant condition and stays positive definite. Positive definiteness is not decoration: it is what guarantees the resulting direction descends, which is the safeguard lesson 16 said pure Newton lacks.
| Curvature | Storage | Work per step | Convergence | |
|---|---|---|---|---|
| Gradient descent | none | $n$ | $n$ | linear |
| Quasi-Newton (BFGS) | estimated | $n^2$ | $n^2$ | superlinear |
| Limited memory (L-BFGS) | estimated, last $m$ steps | $2mn$ | $mn$ | superlinear in practice |
| Newton | exact | $n^2$ | $n^3$ | quadratic |
Limited memory is the version that matters at scale. Instead of storing a matrix, keep the last $m$ pairs $(s_k, y_k)$ — typically $m$ between 5 and 20 — and reconstruct the action of the approximate inverse Hessian on a vector from them. Storage becomes $2mn$ rather than $n^2$, which is the difference between possible and impossible at ten million variables.
Another way: picture
A walker in a valley who cannot survey the terrain but remembers the slope at each place they have stood. From how the slope changed between the last few, they build a picture of the valley's shape — imperfect, improving, and free, because the slopes were measured anyway.
Another way: steps
One BFGS iteration:
Take $f(x) = 3x^2$, so $f'(x) = 6x$ and the true curvature is $6$.
Step from $x = 2$ to $x = 5$. The gradients are $12$ and $30$, so $s = 3$ and $y = 18$, and the secant estimate is $y/s = 6$ — exactly right.
That exactness is special to quadratics, where the curvature is constant and any two points reveal it. On a general function the estimate is an average of the curvature over the step, which is why quasi-Newton converges superlinearly rather than quadratically: the estimate keeps improving and never quite becomes the truth.
Notice what was not done: no second derivative was computed, and no extra function evaluation was made. The gradients at both points were needed by the method anyway.
Losing positive definiteness. The BFGS update preserves it only when $s_k^\top y_k > 0$ — the curvature along the step is positive. A line search satisfying the Wolfe conditions guarantees that, which is why the two are always paired.
Starting badly. $H_0 = I$ makes the first step a gradient step. Scaling $H_0$ after the first step, by a factor read off $s$ and $y$, is a cheap and large improvement.
Using it on a noisy objective. Curvature estimated from differences of noisy gradients is noise amplified. Quasi-Newton wants smooth problems.
Storing the Hessian approximation at scale. Full BFGS is $n^2$ and has the same wall as Newton, one power lower. L-BFGS is the version that scales, and the choice between them is decided by $n$, not by taste.
Both estimate curvature from gradients, so they get conflated, and they are quite different. A finite-difference Hessian spends $n$ extra gradient evaluations per iteration, deliberately probing $n$ directions to fill in a matrix. A quasi-Newton method spends nothing extra: it uses the one step it was going to take anyway, gets one direction's worth of curvature from it, and accumulates the rest over subsequent iterations. That is why it is cheap, and also why its estimate is always somewhat stale — it is built from where the method has been rather than from where it is. The staleness is the price, and on a smooth problem it is a very good deal.
BFGS starts with $H_0 = I$: no curvature information has been gathered, so the best guess is that all directions curve alike.
An honest starting assumption.
Then $d_0 = -I \nabla f = -\nabla f$, which is exactly gradient descent's direction.
So the first step is a gradient step.
After that step, $s_0$ and $y_0$ exist and the first update runs. By a handful of iterations the approximation usually captures the dominant curvature, and the method pulls away from gradient descent sharply. The lesson: judging a quasi-Newton run by its first few iterations is judging gradient descent.
It becomes itself after a few iterations.
$n = 50$: Hessian $2{,}500$ entries, solve about $125{,}000$ operations. Newton is entirely affordable, and its quadratic convergence usually wins.
Small: use exact curvature.
$n = 10^7$: Hessian $10^{14}$ entries. It cannot be stored, let alone factored, whatever the hardware.
Large: exact curvature is not an option.
L-BFGS with $m = 10$ keeps $2 \times 10 \times 10^7 = 2 \times 10^8$ numbers — large but ordinary — and each iteration costs a small multiple of a gradient evaluation. The method is chosen by arithmetic about $n$, done before any code is written.
The choice is a calculation, not a preference.
At $x = 1$ the gradient is $4$; at $x = 4$ it is $16$. The step is $s = 3$ and the gradient change is $y = 12$.
Collect $s$ and $y$ first.
Secant estimate: $y/s = 12/3 = 4$.
And notice what is and is not claimed. If the function is $2x^2$ the curvature really is $4$ everywhere and the estimate is exact. If it is something else, $4$ is the average curvature between $x = 1$ and $x = 4$ — useful for a step of that size, and not a statement about either endpoint.
Match each optimization quantity to the information or cost it represents in a quasi-Newton method.
| Observed change in slope | The displacement against which that change is interpreted | Scales a gradient into a curvature-aware search direction | Avoids storing an $n\times n$ matrix by retaining recent pairs | |
|---|---|---|---|---|
| Gradient difference $y_k=g_{k+1}-g_k$ | ||||
| Step $s_k=x_{k+1}-x_k$ | ||||
| Approximate inverse Hessian $B_k^{-1}$ | ||||
| Limited-memory update |
Moving $2$ in $x$ changed the derivative from $19$ to $36$. What curvature does that imply?
Answer:
How many entries does the Hessian of a function of $9$ variables have?
Answer:
A quasi-Newton method never computes a second derivative. Where does its curvature estimate come from?
| First observed slope | Second observed slope | Observed change in slope | Direction along which curvature is inferred | |
|---|---|---|---|---|
| Gradient at the old point | ||||
| Gradient at the new point | ||||
| Difference of successive gradients | ||||
| Step between the points |
A limited-memory method keeps the last $3$ pairs of step and gradient-difference vectors, each of length $19$. How many numbers is that?
Answer:
A smooth convex objective has ten million variables and a gradient that is cheap to evaluate. Which method fits?
| Infeasible because matrix storage and solves are enormous | Feasible but can converge slowly on bad conditioning | Fits: modest memory and curvature-informed directions | Requires roughly $10^{14}$ entries | |
|---|---|---|---|---|
| Full Newton at ten million variables | ||||
| Plain gradient descent | ||||
| Limited-memory quasi-Newton | ||||
| Full Hessian at this scale |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
How many entries does the Hessian of a function of $11$ variables have?
Answer:
You can compute a secant curvature, say what the secant condition asks, and choose between the four methods on cost. Next: the method for problems whose constraints are the hard part.
9. Your turn: what curvature do these two gradients imply?, step 3