Batch, match, and patch: low-rank approximations for score-based variational inference

Chirag Modi, Diana Cai, Lawrence K. Saul

Abstract

Black-box variational inference (BBVI) scales poorly to high-dimensional problems when it is used to estimate a multivariate Gaussian approximation with a full covariance matrix. In this paper, we extend the batch-and-match (BaM) framework for score-based BBVI to problems where it is prohibitively expensive to store such covariance matrices, let alone to estimate them. Unlike classical algorithms for BBVI, which use stochastic gradient descent to minimize the reverse Kullback-Leibler divergence, BaM uses more specialized updates to match the scores of the target density and its Gaussian approximation. We extend the updates for BaM by integrating them with a more compact parameterization of full covariance matrices. In particular, borrowing ideas from factor analysis, we add an extra step to each iteration of BaM—a patch—that projects each newly updated covariance matrix into a more efficiently parameterized family of diagonal plus low rank matrices. We evaluate this approach on a variety of synthetic target distributions and real-world problems in high-dimensional inference.

Introduction

In Bayesian inference, approximating a complex posterior distribution with a simpler one, such as a Gaussian, is a fundamental task. Black-box variational inference (BBVI) has become the standard approach, typically employing stochastic gradient descent to minimize the divergence between the approximation and the target. However, BBVI faces significant challenges in high-dimensional settings:

  1. Computational Complexity: A full covariance matrix for a 10,000-dimensional problem contains 100 million entries, making storage and updates prohibitively expensive ($O(D^2)$).
  2. Optimization Fragility: Standard methods like ADVI rely on noisy gradients and are highly sensitive to hyperparameters, often leading to slow convergence or divergence in high dimensions.

While low-rank approximations exist, they often fail to fully exploit the underlying structure during optimization. This paper introduces patched Batch-and-Match (pBaM), a score-based inference algorithm designed to overcome these limitations.

Methodology: The Patch Step

The pBaM framework builds upon Batch-and-Match (BaM), which utilizes score-matching—matching the derivative of the log-density of the approximation to that of the target—rather than standard KL gradients. The core innovation is the "Patch" step, a three-stage iterative process:

  1. Batch: Collect samples and evaluate their scores (gradients of the target log-density).
  2. Match: Perform a closed-form proximal point update to create an intermediate covariance matrix.
  3. Patch: Instead of constructing a dense matrix, an Expectation-Maximization (EM) step projects the update directly into a structured family: a diagonal matrix plus a low-rank component ($\Sigma = \Lambda\Lambda^\top + \Psi$).

By leveraging the Woodbury matrix identity, the authors ensure that every step, including the EM projection, scales linearly ($O(D)$) with the number of dimensions.

Computational scaling of pBaM components showing linear time complexity with respect to dimensions, batch size, and rank.

Experimental Results

The authors evaluated pBaM against various ADVI baselines across several benchmarks, including synthetic Gaussian targets (up to $D=8192$), Poisson regression, Log-Gaussian Cox Processes (Coal Mining Disasters), and Item Response Theory models.

Key findings include:

  • Faster Convergence: pBaM converged orders of magnitude faster than low-rank ADVI (ADVI-LR) across all tested dimensions.
  • Superior Stability: In complex models like the Log-Gaussian Cox Process, ADVI frequently diverged or required extensive tuning, whereas pBaM converged reliably to better KL divergence values.
  • Accuracy: pBaM produced estimates comparable to expensive MCMC gold standards, particularly in real-world applications like the coal mining dataset.
Convergence of pBaM versus ADVI across varying dimensions D, demonstrating consistent superiority in speed and stability.

Discussion and Limitations

The EM "patch" acts as a principled projection, forcing the covariance to remain low-rank while retaining the benefits of score-matching updates. By avoiding the linearization inherent in standard gradient descent, pBaM solves a more global optimization problem at each step, leading to its observed stability.

However, some limitations remain:

  • Rank Selection: The rank $K$ must be pre-specified, though future work could explore dynamic rank adjustment.
  • Structural Assumptions: The method assumes a unimodal, roughly Gaussian posterior. Highly multi-modal distributions may still pose challenges.
  • Alternative Structures: Future adaptations could extend the "patch" framework to other structures, such as sparse precision matrices.

Summary updated

Abstract

Black-box variational inference (BBVI) scales poorly to high-dimensional problems when it is used to estimate a multivariate Gaussian approximation with a full covariance matrix. In this paper, we extend the _batch-and-match_ (BaM) framework for score-based BBVI to problems where it is prohibitively expensive to store such covariance matrices, let alone to estimate them. Unlike classical algorithms for BBVI, which use stochastic gradient descent to minimize the reverse Kullback-Leibler divergence, BaM uses more specialized updates to match the scores of the target density and its Gaussian approximation. We extend the updates for BaM by integrating them with a more compact parameterization of full covariance matrices. In particular, borrowing ideas from factor analysis, we add an extra step to each iteration of BaM---a _patch_---that projects each newly updated covariance matrix into a more efficiently parameterized family of diagonal plus low rank matrices. We evaluate this approach on a variety of synthetic target distributions and real-world problems in high-dimensional inference.
BibTeX
@inproceedings{modi2025batch,
  author = {Chirag Modi and Diana Cai and Lawrence K. Saul},
  title = {{Batch, match, and patch: low-rank approximations for score-based variational inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=N6U1Ue7YgT},
}
Figure