Does BB compute second derivatives?

The basic formulas use point and gradient differences rather than explicit second derivatives.

Must every iteration improve the objective?

No. The raw BB method can be nonmonotone; particular safeguarded variants add their own acceptance rules.

What if s dot y is zero or negative?

The usual positive-step interpretation fails or becomes undefined. A robust implementation needs a documented safeguard or fallback.

AI Glossary / Mathematics and optimization / Intermediate

Barzilai - Borwein method

Definition

The Barzilai - Borwein method is a gradient-based optimization approach that chooses its step size from the changes between two successive points and their gradients. It uses this recent information to estimate a useful scale for the next movement without storing a full curvature matrix. The resulting method can be inexpensive per iteration, but its objective values need not decrease at every step.

What it means

Ordinary gradient descent moves opposite the current gradient. Its effectiveness depends heavily on the step size: a small value may waste iterations, while a large one can overshoot.

Barzilai - Borwein, often abbreviated BB, uses the previous displacement and the corresponding change in gradient as a clue about curvature. The search direction remains the negative gradient, while one scalar sets its scale. This is more informed than an arbitrary fixed learning rate, but much simpler than learning a separate curvature response for every direction.

How it works

Let s be the current point minus the previous point, and y the current gradient minus the previous gradient. Two common step sizes are BB1 = (s dot s)/(s dot y) and BB2 = (s dot y)/(y dot y). They arise from different scalar approximations to a secant relation.

After selecting a step alpha, update x to x − alpha times the current gradient. An initial step is needed before a pair of points is available.

Practical implementations check denominators, positivity, and permitted step-size bounds. For general objectives, safeguards and line-search strategies can be part of the chosen variant. The raw formulas alone do not provide a universal convergence guarantee, particularly when s dot y is nonpositive or the supplied gradients are inaccurate.

Three practical examples

1. A smooth least-squares solver uses BB scaling to obtain an inexpensive curvature-informed step without forming a Hessian matrix.

2. An image-reconstruction experiment compares a BB-based gradient routine with fixed-step descent, counting objective and gradient evaluations as well as iterations.

3. A numerical optimization class studies how different coordinate curvatures affect BB1 and BB2, using a small quadratic whose exact minimum is known.

Think of it this way

Think of adjusting how far you turn a dial after observing how strongly the system responded to your previous adjustment. BB uses the change in gradient as its response signal. The analogy does not imply a physical experiment at every iteration, and one scalar cannot fully describe a system whose sensitivity differs across many directions.

Worked example

Minimize f(x1,x2) = 0.5x1 squared + 2x2 squared. Its gradient is (x1,4x2). Start at x_old = (2,1), where the gradient is (2,4). Use an initial step of 0.25, giving x_new = (1.5,0) and gradient (1.5,0).

The displacement is s = (−0.5,−1), and the gradient change is y = (−0.5,−4). Compute s dot s = 1.25, s dot y = 4.25, and y dot y = 16.25.

Therefore BB1 is 1.25/4.25 = 5/17, approximately 0.2941. BB2 is 4.25/16.25 = 17/65, approximately 0.2615. They differ because the previous displacement sampled two different coordinate curvatures.

Using BB1 for the next update gives (1.5,0) − (5/17)(1.5,0) = (18/17,0), approximately (1.0588,0). Its objective is 162/289, approximately 0.5606, down from 1.125 at (1.5,0).

This calculation is one hand-worked step, not evidence that every BB step decreases the objective. On a one-dimensional quadratic f(x) = 0.5h x squared with positive h and a nonzero displacement, y = h s. Both formulas then give alpha = 1/h, illustrating their inverse-curvature interpretation. The multidimensional method still uses a single scale rather than a full inverse Hessian.

Illustrative case study

Fictional case: Rowan Imaging prototypes a reconstruction solver with a BB step. Its progress chart occasionally rises, and the team initially assumes that every rise is a programming error.

Reviewers first verify gradients on a small known problem, then distinguish expected nonmonotone behavior from numerical failures. They document step-size bounds, a fallback for unusable curvature information, and the exact acceptance strategy. Comparisons use the same stopping tolerance and count all evaluations. The case illustrates how to evaluate a particular implementation; it does not assert that BB outperforms the team's existing solver.

Common misconceptions and mistakes

Do not confuse BB scaling with a full quasi-Newton matrix update. It uses recent curvature information in a much more restricted form.

Do not assume BB1 and BB2 are interchangeable numerically. They can generate different sequences and need an explicit selection rule if a variant switches between them.

An objective increase is possible, but that does not justify ignoring unlimited growth or invalid values. Likewise, clamping an invalid step is an implementation choice whose consequences should be assessed. With stochastic gradients, differences can reflect sampling noise rather than curvature, so a deterministic formula needs careful adaptation.

Business use

BB methods are worth evaluating when smooth optimization is large enough that storing or factoring a full Hessian is unattractive. Assess total runtime and achieved accuracy on the intended problem, including the cost of any safeguarding procedure.

Keep the initial step, formula choice, bounds, and stopping criteria in the experiment record. Variable scaling can materially affect the observed gradients and steps. Before attributing poor behavior to the optimization family, check derivatives and units, then compare against a simple, well-understood baseline at the same accuracy target.

Check your understanding

Why is BB1 approximately 0.2941 in the worked example rather than 1.25/16.25?

Answer: BB1 divides s dot s by s dot y. The denominator y dot y belongs to the different BB2 formula.

Related terms

Gradient descent
Step size
Hessian
Line search
secant equation
quasi-Newton method
spectral gradient
curvature

Learn next

Study the secant relation next. Repeat the worked calculation with a displacement only in the second coordinate and explain why both formulas then recover the inverse curvature 1/4 for that direction.

Sources

Primary research reference opened: Huang, Dai, Liu and Zhang, “On the acceleration of the Barzilai–Borwein method,” https://www.math.lsu.edu/~hozhang/papers/AccBB.pdf. Its introduction states both BB formulas and discusses nonmonotone behaviour. Quadratic calculations and the fictional case here are original hand-checked illustrations.

Previous: Barycentric coordinates Next: Base effect