Matrix Factorization SGD Step
Matrix Factorization SGD Step
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:
- Update both vectors simultaneously using the old values:
Both U and V must be updated using their original (pre-update) values.
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
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number
Accepts: number
Matrix Factorization SGD Step
Matrix Factorization SGD Step
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:
- Update both vectors simultaneously using the old values:
Both U and V must be updated using their original (pre-update) values.
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
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number
Accepts: number