Backfitting for large scale crossed random effects regressions
Swarnadip Ghosh, Trevor Hastie, Art B. Owen
The Annals of Statistics · 2022 · Volume 50 · Issue 1
Abstract
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, Roberts and Zanella (Biometrika 107 (2020) 25–40) 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.
Keywords
62J05, 65C60, collapsed Gibbs sampler, generalized least squares, mixed effect models
Enable JavaScript for citation tools and additional paper interactions.