Developer Guide

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
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 2
L
-1 iterations of the main loop. Starting with iteration 2
L
, 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
    ):
  • 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

Product and Performance Information

1

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804