Title: Scalability of coordinate-wise inference algorithms for Bayesian hierarchical models.

Abstract: We study coordinate-wise inference algorithms for Bayesian hierarchical models, seeking schemes whose total computational cost scales linearly with the number of observations and of parameters in the model. We focus on crossed random effects and nested multilevel models, which are ubiquitous in applied statistics, and consider methodologies built around Gibbs sampling, coordinate-ascent variational inference, and backfitting for maximum-a-posteriori estimation. For certain combinations of algorithm and model we establish theoretical guarantees for scalability and for others the lack thereof, leveraging connections to random graphs theory and statistical asymptotics. Crucially, the theoretical results provide methodological guidance to design algorithms with significantly improved cost-vs-accuracy tradeoff, as confirmed by various numerical simulations.