A Divergence Bound for Hybrids of MCMC and Variational Inference and an Application to Langevin Dynamics and SGVI

Justin Domke

Abstract

Two popular classes of methods for approximate inference are Markov chain Monte Carlo (MCMC) and variational inference. MCMC tends to be accurate if run for a long enough time, while variational inference tends to give better approximations at shorter time horizons. However, the amount of time needed for MCMC to exceed the performance of variational methods can be quite high, motivating more fine-grained tradeoffs. This paper derives a distribution over variational parameters, designed to minimize a bound on the divergence between the resulting marginal distribution and the target, and gives an example of how to sample from this distribution in a way that interpolates between the behavior of existing methods based on Langevin dynamics and stochastic gradient variational inference (SGVI).

Introduction

In Bayesian inference, the central challenge is often sampling from a complex posterior distribution $p(z)$. Traditionally, practitioners have relied on two distinct paradigms: Markov Chain Monte Carlo (MCMC) and Variational Inference (VI). MCMC methods, such as Langevin Dynamics, are asymptotically exact but often require significant computational time to converge. Conversely, VI methods are computationally efficient but introduce bias by restricting the posterior to a simple parametric family, such as a Gaussian.

This paper addresses the "no-man's land" between these two extremes. For researchers with moderate time budgets, there has historically been no principled way to trade off the speed of VI with the accuracy of MCMC. We introduce a theoretical framework that hybridizes these approaches by minimizing a convex combination of two divergence bounds, allowing for a smooth interpolation controlled by a single parameter $\\beta$.

Methodology

The core of our approach is the derivation of a distribution over variational parameters $w$ that minimizes a bound on the KL-divergence between the marginal distribution and the target posterior. We define a new objective $D_\\beta$ as a convex combination:

$$D_\\beta = (1 - \\beta)D_0 + \\beta D_1$$

where $D_0$ represents the standard conditional divergence used in VI, and $D_1$ is a joint divergence bound incorporating an auxiliary distribution. By varying $\\beta \\in [0, 1]$, the algorithm transitions between standard Stochastic Gradient Variational Inference (SGVI) at $\\beta = 0$ and Langevin Dynamics at $\\beta = 1$.

Visualizing the interpolation between VI ($\beta=0$) and MCMC ($\beta=1$) on toy 2D distributions.

Experimental Results

We evaluated the hybrid approach on toy 2D distributions (a mixture of Gaussians and a "donut" shape) and four UCI datasets for Bayesian Logistic Regression (a1a, australian, ionosphere, and sonar). Ground truth was established using Hamiltonian Monte Carlo via the Stan probabilistic programming language.

Qualitative Analysis

As shown in Figure 1, the transition from VI to MCMC is a smooth continuum. At $\\beta=0$, the algorithm fits a single large ellipsoid to the target. As $\\beta$ increases, these ellipsoids become more concentrated and numerous, eventually behaving like individual particles in a Markov chain at $\\beta=1$. This demonstrates how the method sources entropy from both the variational distribution and the chain's randomness.

Quantitative Performance

Using Maximum Mean Discrepancy (MMD) to measure distance from the ground truth, we found that intermediate values of $\\beta$ (e.g., 0.2 or 0.4) consistently outperformed both pure SGVI and pure Langevin dynamics across various time horizons.

MMD vs iterations for varying $\beta$, demonstrating the trade-off between early-stage speed and asymptotic accuracy.

As illustrated in Figure 2, the hybrid method often achieves an error level in $10^4$ iterations that pure MCMC requires $10^6$ iterations to reach, while still eventually surpassing the accuracy floor inherent to pure VI.

Discussion

The hybrid method effectively finds a "Pareto frontier" for approximate inference. It captures the "bulk" of the posterior much faster than pure MCMC while avoiding the restrictive bias of pure VI. However, challenges remain regarding hyperparameter tuning, specifically the step-size $\\epsilon$ and the choice of $\\beta$. Future work will explore adaptive schedules for these parameters and the application of this framework to more complex variational families, such as Normalizing Flows.

Summary updated

Abstract

Two popular classes of methods for approximate inference are Markov chain Monte Carlo (MCMC) and variational inference. MCMC tends to be accurate if run for a long enough time, while variational inference tends to give better approximations at shorter time horizons. However, the amount of time needed for MCMC to exceed the performance of variational methods can be quite high, motivating more fine-grained tradeoffs. This paper derives a distribution over variational parameters, designed to minimize a bound on the divergence between the resulting marginal distribution and the target, and gives an example of how to sample from this distribution in a way that interpolates between the behavior of existing methods based on Langevin dynamics and stochastic gradient variational inference (SGVI).
BibTeX
@inproceedings{domke2017divergence,
  author = {Justin Domke},
  title = {{A Divergence Bound for Hybrids of MCMC and Variational Inference and an Application to Langevin Dynamics and SGVI}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=BJ-twiWdZH},
}
Figure