Developer Guide for Intel® Data Analytics Acceleration Library 2019 Update 4
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:
:
Convergence check:
For the LBFGS algorithm, the set of intrinsic parameters S t includes the following:
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:
k:=k+1
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.
Compute the sub-sampled Hessian
Compute the correction pairs (s k , y k ):
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.
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: