# On Mixing Rates for Bayesian CART

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 58 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 10 of 10)

- [Automated versus do-it-yourself methods for causal inference: Lessons learned from a data analysis competition](https://mlsanity.com/paper/1707.02641/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Bayesian Regression Tree Ensembles that Adapt to Smoothness and Sparsity](https://mlsanity.com/paper/1707.09461/) (2017)
- [On the Computational Complexity of High-Dimensional Bayesian Variable Selection](https://mlsanity.com/paper/1505.07925/) (2015)
- [On Theory for BART](https://mlsanity.com/paper/1810.00787/) (2018)
- [Stochastic tree ensembles for regularized nonlinear regression](https://mlsanity.com/paper/2002.03375/) (2020)
- [A Mixing Time Lower Bound for a Simplified Version of BART](https://mlsanity.com/paper/2210.09352/) (2022)
- [Top-down particle filtering for Bayesian decision trees](https://mlsanity.com/paper/1303.0561/) (2013)
- [Dimension-free Mixing for High-dimensional Bayesian Variable Selection](https://mlsanity.com/paper/2105.05719/) (2021)
- [Particle Gibbs for Bayesian Additive Regression Trees](https://mlsanity.com/paper/1502.04622/) (2015)

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

- [MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees](https://mlsanity.com/paper/2309.15312/) (2023)
- [Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces](https://mlsanity.com/paper/2404.03867/) (2024)
- [A phase transition in sampling from Restricted Boltzmann Machines](https://mlsanity.com/paper/2410.08423/) (2024)
- [Graph-Split Bayesian Causal Forest for Spatial Heterogeneous Treatment Effect Estimation](https://mlsanity.com/paper/2609.36046/) (2026)

## Abstract (arXiv)

The success of Bayesian inference with MCMC depends critically on Markov chains rapidly reaching the posterior distribution. Despite the plentitude of inferential theory for posteriors in Bayesian non-parametrics, convergence properties of MCMC algorithms that simulate from such ideal inferential targets are not thoroughly understood. This work focuses on the Bayesian CART algorithm which forms a building block of Bayesian Additive Regression Trees (BART). We derive upper bounds on mixing times for typical posteriors under various proposal distributions. Exploiting the wavelet representation of trees, we provide sufficient conditions for Bayesian CART to mix well (polynomially) under certain hierarchical connectivity restrictions on the signal. We also derive a negative result showing that Bayesian CART (based on simple grow and prune steps) cannot reach deep isolated signals in faster than exponential mixing time. To remediate myopic tree exploration, we propose Twiggy Bayesian CART which attaches/detaches entire twigs (not just single nodes) in the proposal distribution. We show polynomial mixing of Twiggy Bayesian CART without assuming that the signal is connected on a tree. Going further, we show that informed variants achieve even faster mixing. A thorough simulation study highlights discrepancies between spike-and-slab priors and Bayesian CART under a variety of proposals.