mlsanityData to 7 Oct 2026

A Mixing Time Lower Bound for a Simplified Version of BART

arXiv 2210.09352 ↗First posted 17 Oct 2022stat.ML cs.AI cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

10 of 44 references.

References · 10

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  2. 2017PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparisoncited by 139
  3. 2017Automated versus do-it-yourself methods for causal inference: Lessons learned from a data analysis competitioncited by 106
  4. 2021Discussion on "Bayesian Regression Tree Models for Causal Inference: Regularization, Confounding, and Heterogeneous Effects" by Hahn, Murray and Carvalhocited by 77
  5. 2020PMLB v1.0: An open source dataset collection for benchmarking machine learning methodscited by 58
  6. 2017Bayesian Regression Tree Ensembles that Adapt to Smoothness and Sparsitycited by 34
  7. 2019Atlantic Causal Inference Conference (ACIC) Data Analysis Challenge 2017cited by 23
  8. 2018On Theory for BARTcited by 17
  9. 2020Stochastic tree ensembles for regularized nonlinear regressioncited by 14
  10. 2018Variable Selection with ABC Bayesian Forestscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 2; 2025: 1; 2026: 1.

7 papers.

  1. 2025Guided Diffusion Sampling on Function Spaces with Applications to PDEscited by 33
  2. 2023On Mixing Rates for Bayesian CARTcited by 4
  3. 2022flexBART: Flexible Bayesian regression trees with categorical predictorscited by 3
  4. 2024Very fast Bayesian Additive Regression Trees on GPUcited by 2
  5. 2024Ranking Perspective for Tree-based Methods with Applications to Symbolic Feature Selectioncited by 1
  6. 2026BFTS: Thompson Sampling with Bayesian Additive Regression Treescited by 1
  7. 2023Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammarscited by 0