  Ensembles of decision trees are a useful tool for obtaining for obtaining
flexible estimates of regression functions. Examples of these methods include
gradient boosted decision trees, random forests, and Bayesian CART. Two
potential shortcomings of tree ensembles are their lack of smoothness and
vulnerability to the curse of dimensionality. We show that these issues can be
overcome by instead considering sparsity inducing soft decision trees in which
the decisions are treated as probabilistic. We implement this in the context of
the Bayesian additive regression trees framework, and illustrate its promising
performance through testing on benchmark datasets. We provide strong
theoretical support for our methodology by showing that the posterior
distribution concentrates at the minimax rate (up-to a logarithmic factor) for
sparse functions and functions with additive structures in the high-dimensional
regime where the dimensionality of the covariate space is allowed to grow near
exponentially in the sample size. Our method also adapts to the unknown
smoothness and sparsity levels, and can be implemented by making minimal
modifications to existing BART algorithms.
