Problems

1 / 1

L-BFGS Two-Loop Recursion

Optimization

Hard

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:

s_i = x_{i+1} - x_i \qquad y_i = g_{i+1} - g_i \qquad \rho_i = \frac{1}{y_i^T s_i}

Algorithm (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:

\gamma = \frac{s_{m-1}^T y_{m-1}}{y_{m-1}^T y_{m-1}} \qquad r = \gamma \cdot q

Second 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).

Loading visualization...

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

Try Similar Problems

Nesterov Momentum Adam Optimizer Gradient Descent Quadratic Gradient Clipping Adamw Optimizer

Prev Next

L-BFGS Two-Loop Recursion

Optimization

Hard

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:

s_i = x_{i+1} - x_i \qquad y_i = g_{i+1} - g_i \qquad \rho_i = \frac{1}{y_i^T s_i}

Algorithm (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:

\gamma = \frac{s_{m-1}^T y_{m-1}}{y_{m-1}^T y_{m-1}} \qquad r = \gamma \cdot q

Second 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).

Loading visualization...

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

Try Similar Problems

Nesterov Momentum Adam Optimizer Gradient Descent Quadratic Gradient Clipping Adamw Optimizer

Case 1

Case 2

grad =

Accepts: array

s_list =

Accepts: array

y_list =

Accepts: array

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:

s_i = x_{i+1} - x_i \qquad y_i = g_{i+1} - g_i \qquad \rho_i = \frac{1}{y_i^T s_i}

Algorithm (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:

\gamma = \frac{s_{m-1}^T y_{m-1}}{y_{m-1}^T y_{m-1}} \qquad r = \gamma \cdot q

Second 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).