L-BFGS approximates an inverse Hessian using a limited history of parameter changes and gradient changes. Implement its two-loop recursion to compute a descent direction without constructing a Hessian matrix.
The input grad is the current gradient vector. The lists s_list and y_list contain m history vectors ordered from oldest to newest. Every vector has n elements.
For each history index i, define the curvature scale:
ρi=yiTsi1Start the backward pass with:
q=gProcess the history from newest to oldest. For each index i, compute:
αi=ρisiTqThen update:
q=q−αiyiUse the newest history pair to scale the initial inverse-Hessian approximation:
γ=ym−1Tym−1sm−1Tym−1 r=γqProcess the history from oldest to newest. For each index i, compute:
βi=ρiyiTrThen update:
r=r+si(αi−βi)Here, g denotes the current gradient, s_i denotes a parameter change, y_i denotes its corresponding gradient change, and m is the number of stored history pairs.
Return the negated vector, -r, as a list of n floats.
Input: grad = [2], s_list = [[1]], y_list = [[2]]
Output: [-1.0]
Explanation: The single history pair produces an inverse-Hessian scale of one half.
Input: grad = [4, 2], s_list = [[1, 0]], y_list = [[2, 0]]
Output: [-2.0, -1.0]
Store rho and alpha values while traversing history from newest to oldest.
Apply the newest-pair scale before traversing history from oldest to newest.
Accepts: array
Accepts: array
Accepts: array
L-BFGS approximates an inverse Hessian using a limited history of parameter changes and gradient changes. Implement its two-loop recursion to compute a descent direction without constructing a Hessian matrix.
The input grad is the current gradient vector. The lists s_list and y_list contain m history vectors ordered from oldest to newest. Every vector has n elements.
For each history index i, define the curvature scale:
ρi=yiTsi1Start the backward pass with:
q=gProcess the history from newest to oldest. For each index i, compute:
αi=ρisiTqThen update:
q=q−αiyiUse the newest history pair to scale the initial inverse-Hessian approximation:
γ=ym−1Tym−1sm−1Tym−1 r=γqProcess the history from oldest to newest. For each index i, compute:
βi=ρiyiTrThen update:
r=r+si(αi−βi)Here, g denotes the current gradient, s_i denotes a parameter change, y_i denotes its corresponding gradient change, and m is the number of stored history pairs.
Return the negated vector, -r, as a list of n floats.
Input: grad = [2], s_list = [[1]], y_list = [[2]]
Output: [-1.0]
Explanation: The single history pair produces an inverse-Hessian scale of one half.
Input: grad = [4, 2], s_list = [[1, 0]], y_list = [[2, 0]]
Output: [-2.0, -1.0]
Store rho and alpha values while traversing history from newest to oldest.
Apply the newest-pair scale before traversing history from oldest to newest.
Accepts: array
Accepts: array
Accepts: array