# Bounding Wasserstein distance with couplings

arXiv: https://arxiv.org/abs/2112.03152 · HTML: https://mlsanity.com/paper/2112.03152/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 107 references that are in the map.
- First posted on arXiv 6 Dec 2021.

## Builds on (most cited first, 30 of 35)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Measuring Sample Quality with Kernels](https://mlsanity.com/paper/1703.01717/) (2017)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Measuring Sample Quality with Stein's Method](https://mlsanity.com/paper/1506.03039/) (2015)
- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Stochastic gradient Markov chain Monte Carlo](https://mlsanity.com/paper/1907.06986/) (2019)
- [On Markov chain Monte Carlo methods for tall data](https://mlsanity.com/paper/1505.02827/) (2015)
- [Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces](https://mlsanity.com/paper/1804.10556/) (2018)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Stochastic Stein Discrepancies](https://mlsanity.com/paper/2007.02857/) (2020)
- [Validated Variational Inference via Practical Posterior Error Bounds](https://mlsanity.com/paper/1910.04102/) (2019)
- [Measuring Sample Quality with Diffusions](https://mlsanity.com/paper/1611.06972/) (2016)
- [Random Feature Stein Discrepancies](https://mlsanity.com/paper/1806.07788/) (2018)
- [Perturbation theory for Markov chains via Wasserstein distance](https://mlsanity.com/paper/1503.04123/) (2015)
- [Revisiting the Gelman-Rubin Diagnostic](https://mlsanity.com/paper/1812.09384/) (2018)
- [Lasso Meets Horseshoe : A Survey](https://mlsanity.com/paper/1706.10179/) (2017)
- [Estimating Convergence of Markov chains with L-Lag Couplings](https://mlsanity.com/paper/1905.09971/) (2019)
- [Leave Pima Indians alone: binary regression as a benchmark for Bayesian computation](https://mlsanity.com/paper/1506.08640/) (2015)
- [Maximal couplings of the Metropolis-Hastings algorithm](https://mlsanity.com/paper/2010.08573/) (2020)
- [Unbiased Smoothing using Particle Independent Metropolis-Hastings](https://mlsanity.com/paper/1902.01781/) (2019)

## Built on by (most cited first, 5 of 5)

- [Variational Inference for Uncertainty Quantification: an Analysis of Trade-offs](https://mlsanity.com/paper/2403.13748/) (2024)
- [Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets](https://mlsanity.com/paper/2210.14064/) (2022)
- [Generalized Guarantees for Variational Inference in the Presence of Even and Elliptical Symmetry](https://mlsanity.com/paper/2511.01064/) (2025)
- [Centered plug-in estimation of Wasserstein distances](https://mlsanity.com/paper/2203.11627/) (2022)
- [Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport](https://mlsanity.com/paper/2210.13630/) (2022)

## Abstract (arXiv)

Markov chain Monte Carlo (MCMC) provides asymptotically consistent estimates of intractable posterior expectations as the number of iterations tends to infinity. However, in large data applications, MCMC can be computationally expensive per iteration. This has catalyzed interest in approximating MCMC in a manner that improves computational speed per iteration but does not produce asymptotically consistent estimates. In this article, we propose estimators based on couplings of Markov chains to assess the quality of such asymptotically biased sampling methods. The estimators give empirical upper bounds of the Wasserstein distance between the limiting distribution of the asymptotically biased sampling method and the original target distribution of interest. We establish theoretical guarantees for our upper bounds and show that our estimators can remain effective in high dimensions. We apply our quality measures to stochastic gradient MCMC, variational Bayes, and Laplace approximations for tall data and to approximate MCMC for Bayesian logistic regression in 4500 dimensions and Bayesian linear regression in 50000 dimensions.