# ALS vs SGD in parallelization

So given the standard objective in matrix factorization for collaborative filtering of minimizing:

$$L = \sum_{u,i \in S} (r_{ui}-q_i^Tp_u)^2 + \lambda(\sum_i||q_i^2||+\sum_u||p_u^2||)$$ , where $$r_{ui}$$ is the rating by user $$u$$ on movie $$i$$, $$p_u$$ is the $$u$$th row of user embedding matrix $$P$$ and $$q_i$$ is the $$i$$th row of the movie embedding matrix $$Q$$.

The two most common way to solve are Alternating Least Squares and Stochastic Gradient Descent.

ALS does so by alternating between holding $$p_u$$ or $$q_i$$ fixed and solves the least-squares problem: $$q_i=R_uP(P^TP+\lambda I)^{-1}$$ $$p_u=R_iQ(Q^TQ+\lambda I)^{-1}$$

SGD does so by iterating through each training case and update accordingly: $$q_i = q_i + \gamma(e_{ui}*p_u - \lambda*q_i)$$ $$p_u = p_u + \gamma(e_{ui}*q_i - \lambda*p_u)$$ $$e_{ui} = r_{ui}-q_i^Tp_u$$

A lot of the literatures I came across, such as this and this, say that ALS can be parallelized but implies SGD has difficulty doing so. I'm quite confused by this. It seems from the formula I could easily compute, for example, $$q_1$$, $$q_2$$, $$q_3$$ in parallel using the SGD formula. So what's the reason for SGD being difficult to parallelize here?

Literatures also mention that ALS has cubic time complexity in target rank? Could someone also explain this?

• re: cubic complexity, my SWAG is that this is because of the matrix inversions (though I know nothing about collaborative filtering). Aug 8, 2022 at 21:12

SGD can not be parallelised for a single model in vanilla form because it is a single update sequential algorithm by construction. However, SGD-based parallelisation is possible, running multiple streams of batches to construct (build) multiple models and then combine these models, i.e., model averaging. For neural networks, simple periodic-averaging works Parallel training of DNNs with Natural Gradient and Parameter Averaging. For collaborative filtering, similar approach could be implemented by introducing averaging procedure for the matrices that gives some convergence gurantees.

• I'm still not clear on why we can't do parallel in this particular case. Suppose the first training case is (user1, movie1) so we're updating $q_1$ and $p_1$ through the SGD. Now, if the next training case is (user1,movie2) or (user2,movie1), then it does make sense that we can't do the two trainings it in parallel because the updates are not independent. However, I don't see why we cannot run training in parallel for cases like (user2,movie2), (user3, movie3), etc... as their updates have no effect on each other Aug 9, 2022 at 14:40
• Updating $q_1$ updates a row Q in Q in R=QP factorization, so it can potentially affect every entry of $R$, not just the (user1, movie1) entry. Think of what happens when R is rank-1 Aug 9, 2022 at 16:21
• @YaroslavBulatov but that's exactly what we're doing in parallel in ALS, no? Updating $q_1$, $q_2$, etc at the same time. Aug 11, 2022 at 14:50
• Because ALS parallel update is "smart" :) Set regularization to zero, your ALS update is $R P(P^T P)^{-1}$, use formula for pseudo-inverse you get $R P^\dagger$. But if $P$ is invertible, pseudo-inverse is the inverse, so ALS update is $R P^{-1}$, cubic. On other hand your parallel SGD update is $R P^T$, quadratic cost. When are two updates the same? When $P$ is orthogonal matrix, which means examples are uncorrelated and on the same scale. Extra cost of ALS takes care of correlations, not trivial to do in parallel Aug 11, 2022 at 16:41
• PS, performing matrix inversion in ALS is equivalent to decorrelating examples (cubic cost) and applying gradient step. If you find a cheap way to "mostly" decorrelate examples, you get something almost as good as ALS at the cost of SGD. This is known as preconditioning. See this note I wrote -- machine-learning-etc.ghost.io/preconditioners-in-optimization Aug 11, 2022 at 16:45

Note that first update is the standard linear least squares estimation equation, more traditionally written as $$(X^T X)^{-1} X^T y =X^\dagger y$$, whereas your SGD version formulation comes down to solving this system one row at a time. Hence you get the same issue in parallelizing SGD as with a standard least squares problem.

Basic issue is that your examples may interact, and this lowers the efficiency of parallel updates. For instance, two updates could cancel out when applied in parallel, but not cancel out when applied in sequence.

We can look at theory of linear estimation to figure out the limits of parallelism, ie, this paper, and my notes on it here.

If you plot per-step improvement as a function of batch size, it may look something like below, at some point the additional improvement in loss is almost unchanged by increasing number of parallel updates. Here you see that using 1 SGD step with batch size 200 gives almost the same improvement as 7 SGD steps with batch size 1 To summarize: with proper tuning of $$\gamma$$, you'll be able to apply up to $$k$$ updates in parallel where $$k$$ is the "critical batch size." Critical batch size is the point at which your "parallel update" strategy starts exhibiting diminishing returns. In the plot above, critical batch size is about 10 since that's the point where you cross y=0.5x line. Basically it's the point where gain from each new example added in parallel is less than 0.5 of the gain of processing this example serially.

To estimate critical batch size for your problem, you could assume your $$p$$s and $$q$$ are normally distributed with second moment matrix $$\Sigma$$. Hessian of corresponding optimization problem is $$H=\Sigma$$.

Critical batch size is determined by one of the two effective ranks below (from this paper): The first rank gives "worst-case" critical batch size, if you "get unlucky" with the location of the optimum relative to current position, while the second is applicable when all directions towards the optimum are equally likely.

To apply this to your problem, to establish the limit of SGD parallelism, you would evaluate $$r(P^T P)$$, and $$r(Q^T Q)$$. This would give you a lower estimate on the largest batch size you could use for your parallel updates on $$q$$ and on $$p$$. Evaluating $$R(P^T P)$$ and $$R(Q^T Q)$$ would give you an upper estimate on batch size.

• What kind of norm is $\vert| \Sigma \vert|_{op}$? Aug 9, 2022 at 14:10
• operator norm (largest singular value) Aug 9, 2022 at 15:55