  The crossed random effects model is widely used, finding applications in
various fields such as longitudinal studies, e-commerce, and recommender
systems, among others. However, these models encounter scalability challenges,
as the computational time for standard algorithms grows superlinearly with the
number N of observations in the data set, commonly $\Omega(N^{3/2})$ or worse.
Recent work has developed scalable methods for crossed random effects in linear
models and some generalized linear models, but those works only allow for
random intercepts. In this paper we devise scalable algorithms for models that
include random slopes. This problem brings a substantial difficulty in
estimating the random effect covariance matrices in a scalable way. We address
that issue by using a variational EM algorithm. In simulations, we see that the
proposed method is faster than standard methods. It is also more efficient than
ordinary least squares which also has a problem of greatly underestimating the
sampling uncertainty in parameter estimates. We illustrate the new method on a
large dataset (five million observations) from the online retailer Stitch Fix.
