Overview
L-BFGS avoids a dense inverse-Hessian matrix by keeping recent parameter and gradient differences.
SpecializedSource checked
L-BFGS
Runs BFGS-style optimization while storing only a limited history of curvature updates.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Advanced
- Family
- Limited-Memory Quasi-Newton
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
limited memorycorrection pairstwo-loop recursionline search
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(m n)
Average
O(k m n)
Worst
O(k m n)
Space
O(m n)
When to Use
- Use when BFGS is attractive but the parameter vector is too large for dense matrices.
- Use when large smooth optimization is a central requirement.
When Not to Use
- Avoid when the objective is noisy enough that curvature history becomes misleading.
- Avoid when the objective is noisy, discontinuous, or violates the method's assumptions.
What It Does
- Stores recent correction pairs
- Approximates curvature from history
- Scales to larger parameter counts
Use Cases
- Large smooth optimization
- Machine learning parameter fitting
- Text and logistic models
Inputs
- Objective function
- Gradient function
- Initial parameters
- History size
Outputs
- Estimated minimizer
Key Formulas (1)
Correction pair
sk = x_{k+1} − xk; yk = gradient_{k+1} − gradientk
s_k = x_{k+1} - x_k; y_k = gradient_{k+1} - gradient_kStores the parameter and gradient changes used to approximate curvature.
Pseudocode
- 1.Store recent parameter and gradient differences
- 2.Use the two-loop recursion to compute a search direction
- 3.Perform a line search
- 4.Append the newest correction pair
- 5.Drop the oldest pair when history is full
Canonical Example
- Input
- history size = 5, parameters = 100000
- Output
- direction computed from recent correction pairs
- Explanation
- L-BFGS gets curvature help without storing a full matrix.
Implementation Notes
- Use a small history such as 5 to 20 correction pairs before tuning further.
- Track objective value, step size, and convergence criteria at each iteration.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Keeping too little history can behave like poorly scaled gradient descent.
- Stopping too early or using unscaled variables can make a good method look broken.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a fixed-size history window influencing each new search direction.
Step 1 of 5: Store recent parameter and gradient differences
optimization-landscapeNotes
The history size controls the memory and curvature detail tradeoff.
Sources (2)
What each reference supports for this entry.
Numerical Optimization
BookNocedal and Wright textbook reference for gradient descent, quasi-Newton methods, and nonlinear optimization.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofBFGS
L-BFGS is a limited-memory variant of BFGS.
ApproximatesNewton's Method
L-BFGS keeps a compact approximation to Newton-style curvature information.
Related Algorithms
Tags
OptimizationQuasi-NewtonGradient BasedMachine Learning