Problems

1 / 1

L-BFGS Two-Loop Recursion

Optimization

Hard

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:

\rho_i = \frac{1}{y_i^{\mathsf T}s_i}

Start the backward pass with:

q = g

Process the history from newest to oldest. For each index i, compute:

\alpha_i = \rho_i s_i^{\mathsf T}q

Then update:

q = q - \alpha_i y_i

Use the newest history pair to scale the initial inverse-Hessian approximation:

\gamma = \frac{s_{m-1}^{\mathsf T}y_{m-1}}{y_{m-1}^{\mathsf T}y_{m-1}}

r = \gamma q

Process the history from oldest to newest. For each index i, compute:

\beta_i = \rho_i y_i^{\mathsf T}r

Then update:

r = r + s_i(\alpha_i - \beta_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.

Loading visualization...

Examples

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]

Hint 1

Store rho and alpha values while traversing history from newest to oldest.

Hint 2

Apply the newest-pair scale before traversing history from oldest to newest.

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

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:

\rho_i = \frac{1}{y_i^{\mathsf T}s_i}

Start the backward pass with:

q = g

Process the history from newest to oldest. For each index i, compute:

\alpha_i = \rho_i s_i^{\mathsf T}q

Then update:

q = q - \alpha_i y_i

Use the newest history pair to scale the initial inverse-Hessian approximation:

\gamma = \frac{s_{m-1}^{\mathsf T}y_{m-1}}{y_{m-1}^{\mathsf T}y_{m-1}}

r = \gamma q

Process the history from oldest to newest. For each index i, compute:

\beta_i = \rho_i y_i^{\mathsf T}r

Then update:

r = r + s_i(\alpha_i - \beta_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.

Loading visualization...

Examples

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]

Hint 1

Store rho and alpha values while traversing history from newest to oldest.

Hint 2

Apply the newest-pair scale before traversing history from oldest to newest.

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

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:

\rho_i = \frac{1}{y_i^{\mathsf T}s_i}

Start the backward pass with:

q = g

Process the history from newest to oldest. For each index i, compute:

\alpha_i = \rho_i s_i^{\mathsf T}q

Then update:

q = q - \alpha_i y_i

Use the newest history pair to scale the initial inverse-Hessian approximation:

\gamma = \frac{s_{m-1}^{\mathsf T}y_{m-1}}{y_{m-1}^{\mathsf T}y_{m-1}}

r = \gamma q

Process the history from oldest to newest. For each index i, compute:

\beta_i = \rho_i y_i^{\mathsf T}r

Then update:

r = r + s_i(\alpha_i - \beta_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.