How does L-BFGS make Newton-style optimization affordable for a 10,000-parameter model?

## Why the exact step is unaffordable For a model with d = 10,000 parameters, the Hessian is a 10,000-by-10,000 symmetric matrix. That is 10^8 entries — roughly 800 MB in double precision — and you would need to build it fresh at every iteration. Solving the linear system for the Newton step costs on the order of d^3, about 10^12 arithmetic operations. Even where the memory fits, the per-iteration cost is out of proportion to what the step buys. Anything past a few thousand parameters therefore needs an approximation. ## The quasi-Newton idea Quasi-Newton methods refuse to compute second derivatives at all. Instead they infer curvature from the gradients they have already paid for. Between two consecutive iterates define ``` s = x_new - x_old (the step taken) y = g_new - g_old (the change in gradient) ``` For a quadratic these satisfy `y = H s` exactly, and in general they satisfy it approximately over the region traversed. The **secant condition** demands that the maintained approximation `B` of the inverse Hessian reproduce this: `B y = s`. That is one matrix equation with far fewer constraints than unknowns, so a specific update rule is chosen to fill the gap. BFGS picks the update that satisfies the secant condition, stays symmetric, and changes the previous approximation as little as possible in a particular matrix norm — and, crucially, preserves positive definiteness as long as `s^T y > 0`, a curvature condition that a line search satisfying the Wolfe conditions enforces. Positive definiteness matters because it is what keeps every step a descent direction. ## What limited memory changes Plain BFGS carries the dense approximation explicitly. For d = 10,000 that is the same 10^8 entries the Hessian had, so the memory problem is not solved — only the second derivatives are avoided. L-BFGS makes the decisive move: never materialise the matrix. Observe that the only thing the algorithm ever needs is the **product** of the inverse-Hessian approximation with the current gradient. That product can be computed directly from a list of stored `(s, y)` pairs by a two-pass recursion — one backward sweep accumulating scalar coefficients, a scaling in the middle, one forward sweep correcting them. Keeping only the m most recent pairs and discarding the rest gives: - **Memory:** on the order of `m * d` numbers. With m = 10 and d = 10,000 that is 200,000 doubles, a couple of megabytes, versus hundreds of megabytes for the dense form. - **Per-iteration cost:** on the order of `m * d` arithmetic — a few dozen vector dot products and scalings — plus whatever the gradient evaluation itself costs. ## Choosing m m is the one real knob. Small m (say 3) keeps almost no curvature history and the method behaves closer to a scaled first-order step; convergence needs more iterations. Large m (say 50 or 100) captures more curvature directions but multiplies memory and per-step work, and has a subtler cost: old pairs describe curvature at points the optimizer has since left, and on a strongly non-quadratic surface stale pairs can actively mislead the step. The conventional range of roughly 5 to 20 reflects that the benefit saturates quickly. Implementations also discard any pair violating the curvature condition `s^T y > 0`, since accepting it would destroy positive definiteness. ## Operating conditions Two practical caveats decide whether L-BFGS is the right choice. **Gradient quality.** The stored pairs are *differences* of gradients. If gradients are noisy — for instance evaluated on a different random subset of data each iteration — the differences are dominated by noise rather than curvature, and the approximation degrades or becomes actively harmful. L-BFGS is at its best with deterministic or very-low-noise gradients, which is why it is a natural fit for full-data convex fits and smooth scientific objectives. **Line search.** The theory relies on step lengths that satisfy sufficient-decrease and curvature conditions. An implementation that takes fixed-length steps loses the positive-definiteness guarantee and can produce garbage curvature pairs. ## The short interview answer Name the cost that makes exact Newton impossible at d = 10,000, explain that quasi-Newton reads curvature off successive gradients rather than computing it, and then make the limited-memory point precisely: the matrix is never formed, only its action on the gradient, reconstructed from m stored pairs. Finish with the m tradeoff and the sensitivity to gradient noise, and you have covered what the question is actually probing.