CME 323: Distributed Algorithms and Optimization, Spring 2015
http://stanford.edu/~rezab/dao.
Instructor: Reza Zadeh, Databricks and Stanford.
Lecture 14, 5/13/2015.
Yonathan Perez.

Scribed by Haoming Li, Bangzheng He, Michael Lublin,

14

Matrix Completion via Alternating Least Square(ALS)

14.1

Introduction

A common problem faced by internet companies is that of recommending new products to users
in personalized settings (e.g. Amazon’s product recommender system, and Netflix movie recommendations). This can be formulated as a learning problem in which we are given the ratings
that users have given certain items and are tasked with predicting their ratings for the rest of theitems. Formally, if there are n users and m items, we are given an n × m matrix R in which the(u, i)th entry is rui – the rating for item i by user u. Matrix R has many missing entries indicating
unobserved ratings, and our task is to estimate these unobserved ratings.

14.2

Matrix Factorization: Objective and ALS Algorithm on a Single Machine

A popular approach for this is matrix factorization, where we fix a relatively small number k(e.g. k ≈ 10), and summarize each user u with a k dimensional vector xu , and each item i with ak dimensional vector yi . These vectors are referred to as factors. Then, to predict user u’s rating
for item i, we simply predict rui ≈ x|u yi . This can be put in matrix form: Let x1 , . . . , xn ∈ Rk bethe factors for the users, and y1 , . . . , ym ∈ Rk the factors for the items. The k × n user matrix X,and the k × m item matrix Y are then defined by:||||
X = x1 · · · xn  , Y = y1 · · · ym ||||
Our goal is then to estimate the complete ratings matrix R ≈ X T Y . We can formulate thisproblem as an optimization problem in which we aim to minimize an objective function and findoptimal X and Y . In particular, we aim to minimize the least squares error of the observed ratings(and regularize):XXX
min(rui − x|u yi )2 + λ(kxu k2 +kyi k2 )(1)
X,Yurui observediNotice that this objective is non-convex (because of the xTu yi term); in fact it’s NP-hard tooptimize. Gradient descent can be used as an approximate approach here, however it turns out tobe slow and costs lots of iterations. Note however, that if we fix the set of variables X and treat
them as constants, then the objective is a convex function of Y and vice versa. Our approach will1

therefore be to fix Y and optimize X, then fix X and optimize Y , and repeat until convergence.
This approach is known as ALS(Alternating Least Squares). For our objective function, thealternating least squares algorithm is as follows:
Algorithm 1 ALS for Matrix Completion
Initialize X, Y
repeatfor u = 1 . . . n doxu = (−1yi yi| + λIk )Xrui ∈ru∗X

rui yi(2)

rui xu(3)

rui ∈ru∗end forfor i = 1 . . . m doyi = (X−1xu x|u + λIk )rui ∈r∗iX
rui ∈r∗i

end foruntil convergence
For a single machine we can analyze the computational cost of this algorithm. Updating eachxu will cost O(nu k 2 + k 3 ) where nu is the number of items rated by user u, and similarly updatingeach yi will cost O(ni k 2 + k 3 ) where ni is the number of users that have rated item i.
Once we’ve computed the matrices X and Y , there are several ways to do prediction. The
first is to do what was discussed before, which is to simply predict rui ≈ xTu yi for each user u anditem i. This approach will cost O(nmk) if we’d like to estimate every user-item pair. However,this approach is prohibitively expensive for most real-world datasets. A second (and more holistic)
approach is to use the xu and yi as features in another learning algorithm, incorporating thesefeatures with others that are relevant to the prediction task.

14.3

Distributed ALS

There are several ways to distribute the computation of the ALS algorithm(1) depending on how
we distribute the data.
Method 1 (join)First we consider a fully distributed version. In this setup all the data (ratings) and parameters (Xand Y ) are distributed (i.e. stored in an RDD). Specifically, ratings are stored as RDD of triplets:Ratings : RDD((u, i, rui ), . . . )This is reasonable since ratings are always sparse. We use dense representation for factor matrices
X and Y , and these are stored as RDDs of vectors:
X : RDD(x1 , . . . , xn )2

Y : RDD(y1 , . . . , ym )Recall equation(2) from the ALS algorithm(1):X−1 X
yi yi| +λIk )xu = (rui yi
rui ∈ru∗|{zA(4)rui ∈ru∗}|{zB}

To compute parts A and B, we can follow the steps below:
1. Join Ratings with Y factors using key i (items)
2. Map to compute yi yi| and change key to u (user)P
3. ReduceByKey u (user) to compute i yi yi|
4. Invert
5. Another ReduceByKey u(user) to computePrui yi

We can use the similar method to compute equation(3) too.
This approach will always work, but note that we are redoing the computation of yi yiT for eachuser that has rated item i. The next approach takes advantage of the fact that the X and Y factor
matrices are often very small and can be stored locally on each machine:Method 2 (broadcast)
1. Partition Ratings by user to create R1 , and similarly partition Ratings by item to create
R2 (so there are two copies of Ratings with different partitionings). In R1 , all ratings by
the same user are on the same machine, and in R2 all ratings for same item are on the samemachine.
2. Broadcast X, Y (These are now local matrices and not RDDs)
3. Using R1 and Y , we can use equation(2) to compute the update of xu locally on each machine
4. Using R2 and X, we can use equation(3) to compute the update of yi locally on each machine
A further optimization to this method is to group the X and Y factors into blocks (user blocksand item blocks) and reduce the communication by only sending to each machine the block of users(or items) that are needed to compute the updates at that machine. This method is called Block
ALS. It is achieved by precomputing some information about the ratings matrix to determine the“out-links” of each user(which blocks of the items it will contribute to) and “in-link” informationfor each item(which of the factor vectors it receives from each user block it will depend on). For
exmple, assume that machine 1 is responsible for users 1,2,...,37 – these will be block 1 of users.
The items rated by these users are block 1 of items. Only the factors of block 1 of users and block1 of items will be broadcasted to machine 1.
3

14.4

Streaming ALS

We now assume that ratings data rui is streaming in, and that factor matrices X, Y fit in memory ofeach machine. We assume that the stream is shuffled and can use Stochastic Gradient Descent(SGD)
to update the X, Y factor matrices.
Algorithm 2 Streaming ALS using SGD
for new rui doxu ← xu − α(rui − x|u yi )yi + λxu
yi ← yi − α(rui − x|u yi )xu + λyi
end for

14.5

Other methods for Matrix Factorization

Other methods for matrix factorization include:• Sparse Subspace Embedding[1]• Generalized Low Rank Models(GLRM)[2]• Fast ALS[3]References[1] Kenneth L. Clarkson and David P. Woodruff. STOC, 2013.
[2] Madeleine Udell, Corinne Horn, Reza Zadeh, Stephen Boyd. Generalized Low Rank Models.
[3] Trevor Hastie, Rahul Mazumder, Jason D. Lee, Reza Zadeh Matrix Completion and LowRank SVD via Fast Alternating Least Squares. Statistics Department and ICME, Stanford
University, 2014.

4