L-BFGS Two-Loop Recursion
L-BFGS Two-Loop Recursion
L-BFGS is a memory-efficient quasi-Newton optimizer that approximates the inverse Hessian using a limited history of past parameter and gradient differences. The two-loop recursion is its core algorithm for computing the search direction without ever forming the full matrix.
Given the current gradient and a history of m past step differences (s_list) and gradient differences (y_list), compute the L-BFGS search direction.
Definitions
For each history pair i:
si=xi+1−xiyi=gi+1−giρi=yiTsi1Algorithm (Two-Loop Recursion)
First loop (backward, i = m-1 down to 0):
- Start with q = copy of gradient.
- For each i from newest to oldest: compute alpha_i = rho_i * dot(s_i, q), then update q = q - alpha_i * y_i.
Initial scaling using the most recent pair:
γ=ym−1Tym−1sm−1Tym−1r=γ⋅qSecond loop (forward, i = 0 up to m-1):
-
For each i from oldest to newest: compute beta = rho_i * dot(y_i, r), then update r = r + s_i * (alpha_i - beta).
-
Return the negated result: direction = -r (descent direction).
Examples
Input:
grad = [2.0], s_list = [[1.0]], y_list = [[2.0]]
Output:
[-1.0]
With one history pair in 1D: rho = 0.5, alpha = 1.0, q becomes 0. gamma = 0.5, r = 0. After forward loop r = 1.0. Negated: [-1.0].
Input:
grad = [6.0, 4.0, 2.0], s_list = [[1,0,0],[0,1,0],[0,0,1]], y_list = [[2,0,0],[0,2,0],[0,0,2]]
Output:
[-3.0, -2.0, -1.0]
With an identity-like history, the inverse Hessian approximation is 0.5 * I, so the direction is -0.5 * gradient.
Hint 1
The backward loop goes from the most recent history pair (index m-1) to the oldest (index 0). Store each alpha_i for use in the forward loop.
Hint 2
The dot product of two vectors a and b is sum(a_i * b_i). You need it for rho, alpha, beta, and gamma computations.
Requirements
- Implement the backward loop computing alpha values and updating q
- Compute the initial Hessian scaling gamma from the most recent history pair
- Implement the forward loop computing beta and updating r
- Return the negated result as the descent direction
Constraints
- grad is a list of floats (length n)
- s_list and y_list are lists of m vectors, each of length n, with m >= 1
- dot(y_i, s_i) > 0 for all i (curvature condition is satisfied)
- Return a list of n floats (the descent direction)
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array
L-BFGS Two-Loop Recursion
L-BFGS Two-Loop Recursion
L-BFGS is a memory-efficient quasi-Newton optimizer that approximates the inverse Hessian using a limited history of past parameter and gradient differences. The two-loop recursion is its core algorithm for computing the search direction without ever forming the full matrix.
Given the current gradient and a history of m past step differences (s_list) and gradient differences (y_list), compute the L-BFGS search direction.
Definitions
For each history pair i:
si=xi+1−xiyi=gi+1−giρi=yiTsi1Algorithm (Two-Loop Recursion)
First loop (backward, i = m-1 down to 0):
- Start with q = copy of gradient.
- For each i from newest to oldest: compute alpha_i = rho_i * dot(s_i, q), then update q = q - alpha_i * y_i.
Initial scaling using the most recent pair:
γ=ym−1Tym−1sm−1Tym−1r=γ⋅qSecond loop (forward, i = 0 up to m-1):
-
For each i from oldest to newest: compute beta = rho_i * dot(y_i, r), then update r = r + s_i * (alpha_i - beta).
-
Return the negated result: direction = -r (descent direction).
Examples
Input:
grad = [2.0], s_list = [[1.0]], y_list = [[2.0]]
Output:
[-1.0]
With one history pair in 1D: rho = 0.5, alpha = 1.0, q becomes 0. gamma = 0.5, r = 0. After forward loop r = 1.0. Negated: [-1.0].
Input:
grad = [6.0, 4.0, 2.0], s_list = [[1,0,0],[0,1,0],[0,0,1]], y_list = [[2,0,0],[0,2,0],[0,0,2]]
Output:
[-3.0, -2.0, -1.0]
With an identity-like history, the inverse Hessian approximation is 0.5 * I, so the direction is -0.5 * gradient.
Hint 1
The backward loop goes from the most recent history pair (index m-1) to the oldest (index 0). Store each alpha_i for use in the forward loop.
Hint 2
The dot product of two vectors a and b is sum(a_i * b_i). You need it for rho, alpha, beta, and gamma computations.
Requirements
- Implement the backward loop computing alpha values and updating q
- Compute the initial Hessian scaling gamma from the most recent history pair
- Implement the forward loop computing beta and updating r
- Return the negated result as the descent direction
Constraints
- grad is a list of floats (length n)
- s_list and y_list are lists of m vectors, each of length n, with m >= 1
- dot(y_i, s_i) > 0 for all i (curvature condition is satisfied)
- Return a list of n floats (the descent direction)
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array