ALS vs SGD in parallelization

Question

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?

Answer 1

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.

Answer 2

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.