Developer Guide and Reference

  • 2021.6
  • 04/11/2022
  • Public Content
Contents

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 LaTex Math image. and set of intrinsic parameters LaTex Math image. defined for the memory parameter LaTex Math image., frequency of curvature estimates calculation LaTex Math image., and step-length sequence LaTex Math image., algorithm-specific vector LaTex Math image. and power LaTex Math image. of Lebesgue space defined as follows:

Transformation

LaTex Math image.
LaTex Math image.
where LaTex Math image. is an approximation of the inverse Hessian matrix computed from m correction pairs by the Hessian Update Algorithm.
Convergence check: LaTex Math image.

Intrinsic Parameters

For the LBFGS algorithm, the set of intrinsic parameters LaTex Math image. includes the following:
  • Correction pairs LaTex Math image.
  • 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 LaTex Math image.
  • Average value of arguments for the last L iterations LaTex Math image.
Below is the definition and update flow of the intrinsic parameters LaTex Math image.. The index is set and remains zero for the first 2L-1 iterations of the main loop. Starting with iteration LaTex Math image., the algorithm executes the following steps for each of L iterations of the main loop:
  1. LaTex Math image.
  2. Choose a set of indices without replacement: LaTex Math image., LaTex Math image., LaTex Math image., LaTex Math image..
  3. Compute the sub-sampled Hessian
    LaTex Math image.
    at the point LaTex Math image. for the objective function using Hessians of its terms
    ERROR processing math
  4. Compute the correction pairs LaTex Math image.:
    LaTex Math image.
    LaTex Math image.
  • The set LaTex Math image. of intrinsic parameters is updated once per LaTex Math image. iterations of the major loop and remains unchanged between iterations with the numbers that are multiples of LaTex Math image.
  • 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 LaTex Math image., LaTex Math image.:
  1. Set LaTex Math image.
  2. Iterate LaTex Math image. from LaTex Math image. until LaTex Math image.:
    1. LaTex Math image.
    2. LaTex Math image.
  3. Return LaTex Math image.

Computation

The limited-memory BFGS algorithm is a special case of an iterative solver. For parameters, input, and output of iterative solvers, see Computation.
Algorithm Input
In addition to the input of the iterative solver, the limited-memory BFGS algorithm accepts the following optional input:
Algorithm Input for Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Computaion
OptionalDataID
Input
correctionPairs
A numeric table of size LaTex Math image. where the rows represent correction pairs LaTex Math image. and LaTex Math image.. The row correctionPairs[j], LaTex Math image., is a correction vector LaTex Math image., and the row correctionPairs[j], LaTex Math image., is a correction vector LaTex Math image..
correctionIndices
A numeric table of size LaTex Math image. with 32-bit integer indexes. The first value is the index of correction pair LaTex Math image., the second value is the index of last iteration LaTex Math image. from the previous run.
averageArgumentLIterations
A numeric table of size LaTex Math image., where row 0 represents average arguments for previous LaTex Math image. iterations, and row 1 represents average arguments for last LaTex Math image. iterations. These values are required to compute LaTex Math image. correction vectors in the next step.
Algorithm Parameters
In addition to parameters of the iterative solver, the limited-memory BFGS algorithm has the following parameters:
Algorithm Parameters for Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Computaion
Parameter
Default Value
Description
algorithmFPType
float
The floating-point type that the algorithm uses for intermediate computations. Can be
float
or
double
.
method
defaultDense
Performance-oriented computation method
batchIndices
NULL
The numeric table of size LaTex Math image. with 32-bit integer indices of terms in the objective function to be used in step 2 of the limited-memory BFGS algorithm. If no indices are provided, the implementation generates random indices.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.
batchSize
LaTex Math image.
The number of observations to compute the stochastic gradient. The implementation of the algorithm ignores this parameter if the batchIndices numeric table is provided.
If BatchSize equals the number of terms in the objective function, no random sampling is performed and all terms are used to calculate the gradient.
correctionPairBatchSize
LaTex Math image.
The number of observations to compute the sub-sampled Hessian for correction pairs computation. The implementation of the algorithm ignores this parameter if the correctionPairIndices numeric table is provided.
If
correctionPairBatchSize
equals the number of terms in the objective function, no random sampling is performed and all terms are used to calculate the Hessian matrix.
correctionPairIndices
NULL
The numeric table of size LaTex Math image. with 32-bit integer indices to be used instead of random values. If no indices are provided, the implementation generates random indices.
This parameter can be an object of any class derived from
NumericTable
, except for
PackedTriangularMatrix
,
PackedSymmetricMatrix
, and
CSRNumericTable
.
If the algorithm runs with no optional input data, LaTex Math image. rows of the table are used. Otherwise, it can use one more row, LaTex Math image. in total.
LaTex Math image.
LaTex Math image.
The memory parameter. The maximum number of correction pairs that define the approximation of the Hessian matrix.
LaTex Math image.
LaTex Math image.
The number of iterations between calculations of the curvature estimates.
stepLengthSequence
A numeric table of size LaTex Math image. that contains the default step length equal to LaTex Math image..
The numeric table of size LaTex Math image. or LaTex Math image.. The contents of the table depend on its size:
  • LaTex Math image.: values of the step-length sequence LaTex Math image. for LaTex Math image..
  • LaTex Math image.: the value of step length at each iteration LaTex Math image.
..note:
This parameter can be an object of any class derived from ``NumericTable``, except for ``PackedTriangularMatrix``, ``PackedSymmetricMatrix``, and ``CSRNumericTable``.
The recommended data type for storing the step-length sequence is the floating-point type, either float or double, that the algorithm uses in intermediate computations.
engine
SharePtr< engines:: mt19937:: Batch>()
Pointer to the random number generator engine that is used internally for random choosing terms from the objective function.
Algorithm Output
In addition to the output of the iterative solver, the limited-memory BFGS algorithm calculates the following optional results:
Algorithm Output for Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Computaion
OptionalDataID
Output
correctionPairs
A numeric table of size LaTex Math image. where the rows represent correction pairs LaTex Math image. and LaTex Math image.. The row correctionPairs[j], LaTex Math image., is a correction vector LaTex Math image., and the row correctionPairs[j], LaTex Math image., is a correction vector LaTex Math image..
correctionIndices
A numeric table of size LaTex Math image. with 32-bit integer indexes. The first value is the index of correction pair LaTex Math image., the second value is the index of last iteration LaTex Math image. from the previous run.
averageArgumentLIterations
A numeric table of size LaTex Math image., where row 0 represents average arguments for previous LaTex Math image. iterations, and row 1 represents average arguments for last LaTex Math image. iterations. These values are required to compute LaTex Math image. correction vectors in the next step.
Examples
C++ (CPU)
Batch Processing:
Java*
There is no support for Java on GPU.
Batch Processing:
Python*
Batch Processing:

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.