Skip to content

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\).

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.

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.

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.

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.

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.

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.

Relationships to Other Abstractions

Local relationship map for Limited-Memory BFGSParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Limited-Memory BFGSDOMAINPrime abstraction: Optimization — is a kind ofOptimizationPRIME

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

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

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