Recommender Systems

Background

Collaborative filtering dates to Tapestry (Xerox PARC, 1992) and was popularized by the Netflix Prize (2006-2009)
Recommender systems drive 35% of Amazon purchases and 75% of Netflix views
Matrix factorization (SVD) and deep learning embeddings are now the dominant approaches

The Concept

Recommender systems predict what items a user will like based on past behavior (collaborative filtering) or item/user attributes (content-based filtering), or both (hybrid). Matrix factorization decomposes the user-item interaction matrix into user and item embedding vectors.

How it Links

Matrix factorization directly generalizes to word2vec, BERT embeddings, and two-tower neural networks
The cold-start problem (new users/items) connects to few-shot learning
Content-based filtering is essentially feature-based regression/classification on item attributes

Concrete Example

Netflix recommendations: your watch history and ratings form one row in a giant user-item matrix. Factorization finds that you share a latent 'prefers thoughtful sci-fi' factor with thousands of others. Their highly-rated films you have not seen get recommended to you.

Prerequisites

Math you need: linear algebra, Linear regression, Logistic regression, Evaluation metrics

Learning outcomes

Distinguish memory-based collaborative filtering (user-user, item-item) from model-based matrix factorization, and explain why MF generalizes better on sparse data.
Derive the ALS and SGD updates for explicit-feedback matrix factorization with bias terms.
Explain why implicit feedback needs a confidence-weighted MSE (Hu-Koren-Volinsky) or a pairwise BPR loss instead of pointwise log-loss.
State the offline ranking metrics precision@k, recall@k, NDCG@k, and MAP, and derive NDCG.
Describe the production retrieval-then-ranking pipeline (two-tower retrieval feeding a ranking model) and the offline-online metric mismatch.

TL;DR

Recommender systems predict what a user will like next from a sparse history of interactions. Memory-based collaborative filtering (user-user and item-item) [1] recommends by similarity in the rating matrix; it is interpretable but does not generalize across sparsity. Matrix factorization [2] learns latent factors $p_u, q_i$ such that $\hat{r}_{ui} = \mu + b_u + b_i + p_u^\top q_i$ , fit by SGD or ALS, and was the engine of the Netflix Prize era. Implicit feedback (clicks, views) requires a different objective: the Hu-Koren-Volinsky weighted-MSE confidence model [3] or Bayesian Personalized Ranking [4], which optimizes a pairwise log-loss between observed and sampled-negative items and is an AUC surrogate. Factorization machines [5] generalize MF to arbitrary feature interactions. Modern production systems use a two-tower retrieval model feeding a ranking model [6], with sequential models (SASRec [7], BERT4Rec) capturing temporal order. Evaluate with precision@k, recall@k, NDCG@k [8], MAP, and AUC; the offline-online gap is real and the only thing that matters in production is the A/B test.

Intuition

A user-item interaction matrix $R \in \mathbb{R}^{n_u \times n_i}$ is the central object. It is overwhelmingly sparse (most users have rated a tiny fraction of items) and the recommendation problem is to predict the missing entries.

Three families of solution:

Memory-based CF. Compute pairwise similarities (cosine, Pearson) between rows (users) or columns (items) and predict by weighted average of similar users’ ratings or similar items’ ratings. Interpretable, no training, but does not extrapolate.
Model-based / matrix factorization. Learn low-rank latent factors $P \in \mathbb{R}^{n_u \times k}$ , $Q \in \mathbb{R}^{n_i \times k}$ with $R \approx P Q^\top$ . Latent factors generalize across sparsity: a user’s preference for “subtle European thrillers” is encoded in $p_u$ even if she has rated only one such film.
Hybrid / content-based. Blend MF with content features (genre, embeddings, side information). Mitigates cold-start and is the basis of all modern systems.

Why MF beats memory-based CF on sparse data

Memory-based CF can only recommend items that some similar user has rated; on long-tail items it has no signal at all. Matrix factorization compresses the user-item history into a low-dimensional latent space where similarity is geometric, not co-occurrence-based. A new item with only a handful of ratings still gets a useful $q_i$ , and the decomposition transfers preferences across sparsely-overlapping items [2].

Math

Matrix factorization with biases: the Netflix-prize objective

Model

\hat{r}_{ui} = \mu + b_u + b_i + p_u^\top q_i,

where $\mu$ is the global mean rating, $b_u$ and $b_i$ are user and item biases (some users rate uniformly higher; some items are simply more popular), and $p_u, q_i \in \mathbb{R}^{k}$ are latent factors. Typical $k$ is 20 to 200.

Objective (explicit feedback, observed entries only)

Let $\Omega = \{(u, i) : r_{ui} \text{ observed}\}$ . Minimize

\mathcal{L}(P, Q, b) = \sum_{(u, i) \in \Omega} \bigl(r_{ui} - \hat{r}_{ui}\bigr)^{2} + \lambda\, \bigl(\lVert p_u \rVert^{2} + \lVert q_i \rVert^{2} + b_u^{2} + b_i^{2}\bigr).

The sum over $\Omega$ (not all of $R$ ) is the key: missing entries are missing, not zero. Treating them as zero is a standard mistake on explicit feedback.

SGD updates

For one observation $(u, i)$ with prediction error $e_{ui} = r_{ui} - \hat{r}_{ui}$ :

b_u \leftarrow b_u + \eta\,(e_{ui} - \lambda b_u), \qquad b_i \leftarrow b_i + \eta\,(e_{ui} - \lambda b_i),

p_u \leftarrow p_u + \eta\,(e_{ui}\, q_i - \lambda\, p_u), \qquad q_i \leftarrow q_i + \eta\,(e_{ui}\, p_u - \lambda\, q_i).

These are standard squared-loss SGD updates with $\ell_2$ regularization. Cheap per step, embarrassingly parallel across $(u, i)$ pairs.

ALS: closed-form per-block updates

When all $\{q_i\}$ are fixed, the loss is a quadratic in each $p_u$ alone (the user-blocks decouple). Setting the gradient to zero:

p_u = \bigl(Q_{\Omega_u}^\top Q_{\Omega_u} + \lambda I\bigr)^{-1}\, Q_{\Omega_u}^\top \bigl(r_u - \mu - b_u - b\bigr),

where $Q_{\Omega_u}$ stacks the rows of $Q$ for the items user $u$ rated. By symmetry, the $\{q_i\}$ updates are analogous with $P_{\Omega_i}$ . Alternating (fix $Q$ , solve for $P$ ; fix $P$ , solve for $Q$ ) gives ALS [2]. Each update is a small ridge regression, embarrassingly parallel across users (or items), and the loss is non-increasing across alternations.

When to choose SGD vs ALS

SGD is faster on dense data and easy to extend to non-quadratic losses.
ALS parallelizes trivially across users (and across items) and is the right choice on Spark / distributed settings.
For implicit feedback below, ALS-style closed-form updates are essential because the loss sums over all (user, item) pairs.

Implicit feedback: the Hu-Koren-Volinsky confidence model

Setup

In the implicit setting we observe interaction counts $r_{ui}$ (clicks, plays, watch time) but no explicit “dislike” signal. We cannot fit $r_{ui}$ directly because the absence of an interaction is ambiguous: “user did not see it” versus “user saw and ignored”.

Hu, Koren, and Volinsky [3] introduce two derived quantities per pair:

p_{ui} = \begin{cases} 1 & r_{ui} > 0 \\ 0 & r_{ui} = 0 \end{cases}, \qquad c_{ui} = 1 + \alpha\, r_{ui},

where $p_{ui}$ is the “preference” (binary) and $c_{ui}$ is the confidence (always $\ge 1$ , larger when the user interacted more). Typical $\alpha = 40$ .

Objective

Minimize the confidence-weighted squared loss over all $(u, i)$ :

\mathcal{L}(P, Q) = \sum_{u, i} c_{ui}\, \bigl(p_{ui} - p_u^\top q_i\bigr)^{2} + \lambda \bigl(\lVert P \rVert_F^{2} + \lVert Q \rVert_F^{2}\bigr).

Unobserved pairs ( $r_{ui} = 0$ ) are included with $p_{ui} = 0$ and $c_{ui} = 1$ : low-confidence negative signal.

Closed-form ALS update

Because the loss sums over all pairs, the per-user update has a closed form in $O(k^2 n_i)$ per user (with a clever reformulation that keeps it tractable):

p_u = \bigl(Q^\top C_u Q + \lambda I\bigr)^{-1} Q^\top C_u\, p_{u},

where $C_u = \operatorname{diag}(c_{u1}, \dots, c_{u n_i})$ . The trick: $Q^\top C_u Q = Q^\top Q + Q^\top (C_u - I) Q$ , and only the second term varies per user, with $C_u - I$ supported only on the observed items.

This is the standard “implicit ALS” algorithm. It is the engine of the Spark ALS recommender and many production systems.

Bayesian Personalized Ranking: pairwise log-loss as an AUC surrogate

Motivation

Pointwise log-loss treats every (user, item) example independently and is dominated by the (vast) majority of unobserved-pair zeros. We do not actually care about predicting probabilities accurately; we care about ranking relevant items above irrelevant ones.

Triplets and the BPR loss

For each user $u$ , sample triplets $(u, i, j)$ where $i$ is an observed (positive) item and $j$ is a sampled negative (typically uniform over unobserved items). Define $\hat{x}_{uij} = \hat{x}_{ui} - \hat{x}_{uj}$ and minimize

\mathcal{L}_{\text{BPR}} = -\sum_{(u, i, j) \in D_S} \log \sigma\bigl(\hat{x}_{uij}\bigr) + \lambda \lVert \theta \rVert^{2},

where $\sigma(z) = 1 / (1 + e^{-z})$ and $\theta$ are the model parameters [4].

Why this is an AUC surrogate

The empirical AUC of a per-user ranking is

\operatorname{AUC}_u = \frac{1}{|I_u^{+}|\,|I_u^{-}|} \sum_{i \in I_u^{+}} \sum_{j \in I_u^{-}} \mathbb{1}[\hat{x}_{ui} > \hat{x}_{uj}].

Replacing the indicator with $\sigma(\hat{x}_{ui} - \hat{x}_{uj})$ gives a smooth lower bound, and taking the negative log yields the BPR loss. So BPR is directly optimizing a smooth approximation to per-user AUC.

SGD update (matrix factorization variant)

For a triplet $(u, i, j)$ and the MF model $\hat{x}_{ui} = p_u^\top q_i$ :

e = 1 - \sigma(\hat{x}_{uij}),

p_u \leftarrow p_u + \eta\,(e\,(q_i - q_j) - \lambda\, p_u),

q_i \leftarrow q_i + \eta\,(e\, p_u - \lambda\, q_i), \qquad q_j \leftarrow q_j - \eta\,(e\, p_u + \lambda\, q_j).

BPR with negative sampling scales linearly per epoch in the number of observed interactions.

Factorization machines

Factorization machines [5] generalize MF to arbitrary feature vectors $x \in \mathbb{R}^{p}$ (which may concatenate user-id one-hots, item-id one-hots, side features, contexts, etc.). The order-2 FM is

\hat{y}(x) = w_0 + \sum_{j=1}^{p} w_j\, x_j + \sum_{j=1}^{p} \sum_{\ell = j+1}^{p} \langle v_j, v_\ell \rangle\, x_j x_\ell,

with each pairwise interaction parameterized by a low-rank inner product $\langle v_j, v_\ell \rangle$ rather than a free coefficient. The trick: the pairwise sum has a closed-form rewrite

\sum_{j < \ell} \langle v_j, v_\ell \rangle x_j x_\ell = \tfrac{1}{2}\sum_{f=1}^{k} \!\Bigl[\bigl(\textstyle\sum_j v_{jf} x_j\bigr)^{2} - \sum_j v_{jf}^{2} x_j^{2}\Bigr],

so each prediction is $O(k p)$ , not $O(k p^{2})$ . FMs subsume MF (with one-hot user and item ids) and have a clean field-aware extension (FFM, 2016) that took several display-ad CTR competitions.

Modern production: retrieval and ranking are different model classes

Industrial recommenders almost always look like this:

Stage	Goal	Model class	Latency target
Candidate generation (retrieval)	Pull a few hundred plausible items from a catalog of millions	Two-tower / dual-encoder, approximate nearest neighbor (FAISS, ScaNN), embedding-based retrieval	p50 ~10ms; offline ANN index update daily.
Ranking	Score the few hundred candidates by predicted engagement	Wide-and-deep, DLRM, gradient-boosted trees over candidate features, sequential transformers	p50 ~50-200ms; trained on hours-old logs.
Re-ranking / business logic	Diversify, dedupe, apply business rules, exploration	Heuristics + bandits + MMR-style diversification	p50 ~10ms.

Why retrieval and ranking are different model classes

Retrieval must score every item in the catalog (or a sub-linear approximation) for a query, so it is forced into a model with separable user and item embeddings: the user tower and item tower run independently, the score is an inner product, and an ANN index serves it in milliseconds.

Ranking sees only a few hundred candidates per request and can afford a joint model that mixes user, item, and context features arbitrarily (cross-features, sequence transformers, gradient-boosted trees on top). The two-stage design is what makes it possible to serve recommendations from a catalog of $10^{8}$ items at p99 latency below 200ms [6].

Sequential models such as SASRec [7] (causal self-attention over a user’s interaction history) and BERT4Rec (masked-token prediction over the same) are the modern ranking-stage workhorses. They model that the order of interactions carries signal that bag-of-items encodings discard.

Evaluation: ranking metrics

Precision@k, recall@k, NDCG@k, MAP

Precision and recall at k

Let $R_k(u)$ be the top- $k$ items the model returns for user $u$ , and $T(u)$ the held-out relevant items.

\operatorname{precision@}k = \frac{|R_k(u) \cap T(u)|}{k}, \qquad \operatorname{recall@}k = \frac{|R_k(u) \cap T(u)|}{|T(u)|}.

Average over users. Cheap and intuitive but ignore order within the top- $k$ .

Discounted cumulative gain (DCG)

Assign each item rank $i$ in the prediction a relevance grade $\operatorname{rel}_i \in \{0, 1, \dots, R\}$ . The discounted gain is

\operatorname{DCG}_k = \sum_{i=1}^{k} \frac{2^{\operatorname{rel}_i} - 1}{\log_2(i + 1)}.

The numerator $2^{\operatorname{rel}} - 1$ rewards highly-relevant items disproportionately; the denominator $\log_2(i + 1)$ down-weights lower positions [8].

Normalized DCG

\operatorname{NDCG}_k = \frac{\operatorname{DCG}_k}{\operatorname{IDCG}_k},

where $\operatorname{IDCG}_k$ is the ideal DCG (the same formula on the optimally-sorted relevance list). NDCG ranges in $[0, 1]$ and is comparable across users with different numbers of relevant items.

Mean Average Precision (MAP)

Per user, compute precision at each rank where a relevant item appears, average over those ranks (Average Precision = AP), and then average AP over users:

\operatorname{AP}_u = \frac{1}{|T(u)|} \sum_{i=1}^{k} \operatorname{precision@}i \cdot \mathbb{1}[\text{item at rank } i \in T(u)].

MAP rewards getting relevant items high in the list and is the standard metric in IR.

Hit Rate@k

$\operatorname{HR@}k = \mathbb{1}[|R_k(u) \cap T(u)| > 0]$ , averaged over users. Brutal but useful: did we put any relevant item in the top- $k$ ?

AUC

Per user, the fraction of (relevant, irrelevant) pairs the model orders correctly. This is the metric BPR optimizes a smooth surrogate of.

Offline metrics are not online metrics

The hard truth of recommender systems: a 5% lift in offline NDCG can translate to anywhere from -1% to +3% in online clickthrough or watch time, depending on how the model interacts with feedback loops, position bias, exploration, and presentation. The only way to know is to A/B test. Offline evals are useful for ranking candidate models, not for picking the production champion.

How the families compare

Method	Handles cold start (new user/item)?	Handles implicit feedback?	Scales to 100M users?	Captures latent factors?	Eval metric
User-User CF	no (needs neighbors)	with similarity tweaks	no (n^2 similarity)	no (rating averages)	precision@k, recall@k
Item-Item CF	partial (precomputed item-item table works for new users with any history)	with similarity tweaks	with truncation, yes	no	precision@k, recall@k
Matrix Factorization (explicit)	no (no factors for new ids)	no (use HKV instead)	yes (ALS / SGD)	yes	RMSE, NDCG
Implicit ALS (HKV)	no for ids; yes if combined with content	yes (its design goal)	yes (Spark ALS)	yes	NDCG, recall@k, AUC
BPR-MF	no for ids	yes (designed for it)	yes (SGD with negative sampling)	yes	AUC, NDCG
Two-tower retrieval	yes (content features in the towers)	yes	yes (linear in n + ANN serving)	yes (learned embeddings)	recall@k

Implementations

The numpy version implements explicit-feedback MF with biases via SGD on a hard-coded ratings matrix. The PyTorch version is the modern equivalent with gradient-based training. The surprise-style sketch shows the classic single-machine API (note: surprise does not run under Pyodide, so the sketch is shown for shape comparison only).

python

import numpy as np

def fit_mf_sgd(ratings, k=8, n_epochs=50, lr=0.01, lam=0.05, seed=0):
  """Explicit-feedback matrix factorization with biases. ratings is a
  list of (u, i, r) tuples."""
  rng = np.random.default_rng(seed)
  users = np.array([r[0] for r in ratings])
  items = np.array([r[1] for r in ratings])
  vals = np.array([r[2] for r in ratings], dtype=float)

  n_u = users.max() + 1
  n_i = items.max() + 1
  mu = vals.mean()
  bu = np.zeros(n_u)
  bi = np.zeros(n_i)
  P = 0.1 * rng.normal(size=(n_u, k))
  Q = 0.1 * rng.normal(size=(n_i, k))

  for epoch in range(n_epochs):
      order = rng.permutation(len(ratings))
      for j in order:
          u, i, r = users[j], items[j], vals[j]
          pred = mu + bu[u] + bi[i] + P[u] @ Q[i]
          e = r - pred
          bu[u] += lr * (e - lam * bu[u])
          bi[i] += lr * (e - lam * bi[i])
          P_u_old = P[u].copy()
          P[u] += lr * (e * Q[i] - lam * P[u])
          Q[i] += lr * (e * P_u_old - lam * Q[i])
  return mu, bu, bi, P, Q

# Tiny example: 4 users, 5 items, sparse ratings on a 1-5 scale.
ratings = [
  (0, 0, 5), (0, 1, 3), (0, 3, 4),
  (1, 0, 4), (1, 2, 5), (1, 4, 2),
  (2, 1, 5), (2, 3, 4), (2, 4, 4),
  (3, 0, 2), (3, 2, 3), (3, 4, 5),
]
mu, bu, bi, P, Q = fit_mf_sgd(ratings, k=4, n_epochs=200)
print("predicted ratings (4x5):")
print(np.round(mu + bu[:, None] + bi[None, :] + P @ Q.T, 2))

Pure numpy SGD. Production code uses Cython, mini-batches, and JIT-compiled inner loops; the structure of the update is unchanged.

Run a tiny in-memory MF fit live on a 4-user / 5-item ratings matrix and inspect the predicted full matrix:

Idle (packages: numpy)

import numpy as np

# 4 users x 5 items, sparse ratings on a 1-5 scale (entries with 0 are unobserved).
R = np.array([
  [5, 3, 0, 4, 0],
  [4, 0, 5, 0, 2],
  [0, 5, 0, 4, 4],
  [2, 0, 3, 0, 5],
], dtype=float)

mask = R > 0
n_u, n_i = R.shape
k = 4

rng = np.random.default_rng(0)
P = 0.1 * rng.normal(size=(n_u, k))
Q = 0.1 * rng.normal(size=(n_i, k))
mu = R[mask].mean()
bu = np.zeros(n_u)
bi = np.zeros(n_i)

lr, lam, n_epochs = 0.02, 0.05, 500
for epoch in range(n_epochs):
  for u in range(n_u):
      for i in range(n_i):
          if not mask[u, i]:
              continue
          pred = mu + bu[u] + bi[i] + P[u] @ Q[i]
          e = R[u, i] - pred
          bu[u] += lr * (e - lam * bu[u])
          bi[i] += lr * (e - lam * bi[i])
          Pu_old = P[u].copy()
          P[u] += lr * (e * Q[i] - lam * P[u])
          Q[i] += lr * (e * Pu_old - lam * Q[i])

R_hat = mu + bu[:, None] + bi[None, :] + P @ Q.T
print("predicted ratings (rounded):")
print(np.round(R_hat, 2))
print("training RMSE:", round(np.sqrt(((R - R_hat)[mask] ** 2).mean()), 4))

(no output yet)

Real-world uses

Company / system	Stage	What changed historically
Netflix Prize (2006-2009)	Rating prediction	Popularized matrix factorization with biases; the SVD++ winner combined MF with implicit-feedback signals.
YouTube recommendations	Two-stage retrieval + ranking	Covington-Adams-Sargin 2016: candidate-generation deep neural network feeds a ranking deep neural network; explicit hyperparameter for "freshness".
Amazon product recommendations	Item-item CF + content	Item-item table famously precomputed offline; "customers who bought this also bought" remains a useful fallback even in the deep era.
Spotify Discover Weekly	Hybrid (CF + audio embeddings + NLP on playlist titles)	Combats cold-start by leaning on audio content embeddings for new tracks.
TikTok For You	Sequential ranking	Heavy use of sequential transformers and short-feedback signals (watch time, completion rate, replays).

Pitfalls

Cold start is not a side issue, it is the central problem

Pure ID-based matrix factorization has no factors for users or items unseen at training time. Any system that needs to recommend on day 1 - new users, new products, new content - must either fall back to popularity, use content features in the embedding model (two-tower with content towers), or run an explicit exploration policy (a contextual bandit). “We will deal with cold start later” is the line that kills many recsys launches.

Popularity bias amplifies itself through feedback loops

Models trained on logged interactions overweight already-popular items because users were exposed to them more. Without correction (inverse propensity weighting, exploration, off-policy evaluation), the model recommends popular items, which generates more popular-item interactions, which trains the next model. The feedback loop is the most under-discussed hazard in production recsys.

RMSE on ratings is a poor proxy for ranking quality

The classic Netflix-prize metric (RMSE on a 1-5 scale) optimizes pointwise calibration but is essentially uncorrelated with what users actually do (click, watch, buy). Modern systems train on implicit feedback with a ranking loss (BPR, listwise softmax, sampled softmax) and evaluate on NDCG@k or recall@k. Always report a ranking metric in addition to (or instead of) a regression metric.

Offline-online metric mismatch is the rule, not the exception

A 5% lift in offline NDCG can map to anywhere from -1% to +3% in online A/B test impact. The mismatch comes from selection bias in the logs, position bias, freshness, presentation effects, and feedback loops. Treat offline evals as a way to filter candidate models and run an A/B test before declaring victory.

Pop quiz

Check yourself

Score: 0 / 5(0 answered)

1. In the matrix factorization model r_hat_ui = mu + b_u + b_i + p_u . q_i, what role does b_u play?
2. Why does implicit-feedback MF use a confidence-weighted loss summed over ALL pairs, while explicit MF sums only over observed pairs?
3. What is BPR a smooth surrogate for?
4. Why are retrieval and ranking different model classes in production?
5. NDCG@k is preferred over precision@k when...

Interview Q&A

Derive ALS for explicit-feedback matrix factorization.onsite

Setup. With observed entries $\Omega = \{(u, i)\}$ , minimize

\mathcal{L}(P, Q) = \sum_{(u, i) \in \Omega} (r_{ui} - p_u^\top q_i)^{2} + \lambda(\lVert P \rVert_F^{2} + \lVert Q \rVert_F^{2}).

(Biases factor cleanly into the same updates; we omit them here for clarity.)

Block structure. With $Q$ fixed, $\mathcal{L}$ decomposes as a sum over users:

\mathcal{L}(P, Q) = \sum_u \!\Bigl[ \sum_{i \in \Omega_u} (r_{ui} - p_u^\top q_i)^{2} + \lambda \lVert p_u \rVert^{2} \Bigr] + \text{const in } P.

The user blocks decouple. Let $Q_{\Omega_u} \in \mathbb{R}^{|\Omega_u| \times k}$ stack the $q_i$ for $i \in \Omega_u$ and $r_u \in \mathbb{R}^{|\Omega_u|}$ the corresponding ratings. The user- $u$ subproblem is

\min_{p_u}\; \lVert r_u - Q_{\Omega_u} p_u \rVert_2^{2} + \lambda \lVert p_u \rVert^{2}.

Closed-form ridge solution.

p_u = (Q_{\Omega_u}^\top Q_{\Omega_u} + \lambda I_k)^{-1} Q_{\Omega_u}^\top r_u.

Symmetrically,

q_i = (P_{\Omega_i}^\top P_{\Omega_i} + \lambda I_k)^{-1} P_{\Omega_i}^\top r_i.

Algorithm. Alternate (fix $Q$ , solve all $p_u$ in parallel; fix $P$ , solve all $q_i$ in parallel) until convergence. Each block update is monotone non-increasing in $\mathcal{L}$ , so $\mathcal{L}$ converges [2].

Cost. Each user update is a $k \times k$ ridge solve, $O(k^{2}|\Omega_u| + k^{3})$ per user. Across users, embarrassingly parallel.

Why does matrix factorization beat memory-based collaborative filtering on sparse data?onsite

Coverage. Memory-based CF predicts $\hat{r}_{ui}$ from a weighted average of neighbors (similar users or similar items) who have rated item $i$ . On long-tail items, there may be zero such neighbors, so the model has no signal at all. MF, on the other hand, has $p_u$ and $q_i$ for every user and item, and the latent factors generalize across items the user has not interacted with.

Generalization through compression. MF compresses the sparse $n_u \times n_i$ rating matrix into two $k$ -rank tables ( $P, Q$ with $k \approx 50$ ). The $L_2$ -regularized loss explicitly trades fit for parsimony; the model only “spends” capacity on signals supported by enough data. Memory-based CF has no such regularization and treats every co-occurrence at face value.

Latent factors are interpretable as themes. A user who has rated only a handful of films but tends toward “subtle European thrillers” gets a $p_u$ that aligns with that subspace. New films in that subspace get a $q_i$ that scores well against $p_u$ even though no neighbor has rated them.

Empirical evidence. The Netflix Prize was won by ensembles dominated by MF variants (SVD++, timeSVD); pure user-user / item-item CF placed far behind [2][9].

Why do we use BPR loss instead of pointwise log-loss for implicit feedback?onsite

Pointwise log-loss problems. Treating each $(u, i)$ pair as a binary classification example with $y_{ui} = \mathbb{1}[r_{ui} > 0]$ is dominated by the (vast) majority of unobserved pairs. The model spends most of its capacity learning to predict $0$ for the bulk of the catalog, which is not the same as ranking observed items above unobserved ones.

The right objective is per-user AUC. What we actually want is, for each user $u$ with positive set $I_u^{+}$ and negative set $I_u^{-}$ :

\operatorname{AUC}_u = \frac{1}{|I_u^{+}|\,|I_u^{-}|} \sum_{i \in I_u^{+}} \sum_{j \in I_u^{-}} \mathbb{1}[\hat{x}_{ui} > \hat{x}_{uj}].

The indicator is non-differentiable; replace it with $\sigma(\hat{x}_{ui} - \hat{x}_{uj})$ and take $-\log$ to get the BPR loss [4]:

\mathcal{L}_{\text{BPR}} = -\sum_{(u, i, j)} \log \sigma(\hat{x}_{ui} - \hat{x}_{uj}) + \lambda \lVert \theta \rVert^{2}.

So BPR is a smooth, differentiable surrogate for AUC, which is exactly the ranking quantity we care about.

Practical advantage. BPR with negative sampling is $O(\text{positives})$ per epoch (one negative sampled per positive), not $O(n_u n_i)$ .

What strategies handle the cold-start problem?onsite

Three families, often combined:

Content features in the embedding model. A two-tower model where the user tower includes demographics / context and the item tower includes content features (text embeddings, image embeddings, genre, language, …) produces meaningful embeddings for new users and new items because the towers have learned how content features map to the latent space. This is the modern default.
Popularity prior + diversification. For brand-new users, fall back to popular items in their language and region; mix in a diversity prior so the user is exposed to multiple sub-domains and the next-step model gets signal.
Exploration via contextual bandits. Treat recommendation as a bandit: every recommendation collects observations that update the policy. UCB or Thompson sampling on user-item context features explicitly trades exploitation against exploration. This is what makes “discovery” surfaces (Spotify Discover Weekly, YouTube’s mixers) work.

In practice all three coexist: a two-tower retrieval model with content features handles structural cold start, a popularity prior handles unauthenticated traffic, and bandit-style exploration ensures the model keeps learning about niche content that is undersampled in the logs.

Build it yourself

A weekend project to internalize the recsys stack:

Implement explicit-feedback MF with biases via SGD (the numpy CodeCompare block) on the MovieLens 100K dataset and reach RMSE under 0.93 with $k = 50$ and tuned $\lambda$ .
Switch to implicit feedback by binarizing ratings ( $p_{ui} = 1$ for any rating) and implement HKV-style ALS. Compare to BPR-MF on NDCG@10 and recall@10.
Build a tiny two-tower model in PyTorch where the user tower takes (user id, age bucket, country) and the item tower takes (item id, genre one-hot). Train with sampled-softmax. Verify it produces non-trivial recommendations for cold-start users.
Stretch: implement a popularity baseline and verify your MF beats it on NDCG@10 - many production recsys efforts do not.

References

Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. (2001). Item-based collaborative filtering recommendation algorithms. Proc. 10th International World Wide Web Conference (WWW), 285-295. doi:10.1145/371920.372071
Koren, Y., Bell, R., and Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer 42(8), 30-37. doi:10.1109/MC.2009.263
Hu, Y., Koren, Y., and Volinsky, C. (2008). Collaborative filtering for implicit feedback datasets. Proc. 8th IEEE International Conference on Data Mining (ICDM), 263-272. doi:10.1109/ICDM.2008.22
Rendle, S., Freudenthaler, C., Gantner, Z., and Schmidt-Thieme, L. (2009). BPR: Bayesian personalized ranking from implicit feedback. Proc. 25th Conference on Uncertainty in Artificial Intelligence (UAI), 452-461. arXiv:1205.2618
Rendle, S. (2010). Factorization machines. Proc. IEEE International Conference on Data Mining (ICDM), 995-1000. doi:10.1109/ICDM.2010.127
Covington, P., Adams, J., and Sargin, E. (2016). Deep neural networks for YouTube recommendations. Proc. 10th ACM Conference on Recommender Systems (RecSys), 191-198. doi:10.1145/2959100.2959190
Kang, W.-C. and McAuley, J. (2018). Self-attentive sequential recommendation. Proc. IEEE International Conference on Data Mining (ICDM), 197-206. doi:10.1109/ICDM.2018.00035
Järvelin, K. and Kekäläinen, J. (2002). Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems 20(4), 422-446. doi:10.1145/582415.582418
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/

Dimensionality Reduction (PCA, t-SNE, UMAP)Multi-Layer Perceptron