PaperlayerView exact revision on arXiv

Source-linked AI summary

RoBART: Bayesian Additive Regression Trees with Tree-Specific Rotations

Jeongung Heo, Seonghyun Jeong

arXiv:2610.10214v1stat.MLcs.LGmath.STstat.TH

TL;DR

Axis-aligned BART can require many splits to approximate boundaries misaligned with predictor axes. RoBART learns a rotation for each tree and jointly updates rotations and cutpoints. The paper proves contraction results for additive functions and shows a fixed-truth rate separation from axis-aligned BART.

  • Problem

    Axis-aligned BART can require many splits to approximate boundaries misaligned with predictor axes.

    Source: §1 · p. 1

  • Method

    RoBART assigns each tree a rotation shared across its internal nodes and jointly proposes a Givens rotation sequence and affected cutpoints on the resulting grid.

    Source: §1 · p. 1

  • Results

    For a fixed Hölder ridge function on a tensor design, axis-aligned BART need not attain the one-dimensional contraction rate achieved by RoBART.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results establish contraction for additive regression functions with component-specific rotations and anisotropic smoothness, and a fixed-truth rate separation from axis-aligned BART.

    Source: §7 · p. 9

    The contraction result assumes fixed p, T, and R with R ≤ T; extensions to growing p and sampler convergence analysis remain for further study.

    Source: §7 · p. 9

Abstract

from arXiv · show

Bayesian additive regression trees (BART) can require many splits to approximate boundaries misaligned with the predictor axes. RoBART assigns each tree a rotation shared by all internal nodes, retaining axis-aligned splits in rotated coordinates and constant leaves. We jointly propose a Givens rotation sequence and cutpoints on the resulting grid by Metropolis-Hastings and establish reversibility with respect to the conditional posterior with leaf means integrated out. For additive functions with component-specific rotations and anisotropic H\"older smoothness, we prove posterior contraction in empirical $L_2$ distance and for the noise standard deviation. Under the stated prior, design, and grid conditions, with fixed numbers of predictors, trees, and components and no more components than trees, the rate is a sum of componentwise rates determined by smoothness and the number of rotated coordinates used. We also establish a posterior contraction lower bound showing that there exist functions for which RoBART adapts to the intrinsic dimension but axis-aligned BART does not.

1 INTRODUCTION

Axis-aligned BART can require many splits for oblique boundaries. RoBART gives each tree a rotation and establishes reversibility of a joint rotation–cutpoint update, alongside contraction results and a rate separation from axis-aligned BART for a fixed truth.

1 INTRODUCTION

  • Oblique boundaries can require many splits because standard BART produces rectangular cells with splits on individual predictors.A single 45° rotation aligns both boundaries of the X-shaped signal with the axes; away from the boundaries, a depth-two tree with four leaves represents it.Source: §1 · p. 1
  • RoBART assigns each tree a rotation shared across its internal nodes, while retaining axis-aligned splits in rotated coordinates and constant leaves.Rotations may differ across trees, and each tree may use only some rotated coordinates.Source: §1 · p. 1
  • The joint rotation and cutpoint update is reversible with respect to the conditional posterior after integrating out leaf means.The cutpoint grid depends on the rotated predictors, so the proposal jointly updates a Givens rotation sequence and affected cutpoints on the rebuilt grid.Source: §1 · pp. 1–2
  • For a fixed Hölder ridge function on a tensor design, axis-aligned BART need not attain the one-dimensional contraction rate achieved by RoBART.The contraction result for additive functions with component-specific rotations and anisotropic smoothness assumes fixed predictor, tree, and component counts.Source: §1 · p. 2

2 RELATED WORK

Related methods alter tree routing, leaf outputs, or split geometry in different ways. RoBART instead learns tree-specific rotations, and its analysis accounts for component-specific rotations and their cutpoint grids.

2 RELATED WORK

  • Soft BART replaces hard leaf indicators with smooth routing weights, while ridgeBART uses leaf outputs that are linear combinations of ridge functions.Both retain different modeling choices from RoBART, which keeps hard splits and constant leaves while learning split coordinates.Source: §2 · p. 2
  • Oblique BART allows a hyperplane at each split, whereas RoBART restricts within-tree split normals to rows of one rotation matrix.Random rotation ensembles use separate rotations for base learners but choose them before fitting; RoBART learns each rotation jointly with its tree.Source: §2 · p. 2
  • Unlike Bayesian Projection Pursuit Regression's univariate ridge functions, a RoBART tree can use several rotated coordinates and represent interactions among them.Bayesian Projection Pursuit Regression learns the number of ridge functions by reversible-jump MCMC.Source: §2 · p. 2
  • The contraction analysis extends Bayesian tree and forest results to additive components with separate unknown rotations and their resulting cutpoint grids.The paper gives a contraction rate and a fixed-truth rate separation from axis-aligned BART.Source: §2 · p. 2

3 MODEL

The model sums trees that split on rotated predictors, with a rotation specific to each tree. It defines cutpoint grids and priors on those grids, then updates rotations and cutpoints using a conditional posterior with leaf means integrated out.

3.1 Tree-specific rotations

  • Each tree applies its own rotation before making axis-aligned splits, so each split boundary has a normal given by a row of that tree's rotation matrix.Splits on the same rotated coordinate have parallel boundaries; the forest mean is the sum of the tree contributions.Source: §3.1 · p. 3

3.2 Cutpoint grids and prior

  • For each rotated coordinate, the model places a fixed number of equally spaced candidate cutpoints between its training minimum and maximum.A zero-range coordinate has no available split; the prior chooses whether to split by depth and, when possible, selects an available coordinate and cutpoint uniformly.Source: §3.2 · pp. 3–4

3.3 Conditional posterior

  • For a tree update, the conditional posterior over rotation and cutpoint arrays uses the likelihood with the current tree's leaf means integrated out.It is normalized jointly over rotations and cutpoint arrays, with zero density for invalid arrays; the model draws rotations from normalized Haar measure and specifies independent Gaussian leaf means conditional on forest structure.Source: §3.3 · p. 4, §3.2 · p. 4

4 POSTERIOR COMPUTATION

RoBART jointly updates each tree’s rotation and cutpoints while preserving axis-aligned splits in rotated coordinates. The proposal is designed to be reversible for the leaf-collapsed conditional posterior, and the completed tree update refreshes leaf means.

4.1 Selecting coordinate pairs

  • Coordinate-pair sampling favors rotations involving coordinates used by the tree, while allowing rotations to change the span of those coordinates.The selected coordinate set stays fixed during the joint update, although its corresponding rows of the rotation matrix may change.Source: §4.1 · pp. 4–5

4.2 Rotation proposal

  • The proposed rotation is a sequence of Givens rotations with truncated-normal angles, reversible by reversing the pair order and negating the angles.The centered angle distribution gives matching forward and reverse angle densities.Source: §4.2 · p. 5

4.3 Cutpoint proposal

  • Cutpoints are proposed sequentially on the rotation-dependent grid, using a perturbed reference location while respecting ancestor-imposed admissible intervals.Empty intervals or inadmissible retained indices cause the proposal to fail and leave the original state unchanged.Source: §4.3 · p. 5

4.4 Acceptance probability and reversibility

  • The joint update is reversible with respect to the conditional target when the grid is evaluated exactly and the same sequential cutpoint rule is used in both directions.The acceptance ratio accounts for forward and reverse cutpoint proposal probabilities; failed proposals retain the original state.Source: §4.4 · p. 6

4.5 Completing the tree update

  • After the structural updates, leaf means are redrawn from their Gaussian full conditional, including after rotation rejection or proposal failure.The completed update preserves the joint conditional posterior, and valid updates across trees and remaining parameters preserve the full posterior.Source: §4.5 · p. 6

5 POSTERIOR CONTRACTION

The contraction analysis treats additive truths whose components may use different rotations and anisotropic smoothness. Under the stated design, prior, and grid conditions, it establishes rates for the regression function and noise scale, and a lower bound separates RoBART from axis-aligned BART for a constructed truth.

5.1 Fixed-design model and additive truth

  • The truth is assumed to admit an additive representation whose components use rotated coordinate subsets and satisfy component-specific anisotropic Hölder conditions.The rotation and selected coordinates may differ across components, and minimality or identifiability of the representation is not assumed.Source: §5.1 · p. 7

5.2 Prior and grid conditions

  • The theorem uses the specified tree prior and grid conditions; choosing b_n = n satisfies the stated grid condition for sufficiently large n without knowing smoothness or coordinate sets.The conditions include a positive lower bound on the ranges of coordinates used by the truth.Source: §5.2 · p. 7

5.3 Contraction rate

  • Theorem 1 establishes posterior contraction for the regression function and noise standard deviation, with the slowest component determining the overall rate order.The proof verifies local prior-mass, entropy, and sieve-tail conditions using one rotated tree per component; the result concerns f and σ, not component representations.Source: §5.3 · p. 7

5.4 Comparison with axis-aligned BART

  • For a constructed fixed Hölder ridge truth on a tensor design, axis-aligned BART assigns vanishing posterior mass to every fixed-multiple ball at the RoBART rate.Thus, under the stated axis-aligned prior, adaptation to the one-dimensional rotated representation is not guaranteed.Source: §5.4 · p. 8

6 SIMULATION STUDY

The simulations compare five methods across four regression scenarios using shared datasets and repeated replications. RoBART has lower median RMSPE in Scenarios 2–4, with less uniform accuracy gains in Scenario 1, and its runtime falls between several competing methods.

6.1 Benchmark design

  • The benchmark standardizes four regression functions using calibration inputs and uses shared datasets, noise, and test inputs across methods and replications.The predictor design transforms projected Gaussian inputs into correlated coordinates; the smaller training sample is nested in the larger one.Source: §6.1 · p. 8

6.2 Prediction accuracy and runtime

  • Figure 3(a) shows lower median RMSPE for RoBART across Scenarios 2–4, but less uniform improvement in Scenario 1, where some p = 30 settings at n = 1,500 remain near one.RMSPE is measured against the true regression function, and the boxes summarize thirty replications.Source: Figure 3 · p. 9, §6.2 · p. 9
  • Figure 3(b) shows that RoBART takes longer than BART and Oblique BART, but less time than Soft BART and, in most displayed settings, ridgeBART.The comparison reflects the reported fitting settings.Source: Figure 3 · p. 9, §6.2 · p. 9

7 DISCUSSION

RoBART uses tree-specific rotations and a joint rotation–cutpoint update, with reversibility established for the conditional update. For fixed Hölder ridge functions on a tensor design, axis-aligned BART need not attain RoBART’s one-dimensional contraction rate; the contraction result assumes fixed p, T, and R with R ≤ T.

7 DISCUSSION

  • RoBART combines tree-specific rotations with a joint rotation and cutpoint update that accounts for the changing numerical grid.The joint conditional update is shown to be reversible.Source: §7 · p. 9
  • For a fixed Hölder ridge function on a tensor design, axis-aligned BART need not attain RoBART’s one-dimensional contraction rate.Source: §7 · p. 9
  • The contraction result assumes fixed p, T, and R with R ≤ T; extensions to growing p and sampler convergence analysis require further study.Source: §7 · p. 9

Appendices

The appendices define the collapsed conditional target and sequential rotation–cutpoint proposal, prove reversibility, and show how to complete the tree update by refreshing leaf means. They also clarify that these invariance results do not provide a sampler convergence-rate guarantee.

A.1 Conditional target and proposal path

  • The update targets the leaf-collapsed conditional posterior jointly over rotation and cutpoint array; Givens paths reverse by negating angles in reverse order.The target is normalized jointly over rotation and cutpoint arrays.Source: §A.1 · p. 11

A.2 Sequential cutpoint proposal

  • The sequential proposal freezes departure-state references, updates cutpoints parent-first, and treats invalid or failed arrays as explicit failures without resampling.The reverse proposal evaluates the old cutpoint array using recomputed reverse centers and normalizers.Source: §A.2 · pp. 11–12

A.3 Reversibility of the joint update

  • Reversibility pairs each proposal with the reversed Givens path and exchanged cutpoint arrays; rotation and path factors cancel in the acceptance ratio.With the tree topology and split labels fixed, the remaining discrete change is in terminal-node and cutpoint prior factors.Source: §A.3 · pp. 12–13

A.4 Completing the tree update

  • After structural updates, refresh all leaf means—even after rotation rejection or failure—before restoring the tree contribution; the completed tree update preserves the posterior.A sweep through trees and valid updates of remaining parameters preserves the full posterior, but the sweep need not itself be reversible.Source: §A.4 · pp. 13–14

A.5 Computational cost

This section develops computational and technical foundations for approximation and contraction analysis, giving a per-attempt cost bound for a joint proposal and setting out the fixed-design framework and auxiliary bounds involving rotated truths, priors, split grids, tree size, and Haar small-ball probabilities.

A.5 Computational cost

  • One joint proposal costs O{np + Krot(n + p) + J(n + b) + n(1 + D) + Ib + pN(1 + D)} operations.With fixed p, Krot, D, b, and N ≤ 2D+1 − 1, this is O(n); the bound excludes birth–death moves and leaf refreshes and is per attempt, not for complete sweeps or prescribed Monte Carlo accuracy.Source: §A.5 · pp. 14–15

B.1 Introduction

  • The contraction proof assigns one approximating tree to each additive component, allows separate rotations and rotation-dependent grids, and makes remaining trees nearly zero.It verifies local prior mass, sieve entropy, and prior-tail bounds before applying Jeong (2025)’s Gaussian contraction criterion, following Jeong and Ročková (2023).Source: §B.1 · p. 16

B.2.1 Fixed-design regression model

  • The regression setup uses fixed design points in a bounded set, fixed ambient dimension p ≥ 2, and fixed σ0 > 0.Source: §B.2.1 · p. 16

B.2.2 Additive rotated truth and smoothness classes

  • Each true additive component has its own rotation and active rotated-coordinate set, with componentwise anisotropic Hölder smoothness.The active set indexes coordinates in that component’s rotated system, and the smoothness parameters are fixed as n grows.Source: §B.2.2 · pp. 16–17

B.2.3 RoBART prior with uniform coordinate selection

  • The prior draws tree rotations independently from normalized Haar measure, selects split coordinates uniformly, and generates discrete trees independently conditional on rotations.Leaf means are independent N(0, τ^2) variables, and the noise variance has an independent inverse-gamma prior.Source: §B.2.3 · p. 17

B.2.5 Rotation-adaptive split-nets and additive anisotropic k-d trees

  • For each component, the adaptive split-net uses bn equally spaced cutpoints on each active coordinate and leaves coordinates outside its active set unsplit.A fixed discrete template is evaluated on rotation-dependent numerical grids; the stated construction provides a step-function approximation across the specified local rotations.Source: §B.2.5 · pp. 18, 20, 21
  • The ordered split-net topology and labels are fixed across rotations, and its coefficient-center vector varies continuously with rotation, though hard routing need not be continuous.The continuity argument uses continuous empirical extrema and leaf endpoints; the coefficient-center norm is bounded by the sup norm of h0r.Source: §B.2.5 · p. 22

B.2.6 Auxiliary inputs

  • Under the ν-depth prior, realized trees are finite full binary trees with depth at most p b_n, supporting a tree-size-tail bound uniform in n and rotation.The same bound holds after integrating over the tree rotation.Source: §B.2.6 · p. 23
  • For fixed p and d with log(1/r) ≲ log n, the negative log active-row Haar small-ball probability is O(log n).Source: §B.2.6 · p. 24

B.3 Main theorem

The supplement develops the approximation, prior-mass, and entropy bounds used for posterior contraction with additive components that have separate rotations. Its rate has componentwise smoothness and dimension contributions, while rotation and split-label costs are lower order than tree approximation.

B.3 Main theorem

  • For fixed component parameters, the rate’s factors involving λ_r^d_r are constant in n, while d_r remains in the exponents and rotation and split-label costs are lower order than tree approximation.The stated bound is for function-level contraction and does not assert recovery of rotations, active sets, or an additive decomposition.Source: §B.3 · p. 26

B.4.1 Active-row rotation perturbation

  • The approximation proof first controls how a component template changes when its active rotation rows are perturbed.The lemma’s constants depend on the design bound and fixed smoothness vector.Source: §B.4.1 · p. 26

B.4.2 Approximation in the additive rotated coordinates

  • A componentwise rotated step-function approximation uses the active rotated coordinates and leaves coordinates outside the component’s active set unsplit.The approximation bound is evaluated at the design points under the additive rotation-adaptive split-net condition.Source: §B.4.2 · p. 27

B.5.1 An R-signal-tree good set

  • The prior-mass construction assigns one signal tree to each additive component and lets the remaining trees be nearly null, without requiring every tree rotation to approximate a truth frame.The construction uses a good set with the first R trees carrying the components and the remaining T−R trees nearly null.Source: §B.5 · p. 27, §B.5.1 · pp. 28–29

The same set is contained in a Kullback–Leibler neighborhood satisfying

B.6.1 The sieve

  • The sieve is represented through realized routing configurations and their leaf-incidence matrices, making its image a finite union of compact linear images.The construction does not require continuity of hard routing in the rotations.Source: §B.6 · p. 29, §B.6.1 · p. 30

B.6.2 Routing maps generated by shared rotations

The supplement bounds the complexity of empirical routing maps generated by tree-specific rotations and thresholds, then combines this with coefficient covers to control sieve entropy. It also bounds prior mass outside the sieve.

B.6.2 Routing maps generated by shared rotations

  • For fixed topology and split labels, at most exp{C(p^2 + I+) log n} empirical routing maps arise from tree-specific rotations and thresholds.The count treats routing decisions as binary affine comparisons and gives an upper bound by allowing unconstrained rotation matrices and thresholds.Source: §B.6.2 · p. 30
  • Combining topology and label counts, routing-map counts, and leaf-coefficient covers gives sieve entropy bounded by a term of order K̄_n log n + p^2 log n.The joint entropy result also includes a cover for the noise scale.Source: §B.6.2 · pp. 30–31

B.7 Sieve complement prior mass

  • For any prescribed C_tail, sufficiently large sieve cutoffs make the prior mass of the sieve complement at most exp(−C_tail nε_n^2) for large n.The bound controls large trees, leaf magnitudes, and the noise scale; image-space inequalities need not be equalities because representations may be nonunique.Source: §B.7 · pp. 31–32

B.8 Proof of the main theorem

The proof applies a Gaussian posterior contraction criterion to the induced function and noise-scale parameters. Local prior mass, sieve entropy, and tail bounds yield contraction in the joint metric, including the noise standard deviation.

B.8 Proof of the main theorem

  • The likelihood depends on the forest parameters only through the induced mean vector and noise scale, so the posterior can be expressed on that image space.The proof establishes a positive finite normalizing integral before applying Bayes’ formula to the induced parameters.Source: §B.8 · p. 32
  • A Kullback–Leibler neighborhood receives sufficient prior mass at radius proportional to ε_n, with the function and noise-scale errors controlled together.The argument uses the local prior-mass bound and the identity relating empirical function error to mean-vector error.Source: §B.8 · p. 32
  • The selected sieve’s entropy and prior-tail bounds satisfy the contraction criterion, yielding contraction in the joint metric and for the noise standard deviation.The variance-scale conclusion follows from the standard-deviation contraction after enlarging a fixed multiplier.Source: §B.8 · p. 32

C POSTERIOR CONTRACTION LOWER BOUND FOR AXIS-ALIGNED BART

The supplement constructs a fixed Hölder ridge-function truth and compares posterior contraction for RoBART and axis-aligned BART on the same design. It derives an axis-aligned approximation lower bound using empirical tensor-Haar coefficients.

C POSTERIOR CONTRACTION LOWER BOUND FOR AXIS-ALIGNED BART

  • The proof constructs the fixed truth from a Hölder function of one rotated coordinate and uses tensor-Haar coefficients on the fixed tensor design.The results are stated along n = 2^{mp} and under the specified budget condition; b_n = n is sufficient, not required.Source: C POSTERIOR CONTRACTION LOWER BOUND… · pp. 33–34
  • For a fixed rotated one-dimensional Hölder ridge truth, the axis-aligned BART posterior has a contraction lower bound on the same design where RoBART attains its stated rate.The supplement states that ε_n = o(ε^B_n) for p ≥ 2, so the axis-aligned lower-bound scale is slower than the RoBART rate.Source: C POSTERIOR CONTRACTION LOWER BOUND… · pp. 33, 37
  • At a selected Haar level with 2^jp ≍ K, axis-aligned constant-leaf forests with at most K leaves have an empirical approximation lower bound.The argument selects a level where at least half of the truth coefficients are zero for the forest approximation.Source: C POSTERIOR CONTRACTION LOWER BOUND… · p. 35
  • The lower-bound argument applies to the declared empirical-range prior because its comparison class allows arbitrary numerical cutpoints and leaf values.The theorem’s prior specification uses the full training design’s empirical range and permits empty leaves.Source: C POSTERIOR CONTRACTION LOWER BOUND… · pp. 33, 35

D EXPERIMENTAL SETTINGS

The experiments use a fixed benchmark protocol across 30 replications and a separate illustrative-fit setup; comparator-specific preprocessing and sampler settings are also specified.

D EXPERIMENTAL SETTINGS

  • Across 30 benchmark replications, all methods share inputs and noise, use 200 trees and 1,000 post-burn-in draws, and estimate the noise scale.Each replication uses 9,000 burn-in iterations.Source: D EXPERIMENTAL SETTINGS · p. 38
  • RoBART starts from identity rotations with Krot = 5, γ = 0.08 and joint cutpoint retuning, while BART retains identity rotations.Both use 100 cutpoints per coordinate, leaf shrinkage k = 2, and the stated noise-prior and depth-dependent split settings.Source: D EXPERIMENTAL SETTINGS · p. 38
  • Soft BART uses training-only empirical-distribution preprocessing, while Oblique BART and ridgeBART use training-based affine scaling to [−1, 1].Their sampler updates and additional method-specific settings are specified; ridgeBART uses all predictors for splitting and smoothing.Source: D EXPERIMENTAL SETTINGS · p. 38
  • Figure 1 compares BART, Soft BART, ridgeBART, Oblique BART, and RoBART using 200 trees, 4,000 burn-in iterations, 1,000 unthinned draws, and a 151 × 151 prediction grid.Source: D EXPERIMENTAL SETTINGS · p. 38

Related papers

Loading 2610.10214v1…