# Provably Scalable Black-Box Variational Inference with Structured Variational Families

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 84 references that are in the map.
- First posted on arXiv 19 Jan 2024.

## Builds on (most cited first, 30 of 50)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Ladder Variational Autoencoders](https://mlsanity.com/paper/1602.02282/) (2016)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Advances in Variational Inference](https://mlsanity.com/paper/1711.05597/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Automatic Differentiation Variational Inference](https://mlsanity.com/paper/1603.00788/) (2016)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Composing graphical models with neural networks for structured representations and fast inference](https://mlsanity.com/paper/1603.06277/) (2016)
- [Variational Sequential Monte Carlo](https://mlsanity.com/paper/1705.11140/) (2017)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Hierarchical Variational Models](https://mlsanity.com/paper/1511.02386/) (2015)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Auxiliary Deep Generative Models](https://mlsanity.com/paper/1602.05473/) (2016)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Fast and Simple Natural-Gradient Variational Inference with Mixture of Exponential-family Approximations](https://mlsanity.com/paper/1906.02914/) (2019)
- [Bayesian Workflow](https://mlsanity.com/paper/2011.01808/) (2020)
- [Don't Unroll Adjoint: Differentiating SSA-Form Programs](https://mlsanity.com/paper/1810.07951/) (2018)
- [Variance reduction properties of the reparameterization trick](https://mlsanity.com/paper/1809.10330/) (2018)
- [Covariances, Robustness, and Variational Bayes](https://mlsanity.com/paper/1709.02536/) (2017)
- [Advances in Black-Box VI: Normalizing Flows, Importance Weighting, and Optimization](https://mlsanity.com/paper/2006.10343/) (2020)
- [Linear dynamical neural population models through nonlinear embeddings](https://mlsanity.com/paper/1605.08454/) (2016)
- [Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Space](https://mlsanity.com/paper/2304.05398/) (2023)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Black box variational inference for state space models](https://mlsanity.com/paper/1511.07367/) (2015)
- [Faithful Inversion of Generative Models for Effective Amortized Inference](https://mlsanity.com/paper/1712.00287/) (2017)

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

- [Batch, match, and patch: low-rank approximations for score-based variational inference](https://mlsanity.com/paper/2410.22292/) (2024)
- [Optimization Guarantees for Square-Root Natural-Gradient Variational Inference](https://mlsanity.com/paper/2507.07853/) (2025)
- [Nearly Dimension-Independent Convergence of Mean-Field Black-Box Variational Inference](https://mlsanity.com/paper/2505.21721/) (2025)
- [A Hierarchical Variational Graph Fused Lasso for Recovering Relative Rates in Spatial Compositional Data](https://mlsanity.com/paper/2509.20636/) (2025)

## Abstract (arXiv)

Variational families with full-rank covariance approximations are known not to work well in black-box variational inference (BBVI), both empirically and theoretically. In fact, recent computational complexity results for BBVI have established that full-rank variational families scale poorly with the dimensionality of the problem compared to e.g. mean-field families. This is particularly critical to hierarchical Bayesian models with local variables; their dimensionality increases with the size of the datasets. Consequently, one gets an iteration complexity with an explicit O(N2) dependence on the dataset size N. In this paper, we explore a theoretical middle ground between mean-field variational families and full-rank families: structured variational families. We rigorously prove that certain scale matrix structures can achieve a better iteration complexity of Oleft(Nright), implying better scaling with respect to N. We empirically verify our theoretical results on large-scale hierarchical models.