Research map / Probabilistic and scientific modeling / Variational and generative sampling
Provably Scalable Black-Box Variational Inference with Structured Variational Families
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically and empirically that structured (bordered block-diagonal Cholesky) location-scale variational families for hierarchical models with local variables cut BBVI iteration complexity from O(N^3) to O(N) in the dataset size relative to full-rank, matching mean-field scaling.
Problem
Full-rank Gaussian variational families scale poorly with dimensionality in black-box VI, which is severe for hierarchical models with local variables whose dimension grows with dataset size N; mean-field is scalable but crude.
Approach
Characterize gradient variance of location-scale BBVI via the sparsity structure of the scale matrix (effective dimensionality d*), and use a triangular bordered block-diagonal scale matrix that couples global variables with each local block, giving a hierarchical branched structured family whose complexity scales linearly in N rather than as full-rank.
Key results
- Structured families match mean-field scaling: full-rank shows quadratic scaling in iterations with N while mean-field and structured scale linearly in the synthetic experiments.
- Non-standardized parameterization of the structured family is shown to yield a non-convex negative ELBO for a strongly log-concave Gaussian posterior.
- Theoretical sample complexity of structured family is O(N^2 sum kappa_n^2 / eps log(1/eps)), i.e. O(N^3) worst case versus O(N^4) for full-rank under the stated assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a bordered block-diagonal scale matrix instead of a full-rank scale matrix | BBVI for hierarchical models with local variables · Hierarchical models with local variables | sample complexity: \mathcal{O}\left(N^4\right) -> \mathcal{O}\left(N^3\right) | Helped |
| Use structured scale matrices instead of full-rank scale matrices | BBVI on synthetic hierarchical models · Synthetic experiments with varying number of datapoints n | iteration scaling with n | Helped |
| Use structured scale matrices instead of full-rank scale matrices | BBVI on synthetic hierarchical models · Synthetic experiments with varying number of datapoints n | minimum iterations to reach ε accuracy | Helped |
| Use structured scale matrices instead of mean-field scale matrices | BBVI on synthetic hierarchical models · Synthetic experiments with varying number of datapoints n | iteration scaling with n | No clear effect |
| Use the standardized parameterization rather than the non-standardized parameterization | Structured variational families for log-concave posteriors · Hierarchical Bayesian models | convexity of negative ELBO | Helped |
| Use the non-standardized parameterization instead of the standardized parameterization | Structured variational families · Strongly log-concave posterior | convexity of negative ELBO | Hurt |
Surprising findings
- Empirical scaling is polynomially better than the theoretical bound because the isotropic Gaussian target has no cross-component gradient correlations, so the theory is pessimistic.
- Non-standardized parameterization breaks convexity of the negative ELBO even for strongly log-concave posteriors.
Limitations
- Theory uses proximal SGD with fixed stepsize and bounds that are pessimistic in practice; experiments use plain SGD with Adam.
- Analysis restricted to location-scale families with standardized base distributions and strongly log-concave posteriors.
- Empirical experiments are on synthetic and small-to-moderate hierarchical models, with ELBO checks rather than posterior quality on real benchmarks.
Experimental setup
Datasets: rpoisson (synthetic Poisson-log-normal regression data) volatility (stochastic volatility model data) irt (item response theory data) synthetic isotropic Gaussian target
Benchmarks: rpoisson volatility irt synthetic isotropic Gaussian target
Metrics: ELBO iterations to epsilon accuracy scaling with N
Baselines: mean-field full-rank
Builds on: black-box variational inference full-rank BBVI complexity analysis (Domke et al.) hierarchical branched structured families proximal SGD
Closest papers by meaning
- Nearly Dimension-Independent Convergence of Mean-Field Black-Box Variational Inference (NeurIPS 2025 · similarity 0.93)
- EigenVI: score-based variational inference with orthogonal function expansions (NeurIPS 2024 · similarity 0.88)
- Least squares variational inference (NeurIPS 2025 · similarity 0.87)
- Batch and match: black-box variational inference with a score-based divergence (ICML 2024 · similarity 0.87)
- Variational Inference with Mixtures of Isotropic Gaussians (NeurIPS 2025 · similarity 0.87)
- TreeVI: Reparameterizable Tree-structured Variational Inference for Instance-level Correlation Capturing (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.