# Linear-cost unbiased posterior estimates for crossed effects and matrix factorization models via couplings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 58 references that are in the map.
- First posted on arXiv 11 Oct 2024.

## Builds on (most cited first, 16 of 16)

- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Estimating Convergence of Markov chains with L-Lag Couplings](https://mlsanity.com/paper/1905.09971/) (2019)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [Partially factorized variational inference for high-dimensional mixed models](https://mlsanity.com/paper/2312.13148/) (2023)
- [Scalable Bayesian computation for crossed and nested hierarchical models](https://mlsanity.com/paper/2103.10875/) (2021)
- [Scalable inference for crossed random effects models](https://mlsanity.com/paper/1803.09460/) (2018)
- [Maximal couplings of the Metropolis-Hastings algorithm](https://mlsanity.com/paper/2010.08573/) (2020)
- [Backfitting for large scale crossed random effects regressions](https://mlsanity.com/paper/2007.10612/) (2020)
- [On the identifiability of Bayesian factor analytic models](https://mlsanity.com/paper/2004.05105/) (2020)
- [Fast Moment-Based Estimation for Hierarchical Models](https://mlsanity.com/paper/1504.04941/) (2015)
- [Efficient moment calculations for variance components in large unbalanced crossed random effects models](https://mlsanity.com/paper/1602.00346/) (2016)
- [Streamlined Variational Inference for Linear Mixed Models with Crossed Random Effects](https://mlsanity.com/paper/1910.01799/) (2019)
- [Coupling-based convergence assessment of some Gibbs samplers for high-dimensional Bayesian regression with shrinkage priors](https://mlsanity.com/paper/2012.04798/) (2020)
- [Fast and Accurate Estimation of Non-Nested Binomial Hierarchical Models Using Variational Inference](https://mlsanity.com/paper/2007.12300/) (2020)
- [Unbiased Markov Chain Monte Carlo: what, why, and how](https://mlsanity.com/paper/2406.06851/) (2024)
- [Inference in generalized bilinear models](https://mlsanity.com/paper/2010.04896/) (2020)

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

- [Conjugate gradient methods for high-dimensional GLMMs](https://mlsanity.com/paper/2411.04729/) (2024)
- [Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression](https://mlsanity.com/paper/2505.14343/) (2025)

## Abstract (arXiv)

We design and analyze unbiased Markov chain Monte Carlo (MCMC) schemes based on couplings of blocked Gibbs samplers (BGSs), whose total computational costs scale linearly with the number of parameters and data points. Our methodology is designed for and applicable to high-dimensional BGS with conditionally independent blocks, which are often encountered in Bayesian modeling. We provide bounds on the expected number of iterations needed for coalescence for Gaussian targets, as well as on the tails of the coalescence times distribution. These imply that practical two-step coupling strategies achieve coalescence times that match the relaxation times of the original BGS scheme up to logarithmic factors. To illustrate the practical relevance of our methodology, we apply it to high-dimensional crossed random effect and probabilistic matrix factorization models, for which we develop a novel BGS scheme with improved convergence speed. Our methodology provides unbiased posterior estimates at linear cost (usually requiring only a few BGS iterations for problems with thousands of parameters), matching state-of-the-art procedures for both frequentist and Bayesian estimation of those models.