Problems

1 / 1

Matrix Factorization SGD Step

Recommender Systems

Easy

Matrix factorization is the backbone of modern recommender systems (popularized by the Netflix Prize). It approximates the user-item rating matrix as a product of two low-rank matrices: user factors U and item factors V. Each user and item is represented by a latent vector, and the predicted rating is their dot product.

Given a user latent vector U, an item latent vector V, a known rating r, a learning rate lr, and a regularization strength reg, perform one step of stochastic gradient descent to update both vectors.

Algorithm

Compute the prediction error:

e = r - U \cdot V

Update both vectors simultaneously using the old values:

U_i' = U_i + \text{lr} \cdot (e \cdot V_i - \text{reg} \cdot U_i)

V_i' = V_i + \text{lr} \cdot (e \cdot U_i - \text{reg} \cdot V_i)

Both U and V must be updated using their original (pre-update) values.

Loading visualization...

Examples

Input:

U = [1, 0], V = [0, 1], r = 5.0, lr = 0.1, reg = 0.0

Output:

U_new = [1.0, 0.5], V_new = [0.5, 1.0]

Dot product = 0. Error = 5.0 - 0 = 5.0. U[0] += 0.1 × 5.0 × 0 = 0. U[1] += 0.1 × 5.0 × 1 = 0.5. Similarly for V.

Input:

U = [0.5, 0.3], V = [0.4, 0.6], r = 4.0, lr = 0.01, reg = 0.02

Output:

U_new = [0.5145, 0.3216], V_new = [0.4180, 0.6108]

Dot product = 0.38. Error = 3.62. Each factor is updated by lr × (error × partner - reg × self).

Hint 1

First compute dot = sum(U[i] * V[i]). Then error = r - dot. Then compute both new vectors using list comprehensions: U_new[i] = U[i] + lr * (error * V[i] - reg * U[i]). Same pattern for V_new using original U.

Hint 2

The key pitfall is using updated U values when computing V_new. Make sure to compute both U_new and V_new from the original U and V. Store them in separate lists before returning.

Requirements

Compute the prediction error as r minus the dot product of U and V
Update U and V simultaneously using original (pre-update) values
Apply L2 regularization with strength reg to prevent overfitting
Return a tuple (U_new, V_new) where each is a list of floats

Constraints

U and V have the same length (latent dimension k >= 1)
lr > 0, reg >= 0
r is a number
Return a tuple of two lists of floats
Time limit: 300 ms

Try Similar Problems

User Based Cf Prediction Item Cf Predict Baseline Predictor Gradient Descent Quadratic Mean Rating Imputation

Prev Next

Matrix Factorization SGD Step

Recommender Systems

Easy

Given a user latent vector U, an item latent vector V, a known rating r, a learning rate lr, and a regularization strength reg, perform one step of stochastic gradient descent to update both vectors.

Algorithm

Compute the prediction error:

e = r - U \cdot V

Update both vectors simultaneously using the old values:

U_i' = U_i + \text{lr} \cdot (e \cdot V_i - \text{reg} \cdot U_i)

V_i' = V_i + \text{lr} \cdot (e \cdot U_i - \text{reg} \cdot V_i)

Both U and V must be updated using their original (pre-update) values.

Loading visualization...

Examples

Input:

U = [1, 0], V = [0, 1], r = 5.0, lr = 0.1, reg = 0.0

Output:

U_new = [1.0, 0.5], V_new = [0.5, 1.0]

Dot product = 0. Error = 5.0 - 0 = 5.0. U[0] += 0.1 × 5.0 × 0 = 0. U[1] += 0.1 × 5.0 × 1 = 0.5. Similarly for V.

Input:

U = [0.5, 0.3], V = [0.4, 0.6], r = 4.0, lr = 0.01, reg = 0.02

Output:

U_new = [0.5145, 0.3216], V_new = [0.4180, 0.6108]

Dot product = 0.38. Error = 3.62. Each factor is updated by lr × (error × partner - reg × self).

Hint 1

Hint 2

The key pitfall is using updated U values when computing V_new. Make sure to compute both U_new and V_new from the original U and V. Store them in separate lists before returning.

Requirements

Compute the prediction error as r minus the dot product of U and V
Update U and V simultaneously using original (pre-update) values
Apply L2 regularization with strength reg to prevent overfitting
Return a tuple (U_new, V_new) where each is a list of floats

Constraints

U and V have the same length (latent dimension k >= 1)
lr > 0, reg >= 0
r is a number
Return a tuple of two lists of floats
Time limit: 300 ms

Try Similar Problems

User Based Cf Prediction Item Cf Predict Baseline Predictor Gradient Descent Quadratic Mean Rating Imputation

Case 1

Case 2

U =

Accepts: array

V =

Accepts: array

r =

Accepts: number

lr =

Accepts: number

reg =

Accepts: number

Given a user latent vector U, an item latent vector V, a known rating r, a learning rate lr, and a regularization strength reg, perform one step of stochastic gradient descent to update both vectors.

Algorithm

Compute the prediction error:

e = r - U \cdot V

Update both vectors simultaneously using the old values:

U_i' = U_i + \text{lr} \cdot (e \cdot V_i - \text{reg} \cdot U_i)

V_i' = V_i + \text{lr} \cdot (e \cdot U_i - \text{reg} \cdot V_i)

Both U and V must be updated using their original (pre-update) values.