On Mixing Rates for Bayesian CART
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Ideal Bayesian Spatial AdaptationJournal of the American Statistical Association, 2023
- Exponential Tail Bounds for Chisquared Random VariablesJournal of Statistical Theory and Practice, 2021
- Informed Proposals for Local MCMC in Discrete SpacesJournal of the American Statistical Association, 2019
- Adaptive Confidence Bands for Nonparametric Regression FunctionsJournal of the American Statistical Association, 2014
- Wavelet-based statistical signal processing using hidden Markov modelsIEEE Transactions on Signal Processing, 1998
- Embedded image coding using zerotrees of wavelet coefficientsIEEE Transactions on Signal Processing, 1993
- Random walks in a convex body and an improved volume algorithmRandom Structures & Algorithms, 1993
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity FlowCombinatorics, Probability and Computing, 1992
- Rotation distance, triangulations, and hyperbolic geometryJournal of the American Mathematical Society, 1988
- On coupling of Markov chainsProbability Theory and Related Fields, 1976