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

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

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.

Introduction: The Challenge of Capturing Uncertainty

In Bayesian machine learning, the goal is often to approximate a complex, unknown posterior distribution $p$ with a simpler distribution $q$. The standard approach, Variational Inference (VI), typically minimizes the exclusive KL divergence ($KL(q || p)$). While computationally convenient—requiring expectations only over the controllable distribution $q$—exclusive KL is notoriously "mode-seeking." It tends to focus on a single peak of the posterior, often severely underestimating the overall uncertainty or variance of the true distribution.

In contrast, the inclusive KL divergence ($KL(p || q)$) is "mean-seeking," making it far better suited for capturing the full breadth of the posterior. However, minimizing $KL(p || q)$ is difficult because it requires taking expectations over the unknown posterior $p$. Existing techniques, such as Importance Sampling (IS) or Sequential Monte Carlo (SMC), attempt to estimate these expectations but introduce systematic biases into the gradients. These biases persist throughout optimization, preventing the model from ever reaching the true optimum.

Markovian Score Climbing (MSC)

To address these limitations, the authors propose Markovian Score Climbing (MSC). Rather than seeking a perfectly unbiased gradient estimate at every iteration, MSC employs a Markov Chain Monte Carlo (MCMC) approach that evolves alongside the optimization process.

The algorithm follows a three-step cycle:

  1. Markovian Sampling: At each iteration $k$, the algorithm takes the previous sample $z[k-1]$ and updates it using an MCMC kernel (such as Conditional Importance Sampling) to obtain $z[k]$. This chain is designed to have the true posterior $p$ as its stationary distribution.
  2. Score Function Update: The variational parameters are updated using the "score function" of the approximation: $\nabla \log q(z[k])$.
  3. Vanishing Bias: By maintaining the state of the Markov chain across iterations rather than re-initializing, the noise in the gradient estimate becomes Markovian. Under a standard Robbins-Monro step-size schedule, this bias vanishes as the algorithm converges, allowing MSC to provably reach a local optimum of the inclusive KL.

A key advantage of this approach is the "virtuous cycle": as the approximation $q$ improves, the MCMC kernel (which can depend on $q$) becomes more efficient, further refining the samples and the resulting gradients.

Experimental Evaluation

The paper evaluates MSC across three distinct scenarios to demonstrate its robustness and accuracy.

Toy Model: Visualizing Bias

On a scalar skew-normal distribution, the authors compared MSC against standard Importance Sampling (IS) methods. The results highlight the fundamental problem with IS: even with many samples, the gradient bias remains, leading to incorrect estimates of the mean and variance. MSC, however, successfully identifies the true parameters as the Markovian bias vanishes.

Bayesian Probit Regression

MSC was tested on three standard UCI datasets: Pima (diabetes), Ionos (ionosphere), and Heart (heart disease). In these tests, MSC achieved predictive accuracy comparable to Expectation Propagation (EP), which is considered a gold standard for probit models. Crucially, MSC is more general-purpose and easier to implement for a wider variety of models than EP.

Stochastic Volatility in Financial Data

The authors also applied MSC to a stochastic volatility model using monthly returns for 18 currency exchange rates against the US Dollar (2007–2017). MSC consistently found model parameters that yielded significantly higher log-marginal likelihoods than SMC-based optimization methods across the majority of the datasets.

Key Insights and Future Directions

  • Robustness to Sample Size: A major practical finding is that MSC works reliably even with a very small number of samples per step (e.g., $S=2$), whereas IS-based methods require large sample sizes to mitigate bias.
  • Bridging MCMC and VI: MSC effectively combines the asymptotic correctness of MCMC with the optimization framework of Variational Inference, using the strengths of one to fix the weaknesses of the other.
  • Learning Model Parameters: By leveraging the Fisher identity, MSC can simultaneously learn the variational approximation $q$ and the underlying model parameters $\theta$ (Maximum Likelihood).

Limitations

While promising, MSC faces challenges with extremely large "exchangeable" datasets. Standard MCMC kernels require evaluating the full likelihood at each step. While mini-batching (subset average likelihoods) is a potential solution, the authors prove it introduces a new bias that targets a perturbed posterior. Additionally, while MSC can be amortized (e.g., for VAEs), detailed large-scale studies of Amortized MSC remain for future work.

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