Bayesian Regression Tree Ensembles that Adapt to Smoothness and Sparsity

1 Introduction

• Tree-based regression can fail to adapt to higher smoothness, lose predictive performance as dimensionality grows, and lack frequentist large-sample theory.The paper attributes the smoothness limitation to piecewise-constant tree estimators.Source: §1 · p. 2
• SBART combines soft decision trees with sparsity-inducing priors on splitting probabilities to address smoothness and dimensionality limitations.The paper introduces SBART as an extension of the Bayesian additive regression trees framework.Source: §1 · p. 2
• For f0 in a Hölder class of smoothness α, SBART adapts to unknown smoothness and contracts at the minimax rate n^-α/(2α+p), up to logarithmic terms.The stated result concerns the posterior distribution and a Hölder class with smoothness index α and radius R.Source: §1 · p. 2
• When f0 depends on d ≪ p predictors and is α-Hölder smooth, SBART contracts at a minimax-optimal rate even when p grows nearly exponentially in n.The introduction attributes this result to structural sparsity in the regression function.Source: §1 · pp. 2–3
• For additive structures with sparse, smooth components, SBART achieves near-minimax contraction and can allow o(n^β) predictors for some β ∈ (0, 1), versus o(log n) in the general sparse case.The paper presents the larger predictor allowance as a property of the additive-structure rate.Source: §1 · p. 3
• SBART adapts without prior knowledge of component smoothness, component count, or interaction degree, and requires only minor changes to existing fitting strategies.The sparsity prior uses conditionally conjugate Dirichlet priors for Gibbs sampling, while soft trees require minor backfitting changes.Source: §1 · p. 3

1.1 Related Work

• Unlike the spike-and-tree approach of Rockova and van der Pas (2017), which uses a deep tree to approximate smooth functions before dividing it among shallower trees, SBART links sum-of-tree estimators to kernel estimators and uses shallow trees.Source: §1.1 · pp. 3–4
• Unlike the soft CART trees of Irsoy et al. (2012), SBART uses Bayesian backfitting for an ensemble rather than greedy learning of a single tree, and establishes fractional-posterior concentration results.The paper describes fractional-posterior results as allowing less restrictive prior assumptions.Source: §1.1 · p. 4

2.1 Description of the model

• Soft trees route each x probabilistically rather than deterministically, with branch bandwidths controlling decisions from hard-tree-like to constant-model behavior.The bandwidth parameter τb controls decision sharpness, with the hard-tree limit as τb → 0 and a constant model as τb → ∞.Source: §2.1 · pp. 5–6
• Because each leaf influences f globally, local bandwidths let the model borrow information across covariate regions with data-adaptive smoothing.The influence of a leaf as x moves from its center depends on local bandwidths learned from data.Source: §2.1 · p. 6

2.2 Smoothness adaptation

• Soft decision trees approximate linear relationships almost exactly, even when T = 1.The passage contrasts this with BART’s large-scale fit, which resembles a nowhere-differentiable continuous function.Source: §2.2 · p. 7

2.3 Prior specification and implementation

• The default prior uses sparsity-inducing Dirichlet splitting proportions and tree-specific exponential bandwidths; reasonable baseline performance requires no further tuning.The illustrations use r = 0.1, which supports both approximately step-shaped and approximately linear gating functions.Source: §2.3 · pp. 8–9
• Quantile-normalizing predictors to [0, 1] makes the prior invariant under monotone transformations of X.The recommended preprocessing scales responses so most or all fall in [−0.5, 0.5].Source: §2.3 · pp. 8–9
• Attempts to put a prior on the number of trees T using reversible-jump methods resulted in poor MCMC mixing.Source: §2.3 · p. 10
• In the reported comparison, cross-validation selected T = 10, which also minimized the population root mean squared error for f.The authors found K-fold cross-validation most reliable when resources permit; PSIS-LOO may overfit and WBIC may require very long chains.Source: §2.3 · p. 11, Figure 4 · p. 11

2.4 Variable grouping prior

• The sparsity-inducing prior extends to jointly penalize predictor groups, and is primarily used to include categorical predictors through dummy variables.The grouping prior is described as similar to the group lasso.Source: §2.4 · p. 12

2.5 Posterior computation

• Bayesian backfitting uses MCMC to update tree structures, soft decision parameters, leaf values, and sparsity weights; Gaussian errors permit closed-form marginalization over leaf values.Tree proposals include Birth, Death, and Change moves, and the sparsity-weight updates use Gibbs sampling.Source: §2.5 · pp. 12–13
• SBART computes likelihood contributions for each leaf-observation pair, whereas BART needs one per tree, so deep trees make BART substantially faster, though the difference is usually not prohibitive.The authors attribute the qualification to the prior construction, which generally keeps trees from becoming deep.Source: §2.5 · p. 13

3 Theoretical results

• The analysis establishes contraction for fractional posteriors with η < 1 under weak conditions, while the usual posterior’s consistency and same-rate result require more stringent prior conditions.For the usual posterior, the supplementary result requires additional conditions to control prior-tail probabilities and establish a sieve.Source: §3 · pp. 14, 17
• Lemma 1 shows that smooth functions can be approximated by sums of soft decision trees with tree count and approximation error optimally balanced, using a common bandwidth.The lemma also bounds the required tree count by a polynomial in the inverse approximation error.Source: §3 · pp. 15–16
• For bounded Hölder truths depending on at most d covariates, the posterior contracts at a near-minimax rate and adapts to unknown smoothness α without requiring α in advance.The sparse-truth results assume conditions G and P; the rate adapts to the truth’s smoothness.Source: §3 · p. 18
• For sparse additive truths whose components each depend on only d_v covariates, the next result establishes adaptive posterior contraction.The supplied passage introduces this result but cuts off before specifying the rate or adaptation parameters.Source: §3 · p. 18
• The sum of soft decision trees adaptively learns unknown lower-order nonlinear interactions among covariates.The model also adapts to additive structure and the unknown smoothness of each additive component.Source: §3 · p. 18
• Under Theorem 4’s assumptions, the posterior for additive sparse truth attains a near-minimax rate up to log n terms (Yang and Tokdar, 2015).The theorem considers bounded additive components in Cαv,R([0, 1]^p), each depending on at most dv covariates, as n and p grow and εn tends to zero.Source: §3 · p. 18

4.1 Friedman’s example

• Among the compared methods, SBART performs best and improves substantially over DART in both low- and high-noise settings; SBART and DART errors are largely invariant to nuisance predictors.Random forests, BART-CV, and boosting errors increase with log p, while lasso performance remains stable but poor.Source: §4.1 · p. 19, Figure 5 · p. 20
• SBART maintains roughly constant precision across λ and exceeds DART; it detects smaller signals, with recall differences reaching about 10%.Once signals are strong enough, both methods consistently detect all relevant predictors.Source: §4.1 · pp. 20–21
• As λ increases, DART’s RMSE degrades while SBART stays roughly constant, as SBART represents effects of (x4, x5) with fewer parameters.DART must use increasing numbers of branches to capture the additional signal as λ increases.Source: §4.1 · p. 21

4.2 Approximation of non-smooth and locally smooth functions

• Even for a step-function discontinuity, SBART can outperform hard-tree ensembles: both capture the jump, but SBART fits better away from it by varying smoothness locally.Trees near the jump use small τt values to approximate a step; elsewhere, larger τt values allow the fit to be essentially constant.Source: §4.2 · p. 22, Figure 7 · p. 22
• For a localized Daubechies wavelet, SBART adapts to both constant regions outside its support and fast oscillations within it, while BART shows outside-support artifacts and wider credible bands.The comparison uses pointwise 95% posterior credible bands.Source: §4.2 · p. 22, Figure 8 · p. 23

4.3 Benchmark datasets

• SBART/SBART-CV perform very well in practice, attaining the best performance on 8 of 10 datasets; on tecator, SBART outperforms all other methods by a very wide margin.Hatco is the only dataset for which SBART-CV substantially outperforms SBART.Source: §4.3 · p. 24

5 Discussion

• The novel Bayesian sum-of-trees framework improves on existing methods in simulated experiments and practice by combining soft decision trees with sparsity-inducing priors.Source: §5 · p. 25
• For sparse f0, posterior concentration is near-optimal and adapts over smoothness classes.Source: §5 · p. 25
• Although demonstrated for nonparametric regression, the methodology extends to binary classification via a probit link and data augmentation.Source: §5 · p. 25
• Consistent model-support recovery—selecting exactly the predictors on which f0 depends—is left as an open question for future research.Source: §5 · p. 25

Step 3

• Each kernel-mixture component is represented by a soft decision tree with at most 2d splits, yielding the component exactly.The construction splits twice along each coordinate and assigns a single leaf the value needed to recover the kernel component.Source: A Proof of Lemma 1 · pp. 26, 28, 29

Step 1

• For f0 in C^α,R([0,1]^d), Lemma 5 provides an approximant with a uniformly bounded norm, using constants independent of bandwidth τ.The lemma is adapted from Lemma 3.4 of De Jonge et al. (2010).Source: A Proof of Lemma 1 · p. 26

Step 2

• The proof extends kernel-mixture approximation to kernels satisfying Assumption G and to general bounded functions, including signed functions that need not integrate to one.It handles signed functions by decomposing them into nonnegative positive and negative parts, then applying the density-approximation result to each part.Source: A Proof of Lemma 1 · pp. 26–27

B Proof of Theorem 2

• The constructed ensemble satisfies ∥ef − f0∥∞ ≤ C(τ^α + ετ^-d), with its tree count bounded by Cτ^-d log^d(ε^-1).Its splits are restricted to the first d coordinates, with at most 2d eT total splits.Source: B Proof of Theorem 2 · p. 29
• The prior is hierarchical: it specifies tree count and topology, split coordinates, splitting locations, then tree bandwidths and leaf values.These stages define the prior neighborhood whose concentration probability the proof bounds.Source: B Proof of Theorem 2 · p. 29
• Using a high-dimensional Dirichlet distribution argument and Assumption P3, together with tree depth at most 2d and Assumption P5, the proof lower-bounds the prior probability of T = eT given T = eT.Source: B Proof of Theorem 2 · pp. 30–31
• Choosing τ = (log^(d+1)n/n)^(−1/(2α+d)), δ = τ^α, and ε = τ^(d+α) yields the claimed result.The passage states these tuning choices but does not specify the resulting rate.Source: B Proof of Theorem 2 · p. 31

C Proof of Theorem 4

• Lemma 1 supplies V approximants, each with eTv trees, for the vth additive component f0,v, and the combined approximation is their sum.Source: C Proof of Theorem 4 · pp. 31–32
• The proof uses the soft-tree prior structure conditional on total tree count T = sum_v eTv, then invokes Assumption P, prior concentration bound (11) for s, and Theorem 2 for each component.The parameters τv, δv, and εv are chosen for each component as in the proof of Theorem 2.Source: C Proof of Theorem 4 · p. 32

• The τt update uses a random-walk Metropolis–Hastings proposal on log τ.Source: §S.1 · p. 37
• A birth move selects a leaf to split, chooses a predictor, and samples a cut point so the split is not redundant.Source: §S.1 · p. 37
• A death move selects a branch that is not a grandparent and deletes its two child nodes.Source: §S.1 · p. 38
• A change move selects a branch that is not a grandparent, then chooses a new predictor and samples a new cut point.Source: §S.1 · p. 39
• For σ^-2, the flat-prior full conditional based on residuals is used as a proposal; a similar strategy updates σµ, while a is updated by slice sampling.Source: §S.1 · p. 39

S.2 Results for the Usual Posterior

• For any t ≥ α(d + 1)/(2α + d), the usual posterior (fractional posterior with η = 1) has convergence rate at least a n^-1 d log p.The only change required is using the density lower bound for the single global τ rather than the tree-specific τt lower bound.Source: §S.2 · pp. 40–42
• Assumption SP requires an exponentially tailed prior on tree count, a shared bandwidth parameter, exponential-tailed leaf values, and bounded tree depth.The section also requires conditions P1, P3, P4, and P5; the bandwidth tail and density conditions are specified in Assumption SP.Source: §S.2 · p. 41
• Combining the sieve bounds with the approximation argument verifies the posterior-contraction conditions and establishes the desired convergence result.The sieve restricts tree count, tree depth, distinct splitting directions, and leaf values.Source: §S.2 · pp. 42–43
• Lemma 1 bounds sieve covering entropy using dmax log p and tree-size and depth terms, and bounds prior mass outside the sieve.For H ≥ d0, the complement probability bound includes an exponentially decreasing term in Cnε² and a term involving 2^H Cnε².Source: §S.2 · p. 42

S.3 Timing Comparisons and Potential Improvements

• Computing sufficient statistics (Ω, bµ) is SBART’s primary speed bottleneck relative to BART, and the current implementation computes them 3T times per Gibbs iteration.The evaluations occur twice when updating tree topology and leaf parameters, and once when updating τ.Source: §S.3 · p. 47
• Caching φi from the previous iteration and jointly updating tree topology and τ could reduce likelihood evaluations by 66% relative to the current implementation.The joint update could reduce sufficient-statistic evaluations from 3T to 2T per Gibbs iteration; caching removes an additional likelihood evaluation.Source: §S.3 · p. 47
• A monotone ψ that reaches 0 or 1 could enable branch pruning and BART-like caching, but its effective kernel is nonanalytic; SBART likelihood computations can also be parallelized.Branches can be disregarded when ψ{(x − Cb)/τb} equals 0 or 1.Source: §S.3 · p. 47
• Matching dbarts’ speed—which is almost that of randomForest and xgboost—will require further SoftBart optimization.The paper describes the current SoftBart implementation as unoptimized and says substantial improvements are possible.Source: §S.3 · pp. 46–47
• SoftBart is more competitive with other packages under cross-validation because it tunes only T, while other packages have additional tuning parameters.The passage gives dbarts as an example of a package with additional hyperparameters.Source: §S.3 · p. 47
• SoftBart was the slowest package on bbb under default settings with cross-validation, running at roughly half BayesTree’s speed; modest design changes could narrow the gap.Table S.2 reports fitting times in seconds; the passage does not provide specific values for this comparison.Source: §S.3 · p. 47, Table S.2 · p. 48