Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting

Maxime Vono, Daniel Paulin, Arnaud Doucet

TL;DR

This paper introduces a novel Markov Chain Monte Carlo (MCMC) sampling algorithm called the Split Gibbs Sampler (SGS). SGS offers dimension-free convergence rates, meaning its efficiency doesn't degrade as the dimensionality of the problem increases, a significant advantage over many existing methods. This is achieved by leveraging an ADMM-inspired splitting strategy, making it particularly promising for large-scale and distributed Bayesian inference tasks.

What Problem Does This Paper Address?

Bayesian inference, a powerful statistical framework, often involves intractable posterior distributions, especially for complex models with large datasets or high-dimensional parameters. Traditional MCMC methods can struggle with scalability and efficiency in these scenarios. While subsampling and divide-and-conquer approaches exist, they often face reliability issues in high dimensions or require strong assumptions about the posterior. This paper tackles the challenge of developing MCMC methods that are both theoretically sound and practically efficient for these demanding high-dimensional and distributed inference problems.

Methods

The core of this work is the Split Gibbs Sampler (SGS). SGS is inspired by the Alternating Direction Method of Multipliers (ADMM) optimization technique. It works by introducing auxiliary variables and splitting the target distribution into a hierarchical Bayesian model. This allows for:

  • Parallel Sampling: The auxiliary variables can be sampled in parallel, significantly speeding up computation.
  • ADMM-type Splitting: The algorithm leverages a variable splitting technique, similar to ADMM, to reformulate the sampling problem.
  • Theoretical Guarantees: The paper provides rigorous theoretical analysis, establishing explicit, dimension-free convergence rates for SGS using Ricci curvature and coupling techniques. This includes bounds on the bias introduced by the approximation and explicit mixing time bounds.
  • Rejection Sampling for Auxiliaries: For sampling the auxiliary variables, the paper shows that rejection sampling can be used efficiently, requiring only a constant number of expected evaluations of the potential function and its gradient, provided the parameter $p$ is sufficiently small.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses toy models for illustration.

Key Insights and Ideas

  • Dimension-Free Convergence: The most significant insight is the derivation of convergence rates that are independent of the problem's dimension. This is a crucial theoretical breakthrough for MCMC in high-dimensional settings.
  • ADMM Inspiration for Sampling: Applying optimization techniques like ADMM to MCMC sampling is a powerful idea. The splitting strategy effectively decomposes a complex sampling problem into simpler, parallelizable sub-problems.
  • Bias-Variance Trade-off with $p$: The parameter $p$ in the SGS algorithm controls the trade-off between the bias introduced by the approximation and the computational cost. The theoretical analysis provides explicit bounds on this trade-off.
  • Richer Theoretical Guarantees: The paper moves beyond empirical performance by providing explicit, non-asymptotic bounds on bias and mixing times, which are essential for understanding the algorithm's behavior and reliability.

Key Results

  • Explicit Convergence Rates: The paper establishes explicit dimension-free convergence rates for SGS in both total variation (TV) and 1-Wasserstein distances. These rates are shown to be competitive with or superior to existing methods like Langevin dynamics.
  • Bias Bounds: Quantitative bounds on the bias between the approximate posterior (from SGS) and the true posterior are derived, showing a decay in $O(p^2)$ for small $p$.
  • Mixing Time Bounds: Explicit mixing time bounds are derived, demonstrating that SGS can achieve a desired precision $\epsilon$ in a number of steps that scales favorably with the condition number of the potential functions and inversely with $\epsilon$.
  • Empirical Validation: Numerical illustrations on toy Gaussian models and logistic regression demonstrate that SGS achieves the theoretical performance and can be more efficient than standard MCMC methods like ULA. For instance, in a Gaussian mixture example, SGS showed significantly smaller bias and running times compared to ULA for the same precision.

Limitations and Future Work

  • Exact Sampling Assumption: The theoretical analysis primarily assumes that the auxiliary variables can be sampled exactly. The paper acknowledges that in more complex scenarios, approximate sampling methods (like Metropolis-Hastings) might be needed, and extending the results to these cases is a direction for future work.
  • Fixed Parameter $p$: The current analysis assumes a fixed parameter $p$. Investigating the benefits of using a sequence of $p$ values could lead to improved performance.
  • Strongly Convex Assumption: While the paper discusses relaxing the strong convexity assumption, the primary theoretical results are derived under this condition. Extending the analysis to more general non-strongly convex densities is an ongoing area of research.
  • Distributed Implementation: While SGS is amenable to distributed computation, the experiments were run on a serial computer. Further exploration of its performance in truly distributed settings would be valuable.

Summary updated

Abstract

Performing exact Bayesian inference for complex models is computationally\nintractable. Markov chain Monte Carlo (MCMC) algorithms can provide reliable\napproximations of the posterior distribution but are expensive for large\ndatasets and high-dimensional models. A standard approach to mitigate this\ncomplexity consists in using subsampling techniques or distributing the data\nacross a cluster. However, these approaches are typically unreliable in\nhigh-dimensional scenarios. We focus here on a recent alternative class of MCMC\nschemes exploiting a splitting strategy akin to the one used by the celebrated\nalternating direction of multipliers (ADMM) optimization algorithm. These\nmethods appear to provide empirically state-of-the-art performance but their\ntheoretical behavior in high dimension is currently unknown. In this paper, we\npropose a detailed theoretical study of one of these algorithms known as the\nsplit Gibbs sampler. Under regularity conditions, we establish explicit\nconvergence rates for this scheme using Ricci curvature and coupling ideas. We\nsupport our theory with numerical illustrations.\n
BibTeX
@article{vono2022efficient,
  author = {Maxime Vono and Daniel Paulin and Arnaud Doucet},
  title = {{Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting}},
  journal = {J. Mach. Learn. Res.},
  year = {2022},
}
Figure