# Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 121 references that are in the map.
- First posted on arXiv 11 Dec 2024.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry](https://mlsanity.com/paper/1911.01469/) (2019)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Penalising model component complexity: A principled, practical approach to constructing priors](https://mlsanity.com/paper/1403.4630/) (2014)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [MCMC-Based Inference in the Era of Big Data: A Fundamental Analysis of the Convergence Complexity of High-Dimensional Chains](https://mlsanity.com/paper/1508.00947/) (2015)
- [A Cubic Algorithm for Computing Gaussian Volume](https://mlsanity.com/paper/1306.5829/) (2013)
- [Bayesian Inference and Testing of Group Differences in Brain Networks](https://mlsanity.com/paper/1411.6506/) (2014)
- [Sampling for Bayesian Mixture Models: MCMC with Polynomial-Time Mixing](https://mlsanity.com/paper/1912.05153/) (2019)
- [Provably Efficient Posterior Sampling for Sparse Linear Regression via Measure Decomposition](https://mlsanity.com/paper/2406.19550/) (2024)

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

- [Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression](https://mlsanity.com/paper/2505.14343/) (2025)
- [Wasserstein Contraction of Coordinate Ascent Variational Inference](https://mlsanity.com/paper/2605.30253/) (2026)
- [Spectral gap of Metropolis-within-Gibbs under log-concavity](https://mlsanity.com/paper/2509.26175/) (2025)

## Abstract (arXiv)

We propose using a modified conductance-based method to study the mixing time of an important class of two-block Gibbs samplers, the data augmentation (DA) algorithm. %, which is of prominent interest in both theoretical and empirical research. Using this method, we prove the first non-asymptotic polynomial upper bounds on mixing times of three important DA algorithms: DA algorithms for Bayesian Probit regression (Albert and Chib, 1993, ProbitDA) and Bayesian Logit regression (Polson, Scott, and Windle, 2013, LogitDA), and Bayesian Lasso Regression (Park and Casella, 2008, Rajaratnam et al., 2015, LassoDA). Concretely, for ProbitDA and LogitDA, we demonstrate a tight bound that explicitly depends on the design matrix and prior covariance matrix. Under the assumption that data are independently generated from either a sub-Gaussian or log-concave distribution and properly scaled, the bound implies that with η-warm start, parameter dimension d, and sample size n, with high probability over data, the two algorithms require Oleft(nlog left(fraclog ηεright)right) steps to obtain samples with at most ε error in TV, KL, or chi2 distance. Meanwhile, we show that under minimal data assumptions, LassoDA requires Oleft(d2(dlog d +n log n)2 log left(fracηεright)right) steps to achieve ε-accuracy in TV distance. The results are generally applicable to settings with large n and large d, including settings with highly imbalanced response data in Probit and Logit regression. We compare them with the best known guarantees of Langevin Monte Carlo and Metropolis Adjusted Langevin Algorithm. We evaluate our theoretical results using numerical examples, and discuss the mixing times of the three algorithms under feasible initialization.