Data Science & Machine Learning — Article 52

Broyden-Fletcher-Goldfarb-Shanno (BFGS): A Comprehensive Guide

Explore detailed Broyden-Fletcher-Goldfarb-Shanno (BFGS)

Data Science & Machine Learning — Article 52

Introduction

Article 50 left a clear gap. Newton’s method needed 5 iterations where gradient descent needed 464, and it was ruled out anyway because forming a Hessian costs O(d²) memory and O(d³) time.

BFGS closes it differently. Each iteration produces a step and a change in gradient, and that pair is a measurement of curvature along one direction.

Accumulate those measurements and a full approximate inverse Hessian emerges from information the optimizer was already computing.

Table of Contents

• Introduction
• Table of Contents
• What is BFGS
• Core Components of BFGS
• Mathematical Foundation
• Types of BFGS
• Evaluation Metrics
• Selecting Evaluation Metrics

What is BFGS

Definition

BFGS is a quasi-Newton method that maintains an approximation Hₖ to the inverse Hessian, updated at each step from the step vector sₖ and the gradient change yₖ, and takes the search direction pₖ = -Hₖ ∇ f(xₖ).

Why it is needed

• It achieves superlinear convergence using only gradients, so the O(d³) Hessian solve that ruled Newton out disappears.
• The approximation is a full matrix, not a diagonal, so it captures the parameter correlations that Article 51 showed Adam cannot.

The secant idea

For a quadratic with Hessian A, the gradient change over a step is exactly

so each step reveals the Hessian’s action along one direction. Requiring the approximation to reproduce that measurement gives the secant equation:

One equation in d² unknowns, so the update is underdetermined. BFGS resolves it by choosing the Hₖ₊₁ closest to Hₖ in a weighted Frobenius sense, subject to the secant equation and symmetry.

Against its neighbours

• The O(d²) memory is BFGS’s own limit, and L-BFGS in Section 6 removes it.

Core Components of BFGS

The inverse Hessian approximation Hₖ

• Maintained directly, so the search direction is a matrix-vector product rather than a linear solve.
• Initialized to I, which makes the first step a plain gradient step.

The update formula

• This form makes two properties structural rather than accidental: it satisfies the secant equation exactly, and it preserves positive definiteness whenever yₖ⊤ sₖ > 0.

The curvature condition

• The requirement for the update to keep H positive definite. Section 5.5 examines when it can fail, and finds it cannot on a convex problem.

The line search

• BFGS needs a step length. The Wolfe conditions are the standard choice because the second of them guarantees yₖ⊤ sₖ > 0:
• With 0 < c₁ < c₂ < 1. Backtracking on the first condition alone is common and usually sufficient for convex problems.

The initial scaling

• H₀ = I makes the first step’s magnitude depend on the units of f.
• A common improvement is to rescale H₀ after the first step using y₀⊤ s₀ / y₀⊤ y₀, which removes that sensitivity.

Mathematical Foundation

Termination in d steps on a quadratic

With an exact line search on a quadratic, BFGS generates conjugate directions and therefore terminates in at most d iterations. On the κ = 10 problem from Article 49, with d = 2:

Exactly 2 iterations, matching d = 2. And the final approximation is the true inverse Hessian:

with max∣H₂ — A⁻¹∣ = 2.220×10⁻¹⁶. The curvature was recovered exactly from two gradient differences, never having formed or been told the Hessian.

Repeating at κ = 1000, where gradient descent needed 9613 iterations:

Still 2. The iteration count is d, independent of conditioning. That is Newton’s insensitivity achieved with first derivatives only, at the cost of needing d steps rather than 1.

Superlinear but not quadratic

On a nonlinear problem the behavior is between gradient descent and Newton, and the distinction is measurable.

Using the regularized logistic regression from Article 50, with reference minimizer w* = (-1.378570463290, 0.453873097160) and unit-step BFGS with backtracking:

Read the two ratio columns against each other, because together they identify the convergence order precisely.

eₖ/eₖ₋₁ tends to zero: 0.9636, then 0.0371, 0.1089, 0.1006, and eventually 0.0049, 0.0180, 0.0085, 0.0065. A ratio tending to zero rather than to a positive constant is the definition of superlinear convergence.

eₖ/eₖ₋₁² grows without bound, reaching 1.886×1⁰¹¹. Article 50 measured this same ratio for Newton settling at 0.837162.

A bounded ratio means quadratic; an unbounded one means slower than quadratic.

So BFGS is strictly between gradient descent and Newton, and the two ratio columns prove it rather than asserting it.

This is the single most useful diagnostic in the article: computing both ratios on any implementation immediately says which of the three regimes it is in.

Note iteration 9, where the ratio jumps to 0.508 before resuming. Around 10⁻¹⁰ the gradient is near the noise floor for these magnitudes, so the measured step quality degrades.

That is floating-point reality rather than an algorithmic property, and it is why the last few rows should not be over-interpreted.

The three methods side by side

Same problem, same starting point:

Three distinct scaling behaviors, visible in the columns. Gradient descent adds about 77 iterations per four digits, which is the linear rate.

Newton adds one iteration per four digits, which is quadratic. BFGS adds two to three, which is superlinear.

BFGS needs about twice Newton’s iterations and about 40× fewer than gradient descent, using the same first-order information gradient descent uses.

That is the trade the method exists to make, and at d = 2 its O(d²) update cost is negligible while Newton’s O(d³) solve is too.

The secant equation holds exactly

The update is constructed so that Hₖ₊₁yₖ = sₖ exactly. Verifying at each iteration on the logistic problem:

The residual is at machine precision throughout, confirming the algebra is being implemented correctly.

This is a stronger implementation check than watching the loss decrease, because it tests the update formula in isolation.

The y⊤ s column is worth reading too. It falls from 1.80 to 1.81×10⁻⁸ as the iterates converge, because both s and y shrink.

That decay is why ρₖ = 1/(y⊤ s) eventually becomes enormous and the update becomes numerically delicate, and it is the practical reason implementations skip the update when y⊤ s falls below a threshold relative to ‖s‖‖y‖.

The curvature condition cannot fail on a convex problem

The update requires y⊤ s > 0. Attempting to violate it by deliberately stepping uphill from w₀ = (0,0), along +∇ f rather than against it:

Still positive. That is not luck. For a convex differentiable f, monotonicity of the gradient gives

for any s, with strict inequality when f is strictly convex and s ≠ 0. So on a convex problem the curvature condition holds regardless of the direction taken, and BFGS cannot produce an indefinite H.

The condition bites only on non-convex problems, where a step can cross a region of negative curvature and produce y⊤ s ≤ 0.

The standard remedies are to skip the update, or to apply Powell damping, which replaces y with a convex combination of y and Bs chosen to force the condition.

This is worth stating because the curvature condition is usually presented as a hazard to guard against.

On the convex problems where BFGS is most often demonstrated, it is automatically satisfied, and the guard is dead code.

Why the approximation converges to the true inverse

BFGS does not converge to A⁻¹ in general; it converges to something that acts like A⁻¹ on the directions actually explored.

On a quadratic in d dimensions with exact line searches, the d steps span the whole space, so the secant conditions

pin down Hd A sᵢ = sᵢ for d independent sᵢ, forcing Hd = A⁻¹. That is exactly what Section 5.1 measured to 2.220×10⁻¹⁶.

On a nonlinear problem the Hessian changes between steps, so the accumulated measurements are of different matrices and Hₖ tracks a moving target.

It nonetheless satisfies the Dennis-Moré condition asymptotically,

which requires only that Bₖ be accurate along the search directions, not everywhere.

That weaker requirement is precisely what yields superlinear rather than quadratic convergence, and it explains Section 5.2’s two ratio columns.

Types of BFGS

DFP

• The earlier formula, updating H by a different rank-two correction.
• Mathematically dual to BFGS but empirically less robust to inexact line searches, which is why BFGS displaced it.

L-BFGS

• Stores the last m pairs (sᵢ, yᵢ) instead of the matrix, and reconstructs the product Hₖ gₖ by a two-loop recursion in O(md) time.
• With m between 5 and 20 this makes quasi-Newton methods usable at millions of parameters, and it is the standard choice for large smooth deterministic problems.

L-BFGS-B

• Adds box constraints by combining L-BFGS with a gradient-projection step.
• This is the workhorse behind most general-purpose bounded optimizers.

Damped BFGS

• Applies Powell damping so the curvature condition holds even when the raw y⊤ s ≤ 0, which Section 5.5 identified as a non-convex-only concern.

SR1

• A symmetric rank-one update that does not enforce positive definiteness.
• That sounds like a defect and is an advantage inside a trust region, because an indefinite model can detect and exploit negative curvature directions, which is exactly what Newton failed to do at the saddle in Article 50.

Stochastic quasi-Newton

• Adapting BFGS to noisy gradients is genuinely hard, because yₖ computed from two different mini-batches is dominated by sampling noise rather than curvature.
• This is the main reason Adam rather than L-BFGS dominates deep learning.

Evaluation Metrics

Both convergence ratios

• The pair identifies the regime unambiguously: both bounded away from zero means linear, the first tending to zero means superlinear, the second bounded means quadratic.

Secant residual

• Should be at machine precision by construction. A residual above 10⁻¹⁰ indicates the update formula is implemented incorrectly, and this test is independent of whether the optimizer appears to work.

The curvature product y⊤ s

• Positive on convex problems always. Its magnitude relative to ‖s‖‖y‖ is the practical skip criterion.

Positive definiteness of H

• Should hold at every iteration on a convex problem. Losing it means either y⊤ s ≤ 0 was accepted or the update has a sign error.

Line search rejections

• The fraction of iterations where t = 1 was rejected. High and persistent means the quadratic model is poor

Iterations against gradient evaluations

• BFGS’s line search costs extra gradient evaluations, so iteration counts understate the true cost. Report both.