When do you fit matrix factorization with alternating least squares rather than SGD?

middlemust knowfreq 60%

answer

convex one side at a time
freeze one side, solve the other exactly
independent solves across users
no learning rate versus a k-cubed solve
all-cells objectives rule SGD out

basics

~20 s

Use alternating least squares when the per-user and per-item solves can be spread across a cluster, or when the loss covers every cell. Use SGD when ratings are sparse and observed-only, and you want a cheap, easily extended update.

solid answer

~50 s

The joint loss over user factors P and item factors Q is not convex, but it is convex in either one with the other held fixed. ALS exploits that: freeze Q, and each user's factor vector is the solution of a small ridge regression over the items that user rated — a closed-form k x k solve. Freeze P and mirror it per item. Every user solve is independent, so a sweep parallelises across machines with no coordination and there is no learning rate to tune; the cost is a k x k inverse per user, growing as k^3. SGD instead walks observed ratings one at a time, nudging p_u and q_i by the residual. It touches only observed cells, so on a 99%-empty explicit matrix it is far cheaper per epoch and extends easily, but it needs a learning-rate schedule and is sequential.

The joint loss over user factors `P` and item factors `Q` is not convex, but it is convex in either one with the other held fixed. ALS exploits that: freeze `Q`, and each user's factor vector is the solution of a small ridge regression over the items that user rated — a closed-form `k x k` solve. Freeze `P` and mirror it per item. Every user solve is independent, so a sweep parallelises across machines with no coordination and there is no learning rate to tune; the cost is a `k x k` inverse per user, growing as `k^3`. SGD instead walks observed ratings one at a time, nudging `p_u` and `q_i` by the residual. It touches only observed cells, so on a 99%-empty explicit matrix it is far cheaper per epoch and extends easily, but it needs a learning-rate schedule and is sequential.

code

python · 21 lines

python

import random
random.seed(7)
k = 3
p = [random.uniform(-0.1, 0.1) for _ in range(k)]   # one user's factors
q = [random.uniform(-0.1, 0.1) for _ in range(k)]   # one film's factors
mu, b_u, b_i = 3.7, 0.4, -0.2                       # global, user, item bias
lr, lam = 0.02, 0.05                                # step size, L2 strength
r = 5.0                                             # the one observed rating

def predict():
    return mu + b_u + b_i + sum(p[f] * q[f] for f in range(k))

for step in range(4):
    e = r - predict()                               # residual on this cell
    b_u += lr * (e - lam * b_u)
    b_i += lr * (e - lam * b_i)
    p_old = p[:]                                    # update both sides together
    for f in range(k):
        p[f] += lr * (e * q[f] - lam * p[f])
        q[f] += lr * (e * p_old[f] - lam * q[f])
    print(step, "error", round(e, 4), "prediction", round(predict(), 4))

go deeper

for a junior

Be ready to say that ALS freezes one side and solves the other exactly while SGD nudges both vectors one rating at a time, and that only SGD needs a learning rate.

for a middle

Explain biconvexity, write the per-user ridge solve ALS performs, give the SGD update for a single observed cell, and state the cost of each in terms of the latent dimension.

for a senior

Show you choose by constraints, not habit: cluster versus single machine, observed-only versus all-cells objective, and how much the model is still changing shape.

for a principal

Own the platform consequence — which fitting strategy your infrastructure and retraining cadence can actually sustain, and whether the operational simplicity of a tuning-free fit outweighs raw convergence speed.

The optimisation problem

You are minimising

loss(P, Q) = sum over observed (u,i) of (r_ui - dot(p_u, q_i))^2 + lambda * (||P||^2 + ||Q||^2)

(plus bias terms, omitted here for clarity). This function is not jointly convex in P and Q — the product of two unknowns never is — so neither method finds a global optimum, and both depend on initialisation. What the loss is is biconvex: fix Q and it is an ordinary regularized least-squares problem in P, and vice versa. That single fact is the whole basis of ALS.

Alternating least squares

One sweep is two half-steps.

Half-step one: hold every item vector fixed. Then user u's rows are an independent ridge regression — the targets are that user's observed ratings, the design rows are the fixed factor vectors of the items they rated. The solution is closed form: build the k x k matrix Q_u^T Q_u + lambda I where Q_u stacks the vectors of the items user u rated, and solve against Q_u^T r_u. Cost per user is roughly k^2 * n_u to build plus k^3 to solve, where n_u is that user's rating count.

Half-step two: hold every user vector fixed and do the mirror image per item.

Properties that follow directly:

Monotone. Each half-step solves its subproblem exactly, so the objective never increases. You get a clean convergence curve and no divergence.
Embarrassingly parallel. With Q frozen, no two user solves interact. Partition users across machines, broadcast the item factors, collect the results. This is the reason ALS became the standard distributed recommender fit.
No learning rate. Only k and lambda to tune, which removes the most fragile knob.
Cubic in k. The k x k solve means the per-solve cost grows as k^3. Going from 20 factors to 200 multiplies that term by about a thousand, so ALS gets expensive at high rank.
Memory-hungry per solve. You need the fixed side's factors available wherever the solves run.

Stochastic gradient descent

Iterate over the observed ratings in random order. For each one compute the residual and move both vectors:

e = r_ui - r_hat(u, i)
p_u <- p_u + lr * (e * q_i - lambda * p_u)
q_i <- q_i + lr * (e * p_u_old - lambda * q_i)

Note that both sides use the pre-update value of the other, and that the update for the user factor is driven by the item factor and vice versa — the gradient of a product.

Properties:

Cost scales with observed ratings only. One epoch is O(observed * k), linear in k, not cubic. On a 99%-empty explicit matrix with a large rank this beats ALS comfortably.
Easy to extend. Adding bias terms, time-varying effects, implicit-signal terms or side features means writing one more update line. Getting the same term into an ALS closed form means re-deriving the normal equations.
Sequential and tuning-sensitive. Two updates that touch the same popular item conflict, so naive parallelism has write races (lock-free schemes exist and mostly work because the matrix is sparse). You must choose a learning rate and a decay schedule, and a bad one either crawls or blows up.

Choosing between them

The decision hinges on three questions.

Does the loss sum over observed cells only, or over every cell? If your objective weights all user-item pairs — the standard formulation for implicit data — SGD over billions of cells is hopeless, while ALS restructures the normal equations so the all-cells sum stays affordable. This alone settles most implicit-data cases in favour of ALS.

Where does it run? On a cluster, ALS's independent per-user solves map onto data-parallel execution with almost no communication beyond broadcasting the frozen side. On one machine with a sparse explicit dataset, SGD usually converges in fewer wall-clock minutes.

How exotic is the model? Every extra term the research literature adds to plain factorization — temporal drift, implicit-signal augmentation, side features — was easier to bolt onto an SGD loop. If your model is still evolving, SGD keeps the derivative work small.

Things both share

Neither escapes the non-convexity, so initialise small and random (all-zeros gives zero gradients through the product and never breaks symmetry), and expect run-to-run variation in the factors even when held-out error is stable. Both need the same k and lambda chosen on a validation split, and for both the honest evaluation split for a recommender is time-based rather than random, so you are not predicting the past from the future.

## The optimisation problem You are minimising ``` loss(P, Q) = sum over observed (u,i) of (r_ui - dot(p_u, q_i))^2 + lambda * (||P||^2 + ||Q||^2) ``` (plus bias terms, omitted here for clarity). This function is **not jointly convex** in `P` and `Q` — the product of two unknowns never is — so neither method finds a global optimum, and both depend on initialisation. What the loss *is* is **biconvex**: fix `Q` and it is an ordinary regularized least-squares problem in `P`, and vice versa. That single fact is the whole basis of ALS. ## Alternating least squares One sweep is two half-steps. **Half-step one:** hold every item vector fixed. Then user `u`'s rows are an independent ridge regression — the targets are that user's observed ratings, the design rows are the fixed factor vectors of the items they rated. The solution is closed form: build the `k x k` matrix `Q_u^T Q_u + lambda I` where `Q_u` stacks the vectors of the items user `u` rated, and solve against `Q_u^T r_u`. Cost per user is roughly `k^2 * n_u` to build plus `k^3` to solve, where `n_u` is that user's rating count. **Half-step two:** hold every user vector fixed and do the mirror image per item. Properties that follow directly: - **Monotone.** Each half-step solves its subproblem exactly, so the objective never increases. You get a clean convergence curve and no divergence. - **Embarrassingly parallel.** With `Q` frozen, no two user solves interact. Partition users across machines, broadcast the item factors, collect the results. This is the reason ALS became the standard distributed recommender fit. - **No learning rate.** Only `k` and `lambda` to tune, which removes the most fragile knob. - **Cubic in `k`.** The `k x k` solve means the per-solve cost grows as `k^3`. Going from 20 factors to 200 multiplies that term by about a thousand, so ALS gets expensive at high rank. - **Memory-hungry per solve.** You need the fixed side's factors available wherever the solves run. ## Stochastic gradient descent Iterate over the observed ratings in random order. For each one compute the residual and move both vectors: ``` e = r_ui - r_hat(u, i) p_u <- p_u + lr * (e * q_i - lambda * p_u) q_i <- q_i + lr * (e * p_u_old - lambda * q_i) ``` Note that both sides use the *pre-update* value of the other, and that the update for the user factor is driven by the item factor and vice versa — the gradient of a product. Properties: - **Cost scales with observed ratings only.** One epoch is `O(observed * k)`, linear in `k`, not cubic. On a 99%-empty explicit matrix with a large rank this beats ALS comfortably. - **Easy to extend.** Adding bias terms, time-varying effects, implicit-signal terms or side features means writing one more update line. Getting the same term into an ALS closed form means re-deriving the normal equations. - **Sequential and tuning-sensitive.** Two updates that touch the same popular item conflict, so naive parallelism has write races (lock-free schemes exist and mostly work because the matrix is sparse). You must choose a learning rate and a decay schedule, and a bad one either crawls or blows up. ## Choosing between them The decision hinges on three questions. **Does the loss sum over observed cells only, or over every cell?** If your objective weights *all* user-item pairs — the standard formulation for implicit data — SGD over billions of cells is hopeless, while ALS restructures the normal equations so the all-cells sum stays affordable. This alone settles most implicit-data cases in favour of ALS. **Where does it run?** On a cluster, ALS's independent per-user solves map onto data-parallel execution with almost no communication beyond broadcasting the frozen side. On one machine with a sparse explicit dataset, SGD usually converges in fewer wall-clock minutes. **How exotic is the model?** Every extra term the research literature adds to plain factorization — temporal drift, implicit-signal augmentation, side features — was easier to bolt onto an SGD loop. If your model is still evolving, SGD keeps the derivative work small. ## Things both share Neither escapes the non-convexity, so initialise small and random (all-zeros gives zero gradients through the product and never breaks symmetry), and expect run-to-run variation in the factors even when held-out error is stable. Both need the same `k` and `lambda` chosen on a validation split, and for both the honest evaluation split for a recommender is time-based rather than random, so you are not predicting the past from the future.

Is the matrix factorization objective convex, and what does ALS actually converge to?
It is not jointly convex in the user and item factors — their product makes it non-convex — but it is convex in each block with the other fixed. ALS therefore decreases the objective monotonically and converges to a stationary point, not a global optimum. Different initialisations give different factor matrices, though held-out error is usually comparable.
How does the cost of ALS change if you move from 20 latent factors to 200?
Each user and item solve inverts a `k x k` matrix, so the solve term grows roughly as `k^3` — about a thousandfold from 20 to 200 — while building the matrix grows as `k^2` times the user's rating count. SGD grows only linearly in `k`, which is why high-rank fits on one machine favour SGD.
Can SGD for matrix factorization be parallelised?
Partially. Updates conflict only when two threads touch the same user or item row, and the matrix is sparse enough that lock-free updates usually converge in practice. A cleaner scheme partitions users and items into blocks so that concurrently processed blocks share no rows or columns. Neither is as effortless as ALS's independent solves.
Why should the factor matrices not be initialised to zero?
The gradient of a product is the other factor, so with both sides at zero every update is zero and nothing ever moves — and in ALS the frozen side contributes a zero design matrix. Standard practice is small random values, which breaks symmetry and keeps early predictions close to the bias-only baseline.

saying these in an interview costs you the question

Calls the joint factorization objective convex
Says ALS finds the global optimum
Claims SGD parallelises as cleanly as ALS
Ignores that ALS solve cost grows as k cubed
Initialises both factor matrices to zero

When do you fit matrix factorization with alternating least squares rather than SGD?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The optimisation problem

Alternating least squares

Stochastic gradient descent

Choosing between them

Things both share

▾common follow-ups4 questions

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The optimisation problem

Alternating least squares

Stochastic gradient descent

Choosing between them

Things both share

answer

go deeper

context