Markovian Score Climbing: Variational Inference with KL(p||q)

Christian A. Naesseth, Fredrik Lindsten, David M. Blei

Introduction

In Bayesian inference, we often approximate a complex, intractable posterior distribution $p$ with a simpler, parameterized distribution $q$. Modern Variational Inference (VI) typically minimizes the exclusive Kullback-Leibler (KL) divergence, $KL(q||p)$. While computationally convenient, this "mode-seeking" approach tends to fit $q$ to a single peak of the posterior, significantly underestimating the true uncertainty (variance).

Alternatively, the inclusive KL divergence, $KL(p||q)$, is "mass-covering" and provides a much better estimate of uncertainty. However, optimizing it is notoriously difficult because the gradient requires taking an expectation over the intractable distribution $p$. Existing workarounds, such as Importance Sampling (IS) or Sequential Monte Carlo (SMC), introduce systematic bias into the gradients. Consequently, even with infinite computing time, these algorithms may never converge to the actual local optimum.

This paper introduces Markovian Score Climbing (MSC), a novel algorithm that reliably minimizes the inclusive KL divergence using stochastic gradients with vanishing bias.

Methods: Markovian Score Climbing

The core innovation of MSC is using Markov Chain Monte Carlo (MCMC) to estimate the intractable gradients of the inclusive KL. Standard MCMC-based optimization is prohibitively slow because it requires running a chain to convergence at every optimization step.

MSC bypasses this bottleneck via Markovian stochastic approximation. Instead of restarting the chain, MSC updates the variational parameters $\lambda$ using a single sample from a Markov kernel passed from the previous iteration. This "warm start" makes the computational overhead negligible compared to biased, non-Markovian alternatives.

Key technical components include:

  • The Score Function: The algorithm follows the gradient of the log-density of the approximation, $\nabla_\lambda \log q(z)$, evaluated at the current MCMC sample.
  • Adaptive Kernels: The MCMC kernel can depend on the current approximation $q$, allowing the MCMC process to "climb" alongside the variational distribution.
  • Conditional Importance Sampling (CIS): The authors highlight CIS as an efficient MCMC kernel that turns standard importance sampling into a valid Markovian process for MSC, removing the bias inherent in traditional IS-based VI.

Datasets

The researchers evaluated MSC across three distinct scenarios:

  1. Toy Skew-Normal Model: A synthetic 1D example to visualize how biased methods fail to find true variance.
  2. Bayesian Probit Regression: Tested on three classic classification datasets from the UCI Machine Learning Repository: Pima Indians Diabetes, Ionosphere, and Heart Disease.
  3. Stochastic Volatility Model: Applied to real-world financial data consisting of 18 currency exchange rates against the US Dollar (2007–2017).

Key Results and Insights

Bias Elimination: Previous methods like Reweighted Wake-Sleep hit a "glass ceiling" due to gradient bias. MSC removes this ceiling. In the skew-normal toy task, MSC successfully converged to the true parameters, whereas the standard IS-based approach consistently underestimated the variance.

Log-variance convergence on the toy skew-normal task. MSC converges to the true value, while IS underestimates it.

Robustness to Sample Size: MSC is significantly more robust to the number of samples ($S$) used. In the Heart and Ionosphere datasets, MSC maintained stable performance with very few samples, while IS-based methods struggled with high bias.

Parameter estimates across different sample sizes for the Heart and Ionosphere datasets. MSC remains stable even at low sample counts.

Superior Financial Modeling: Because it optimizes the inclusive KL, MSC is much better at "stretching" the approximation $q$ to cover the full spread of the posterior $p$. On the stochastic volatility task, MSC achieved higher log-marginal likelihoods than the SMC-based state-of-the-art, indicating a better fit to the complex dynamics of financial markets.

Limitations and Future Work

  • Large-Scale Exchangeable Data: For models with "exchangeable" data (where the likelihood is a product of many terms), standard MCMC kernels require evaluating the full likelihood at every step, making scaling to massive datasets difficult.
  • MCMC Mixing: Like all MCMC-based methods, MSC's performance depends on the "mixing" speed of the Markov chain. If the posterior has extremely isolated modes, the chain might take a long time to navigate between them.
  • Future Directions: The authors suggest exploring "approximate MCMC" techniques to handle large-scale data and investigating the use of MSC for learning "inference networks" (amortized inference) in deep generative models.

Summary updated

Abstract

Modern variational inference (VI) uses stochastic gradients to avoid intractable expectations, enabling large-scale probabilistic inference in complex models. VI posits a family of approximating distributions q and then finds the member of that family that is closest to the exact posterior p. Traditionally, VI algorithms minimize the “exclusive Kullback-Leibler (KL)” KL(q||p), often for computational convenience. Recent research, however, has also focused on the “inclusive KL” KL(p||q), which has good statistical properties that makes it more appropriate for certain inference problems. This paper develops a simple algorithm for reliably minimizing the inclusive KL using stochastic gradients with vanishing bias. This method, which we call Markovian score climbing (MSC), converges to a local optimum of the inclusive KL. It does not suffer from the systematic errors inherent in existing methods, such as Reweighted Wake-Sleep and Neural Adaptive Sequential Monte Carlo, which lead to bias in their final estimates. We illustrate convergence on a toy model and demonstrate the utility of MSC on Bayesian probit regression for classification as well as a stochastic volatility model for financial data.
BibTeX
@inproceedings{naesseth2020markovian,
  author = {Christian A. Naesseth and Fredrik Lindsten and David M. Blei},
  title = {{Markovian Score Climbing: Variational Inference with KL(p||q)}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=AA_jcYuLOUH},
}
Figure