# Backfitting for large scale crossed random effects regressions

arXiv: https://arxiv.org/abs/2007.10612 · HTML: https://mlsanity.com/paper/2007.10612/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

## Built on by (most cited first, 6 of 6)

- [Quasi-Newton Quasi-Monte Carlo for variational Bayes](https://mlsanity.com/paper/2104.02865/) (2021)
- [Linear-cost unbiased posterior estimates for crossed effects and matrix factorization models via couplings](https://mlsanity.com/paper/2410.08939/) (2024)
- [Conjugate gradient methods for high-dimensional GLMMs](https://mlsanity.com/paper/2411.04729/) (2024)
- [Scalable and Calibrated Sampling for Bayesian Generalized Linear Mixed Model via Stochastic Gradient Markov Chain Monte Carlo](https://mlsanity.com/paper/2403.03007/) (2024)
- [Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression](https://mlsanity.com/paper/2403.13300/) (2024)
- [Scalable Krylov Subspace Methods for Generalized Mixed-Effects Models with Crossed Random Effects](https://mlsanity.com/paper/2505.09552/) (2025)

## Abstract (arXiv)

Regression models with crossed random effect errors can be very expensive to compute. The cost of both generalized least squares and Gibbs sampling can easily grow as N3/2 (or worse) for N observations. Papaspiliopoulos et al. (2020) present a collapsed Gibbs sampler that costs O(N), but under an extremely stringent sampling model. We propose a backfitting algorithm to compute a generalized least squares estimate and prove that it costs O(N). A critical part of the proof is in ensuring that the number of iterations required is O(1) which follows from keeping a certain matrix norm below 1-δ for some δ>0. Our conditions are greatly relaxed compared to those for the collapsed Gibbs sampler, though still strict. Empirically, the backfitting algorithm has a norm below 1-δ under conditions that are less strict than those in our assumptions. We illustrate the new algorithm on a ratings data set from Stitch Fix.