# A Mixing Time Lower Bound for a Simplified Version of BART

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 44 references that are in the map.
- First posted on arXiv 17 Oct 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [Automated versus do-it-yourself methods for causal inference: Lessons learned from a data analysis competition](https://mlsanity.com/paper/1707.02641/) (2017)
- [Discussion on "Bayesian Regression Tree Models for Causal Inference: Regularization, Confounding, and Heterogeneous Effects" by Hahn, Murray and Carvalho](https://mlsanity.com/paper/2108.02836/) (2021)
- [PMLB v1.0: An open source dataset collection for benchmarking machine learning methods](https://mlsanity.com/paper/2012.00058/) (2020)
- [Bayesian Regression Tree Ensembles that Adapt to Smoothness and Sparsity](https://mlsanity.com/paper/1707.09461/) (2017)
- [Atlantic Causal Inference Conference (ACIC) Data Analysis Challenge 2017](https://mlsanity.com/paper/1905.09515/) (2019)
- [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)
- [Variable Selection with ABC Bayesian Forests](https://mlsanity.com/paper/1806.02304/) (2018)

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

- [Guided Diffusion Sampling on Function Spaces with Applications to PDEs](https://mlsanity.com/paper/2505.17004/) (2025)
- [On Mixing Rates for Bayesian CART](https://mlsanity.com/paper/2306.00126/) (2023)
- [flexBART: Flexible Bayesian regression trees with categorical predictors](https://mlsanity.com/paper/2211.04459/) (2022)
- [Very fast Bayesian Additive Regression Trees on GPU](https://mlsanity.com/paper/2410.23244/) (2024)
- [Ranking Perspective for Tree-based Methods with Applications to Symbolic Feature Selection](https://mlsanity.com/paper/2410.02623/) (2024)
- [BFTS: Thompson Sampling with Bayesian Additive Regression Trees](https://mlsanity.com/paper/2602.07767/) (2026)
- [Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammars](https://mlsanity.com/paper/2302.07407/) (2023)

## Abstract (arXiv)

Bayesian Additive Regression Trees (BART) is a popular Bayesian non-parametric regression algorithm. The posterior is a distribution over sums of decision trees, and predictions are made by averaging approximate samples from the posterior. The combination of strong predictive performance and the ability to provide uncertainty measures has led BART to be commonly used in the social sciences, biostatistics, and causal inference. BART uses Markov Chain Monte Carlo (MCMC) to obtain approximate posterior samples over a parameterized space of sums of trees, but it has often been observed that the chains are slow to mix. In this paper, we provide the first lower bound on the mixing time for a simplified version of BART in which we reduce the sum to a single tree and use a subset of the possible moves for the MCMC proposal distribution. Our lower bound for the mixing time grows exponentially with the number of data points. Inspired by this new connection between the mixing time and the number of data points, we perform rigorous simulations on BART. We show qualitatively that BART's mixing time increases with the number of data points. The slow mixing time of the simplified BART suggests a large variation between different runs of the simplified BART algorithm and a similar large variation is known for BART in the literature. This large variation could result in a lack of stability in the models, predictions, and posterior intervals obtained from the BART MCMC samples. Our lower bound and simulations suggest increasing the number of chains with the number of data points.