Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm

The limited-memory Broyden-Fletcher-Goldfarb-Shanno (LBFGS) algorithm [Byrd2015] follows the algorithmic framework of an iterative solver with the algorithm-specific transformation T and set of intrinsic parameters S t defined for the memory parameter m, frequency of curvature estimates calculation L, and step-length sequence α t > 0, algorithm-specific vector U and power d of Lebesgue space defined as follows:

Transformation

:



where H is an approximation of the inverse Hessian matrix computed from m correction pairs by the Hessian Update Algorithm.

Convergence check:

Intrinsic Parameters

For the LBFGS algorithm, the set of intrinsic parameters S t includes the following:

  • Correction pairs (s j , y j )
  • Correction index k in the buffer that stores correction pairs
  • Index of last iteration t of the main loop from the previous run
  • Average value of arguments for the previous L iterations
  • Average value of arguments for the last L iterations

Below is the definition and update flow of the intrinsic parameters (s i , y i ). The index is set and remains zero for the first 2L-1 iterations of the main loop. Starting with iteration 2L, the algorithm executes the following steps for each of L iterations of the main loop:

  1. k:=k+1

  2. Choose a set of indices without replacement: I H = {i 1, i 2, ... , i bH }, 1 ≤ i l < n, l ∈ {1, ..., b H }, | I H | = b H = correctionPairBatchSize.

  3. Compute the sub-sampled Hessian



    at the point for the objective function using Hessians of its terms


  4. Compute the correction pairs (s k , y k ):

Note

  • The set S k of intrinsic parameters is updated once per L iterations of the major loop and remains unchanged between iterations with the numbers that are multiples of L

  • A cyclic buffer stores correction pairs. The algorithm fills the buffer with pairs one-by-one. Once the buffer is full, it returns to the beginning and overwrites the previous correction pairs.

Hessian Update Algorithm

This algorithm computes the approximation of the inverse Hessian matrix from the set of correction pairs [Byrd2015]).

For a given set of correction pairs (s j , y j ), j = k - min (k, m) +1, ..., k:

  1. Set

  2. Iterate j from k - min (k, m)+1 until k:





  3. Return H

For more complete information about compiler optimizations, see our Optimization Notice.
Select sticky button color: 
Orange (only for download buttons)