L-BFGS Algorithm

Are you wrestling with slow machine learning models? Do you need faster, more efficient ways to train them? L-BFGS might be the answer. It’s a popular and powerful optimization method. This article breaks down the maths behind L-BFGS. Get ready to unlock its potential!

Quasi-Newton methods are optimization algorithms. They approximate the Hessian matrix (a matrix of second derivatives) to find the minimum of a function. These methods are useful when calculating the exact Hessian is too hard.

BFGS (Broyden–Fletcher–Goldfarb–Shanno) and L-BFGS are related. L-BFGS is a limited-memory version. This limited memory is key for handling large datasets.

The Essence of Optimization: Setting the Stage

Let’s understand optimization. This is key to grasping L-BFGS.

What is Optimization?

Optimization means finding the best solution from many possibilities. In machine learning, it’s about training models. We want to minimize a cost or loss function. Think of it like adjusting knobs until your model performs best.

Gradient Descent is one such optimization method. It’s like walking downhill to find the lowest point. We adjust the model’s parameters to reduce the error.

Gradient Descent Limitations

Gradient Descent has limits. It can be slow. The learning rate (step size) is important. Too big, and we overshoot. Too small, and we crawl. Gradient Descent can also get stuck in local minima. These are false bottoms that prevent reaching the true minimum. More advanced optimization is needed.

Newton’s Method: A Second-Order Approach

Newton’s method is faster than Gradient Descent. It uses the Hessian matrix. This gives information about the curvature of the loss function. It’s like using a map to find the quickest route. The problem? Calculating and inverting the Hessian is costly. This is especially true for big problems.

BFGS: Approximating the Hessian

BFGS comes to the rescue! It’s a quasi-Newton method. It approximates the Hessian matrix. This avoids the expensive calculation. BFGS offers faster convergence without the computational burden.

Secant Condition

The Secant Condition is key to approximating the Hessian. It ensures that the approximate Hessian behaves like the real one. Mathematically, it looks like this:

Bₖ₊₁sₖ = yₖ

Here, Bₖ₊₁ is the approximate Hessian at iteration k+1, sₖ = xₖ₊₁ - xₖ is the change in parameters, and yₖ = ∇fₖ₊₁ - ∇fₖ is the change in the gradient.

BFGS Update Formula

The BFGS update formula refines the Hessian approximation. It uses information from the current iteration. Here’s the formula:

Bₖ₊₁ = Bₖ - (BₖsₖsₖᵀBₖᵀ) / (sₖᵀBₖsₖ) + (yₖyₖᵀ) / (yₖᵀsₖ)

Get Ravi Sankar Uppala’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Let’s break it down:

• Bₖ₊₁ is the updated inverse Hessian approximation.
• Bₖ is the current inverse Hessian approximation.
• sₖ is the change in parameters (xₖ₊₁ - xₖ).
• yₖ is the change in gradient (∇fₖ₊₁ - ∇fₖ).

This formula updates the Hessian approximation. It uses the changes in parameters and gradients.

L-BFGS: Scaling BFGS for Big Data

L-BFGS is made for large-scale optimization. It’s a limited-memory version of BFGS. BFGS can hog memory, especially with huge datasets. L-BFGS solves this by storing only a few vectors.

Memory Efficiency: Storing Update Vectors

L-BFGS stores only ‘m’ update vectors (sₖ and yₖ) from recent iterations. These vectors capture the history of updates. They implicitly represent the approximate inverse Hessian. This saves a ton of memory.

The Two-Loop Recursion

L-BFGS uses a clever trick: two-loop recursion. This computes the search direction. It avoids explicitly forming the Hessian. Here’s how it works:

1. Initialization: Start with an initial guess for the inverse Hessian, H₀.
2. First Loop (Forward): For i = k-1, k-2, ..., k-m:

• αᵢ = ρᵢsᵢᵀq, where ρᵢ = 1 / (yᵢᵀsᵢ)
• q = q - αᵢyᵢ

1. Middle Step: r = H₀q
2. Second Loop (Backward): For i = k-m, k-m+1, ..., k-1:

• β = ρᵢyᵢᵀr
• r = r + sᵢ(αᵢ - β)

Result: The search direction is -r.

Here, q and r are temporary vectors. The sᵢ and yᵢ are the stored update vectors. This two-loop process efficiently computes the search direction.

Choosing ‘m’: The Memory Parameter

The memory parameter ‘m’ is important. It controls how many update vectors are stored. A larger ‘m’ means more memory. It can also lead to better optimization. A smaller ‘m’ saves memory. It might sacrifice some performance. Choose ‘m’ based on your problem size and resources. Values between 3 and 20 are common.

Mathematical Details of L-BFGS

Now, let’s dive deeper into the maths.

Derivation of the Two-Loop Recursion (Optional)

The two-loop recursion comes from the BFGS update formula. It also comes from the limited-memory constraint. We won’t show the full derivation. It involves applying the BFGS update recursively. We then use the stored vectors to approximate the inverse Hessian. This leads to the two-loop algorithm.

Convergence Analysis of L-BFGS (Optional)

L-BFGS converges under certain conditions. The loss function must be smooth and convex. The choice of ‘m’ also affects convergence. Optimization theory provides theorems about L-BFGS convergence. These theorems help ensure that the algorithm will find a good solution.

Practical Considerations and Applications

Let’s explore how to use L-BFGS in practice.

Preconditioning Techniques

Preconditioning can boost L-BFGS performance. It involves scaling the input space. This makes the optimization problem easier. Common pre conditioners include:

• Diagonal scaling: Scale each dimension independently.
• Incomplete Cholesky factorization: Approximate the Hessian and use its inverse.

Preconditioning can speed up convergence.

Real-World Examples

L-BFGS shines in large-scale machine learning. It’s used to train deep neural networks. It also trains logistic regression models with millions of features. For example, training a large language model might use L-BFGS.

Finance also uses L-BFGS. It’s used for portfolio optimization. It’s also used in risk management.