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:
- Toy Skew-Normal Model: A synthetic 1D example to visualize how biased methods fail to find true variance.
- Bayesian Probit Regression: Tested on three classic classification datasets from the UCI Machine Learning Repository: Pima Indians Diabetes, Ionosphere, and Heart Disease.
- 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.
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.
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