  We analyze the complexity of Gibbs samplers for inference in crossed random
effect models used in modern analysis of variance. We demonstrate that for
certain designs the plain vanilla Gibbs sampler is not scalable, in the sense
that its complexity is worse than proportional to the number of parameters and
data. We thus propose a simple modification leading to a collapsed Gibbs
sampler that is provably scalable. Although our theory requires some
balancedness assumptions on the data designs, we demonstrate in simulated and
real datasets that the rates it predicts match remarkably the correct rates in
cases where the assumptions are violated. We also show that the collapsed Gibbs
sampler, extended to sample further unknown hyperparameters, outperforms
significantly alternative state of the art algorithms.
