Abstract
Performing exact Bayesian inference for complex models is computationally intractable. Markov chain Monte Carlo (MCMC) algorithms can provide reliable approximations of the posterior distribution but are expensive for large datasets and high-dimensional models. A standard approach to mitigate this complexity consists in using subsampling techniques or distributing the data across a cluster. However, these approaches are typically unreliable in high-dimensional scenarios. We focus here on a recent alternative class of MCMC schemes exploiting a splitting strategy akin to the one used by the celebrated alternating direction of multipliers (ADMM) optimization algorithm. These methods appear to provide empirically state-of-the-art performance but their theoretical behavior in high dimension is currently unknown. In this paper, we propose a detailed theoretical study of one of these algorithms known as the split Gibbs sampler. Under regularity conditions, we establish explicit convergence rates for this scheme using Ricci curvature and coupling ideas. We support our theory with numerical illustrations.
Introduction
Bayesian inference is a cornerstone of modern statistics, yet its application to "Big Data" and high-dimensional models remains a significant challenge. Traditional Markov chain Monte Carlo (MCMC) methods often struggle with scalability. While subsampling and divide-and-conquer strategies exist, they frequently falter as model dimensionality increases or rely on restrictive Gaussian approximations of the posterior.
This paper investigates the Split Gibbs Sampler (SGS), a method inspired by the variable splitting techniques of the Alternating Direction of Multipliers Method (ADMM) optimization algorithm. While SGS has shown empirical success, this work provides the first rigorous theoretical analysis of its convergence properties, particularly in high-dimensional settings.
The Split Gibbs Sampler (SGS) Framework
The core innovation of SGS lies in its "variable splitting" strategy. Instead of sampling directly from a complex posterior distribution $p(\theta | y)$, the algorithm introduces auxiliary variables $z_i$ that act as local copies of the parameter $\theta$ for different blocks of data.
As shown in the graphical model comparison above, the standard model (left) couples all data points $y_i$ through a single parameter $\theta$. In the split model (right), each data block $y_i$ is associated with its own auxiliary variable $z_i$. These local variables are then tied back to the "master" parameter $\theta$ through a Gaussian prior, effectively decoupling the likelihood terms.
The algorithm alternates between two primary steps:
- Local Step: Sample each $z_i$ given $\theta$. Because the $z_i$ are conditionally independent, this step is inherently parallelizable across distributed systems.
- Global Step: Update the master parameter $\theta$ given all $z_i$. This typically involves a straightforward Gaussian update, acting as a consensus step.
Theoretical Contributions: Dimension-Free Convergence
The authors utilize Ricci curvature and coupling techniques to establish explicit convergence rates for SGS. Their most significant finding is that the convergence rate is dimension-free. Unlike many MCMC methods whose performance degrades as the number of parameters $d$ grows, the mixing time of SGS depends primarily on the "penalty parameter" $\rho$ and the underlying curvature of the model, rather than $d$ itself.
Furthermore, the paper demonstrates that SGS offers a superior bias-to-step-size ratio compared to the Unadjusted Langevin Algorithm (ULA). While ULA's discretization error scales linearly with the step size, SGS's error scales quadratically ($O(\rho^2)$), allowing for larger steps without sacrificing accuracy.
Empirical Validation
The theoretical bounds were validated through several experiments:
- Gaussian Mixture Models: Used to compare SGS against ULA, demonstrating more efficient exploration of complex distributions.
- Bayesian Binary Logistic Regression: Tested on high-dimensional synthetic data. SGS required an order of magnitude fewer iterations and significantly less CPU time than ULA to achieve comparable precision.
- Parallel Efficiency: The experiments confirmed that the local sampling step scales efficiently in distributed computing environments, making it a viable candidate for massive datasets.
Conclusion and Future Directions
This work provides a solid theoretical foundation for the Split Gibbs Sampler, proving its robustness in high-dimensional Bayesian inference. While the current theory focuses on strongly log-concave distributions, it opens the door for future research into non-convex (multi-modal) landscapes and dynamic tuning of the penalty parameter $\rho$ to further accelerate convergence. By bridging the gap between optimization-inspired splitting and stochastic sampling, SGS represents a powerful tool for modern large-scale Bayesian analysis.
Summary updated