Limited-Memory BFGS

A quasi-Newton optimizer that stores a short history of step and gradient-difference pairs and applies the implied inverse-Hessian approximation by two-loop recursion.

Version

v2 · 2026-09-19 · History

Domain-specific #

2182

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomains

Numerical Optimization, Quasi Newton Methods → Mathematics

Aliases

L-BFGS, LBFGS, Limited memory BFGS

Core Idea

Limited-memory BFGS (L-BFGS) is a quasi-Newton method for smooth optimization that approximates the action of an inverse Hessian without storing a dense \(n\times n\) matrix. At iteration \(k\), it retains only the most recent \(m\) displacement pairs

\[ s_k=x_{k+1}-x_k,\qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k), \]

and applies the inverse-Hessian approximation to the gradient through a two-loop recursion. Storage and per-iteration linear algebra scale as \(O(mn)\), making quasi-Newton curvature practical when \(n\) is large and \(m\ll n\).^[1][2]

The method combines a limited curvature history, a positive-curvature condition such as \(s_k^Ty_k>0\), an initial scaling, a descent direction, and a line search. Its identity is not “BFGS with less RAM” in an informal sense; it is the implicit representation and recursion induced by a window of BFGS correction pairs.

How would you explain it like I'm…

Remember-a-Few-Steps Hiker

Imagine walking downhill in fog to find the lowest spot. You can't see the whole hill, so you remember your last few steps and how the slope changed. Those few memories help you guess a smarter next step, without carrying a giant map.

Short-Memory Valley Finder

Limited-Memory BFGS is a way for computers to find the lowest point of a smooth function, like the bottom of a valley. A really good method would need a giant table describing how the valley curves everywhere, which is too big when there are millions of variables. Instead, it remembers just the last few steps and how the slope changed during each one. From those few memories it figures out a smart direction to move, then checks how far to go along it.

Windowed Curvature Optimizer

Limited-Memory BFGS is an optimization method. It belongs to the 'quasi-Newton' family, which uses curvature (how the slope itself changes) to choose better steps than plain downhill moves. Full BFGS stores an n-by-n matrix estimating that curvature, which is impossible when n is huge. Limited-Memory BFGS keeps only the last m pairs of (change in position, change in gradient) and uses a clever two-loop calculation to apply the curvature estimate directly to the gradient. It is not just 'BFGS with a smaller matrix': the matrix never exists, only the recipe built from those pairs. A line search then picks the step length along the resulting downhill direction.

 

Limited-Memory BFGS (L-BFGS) is a quasi-Newton method for minimizing smooth functions. Newton's method uses the inverse Hessian to scale the gradient; BFGS builds an approximation of that inverse from observed gradient changes, but stores it as a dense n×n matrix. L-BFGS instead keeps the most recent m displacement pairs, s_k = x_{k+1} − x_k and y_k = ∇f(x_{k+1}) − ∇f(x_k). A two-loop recursion applies the implied inverse-Hessian approximation to the current gradient without ever forming the matrix. Storage and work per iteration are O(mn), practical when m is much smaller than n. Each pair should satisfy a positive-curvature condition such as s_kᵀy_k > 0 so the approximation stays positive definite. An initial scaling seeds the recursion, the result gives a descent direction, and a line search chooses the step. Its identity is this implicit representation from a window of BFGS correction pairs, not a loose memory-saving variant.

Structural Signature

Mandatory roles:

• A differentiable objective \(f:\mathbb R^n\to\mathbb R\) and current gradient.
• Iterate displacement \(s_k\) and gradient displacement \(y_k\).
• A bounded history length \(m\) that discards older pairs.
• Curvature checks protect the positive-definite inverse approximation under suitable line searches.
• An initial inverse-Hessian scale \(H_k^0\), commonly a scalar multiple of identity.
• The two-loop recursion computes \(H_k\nabla f(x_k)\) implicitly.
• A line search and update rule choose the step and produce the next pair.

Recognition test. A method qualifies when its search direction is computed from a sliding collection of BFGS curvature pairs through an algebraically equivalent limited-memory representation. Merely using recent gradients, momentum, or a diagonal preconditioner is not L-BFGS.

What It Is Not

• It is not full BFGS, which stores and updates a dense Hessian or inverse-Hessian approximation.
• It is not gradient descent; curvature pairs change scaling and coupling between coordinates.
• It is not conjugate gradient, although both may use \(O(n)\)-scale memory and related quadratic behavior.
• It is not L-BFGS-B, which adds bound handling and projected/active-set machinery around a limited-memory matrix.
• It is not guaranteed for nonsmooth objectives, noisy gradients, or arbitrary line searches without modified theory.

Scope of Application

L-BFGS is used for large, smooth, unconstrained optimization in statistical estimation, scientific computing, and machine learning. It is attractive when gradients are available, the parameter dimension makes dense BFGS storage prohibitive, and a modest history captures useful curvature. Batch logistic regression and smooth regularized likelihoods are canonical settings.

Variants place the limited-memory matrix inside constrained algorithms, stochastic regimes, or trust-region methods, but those extensions add obligations. The core does not itself enforce box constraints, sparsity, or stochastic robustness. If evaluating a gradient is extremely noisy or the objective has kinks, a different method or safeguards may be necessary.

The method is particularly useful when a full Hessian is unavailable but gradients are substantially more informative than function values alone. It may be less attractive when each iteration exposes only a tiny stochastic sample, when reliable line searches are impossible, or when a specialized sparse Newton system can be solved cheaply. These are deployment boundaries, not changes to the algorithm’s identity.

Clarity

The curvature pair explains what the method learns. Since \(y_k\approx\nabla^2 f(x_k)s_k\), the secant equation asks the approximate Hessian to map \(s_k\) toward \(y_k\). BFGS integrates successive secant information; L-BFGS remembers only a window and represents its effect implicitly.

The two-loop recursion is not two optimization loops. The first sweep walks backward through stored pairs to remove components, the initial scale is applied, and the second sweep walks forward to restore BFGS corrections. A code claiming L-BFGS but forming no \((s,y)\) pairs or applying no equivalent recursion lacks the named structure.

Manages Complexity

Dense BFGS costs \(O(n^2)\) storage and matrix-vector work. L-BFGS reduces this to a history of \(m\) vector pairs plus working vectors. The limited representation makes curvature modeling possible for millions of parameters when \(m\) is perhaps a small fixed number.

The reduction trades global memory for recency. Discarded pairs may contain useful long-range curvature, while too many pairs increase work and can preserve stale information. L-BFGS manages algebraic scale, not all optimization complexity: objective evaluation, line search, ill conditioning, and stopping criteria remain.

Implementation can store each \(s_i\) and \(y_i\) as vectors plus scalar reciprocal curvature. Circular buffers make eviction explicit. The algorithm avoids a dense matrix, but it still moves several full vectors per recursion; on bandwidth-bound hardware that traffic can dominate arithmetic. Complexity claims should therefore state both asymptotic storage and measured data movement.

Abstract Reasoning

Under a positive curvature condition, BFGS updates preserve positive definiteness, so the negative implicit inverse-Hessian product is a descent direction for a nonzero gradient. A Wolfe-type line search can help produce the needed curvature relation. The secant interpretation predicts improved scaling over steepest descent on locally quadratic objectives.^[2]

The method also yields diagnostics. If \(s^Ty\) is nonpositive or nearly zero, accepting the pair can damage scaling; an implementation may skip or damp it. If history order is reversed in one recursion loop, the result no longer equals the intended BFGS product. Directional-derivative checks distinguish a recursion defect from a line-search failure.

Scaling of \(H_k^0\) matters because limited history leaves many directions governed by that baseline. A common scalar choice estimates recent curvature, but it is not part of the objective and must remain positive. Tests should therefore vary both history length and initialization rather than attributing every failure to the line search.

Knowledge Transfer

The limited-memory principle transfers to other quasi-Newton updates and inverse problems: retain a small set of informative low-rank corrections rather than a dense operator. Curvature-pair storage can also precondition related subproblems.

Literal L-BFGS transfer requires the BFGS update algebra and two-loop-equivalent action. Calling an optimizer “L-BFGS-like” because it stores recent gradients is only analogy. The portable parents are Optimization, Approximation, and Memory–Accuracy Tradeoff.

Examples

Smooth logistic objective. Given a regularized logistic-loss function with many coefficients, compute the gradient, obtain a direction from the latest \((s_i,y_i)\) pairs, conduct a line search, and append the new pair if curvature is acceptable. No dense Hessian is formed. The retained history adapts coordinate scaling from observed changes in gradients.

Quadratic check. For \(f(x)=\tfrac12x^TAx-b^Tx\) with positive-definite \(A\), each \(y_k=As_k\). Curvature is positive for nonzero steps, and stored pairs contain exact directional Hessian actions. Comparing the two-loop result with an explicitly formed small BFGS matrix provides a unit test.

Boundary case. Applying the same code to an objective with discontinuous gradients can produce unstable \(y_k\) and repeated line-search failures. The presence of a function named lbfgs does not restore smooth quasi-Newton assumptions.

Structural Tensions

• Memory economy versus curvature retention: a short history scales well but forgets directions. Diagnostic: does increasing \(m\) materially reduce iterations without unacceptable memory cost?
• Aggressive curvature use versus positive definiteness: new pairs inform the model but can violate safeguards. Diagnostic: is \(s^Ty\) checked or damped under the selected line search?
• Cheap implicit action versus debugging opacity: no matrix is stored, so recursion errors can hide. Diagnostic: does a low-dimensional explicit BFGS comparison match the two-loop product?
• Local speed versus line-search cost: better directions may require multiple objective/gradient evaluations. Diagnostic: is total evaluation count improving, not merely iteration count?
• General optimizer label versus exact method: many algorithms have bounded memory. Diagnostic: are BFGS pairs, initial scaling, and the two sweeps all identifiable?

Structural–Framed Character

L-BFGS is strongly structural within numerical optimization. Its pair definitions, recursion, secant relation, and storage bound are mathematical. Choices of memory size, line search, and damping frame an implementation, but do not socially constitute the method.

It remains domain-specific because its literal roles are gradients, curvature, and quasi-Newton matrices. Optimization is the cross-domain parent.

Structural Core vs. Domain Accent

Structural core. Preserve a bounded set of low-rank observations and apply their accumulated operator effect without materializing the full operator.

Domain accent. Step and gradient differences, BFGS secant updates, positive curvature, line search, and inverse-Hessian products define L-BFGS. Removing them leaves generic limited-memory approximation.

The method has an autonomous residual because these roles determine correctness, convergence assumptions, computational complexity, and characteristic failure modes.

Instantiates / Related Primes

This entry is a kind of Optimization.

L-BFGS specializes Optimization by defining an iterative search direction for smooth objectives. It relates to Approximation through its implicit inverse Hessian, Iteration through successive curvature pairs, and Tradeoff through memory versus information. Of these, only Optimization is a broader form of the method.

Relationships to Other Abstractions

Current abstraction Limited-Memory BFGS Domain-specific

Parents (1) — outgoing typed relations

• Limited-Memory BFGS is a kind of Optimization Prime

  L-BFGS specializes Optimization by defining an iterative search direction for smooth objectives.

Hierarchy path (1) — routes to 1 parentless root

• Limited-Memory BFGS → is a kind of Optimization

Neighborhood in Abstraction Space

Limited-Memory BFGS sits in a sparse region of the domain-specific corpus (81^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Hartman–Grobman Theorem — 0.83
• Verlet Integration — 0.82
• Minimum Relevant Variables in a Linear System — 0.82
• Bonnet Theorem — 0.81
• Conjugate Gradient Method — 0.81

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With

• BFGS: stores a dense approximation. Tell: is only a small pair history retained?
• L-BFGS-B: includes explicit bound constraints. Tell: are projected gradients and active bounds part of the procedure?
• Conjugate gradient: constructs conjugate directions with different recurrences. Tell: are secant pairs and BFGS coefficients used?
• Adam or momentum: uses moving gradient moments. Tell: is an inverse-Hessian action reconstructed from \((s,y)\) pairs?
• Hessian-free Newton: solves Newton systems from Hessian-vector products. Tell: is curvature observed through gradients across iterations or queried directly?

References

[1] Richard H. Byrd, Jorge Nocedal, and Robert B. Schnabel, “Representations of Quasi-Newton Matrices and Their Use in Limited Memory Methods,” Mathematical Programming 63 (1994), 129–156, https://doi.org/10.1007/BF01582063. registry ↩ Show verification details

[2] Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2^nd ed., Springer, 2006, Chapter 7, https://doi.org/10.1007/978-0-387-40065-5. registry ↩a ↩b