$\mathfrak{E}=\mathfrak{E}^{0},\mathfrak{E}^{1},\ldots,\mathfrak{E}^{k}=\mathfrak{E}^{\prime}$
such that $\mathfrak{E}^{i}\succsim\mathfrak{E}^{i+1}$ for $i=0,1,\ldots,k-1$.

#### Set-up.

Without loss of generality, let $(x_{1},x_{2})$ be a pure interaction for
$f^{*}$. Let $\mathfrak{E}_{\text{bad}}$ be any TSE such that

  * •

$\mathfrak{E}_{\text{bad}}$ is reachable from $\mathfrak{E}_{\emptyset}$;

  * •

There does not exist $\mathfrak{E}\in\Omega_{\text{TSE},m}$ such that
$\mathfrak{E}$ is reachable from $\mathfrak{E}_{\text{bad}}$ but
$\mathfrak{E}_{\text{bad}}$ is not reachable from $\mathfrak{E}$.

Note that such a TSE exists because $\Omega_{\text{TSE},m}$ is finite and
$\succeq$ is a partial ordering on this space. By definition, there exists a
sequence of TSEs
$\mathfrak{E}_{\emptyset}=\mathfrak{E}^{0},\mathfrak{E}^{1},\ldots,\mathfrak{E}^{k}=\mathfrak{E}_{\text{bad}}$
such that $\mathfrak{E}^{i}\succeq\mathfrak{E}^{i+1}$ for $i=0,1,\ldots,k-1$.
We set $\mathcal{A}$ to be the equivalence class of
$\mathfrak{E}_{\text{bad}}$ under $\succeq$ and set $\mathcal{B}$ to be the
outer boundary of $\mathcal{A}$. For $n$ large enough, using Proposition 4.2
and Proposition 4.1, there is a $1-\delta/2$ event over which, for
$i=1,2,\ldots,k$,

$\displaystyle\log p(\mathfrak{E}^{i}|\mathbf{y})-\log
p(\mathfrak{E}^{i-1}|\mathbf{y})$
$\displaystyle\quad=\begin{cases}\frac{n}{2\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})-\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})\right)+O\left(\sqrt{n\log(k/\delta)}\right)&\text{if}~{}\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})>\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})\\\
\frac{\log
n}{2}\left(\textnormal{df}(\mathfrak{E}^{i-1})-\textnormal{df}(\mathfrak{E}^{i})\right)+O\left(\log\right)(k/\delta)&\text{otherwise}.\end{cases}$

In either case, we get

$\frac{p(\mathfrak{E}^{i}|\mathbf{y})}{p(\mathfrak{E}^{i-1}|\mathbf{y})}=\Omega(1).$
(35)

Using Proposition 4.1 again, there is a further $1-\delta/2$ probability event
over which $\Delta\textnormal{BIC}(\mathfrak{E},\mathfrak{E}_{\text{bad}})$
satisfies either (5) or (6) simultaneously for all
$\mathfrak{E}\in\mathcal{B}$ (after dividing the $\delta$ that appears in the
formulas by $|\mathcal{B}|$). Condition on these two events.

#### Hitting precedence probability lower bound.

Using Lemma D.1 and Lemma D.2, we see that
$\mathfrak{E}^{i}\notin\textnormal{OPT}_{m}(f^{*},\infty)$ for
$i=0,1,\ldots,k$. We therefore have

$\displaystyle
P\left\\{\tau_{\mathfrak{E}_{\text{bad}}}<\tau_{\textnormal{OPT}_{m}(f^{*},\infty)}\right\\}$
$\displaystyle\geq
P\left\\{\mathfrak{E}_{i}=\mathfrak{E}^{i}~{}\text{for}~{}i=1,2,\ldots,k\right\\}$
$\displaystyle=\prod_{i=1}^{k}P(\mathfrak{E}^{i-1},\mathfrak{E}^{i}).$ (36)

It suffices to show that $P(\mathfrak{E}^{i-1},\mathfrak{E}^{i})$ is bounded
from below by a constant. To see this, we note that

$\displaystyle P(\mathfrak{E}^{i-1},\mathfrak{E}^{i})$
$\displaystyle=Q(\mathfrak{E}^{i-1},\mathfrak{E}^{i})\min\left\\{\frac{Q(\mathfrak{E}^{i},\mathfrak{E}^{i-1})p(\mathfrak{E}^{i}|\mathbf{y})}{Q(\mathfrak{E}^{i-1},\mathfrak{E}^{i})p(\mathfrak{E}^{i-1}|\mathbf{y})},1\right\\}$
$\displaystyle=\Omega\left(\min\left\\{\frac{p(\mathfrak{E}^{i}|\mathbf{y})}{p(\mathfrak{E}^{i-1}|\mathbf{y})}\right\\},1\right)$
$\displaystyle=\Omega(1),$ (37)

where the first two inequalities follow because the proposal distributions do
not depend on the training sample size $n$, while the last equality follows
from equation (35).

#### BIC lower bound.

Consider $\mathfrak{E}^{\prime}\in\mathcal{B}$. By definition of
$\mathcal{B}$, there exists $\mathfrak{E}\in\mathcal{A}$ such that
$\mathfrak{E}$ and $\mathfrak{E}^{\prime}$ are connected by an edge, but
$\mathfrak{E}\not\succsim\mathfrak{E}^{\prime}$. This implies that either
$\textnormal{Bias}^{2}(\mathfrak{E};f^{*})<\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})$
or
$\textnormal{Bias}^{2}(\mathfrak{E};f^{*})=\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})$
and
$\textnormal{df}(\mathfrak{E};f^{*})<\textnormal{df}(\mathfrak{E}^{\prime};f^{*})$.
Since $\mathfrak{E}$ and $\mathfrak{E}_{\text{bad}}$ are mutually reachable,
we have
$\textnormal{Bias}^{2}(\mathfrak{E};f^{*})=\textnormal{Bias}^{2}(\mathfrak{E}_{\text{bad}};f^{*})$
and
$\textnormal{df}(\mathfrak{E})=\textnormal{df}(\mathfrak{E}_{\text{bad}})$. We
therefore conclude that $\mathfrak{E}^{\prime}$ either has a larger squared
bias or larger degrees of freedom compared to $\mathfrak{E}_{\text{bad}}$.
Applying equations (5) and (6) and taking the minimum sample size $N$ large
enough gives

$\Delta\textnormal{BIC}(\mathfrak{E},\mathfrak{E}_{\text{bad}})\geq\log
n+O\left(\log(|\mathcal{B}|/\delta)\right).$ (38)

#### Conclusion.

Applying Proposition 6.1 with equations (D) and (38), we get a $1-2\delta$
probability event over which

$E\left\\{\tau_{\textnormal{OPT}_{m}(f^{*},\infty)}\right\\}=\Omega\left(n^{1/2}\right).$
(39)

######  Lemma D.1.

For $i=0,1\ldots,k$, no tree in $\mathfrak{E}^{i}$ contains a split on either
$x_{1}$ or $x_{2}$.

###### Proof.

Suppose otherwise. By changing the labeling of $x_{1}$ and $x_{2}$ if
necessary, there exists

$i\coloneqq\min\left\\{1\leq j\leq l\colon\mathfrak{E}_{j}~{}\text{contains
split on}~{}x_{1}\right\\}.$ (40)

Since only “grow” and “prune” moves are allowed, $\mathfrak{E}_{i}$ is
obtained from $\mathfrak{E}_{i-1}$ via a “grow” move that splits a leaf node
$\mathcal{L}$ into:

$\mathcal{L}_{L}\coloneqq\left\\{\mathbf{x}\in\mathcal{L}\colon x_{i}\leq
t\right\\},\quad\quad\mathcal{L}_{R}\coloneqq\left\\{\mathbf{x}\in\mathcal{L}\colon
x_{i}>t\right\\}.$

Define the function
$\psi\coloneqq\mathbf{1}_{\mathcal{L}_{L}}-\mathbf{1}_{\mathcal{L}_{R}}$. Then
the span of
$\left\\{\mathbf{1}_{\mathcal{L}_{L}},\mathbf{1}_{\mathcal{L}_{R}}\right\\}$
is the same as that of $\left\\{\mathbf{1}_{\mathcal{L}},\psi\right\\}$, which
implies that

$\mathcal{F}(\mathfrak{E}_{i})=\textnormal{span}\left\\{\mathcal{F}(\mathfrak{E}_{i-1}),\psi\right\\}.$
(41)

Furthermore, we have $\psi\notin\mathcal{F}(\mathfrak{E}_{i-1})$ since all
functions in $\mathcal{F}(\mathfrak{E}_{i-1})$ do not depend on $x_{1}$. This
implies that
$\textnormal{df}(\mathfrak{E}_{i})=\textnormal{df}(\mathfrak{E}_{i-1})+1$. On
the other hand, since $x_{i}\perp\\!\\!\\!\perp
y~{}|~{}\mathbf{x}\in\mathcal{L}$, we have $\psi\perp y$, which means that
$\textnormal{Bias}^{2}(\mathfrak{E}_{i};f^{*})=\textnormal{Bias}^{2}(\mathfrak{E}_{i-1};f^{*})$.
As such, we have $\mathfrak{E}_{i-1}\not\succsim\mathfrak{E}_{i}$, which gives
a contradiction. ∎

######  Lemma D.2.

For any $\mathfrak{E}\in\Omega_{\text{TSE},m}$, if $\mathfrak{E}$ does not
contain splits on both $x_{1}$ and $x_{2}$, then
$\textnormal{Bias}^{2}(\mathfrak{E};f^{*})>0$.

###### Proof.

Since $(x_{1},x_{2})\not\perp\\!\\!\\!\perp y$, there exist values
$(a_{1},a_{2})$, $(b_{1},b_{2})$ and $(c_{3},c_{4},\ldots,c_{d})$ such that
$f^{*}(a_{1},a_{2},c_{3},\ldots,c_{d})\neq
f^{*}(b_{1},b_{2},c_{3},\ldots,c_{d})$. On the other hand, all functions in
$\mathcal{F}(\mathfrak{E})$ are constant with respect to $x_{1}$ and $x_{2}$,
so that $f^{*}\notin\mathcal{F}(\mathfrak{E})$. ∎

##  Appendix E Proof of Theorem 5.3

#### Set-up.

For convenience, we repeat the relevant construction here. Without loss of
generality, let $x_{1}$ be the feature that gives $f^{*}$ root dependence. By
assumption, there is a threshold $t$ such that splitting the trivial tree on
$x_{1}$ at $t$ gives a decrease in squared bias. We set

$\mathcal{A}=\left\\{\mathfrak{T}\in\Omega_{\text{TSE},1}\colon\mathfrak{T}~{}\text{has
root split on}~{}x_{1}~{}\text{at}~{}t\right\\},$

and

$\mathfrak{T}_{\text{bad}}=\arg\min\left\\{\textnormal{BIC}(\mathfrak{E})\colon\mathfrak{E}\in\mathcal{A}\right\\}.$

Note that the outer boundary of $\mathcal{A}$ is a singleton set comprising
the trivial tree $\mathfrak{T}_{\emptyset}$. By assumption, we have
$\mathcal{A}\cap\textnormal{OPT}_{1}(f^{*},0)=\emptyset$.

We continue this construction by denoting
$\mathfrak{T}_{0}=\mathfrak{T}_{\emptyset}$ and letting $\mathfrak{T}_{1}$ be
a tree structure comprising a single root split at $(x_{1},t)$. By adding the
splits in $\mathfrak{T}_{\text{bad}}$ iteratively, we get a sequence
$\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{k}$ of nested tree
structures with $\mathfrak{T}_{k}=\mathfrak{T}_{\text{bad}}$. By Proposition
4.1 and Proposition 4.2, for any training sample size $n$ large enough, there
is a $1-\delta$ probability event with respect to $\mathbb{P}_{n}$ such that

$\log p(\mathfrak{T}_{j}|\mathbf{y})-\log
p(\mathfrak{T}_{0}|\mathbf{y})=\frac{n}{2\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})-\textnormal{Bias}^{2}(\mathfrak{T}_{j};f^{*})\right)+O\left(\sqrt{n\log(2k/\delta)}\right)$
(42)

for $j=1,2,\ldots,k$. Condition on this event.

We note the following:

$\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})=\int(f^{*})^{2}d\nu-\left(\int
f^{*}d\nu\right)^{2}$ (43) $\textnormal{Bias}^{2}(\mathfrak{T}_{k};f^{*})=0$
(44)
$\textnormal{Bias}^{2}(\mathfrak{T}_{j};f^{*})\leq\textnormal{Bias}^{2}(\mathfrak{T}_{1};f^{*})<\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})\quad\quad\text{for}~{}j=1,2,\ldots,k.$
(45)

Here, the last statement follows from the fact that

$\frac{\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})-\textnormal{Bias}^{2}(\mathfrak{T}_{1};f^{*})}{\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})}=\text{Corr}^{2}\left(f^{*}(\mathbf{x}),\mathbf{1}\left\\{x_{1}\leq
t\right\\}\right)>0,$

and because $\mathfrak{T}_{j}$ is a refinement of $\mathfrak{T}_{1}$ for each
$j=1,2,\ldots,k$.

#### Hitting precedence probability lower bound.

We define a conductance function on $\Omega_{\text{TSE},1}$ via

$c(\mathfrak{T},\mathfrak{T}^{\prime})=p(\mathfrak{T}|\mathbf{y})P(\mathfrak{T},\mathfrak{T}^{\prime}),$

where $P$ is the transition kernel of the BART sampler. It is clear that the
Markov chain for Bayesian CART is equivalent to the Markov chain associated
with the network $(\Omega_{\text{TSE},1},c)$. By ignoring quantities that do
not depend on the training sample size $n$, we get

$\displaystyle c(\mathfrak{T},\mathfrak{T}^{\prime})$
$\displaystyle=\min\left\\{p(\mathfrak{T}|\mathbf{y})Q(\mathfrak{T},\mathfrak{T}^{\prime}),p(\mathfrak{T}^{\prime}|\mathbf{y})Q(\mathfrak{T}^{\prime},\mathfrak{T})\right\\}$
$\displaystyle\asymp\min\left\\{p(\mathfrak{T}|\mathbf{y}),p(\mathfrak{T}^{\prime}|\mathbf{y})\right\\}.$

Consider the set
$\mathcal{C}\coloneqq\Omega\backslash\left(\mathcal{A}\cup\left\\{\mathfrak{T}_{\emptyset}\right\\}\right)$.
Then $\textnormal{OPT}_{1}(f^{*},0)\subset\mathcal{C}$ by assumption, and we
have $\tau_{\mathcal{C}}\leq\tau_{\textnormal{OPT}_{1}(f^{*},0)}$. This means
that it suffices to consider

$P\left\\{\tau_{\mathfrak{T}_{\text{bad}}}<\tau_{\mathcal{C}}\right\\}=\textnormal{HPP}(\mathfrak{T}_{\emptyset};\mathcal{C},\mathfrak{T}_{\text{bad}})$

and to bound it from below. To calculate values for the harmonic function
$\textnormal{HPP}(-;\mathcal{C},\mathfrak{T}_{\text{bad}})$, we use Lemma C.2
to glue all states in $\mathcal{C}$ together without changing the values the
function values. We will abuse notation and denote the new glued state using
$\mathcal{C}$ while continuing to use $c$ to denote the conductance function
on the new state space.

Notice that the only edge from $\mathcal{C}$ connects to
$\mathfrak{T}_{\emptyset}$. As such, we can compute

$\displaystyle c(\mathfrak{T}_{\emptyset},\mathcal{C})$
$\displaystyle\leq\sum_{\mathfrak{T}\sim\mathfrak{T}_{\emptyset}}\min\left\\{p(\mathfrak{T}_{\emptyset}|\mathbf{y})Q(\mathfrak{T}_{\emptyset},\mathfrak{T}),p(\mathfrak{T}|\mathbf{y})Q(\mathfrak{T},\mathfrak{T}_{\emptyset})\right\\}$
$\displaystyle\leq
p(\mathfrak{T}_{\emptyset}|\mathbf{y})\sum_{\mathfrak{T}\sim\mathfrak{T}_{\emptyset}}Q(\mathfrak{T}_{\emptyset},\mathfrak{T})$
$\displaystyle\leq p(\mathfrak{T}_{\emptyset}|\mathbf{y}).$

This implies, using equations (42) and (45), that we can bound the ratios of
conductances for $j=1,2\ldots,k$ as:

$\displaystyle\log\frac{c(\mathfrak{T}_{j},\mathfrak{T}_{j-1})}{c(\mathfrak{T}_{0},\mathcal{C})}$
$\displaystyle\gtrsim\min\left\\{\log p(\mathfrak{T}_{j}|\mathbf{y})-\log
p(\mathfrak{T}_{0}|\mathbf{y}),\log p(\mathfrak{T}_{j-1}|\mathbf{y})-\log
p(\mathfrak{T}_{0}|\mathbf{y})\right\\}$
$\displaystyle\geq\begin{cases}\frac{n}{2\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{T}_{0};f^{*})-\textnormal{Bias}^{2}(\mathfrak{T}_{j-1};f^{*})\right)+O\left(\sqrt{n\log(2k/\delta)}\right)&j\geq
2\\\ 0&j=1.\end{cases}$ (46)

By (45), there is some minimum training sample size $N$ so that for all $n\geq
N$, the right hand side side of (E) is nonnegative. In this case, the
assumptions of Lemma C.5 hold, and we get

$P\left\\{\tau_{\mathfrak{T}_{\text{bad}}}<\tau_{\mathcal{C}}\right\\}=\Omega(1)$
(47)

as desired.

#### BIC lower bound.

From equations (43) and (44), we have

$\displaystyle\Delta\textnormal{BIC}(\mathfrak{T}_{\emptyset},\mathfrak{T}_{\text{bad}})$
$\displaystyle=\frac{n}{\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{T}_{\emptyset};f^{*})-\textnormal{Bias}^{2}(\mathfrak{T}_{\text{bad}};f^{*})\right)+O\left(\sqrt{n\log(2k/\delta)}\right)$
$\displaystyle=\frac{n}{\sigma^{2}}\left(\int(f^{*})^{2}d\nu-\left(\int
f^{*}d\nu\right)^{2}\right)+O\left(\sqrt{n\log(2k/\delta)}\right).$ (48)

#### Conclusion.

Applying Proposition 6.1 with equations (47) and (E), we get a $1-2\delta$
probability event over which

$E\left\\{\tau_{\textnormal{OPT}_{1}(f^{*},0)}\right\\}=\Omega\left(\exp\left(\frac{n}{2\sigma^{2}}\left(\int(f^{*})^{2}d\nu-\left(\int
f^{*}d\nu\right)^{2}\right)+O\left(\sqrt{n\log(2k/\delta)}\right)\right)\right).$

Taking logarithms, dividing by $n$ and applying Markov’s inequality gives

$\mathbb{E}_{n}\left\\{\frac{\log
E\left\\{\tau_{\textnormal{OPT}_{1}(f^{*},0)}\right\\}}{n}\right\\}\geq\frac{(1-\delta)(1-O(n^{-1/2})}{2\sigma^{2}}\left(\int(f^{*})^{2}d\nu-\left(\int
f^{*}d\nu\right)^{2}\right).$

Letting $\delta\to 0$ and taking $n\to\infty$ finishes the proof.

##  Appendix F Splitting Rules, Local Decision Stumps and Coverage

Before proving Theorem 5.1, we first introduce some required machinery.

#### Local decision stump basis.

Let $\mathfrak{T}$ be a tree structure. Let $(v_{j},\tau_{j})$, $j=1,\ldots,l$
denote the splits (or splitting rules) on $\mathfrak{T}$ (the labels of its
internal nodes). Every node on the tree corresponds to rectangular region
$\mathfrak{t}\subset\mathcal{X}$ that is obtained by recursively partitioning
the covariate space using the splits further up the tree. If $\mathfrak{t}$ is
an internal node, it has two children nodes denoted $\mathfrak{t}_{L}$ and
$\mathfrak{t}_{R}$ defined by

$\mathfrak{t}_{L}\coloneqq\left\\{\mathbf{x}\in\mathfrak{t}~{}\colon~{}x_{v}\leq\tau\right\\}$
$\mathfrak{t}_{R}\coloneqq\left\\{\mathbf{x}\in\mathfrak{t}~{}\colon~{}x_{v}>\tau\right\\}$

where $(v,\tau)$ is the split on $\mathfrak{t}$. For each internal node
$(\mathfrak{t}_{j},v_{j},\tau)$, define a _local decision stump function_

$\psi_{j}(\mathbf{x})\coloneqq\frac{\nu(\mathfrak{t}_{R})\mathbf{1}\\{\mathbf{x}\in\mathfrak{t}_{L}\\}-\nu(\mathfrak{t}_{L})\mathbf{1}\\{\mathbf{x}\in\mathfrak{t}_{R}\\}}{\sqrt{\nu(\mathfrak{t}_{L})\nu(\mathfrak{t}_{R})}},$
(49)

where $\mathfrak{t}_{L}$ and $\mathfrak{t}_{R}$ denote the children of
$\mathfrak{t}$. It is easy to check (see for instance Agarwal et al., (2022))
that $\psi_{1},\psi_{2},\ldots,\psi_{l}$ are orthogonal, and that, together
with the constant function $\psi_{0}\equiv 1$, form a basis for
$\mathcal{F}(\mathfrak{T})$. Using this basis makes it more convenient to
analyze the difference between $\mathcal{F}(\mathfrak{T})$ and
$\mathcal{F}(\mathfrak{T}^{\prime})$ when $\mathfrak{T}^{\prime}$ is obtained
from $\mathfrak{T}$ via a “grow” move. Indeed, let $\psi_{l+1}$ denote the
local decision stump corresponding to the new split. We then have
$\mathcal{F}(\mathfrak{T}^{\prime})=\mathcal{F}(\mathfrak{T})\oplus\textnormal{span}(\psi_{l+1})$.

Now consider a TSE
$\mathfrak{E}=(\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{m})$. We
may also write a basis for $\mathcal{F}(\mathfrak{E})$ by concatenating the
bases $\left\\{\psi_{i,1},\psi_{i,2},\ldots,\psi_{i,l_{i}}\right\\}$ for each
tree $\mathfrak{T}_{i}$, together with the constant function. If
$\mathfrak{E}^{\prime}$ is obtained from TSE via a “grow” move, we likewise
have the property
$\mathcal{F}(\mathfrak{E}^{\prime})=\mathcal{F}(\mathfrak{E})\oplus\textnormal{span}(\psi^{\prime})$,
where $\psi^{\prime}$ is the local decision stump corresponding to the new
split. On the other hand, the basis functions from different trees need not be
orthogonal to each other. To regain orthogonality, we use the following lemma:

######  Lemma F.1 (Conditions for orthogonality).

Suppose $\nu=\nu_{1}\times\nu_{2}\times\cdots\times\nu_{d}$ is a product
measure on $\mathcal{X}$. Let $\mathfrak{T}_{1}$ and $\mathfrak{T}_{2}$ be two
trees, and let $I_{1},I_{2}\subset\left\\{1,2,\ldots,d\right\\}$ be two
disjoint subsets of indices such that $\mathfrak{T}_{1}$ and
$\mathfrak{T}_{2}$ contain splits only on features in $I_{1}$ and $I_{2}$
respectively. Then the local decision stumps for both trees,
$\left\\{\psi_{1,1},\psi_{1,2},\ldots,\psi_{1,l_{1}}\right\\}$ and
$\left\\{\psi_{2,1},\psi_{2,2},\ldots,\psi_{2,l_{2}}\right\\}$, are orthogonal
to each other.

###### Proof.

Consider two stumps from different trees: $\psi_{1,k_{1}}$ and
$\psi_{2,k_{2}}$. Under the assumption of a product measure, $\\{x_{i}\colon
i\in I_{1}\\}$ is independent of $\\{x_{i}\colon i\in I_{2}\\}$. Since
$\psi_{1,k_{1}}$ is a function of the first set of variables and
$\psi_{2,k_{2}}$ is a function of the second set, they are thus independent of
each other. We therefore have

$\int\psi_{1,k_{1}}\psi_{2,k_{2}}d\nu=\int\psi_{1,k_{1}}d\nu_{I_{1}}\int\psi_{2,k_{2}}d\nu_{I_{2}}=0,$

where the second equality follows from the fact that all local decision stumps
have mean zero. ∎

######  Lemma F.2 (Existence of informative split).

For any finite contiguous subset of integers $I$, let $g\colon I\to\mathbb{R}$
be non-constant. Let $\nu$ be any measure on $I$. Then there exists a split at
a threshold $t$ with associated decision stump $\psi$ such that $t$ is a knot
for $g$ and

$\left(\int\phi gd\nu\right)^{2}>0.$

As such, there is a sequence of recursive splits with associated local
decision stumps $\psi_{1},\psi_{2},\ldots,\psi_{q}$, where $q$ is the number
of knots of $g$, such that

  * •

$g\in\textnormal{span}\left(\psi_{1},\psi_{2},\ldots,\psi_{q}\right)$;

  * •

$\left(\int\psi_{i}gd\nu\right)^{2}>0$ for $i=1,2,\ldots,q$;

  * •

$\psi_{i}$ splits on a knot of $g$ for $i=1,2,\ldots,q$.

###### Proof.

Let $i_{1},i_{2},\ldots,i_{k}$ denote the knots of $g$, and let
$\tilde{\psi}_{j}$ denote the decision stump functions corresponding to a
split at threshold $x=i_{j}$ for $j=1,2,\ldots,k$, using the formula (49). Let
$\tilde{\psi}_{0}\equiv 1$ denote the constant function as usual. Then it is
easy to see that
$g\in\textnormal{span}\left(\tilde{\psi}_{0},\tilde{\psi}_{1},\ldots,\tilde{\psi}_{k}\right)$.
As such, if $g\perp\tilde{\psi}_{k}$ for $k>1$, then
$g\in\textnormal{span}(\tilde{\psi}_{0})$, i.e. $g$ is a constant function. To
conclude the second statement, we apply the first part recursively to leaves
obtained by making each split. ∎

######  Lemma F.3 (Formula for decrease in bias).

Suppose $\mathfrak{E}^{\prime}$ is obtained from $\mathfrak{E}$ via a “grow”
move. Let $\psi$ be the local decision stump associated with the new split.
Let
$\phi\coloneqq\frac{\psi-\Pi_{\mathcal{F}(\mathfrak{E})}[\psi]}{\left\|\psi-\Pi_{\mathcal{F}(\mathfrak{E})}[\psi]\right\|_{L^{2}(\nu)}}$.
Then for any regression function $f$, we have

$\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f)=\textnormal{Bias}^{2}(\mathfrak{E};f)-\left(\int\phi
fd\nu\right)^{2}.$

###### Proof.

We have

$\mathcal{F}(\mathfrak{E}^{\prime})=\mathcal{F}(\mathfrak{E})\oplus\textnormal{span}(\psi^{\prime})=\mathcal{F}(\mathfrak{E})\oplus\textnormal{span}(\phi),$

with the last expression comprising an orthogonal decomposition. As such, we
have

$\displaystyle\textnormal{Bias}^{2}(\mathfrak{E};f)-\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f)$
$\displaystyle=\left\|f-\Pi_{\mathcal{F}(\mathfrak{E})}[f]\right\|_{L^{2}(\nu)}^{2}-\left\|f-\Pi_{\mathcal{F}(\mathfrak{E})}[f]-\Pi_{\textnormal{span}(\phi)}[f]\right\|_{L^{2}(\nu)}^{2}$
$\displaystyle=\left\|\Pi_{\textnormal{span}(\phi)}[f]\right\|_{L^{2}(\nu)}^{2}$
$\displaystyle=\left(\int\phi fd\nu\right)^{2}$

as we wanted. ∎

#### Coverage.

We first introduce some useful notation. Given a coordinate index $i$, let
$\mathbf{x}^{-i}\in\left\\{1,2,\ldots,b\right\\}^{d-1}$,
$x_{i}\in\left\\{1,2,\ldots,b\right\\}$. Combining these, we let
$(\mathbf{x}^{-i},x_{i})\in\left\\{1,2,\ldots,b\right\\}^{d}$ have $i$-th
coordinate equal to $x_{i}$ and all other coordinates given by
$\mathbf{x}^{-i}$. Also use $\mathbf{e}_{i}\in\mathbb{R}^{d}$ to denote the
$i$-th coordinate vector. Given a real-valued function $f$ defined on
$\left\\{1,2,\ldots,b\right\\}^{d}$, we say that
$\mathbf{x}\in\left\\{1,2,\ldots,b\right\\}^{d}$ is a _jump location_ for $f$
with respect to feature $i$ if $f(\mathbf{x})\neq
f(\mathbf{x}+\mathbf{e}_{i})$. Let $\mathbb{V}$ be a PEM. For each feature
$i=1,2,\ldots,d$ and $t=1,2,\ldots,b$, the _coverage_ of $\mathbb{V}$ of the
split $(i,t)$ is defined as

$\textnormal{coverage}(i,t;\mathbb{V})\coloneqq\left\\{\mathbf{x}^{-i}\in\left\\{1,2,\ldots,b\right\\}^{d-1}\colon\exists
f\in\mathbb{V},(\mathbf{x}^{-i},t)~{}\text{is a jump location
for}~{}f~{}\text{with respect to feature}~{}i\right\\}.$ (50)

If
$\textnormal{coverage}(i,t;\mathbb{V})=\left\\{1,2,\ldots,b\right\\}^{d-1}$,
we say that $\mathbb{V}$ has _full coverage_ of the split $(i,t)$. Note that
given a collection of PEMs
$\mathbb{V}_{1},\mathbb{V}_{2},\ldots,\mathbb{V}_{m}$, we have

$\textnormal{coverage}(i,t;\mathbb{V}_{1}+\mathbb{V}_{2},\ldots,\mathbb{V}_{m})=\bigcup_{j=1}^{m}\textnormal{coverage}(i,t;\mathbb{V}_{j}).$

######  Lemma F.4 (Zero bias requires full coverage of all knots).

Suppose $f^{*}\in\mathbb{V}$, where
$f^{*}(\mathbf{x})=f_{1}(x_{1})+f_{2}(x_{2})+\cdots+f_{m^{\prime}}(x_{m^{\prime}})$
for some univariate functions $f_{1},f_{2},\ldots,f_{m^{\prime}}$. Then for
any feature $1\leq i\leq m^{\prime}$ and any knot $t$ of $f_{i}$, i.e. a value
for which $f_{i}(t)\neq f_{i}(t+1)$, $\mathbb{V}$ has full coverage of the
split $(i,t)$.

###### Proof.

For any $\mathbf{x}^{-i}\in\left\\{1,2,\ldots,b\right\\}^{d-1}$, we have

$f^{*}((\mathbf{x}^{-i},t+1))-f^{*}((\mathbf{x}^{-i},t)=f_{i}(t+1)-f_{i}(t)\neq
0,$

so that $(\mathbf{x}^{-i},t)$ is a jump location for $f^{*}$ with respect to
feature $i$. Hence, if $f^{*}\in\mathbb{V}$, it provides the desired function
in the definition (50). ∎

######  Lemma F.5 (Full coverage implies inclusion of grid cells).

Suppose $\mathbb{V}=\mathcal{F}(\mathfrak{T})$ for a single tree
$\mathfrak{T}$. Suppose $\mathbb{V}$ has full coverage of split
$(i,\xi_{i,1}),(i,\xi_{i,2},\ldots,(i,\xi_{i,q_{i}})$ for $i=1,2,\ldots,k$.
For any choice of $1\leq j_{i}\leq q_{i}$, $i=1,2,\ldots,k$, denote the cell

$\mathcal{C}\coloneqq\left\\{\mathbf{x}\colon\xi_{i,j_{i-1}}<x_{i}\leq\xi_{i,j_{i}}~{}\text{for}~{}i=1,2,\ldots,k\right\\}.$

We then have $\mathbf{1}_{\mathcal{C}}\in\mathbb{V}$.

###### Proof.

Let $\mathbf{x}\in\mathcal{C}$ be any point, and let $\mathcal{L}(\mathbf{x})$
be the leaf of $\mathfrak{T}$ containing $\mathbf{x}$. We claim that
$\mathcal{L}(\mathbf{x})\subset\mathcal{C}$. Suppose not, then there exists a
coordinate direction $i$ in which $\mathcal{L}(\mathbf{x})$ exceeds
$\mathcal{C}$. By reordering if necessary, we may thus assume that
$(\mathbf{x}^{-i},\xi_{i,j_{i}}+1)\in\mathcal{L}(\mathbf{x})$. For any
$f\in\mathbb{V}$, we may write
$f=a_{0}\mathbf{1}_{\mathcal{L}(\mathbf{x})}+\sum_{l=1}^{L}a_{l}\mathbf{1}_{\mathcal{L}_{l}}$,
where $\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{L}$ are leaves in
$\mathfrak{T}$. We then have

$f(\mathbf{x}^{-i},\xi_{i,j_{i}}+1)=a_{0}=f(\mathbf{x}^{-i},\xi_{i,j_{i}}),$

which contradicts our assumption that $\mathbb{V}$ has full coverage of the
split at $(i,\xi_{i,j_{i}})$. We thus have

$\mathcal{C}=\bigcup_{\mathbf{x}\in\mathcal{C}}\mathcal{L}(\mathbf{x})=\bigcup_{\mathcal{L}_{l}\subset\mathcal{C}}\mathcal{L}_{l}.$

Since the right hand side is union over a collection of disjoint sets, we have
$\mathbf{1}_{\mathcal{C}}=\sum_{\mathcal{L}_{l}\subset\mathcal{C}}\mathbf{1}_{\mathcal{L}_{l}}\in\mathbb{V}$.
∎

######  Lemma F.6 (Sufficient condition for lack of coverage).

Let $\mathfrak{T}$ be a tree structure. Consider a split $(i,t)$, and let
$\mathfrak{t}$ be any node in $\mathfrak{T}$. Suppose the following hold:

  * •

$(\mathbf{x}^{-i},t)\in\mathfrak{t}$ for some
$\mathbf{x}^{-i}\in\\{1,2\ldots,b\\}^{d-1}$;

  * •

No ancestor or descendant of $\mathfrak{t}$, including $\mathfrak{t}$ itself,
uses the splitting rule $(i,t)$;

Then if we let $\mathfrak{t}^{-i}$ denote the projection of $\mathfrak{t}$
onto all but the $i$-th coordinate, we have

$\textnormal{coverage}(i,t;\mathcal{F}(\mathfrak{T}))\cap\mathfrak{t}^{-i}=\emptyset.$

###### Proof.

Let $\mathbf{z}^{-i}\in\mathfrak{t}^{-i}$ be any point. By the first
assumption, $t$ is within the bounds of $\mathfrak{t}$ along direction $i$, so
$(\mathbf{z}^{-i},t)\in\mathfrak{t}$. Let $\mathcal{L}_{0}$ be the leaf node
containing $(\mathbf{z}^{-i},t)$. By the second assumption,
$(\mathbf{z}^{-i},t+1)\in\mathcal{L}_{0}$, otherwise some parent of
$\mathcal{L}$ would have made the split $(i,t)$. To show that
$\mathbf{z}^{-i}\notin\textnormal{coverage}(i,t;\mathcal{F}(\mathfrak{T}))$,
it suffices to show that $f(\mathbf{z}^{-i},t+1)=f(\mathbf{z}^{-i},t)$ for all
$f\in\mathcal{F}(\mathfrak{T})$. We may write
$f=\sum_{j=0}^{k}a_{j}\mathbf{1}_{\mathcal{L}_{j}}$ where
$\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{j}$ are other leaves in
$\mathfrak{T}$. We then have
$f(\mathbf{z}^{-i},t+1)=a_{0}=f(\mathbf{z}^{-1},t)$ as we wanted. ∎

######  Proposition F.7 (Dimension of additive functions).

Suppose $f^{*}\in\mathbb{V}$, where
$f^{*}(\mathbf{x})=f_{1}(x_{1})+f_{2}(x_{2})+\cdots+f_{m}(x_{m})$ for some
univariate functions $f_{1},f_{2},\ldots,f_{m^{\prime}}$. Then for any $l<m$
we have $\dim_{l}(f^{*})>\dim_{m}(f^{*})$, while for any $l\geq m$, we have
$\dim_{l}(f^{*})=\dim_{m}(f^{*})$.

###### Proof.

Let $\mathbb{V}=\mathcal{F}(\mathfrak{E})$ for some $\mathfrak{E}$ with $l$
trees, and suppose $f^{*}\in\mathbb{V}$. For $i=1,2,\ldots,m$, let
$(i,\xi_{i,1}),(i,\xi_{i,2}),\ldots,~{}$ $(i,\xi_{i,q_{i}-1})$ denote the
knots of $f_{i}$, where $q_{i}=\dim_{1}(f_{i})$ We claim that $\mathfrak{E}$
must contain a node with splitting rule $(i,\xi_{i,j})$ for every choice of
$i$ and $j$. If not, then $\mathbb{V}$ does not cover $(i,\xi_{i,j})$,
contradicting Lemma F.4.

Construct $\mathfrak{E}$ via a sequence of grow moves in arbitrary order,
thereby deriving a sequence
$\mathfrak{E}_{\emptyset}=\mathfrak{E}^{0},\mathfrak{E}^{1},\ldots,\mathfrak{E}^{k}$.
Consider the first time $t_{i,j}$ for which a split using rule $(i,\xi_{i,j})$
is added to the TSE. Let $\psi_{i,j}$ denote the local decision stump
associated with the split. Since $\mathcal{F}(\mathfrak{E}^{t_{i,j}-1})$ has
zero coverage of $(i,\xi_{i,j})$, we have
$\textnormal{df}(\mathfrak{E}_{i,j})=\textnormal{df}(\mathfrak{E}_{i,j})+1$.
Adding this up over all splits gives the lower bound
$\textnormal{df}(\mathbb{V})\geq\sum_{i=1}^{m}q_{i}-m$. By putting all splits
on feature $i$ on the $i$-th tree for $i=1,2,\ldots,m$, we see that this lower
bound is achievable whenever $l\geq m$, thereby giving

$\dim_{l}(f^{*})=\sum_{i=1}^{m}q_{i}-m=\dim_{m}(f^{*}).$

When $l<m$, then by the pigeonhole principle, there exists splits on different
features $(i,s)$ and $(j,t)$ that occur on the same tree. We claim that this
implies that either there exists two linearly independent local decision
stumps $\phi$ and $\psi$ splitting on $(i,s)$ or the same applies to $(j,t)$.
Suppose not, then the unique local decision stump splitting on $(i,s)$ must
not depend on any other feature, while the same applies to that splitting on
$(j,t)$. However, because nodes depend on the feature used in the root split,
this cannot be simultaneously true if they both correspond to splits on the
same tree. By repeating the argument above, we therefore get
$\textnormal{df}(\mathfrak{E})\geq\sum_{i=1}^{m}q_{i}-m+1$. Since this holds
for any $\mathfrak{E}$, we have

$\dim_{l}(f^{*})\geq\sum_{i=1}^{m}q_{i}-m+1>\dim_{m}(f^{*})$

as we wanted. ∎

##  Appendix G Proof of Theorem 5.1 Part 1

#### Set-up.

For $i=1,2,\ldots,m^{\prime}$, denote $q_{i}=\dim_{1}(f_{i})$, and let
$0=\xi_{i,0}<\xi_{i,1}<\cdots<\xi_{i,q_{i}}=b$ denote the _knots_ of $f_{j}$,
i.e. the values for which $f_{i}(\xi_{i,j})\neq f_{i}(\xi_{i,j}+1)$, together
with the endpoints.121212 $\dim_{1}(f_{i})$ is simply the number of constant
pieces of $f_{i}$ or alternatively, one larger than the number of knots of
$f_{i}$. Without loss of generality, assume that $f_{1},\ldots,f_{m^{\prime}}$
are ordered in descending order of their 1-ensemble dimension, i.e. $q_{1}\geq
q_{2}\geq\cdots\geq q_{m^{\prime}}$.

We now define $\mathfrak{E}_{\text{bad}}$ and a “bad set” $\mathcal{A}$. To
this end, we define a collection of partition models
$\mathbb{V}_{1},\mathbb{V}_{2},\ldots,\mathbb{V}_{m}$ (spans of indicators in
a single partition) as follows. First, for $i=3,4,\ldots,m-1$,
$j=1,2,\ldots,q_{i}$, define the cells
$\mathcal{L}_{i,j}\coloneqq\\{\mathbf{x}\colon\xi_{i,{j-1}}<x_{i}\leq\xi_{i,j}\\}$,
and set
$\mathbb{V}_{i}=\textnormal{span}\left(\left\\{\mathbf{1}_{\mathcal{L}_{i,j}}\colon
j=1,2,\ldots,q_{i}\right\\}\right)$, i.e. for each $i$, $\mathbb{V}_{i}$
contains splits only on feature $i$, and only at the knots of $f_{i}$. This
also implies that $f_{i}\in\mathbb{V}_{i}$. Next, for the remaining component
functions, $i=m,m+1,\ldots,m^{\prime}$, $j_{i}=1,2,\ldots,q_{i}$, define the
cells

$\mathcal{L}_{m,j_{m},j_{m+1},\ldots,j_{m^{\prime}}}\coloneqq\left\\{\mathbf{x}\colon\xi_{i,j_{i-1}}<x_{i}\leq\xi_{i,j_{i}}~{}\text{for}~{}i=m,m+1,\ldots,m^{\prime}\right\\},$
(51)

and set $\mathbb{V}_{m}$ to be the span of their indicators. Observe that
$\mathbb{V}_{m}$ comprises a grid contains splits only on features
$m,{m+1},\ldots,{m^{\prime}}$, and only at the knots of
$f_{m},f_{m+1},\ldots,f_{m^{\prime}}$ respectively. This also implies
$f_{m},f_{m+1},\ldots,f_{m^{\prime}}\in\mathbb{V}_{m}$.

Finally, to introduce inefficiency, we define each of $\mathbb{V}_{1}$ and
$\mathbb{V}_{2}$ to have splits on both features 1 and 2. This construction is
fairly involved and will be detailed in full in the next section. For now, it
suffices to assume that $f_{1}+f_{2}\in\mathbb{V}_{1}+\mathbb{V}_{2}$, which
implies that $f^{*}\in\mathbb{V}_{1}+\mathbb{V}_{2}+\cdots+\mathbb{V}_{m}$.
Define $\mathcal{A}$ via

$\mathcal{A}\coloneqq\left\\{(\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{m})\colon\mathcal{F}(\mathfrak{T}_{i})=\mathbb{V}_{i}~{}\text{for}~{}i=1,2,\ldots,m\right\\}.$

It is clear that for any $\mathfrak{E}\in\mathcal{A}$, we have
$\mathcal{F}(\mathfrak{E})=\mathbb{V}_{1}+\mathbb{V}_{2}+\cdots+\mathbb{V}_{m}$,
so that $\mathcal{A}$ comprises a collection of TSEs with zero bias. We will
set $\mathfrak{E}_{\text{bad}}$ to be a particular element of $\mathcal{A}$.
We set $\mathcal{B}$ to be the outer boundary of $\mathcal{A}$.

#### Hitting precedence probability lower bound.

Step 1: Construction of path. We construct a path in $\Omega_{\text{TSE},m}$
comprising
$\mathfrak{E}_{\emptyset}=\mathfrak{E}^{0},\mathfrak{E}^{1},\ldots,\mathfrak{E}^{s}=\mathfrak{E}_{\text{bad}}$
such that $\mathfrak{E}^{i+1}$ is obtained from $\mathfrak{E}^{i}$ via a
“grow” move for $i=0,1,\ldots,s-1$. To do this, we first apply Lemma F.2 to
obtain, for each feature $j=1,2,\ldots,m^{\prime}$, a sequence of recursive
splits $\psi_{j,1},\psi_{j,2},\ldots,\psi_{j,q_{j}-1}$ such that

  * •

$f_{j}\in\textnormal{span}(\psi_{j,1},\psi_{j,2},\ldots,\psi_{j,q_{j}-1})$;

  * •

$\left(\int f_{j}\psi_{j,l}d\nu_{j}\right)^{2}>0$ for $l=1,2,\ldots,q_{j}-1$;

  * •

$\psi_{j,l}$ splits on a knot of $f_{j}$ for $l=1,2,\ldots,q_{j}-1$.

Note that for convenience, we have identified the splits with their associated
local decision stumps. We break up the path into $m$ segments,
$0=s_{0}<s_{1}<\cdots<s_{m}=k$, with the $j$-th segment comprising
$\mathfrak{E}^{s_{j-1}+1},\mathfrak{E}^{s_{j-1}+2},\ldots,\mathfrak{E}^{s_{j}}$,
possessing the following desired properties:

  * •

During this segment, the $j$-th tree is grown from the empty tree
$\mathfrak{T}_{\emptyset}$ to its final state $\mathfrak{T}_{j}^{*}$, while no
other trees are modified;

  * •

$\mathcal{F}(\mathfrak{T}_{j}^{*})=\mathbb{V}_{j}$;

  * •

$\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})>\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})$
for $i=s_{j-1}+1,s_{j-1}+2,\ldots,s_{j}$.

For $j=3,4,\ldots,m-1$, the splits
$\psi_{j,1},\psi_{j,2},\ldots,\psi_{j,q_{j}-1}$ immediately yield a sequence
of trees
$\mathfrak{T}_{\emptyset}=\mathfrak{T}_{j}^{0},\mathfrak{T}_{j}^{1},\ldots,\mathfrak{T}_{j}^{q_{j}-1}=\mathfrak{T}_{j}^{*}$
such that each $\mathfrak{T}_{j}^{l}$ is obtained from $\mathfrak{T}^{l-1}$
via adding the split $\psi_{j,l}$. Next, assuming correctness of the
construction up to $\mathfrak{E}^{s_{j-1}}$, $\psi_{j,l}$ is orthogonal to
$\mathcal{F}(\mathfrak{E}^{s_{j-1}})$ and also to the previous splits
$\psi_{j,1},\psi_{j,2},\ldots,\psi_{j,l-1}$, by Lemma F.1. This allows us to
apply Lemma F.3 to get

$\textnormal{Bias}^{2}(\mathfrak{E}^{s_{j-1}+i};f)=\textnormal{Bias}^{2}(\mathfrak{E}^{s_{j-1}+i-1};f)-\left(\int\psi_{i}f^{*}d\nu\right)^{2}.$

We then notice that by the independence of different features,

$\left(\int\psi_{i}f^{*}d\nu\right)^{2}=\left(\int\psi_{i}f_{j}d\nu\right)^{2}>0.$

To construct $\mathfrak{T}^{*}_{m}$, fix $0\leq p<m^{\prime}-m$, and assume
that we have constructed a tree $\mathfrak{T}_{m,p}^{*}$ such that the leaves
of $\mathfrak{T}_{m,p}$ comprise the collection (see equation (51)):

$\left\\{\mathcal{L}_{m,j_{m},j_{m+1},\ldots,j_{m+p}}\colon 1\leq j_{m+i}\leq
q_{m+i},i=0,1,2,\ldots,p\right\\}$

We now construct a sequence
$\mathfrak{T}_{m,p}^{*}=\mathfrak{T}_{m,p}^{0},\mathfrak{T}_{m,p}^{1},\ldots,\mathfrak{T}_{m,p}^{r}=\mathfrak{T}_{m,p+1}^{*}$
by looping over the leaves, and for each leaf
$\mathcal{L}=\mathcal{L}_{m,j_{m},j_{m+1},\ldots,j_{m+p}}$, iteratively adding
the splits
$\tilde{\psi}_{1},\tilde{\psi}_{2},\ldots,\tilde{\psi}_{q_{m+p+1}-1}$, where
$\tilde{\psi}_{l}=\nu(\mathcal{L})^{-1/2}\psi_{m+p+1,l}\mathbf{1}_{\mathcal{L}}$
for $l=1,2,\ldots,q_{m+p+1}-1$. Note that these are orthonormal. When adding
the split $\tilde{\psi}_{l}$, the decrease in squared bias can thus be
computed as

$\textnormal{Bias}^{2}(\mathfrak{T}_{m,p}^{i-1})-\textnormal{Bias}^{2}(\mathfrak{T}_{m,p}^{i})=\left(\int\tilde{\psi}_{l}f^{*}d\nu\right)^{2}=\nu(\mathcal{L})\left(\int\psi_{m+p+1,l}f_{j}d\nu\right)^{2}>0.$
(52)

We lift the sequence of tree structures to a sequence of TSEs, using Lemma F.1
and Lemma F.3 as before to translate (52) to be in terms of the sequence of
TSEs.

It remains to define $\mathbb{V}_{1}$ and $\mathbb{V}_{2}$ and construct
$\mathfrak{T}_{1}^{*}$ and $\mathfrak{T}_{2}^{*}$. Let $a_{i}$ be the index of
the knot $\xi_{i,a_{i}}$ forming the threshold for $\psi_{i,q_{i}}$ for
$i=1,2$. For $k=0,1,\ldots,q_{1}-1$, define $b_{k}=k$ for $k<a_{i}$ and
$b_{k}=k+1$ for $k\geq a_{i}$. Similarly, for $l=0,1,\ldots,q_{2}-1$,define
$c_{l}=l$ for $l<a_{2}$ and $c_{l}=l+1$ for $k\geq a_{2}$. Set
$\mathbb{V}_{1}$ to be the span of indicators of the cells

$\mathcal{L}_{1,k,l}\coloneqq\left\\{\mathbf{x}\colon\xi_{1,b_{k-1}}<x_{1}\leq\xi_{1,b_{k}}~{}\text{and}~{}\xi_{2,c_{l-1}}<x_{2}\leq\xi_{2,c_{l}}\right\\}$

for $k=1,2,\ldots,q_{1}-1$ and $l=1,2$. Next, define $d_{0}=0$, $d_{1}=a_{1}$,
$d_{2}=q_{1}$, $e_{1}=0$, $e_{1}=a_{2}$, $e_{2}=q_{2}$. We set
$\mathbb{V}_{2}$ to be the span of indicators of the cells

$\mathcal{L}_{2,k,l}\coloneqq\left\\{\mathbf{x}\colon\xi_{1,d_{k-1}}<x_{1}\leq\xi_{1,d_{k}}~{}\text{and}~{}\xi_{2,e_{l-1}}<x_{2}\leq\xi_{2,e_{l}}\right\\}$

for $k,l=1,2$. We construct $\mathfrak{T}_{1}^{*}$ similarly to
$\mathfrak{T}_{m}^{*}$, through recursive partitioning on $x_{1}$ and $x_{2}$,
but without making the final split on both features. Using the same argument
as before, we obtain the desired sequence of trees. Finally, to construct
$\mathfrak{T}_{2}^{*}$, we simply make the omitted splits on the new tree.
More precisely, we define the splits

$\psi_{1}=\frac{\nu\left\\{x_{1}>\xi_{1,a_{1}}\right\\}\mathbf{1}\left\\{x_{1}\leq\xi_{1,a_{1}}\right\\}-\nu\left\\{x_{1}\leq\xi_{1,a_{1}}\right\\}\mathbf{1}\left\\{x_{1}>\xi_{1,a_{1}}\right\\}}{\sqrt{\nu\left\\{x_{1}\leq\xi_{1,a_{1}}\right\\}\nu\left\\{x_{1}>\xi_{1,a_{1}}\right\\}}}$

and
$\psi_{2}=\nu\left\\{x_{1}\leq\xi_{1,a_{1}}\right\\}^{1/2}\phi\mathbf{1}\left\\{x\leq\xi_{1,a_{1}}\right\\}$,
$\psi_{3}=\nu\left\\{x_{1}>\xi_{1,a_{1}}\right\\}^{1/2}\phi\mathbf{1}\left\\{x>\xi_{1,a_{1}}\right\\}$,
where

$\phi=\frac{\nu\left\\{x_{2}>\xi_{2,a_{2}}\right\\}\mathbf{1}\left\\{x_{2}\leq\xi_{2,a_{2}}\right\\}-\nu\left\\{x_{2}\leq\xi_{2,a_{2}}\right\\}\mathbf{1}\left\\{x_{2}>\xi_{2,a_{2}}\right\\}}{\sqrt{\nu\left\\{x_{2}\leq\xi_{2,a_{2}}\right\\}\nu\left\\{x_{2}>\xi_{2,a_{2}}\right\\}}}.$

It is clear that these, together with the constant function, span
$\mathbb{V}_{2}$. Furthermore, it is easy to see that we have

$\frac{\psi_{1}-\Pi_{\mathbb{V}_{1}}[\psi_{1}]}{\|\psi_{1}-\Pi_{\mathbb{V}_{1}}[\psi_{1}]\|_{L^{2}(\nu)}}=\psi_{1,q_{1}},$
$\frac{\psi_{2}-\Pi_{\mathbb{V}_{1}\oplus\textnormal{span}(\psi_{1})}[\psi_{2}]}{\|\psi_{2}-\Pi_{\mathbb{V}_{1}\oplus\textnormal{span}(\psi_{1})}[\psi_{2}]\|_{L^{2}(\nu)}}=\nu\left\\{x_{1}\leq\xi_{1,a_{1}}\right\\}^{-1/2}\psi_{2,q_{2}}\mathbf{1}\left\\{x\leq\xi_{1,a_{1}}\right\\},$
$\frac{\psi_{3}-\Pi_{\mathbb{V}_{1}\oplus\textnormal{span}(\psi_{1},\psi_{2})}[\psi_{3}]}{\|\psi_{3}-\Pi_{\mathbb{V}_{1}\oplus\textnormal{span}(\psi_{1},\psi_{2})}[\psi_{3}]\|_{L^{2}(\nu)}}=\nu\left\\{x_{1}>\xi_{1,a_{1}}\right\\}^{-1/2}\psi_{2,q_{2}}\mathbf{1}\left\\{x>\xi_{1,a_{1}}\right\\}.$

By construction, we have

$\left(\int\psi_{1,q_{1}}f_{1}d\nu_{1}\right)^{2},\left(\int\psi_{2,q_{2}}f_{2}d\nu_{2}\right)^{2}>0.$

Applying Lemma F.3 then shows that the desired property for the 2nd segment of
TSEs is satisfied. It is clear from the construction that
$\psi_{j1},\psi_{j2},\ldots,\psi_{jq_{j-1}}\in\mathbb{V}_{1}$ and that
$\psi_{jq_{j}}\in\mathbb{V}_{2}$ for $j=1,2$. This implies that
$f_{1}+f_{2}\in\mathbb{V}_{1}+\mathbb{V}_{2}$ as desired.

Step 2: Disjointness from optimal set. We have already proved, in this
construction, that every “grow” move adds a split that decreases bias, and
therefore must be linearly independent from the existing PEM. In other words,
we have
$\textnormal{df}(\mathfrak{E}^{i+1})=\textnormal{df}(\mathfrak{E}^{i})$ for
$i=0,1,\ldots,{k-1}$. Expanding this gives
$\textnormal{df}(\mathfrak{E}_{\text{bad}})=k+1=\sum_{j=1}^{m}(s_{j}-s_{j-1})+1$.
Since each split increments the number of leaf nodes by one, each
$s_{j}-s_{j-1}+1$ is equal to the number of cells in $\mathbb{V}_{j}$, which
we now compute as follows. For $j=3,4,\ldots,m-1$, we have
$s_{j}-s_{j-1}=\dim_{1}(f_{j})-1$, while for $j=m$, we have
$s_{m}-s_{m-1}=\prod_{l=m}^{m^{\prime}}\dim_{1}(f_{l})-1$. Likewise, we have
$s_{1}=\left(\dim_{1}(f_{1})-1\right)\left(\dim_{1}(f_{2})-1\right)-1$ and
$s_{2}-s_{1}=3$. Putting these together gives

$\textnormal{df}(\mathfrak{E}_{\text{bad}})=\sum_{j=3}^{m-1}\dim_{1}(f_{j})+\prod_{l=m}^{m^{\prime}}\dim_{1}(f_{l})+\left(\dim_{1}(f_{1})-1\right)\left(\dim_{1}(f_{2})-1\right)+2-m.$

Let us now show that this is suboptimal, by constructing a TSE
$\mathfrak{E}_{\text{good}}$ with zero bias but fewer degrees of freedom. To
do so, we simply set
$\mathfrak{E}_{\text{good}}=\left(\mathfrak{T}_{1}^{\prime}\mathfrak{T}_{2}^{\prime},\mathfrak{T}_{3}^{*},\ldots,\mathfrak{T}_{m}^{*}\right)$,
where $\mathfrak{T}_{j}^{*}$ has the same structure as in
$\mathfrak{T}_{\text{bad}}$ for $j=3,4,\ldots,m$. On the other hand, we define
$\mathfrak{T}_{1}^{\prime}$ using
$\psi_{1,1},\psi_{1,2},\ldots,\psi_{1,q_{1}}$ and $\mathfrak{T}_{2}^{\prime}$
using $\psi_{2,1},\psi_{2,2},\ldots,\psi_{2,q_{2}}$. By assumption, we have
$f_{j}\in\mathcal{F}(\mathfrak{T}_{j}^{\prime})$ for $j=1,2$, which yields
unbiasedness. The degrees of freedom is given by

$\textnormal{df}(\mathfrak{E}_{\text{good}})=\sum_{j=1}^{m-1}\dim_{1}(f_{j})+\prod_{l=m}^{m^{\prime}}\dim_{1}(f_{l})-m.$
(53)

Taking the difference gives

$\displaystyle\textnormal{df}(\mathfrak{E}_{\text{bad}})-\textnormal{df}(\mathfrak{E}_{\text{good}})$
$\displaystyle=\left(\dim_{1}(f_{1})-1\right)\left(\dim_{1}(f_{2})-1\right)+2-\dim_{1}(f_{1})-\dim_{1}(f_{2})$
$\displaystyle=\left(\dim_{1}(f_{1})-2\right)\left(\dim_{1}(f_{2})-2\right)-1,$

which is strictly larger than 0 if $\dim_{1}(f_{1}),\dim_{1}(f_{2})>3$.
Combining this with the fact that $\textnormal{Bias}^{2}(\mathfrak{E}^{i})>0$
for all $i<s$, we therefore have
$\mathfrak{E}^{i}\notin\textnormal{OPT}_{m}(f^{*},k)$ for all
$i=0,1,\ldots,s$, with
$k=\left(\dim_{1}(f_{1})-2\right)\left(\dim_{1}(f_{2})-2\right)-2$.

Step 3: Conclusion. Using Proposition 4.1 and Proposition 4.2, for $n$ large
enough, there is a $1-\delta/2$ event over which

$\log p(\mathfrak{E}^{i}|\mathbf{y})-\log
p(\mathfrak{E}^{i-1}|\mathbf{y})=\frac{n}{2\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})-\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})\right)+O\left(\sqrt{n\log(s/\delta)}\right).$
(54)

Conditioning on this set, we get
$\frac{p(\mathfrak{E}^{i}|\mathbf{y})}{p(\mathfrak{E}^{i-1}|\mathbf{y})}=\Omega(1)$
for $i=1,2,\ldots,s$ for all $n$ large enough. We may then repeat the
calculations in the proof of Theorem 5.2, specifically equations (D) and (D),
to get

$P\left\\{\tau_{\mathfrak{E}_{\text{bad}}}<\tau_{\textnormal{OPT}_{m}(f^{*},k)}\right\\}\geq
P\left\\{\mathfrak{E}_{i}=\mathfrak{E}^{i}~{}\text{for}~{}i=1,2,\ldots,s\right\\}=\Omega(1).$

#### BIC lower bound.

Consider
$\mathfrak{E}^{\prime}=(\mathfrak{T}_{1}^{\prime},\mathfrak{T}_{2}^{\prime},\ldots,\mathfrak{T}_{m}^{\prime})\in\mathcal{B}$.
By definition of $\mathcal{B}$, there exists
$\mathfrak{E}=(\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{m})\in\mathcal{A}$
such that $\mathfrak{E}^{\prime}$ is obtained from $\mathfrak{E}$ via a
“grow”, “prune”, “change”, or “swap” move. We now consider each type of move
and show that either $\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0$ or
$\textnormal{df}(\mathfrak{E}^{\prime})>\textnormal{df}(\mathfrak{E})=\textnormal{df}(\mathfrak{E}_{\text{bad}})$.
To prove this, we make use of a few key observations.

  * •

Since a move only affects one tree with index $i_{0}$, we have
$\mathfrak{T}_{i}^{\prime}=\mathfrak{T}_{i}$ and
$\mathcal{F}(\mathfrak{T}_{i}^{\prime})=\mathbb{V}_{i}$ for all $i\neq i_{0}$;

  * •

Every split $(i,\xi_{i,j})$ necessary for $\mathcal{F}(\mathfrak{E}^{\prime})$
to be unbiased (see Lemma F.4) has full coverage in a single tree and has zero
coverage in all other trees;

  * •

Since no move is allowed to result in an empty leaf node, if $\mathfrak{t}$ is
an internal node in $\mathfrak{T}_{i_{0}}$ or $\mathfrak{T}_{i_{0}}^{\prime}$
with a split $(i,\xi)$, no ancenstor or descendent of $\mathfrak{t}$ makes the
same split $(i,\xi)$.

For convenience, we denote
$\mathbb{V}_{-i_{0}}=\mathbb{V}_{1}+\cdots\mathbb{V}_{i_{0}-1}+\mathbb{V}_{i_{0}+1}+\cdots+\mathbb{V}_{m}$.

Case 1: “grow” move. Let $\psi$ denote the local decision stump associated
with the new split, and let $\mathcal{L}$ denote the leaf that is split. As
shown earlier, we have $\psi\perp\mathbb{V}_{i_{0}}$. Next, for any boundary
point $(\mathbf{x}^{-j},\xi)$ of $\mathcal{L}$ in direction $j$ (that is not
an a boundary point of the entire space $\mathcal{X}$), $\psi$ has a jump
location at $(\mathbf{x}^{-j},\xi)$ with respect to feature $j$. On the other
hand, by our construction, this means that $(j,\xi)$ is a split fully covered
by $\mathbb{V}_{i_{0}}$ and has zero coverage in $\mathbb{V}_{-i_{0}}$. By
Lemma F.4, this means $\psi\notin\mathbb{V}_{-i_{0}}$. Together, this implies
that $\psi\notin\mathcal{F}(\mathfrak{E})$ and
$\textnormal{df}(\mathfrak{E}^{\prime})=\textnormal{df}(\mathfrak{E})+1$ as
desired.

Case 2: “prune” move. Suppose the pruned split is $(k,t)$ and occurs on a leaf
$\mathcal{L}$. Let $\mathcal{L}^{-k}$ denote the projection of the leaf onto
all but the $k$-th coordinate. Applying the third observation above together
with Lemma F.6 gives

$\textnormal{coverage}(k,t;\mathcal{F}(\mathfrak{E}^{\prime}))\cap\mathcal{L}^{-k}=\textnormal{coverage}(k,t;\mathcal{F}(\mathfrak{T}_{i_{0}}^{\prime}))\cap\mathcal{L}^{-k}=\emptyset.$

Lemma F.4 then implies that
$\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0$.

Case 3: “change” move. Suppose the “changed” split occurs on a node
$\mathfrak{t}$ and is with respect to a feature $k$ at threshold $\xi_{k,j}$.
Then since no descendant of $\mathfrak{t}$ makes the same split, if we let
$\mathfrak{t}^{-k}$ denote the projection of $\mathfrak{t}$ onto all but the
$k$-th coordinate, then as before, we have

$\textnormal{coverage}(k,t;\mathcal{F}(\mathfrak{E}^{\prime}))\cap\mathfrak{t}^{-k}=\textnormal{coverage}(k,t;\mathcal{F}(\mathfrak{T}_{i_{0}}^{\prime}))\cap\mathfrak{t}^{-k}=\emptyset,$

and $\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0$.

Case 4: “swap” move. The swap move can either be performed on a pair of
parent-child nodes, or on a parent with both of its children, if both children
have the same splitting rule. In the latter case,
$\mathcal{F}(\mathfrak{T}^{\prime})=\mathcal{F}(\mathfrak{T})$, contradicting
our assumption that $\mathfrak{E}^{\prime}\notin\mathcal{A}$. In the former
case, let $\mathfrak{t}$ denote the parent, and let $\mathfrak{t}_{L}$ and
$\mathfrak{t}_{R}$ denote its two children. Suppose without loss of generality
that the splitting rules $(j,s)$ and $(k,t)$, of $\mathfrak{t}$ and
$\mathfrak{t}_{L}$ respectively, are to be swapped. Then by construction of
$\mathfrak{T}_{i_{0}}$, $t$ must be a knot for $f_{k}$. By the third
observation, no ancestor of $\mathfrak{t}_{L}$ uses the splitting rule
$(k,t)$, which implies that a descendent of $\mathfrak{t}_{R}$ must split on
$(k,t)$. However, this would mean that this swap move is not allowed, giving a
contradiction.

Finally, using Proposition 4.1 and Proposition 4.2, for $n$ large enough,
there is a $1-\delta/2$ event over which

$\displaystyle\Delta\textnormal{BIC}(\mathfrak{E}^{\prime},\mathfrak{E})$
$\displaystyle\quad=\begin{cases}\frac{n}{\sigma^{2}}\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})+O\left(\sqrt{n\log(|\mathcal{B}|/\delta)}\right)&\text{if}~{}\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0\\\
\log
n\left(\textnormal{df}(\mathfrak{E}^{\prime})-\textnormal{df}(\mathfrak{E}_{\text{bad}})\right)+O\left(\log(|\mathcal{B}|/\delta)\right)&\text{otherwise}.\end{cases}$
(55)

Condition further on this event.

#### Conclusion.

Applying Proposition 6.1 together with equations (54) and (G), while taking
$n$ large enough, we get a $1-2\delta$ probability event over which

$E\left\\{\tau_{\textnormal{OPT}_{m}(f^{*},k}\right\\}=\Omega\left(n^{1/2}\right),$

where $k=\left(\dim_{1}(f_{1})-2\right)\left(\dim_{1}(f_{2})-2\right)-1$.

##  Appendix H Proof of Theorem 5.1 Part 2

#### Set-up.

We first use the same definition of
$\mathfrak{E}_{\text{good}}=(\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{m})$
as in the previous section (see the paragraph immediately preceding equation
(53)). To define
$\mathfrak{E}_{\text{bad}}=(\mathfrak{T}_{1}^{*},\mathfrak{T}_{2}^{*},\ldots,\mathfrak{T}_{m}^{*})$,
we start with $\mathfrak{E}_{\text{good}}$ and simply swap the roles of
$f_{1}$ and $f_{m^{\prime}}$. More precisely, we let
$\mathfrak{T}_{j}^{*}=\mathfrak{T}_{j}$ for $j=2,3,\ldots,m-1$. We define
$\mathfrak{T}_{1}^{*}$ as comprising the local decision stumps
$\phi_{m^{\prime},1},\phi_{m^{\prime},2},\ldots,\phi_{m^{\prime},q_{m^{\prime}}}$,
which were defined in the proof of the hitting precedence probability lower
bound in the previous section. Define
$\mathbb{V}_{j}=\mathcal{F}(\mathfrak{T}_{j}^{*})$ for $j=1,2,\ldots,m-1$. We
then define $\mathbb{V}_{m}$ to be a grid on features
$\left\\{1,m,m+1,\ldots,m^{\prime}-1\right\\}$, or in other words,
$\mathcal{F}(\mathfrak{T}_{m}^{*})$ is the span of indicators of the cells

$\mathcal{L}_{m,j_{m},j_{m+1},\ldots,j_{m^{\prime}}}\coloneqq\left\\{\mathbf{x}\colon\xi_{i,j_{i-1}}<x_{i}\leq\xi_{i,j_{i}}~{}\text{for}~{}i=1,m,m+1,\ldots,m^{\prime}-1\right\\},$
(56)

as we vary $i=1,m,m+1,\ldots,m^{\prime}-1$ and $j_{i}=1,2,\ldots,q_{i}$. We
construct $\mathfrak{T}_{m}^{*}$ such that
$\mathcal{F}(\mathfrak{T}_{m}^{*})$, in the manner described in the proof of
the hitting precedence probability lower bound in the previous section. Here,
recall that $\dim_{1}(f_{1})>\dim_{1}(f_{m})$, which will introduce
suboptimality into $\mathfrak{E}_{\text{bad}}$.

Notice that
$f^{*}\in\mathbb{V}\coloneqq\mathbb{V}_{1}+\mathbb{V}_{2}+\cdots\mathbb{V}_{m}$
via the same argument as in the previous section. Next, we define the set
$\mathcal{A}$ via

$\mathcal{A}\coloneqq\left\\{\left(\mathfrak{E}_{1}^{\prime},\mathfrak{E}^{\prime},\ldots,\mathfrak{E}^{\prime}\right)\colon\mathcal{F}(\mathfrak{E}_{j})\supseteq\mathbb{V}_{j}~{}\text{for}~{}j=1,2,\ldots,m\right\\}.$

We define $\mathcal{B}$ to be the outer boundary of $\mathcal{A}$.

#### Hitting precedence probability lower bound.

This follows the proof of the hitting precedence probability lower bound in
the previous section almost exactly. First, using the same construction, there
is path in $\Omega_{\text{TSE},m}$ comprising
$\mathfrak{E}_{\emptyset}=\mathfrak{E}^{0},\mathfrak{E}^{1},\ldots,\mathfrak{E}^{s}=\mathfrak{E}_{\text{bad}}$
such that $\mathfrak{E}^{i+1}$ is obtained from $\mathfrak{E}^{i}$ via a
“grow” move and

$\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})>\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})$

for $i=0,1,\ldots,s-1$.

Next, we compute

$\textnormal{df}(\mathfrak{E}_{\text{bad}})=\sum_{j=2}^{m-1}\dim_{1}(f_{j})+\dim_{1}(f_{m^{\prime}})+\dim_{1}(f_{1})\prod_{j=m}^{m^{\prime}-1}\dim_{1}(f_{j})-m.$

Taking the difference between this and (53) gives

$\displaystyle\textnormal{df}(\mathfrak{E}_{\text{bad}})-\textnormal{df}(\mathfrak{E}_{\text{good}})$
$\displaystyle=\dim_{1}(f_{m^{\prime}})-\dim_{1}(f_{1})+\dim_{1}(f_{1})\prod_{j=m}^{m^{\prime}-1}\dim_{1}(f_{j})-\prod_{j=m}^{m^{\prime}}\dim_{1}(f_{j})$
$\displaystyle=\left(\dim_{1}(f_{1})-\dim_{1}(f_{m^{\prime}})\right)\prod_{j=m}^{m^{\prime}-1}\dim_{1}(f_{j}),$
(57)

which is strictly larger than 0 if $\dim_{1}(f_{1})>\dim_{1}(f_{m^{\prime}})$.
Combining this with the fact that $\textnormal{Bias}^{2}(\mathfrak{E}^{i})>0$
for all $i<s$, we therefore have
$\mathfrak{E}^{i}\notin\textnormal{OPT}_{m}(f^{*},k-1)$ where $k$ is the
quantity on the right hand side of (H).

Finally, using Proposition 4.1 and Proposition 4.2, for $n$ large enough,
there is a $1-\delta/2$ event over which

$\log p(\mathfrak{E}^{i}|\mathbf{y})-\log
p(\mathfrak{E}^{i-1}|\mathbf{y})=\frac{n}{2\sigma^{2}}\left(\textnormal{Bias}^{2}(\mathfrak{E}^{i-1};f^{*})-\textnormal{Bias}^{2}(\mathfrak{E}^{i};f^{*})\right)+O\left(\sqrt{n\log(s/\delta)}\right).$
(58)

Conditioning on this set, we get
$\frac{p(\mathfrak{E}^{i}|\mathbf{y})}{p(\mathfrak{E}^{i-1}|\mathbf{y})}=\Omega(1)$
for $i=1,2,\ldots,s$ for all $n$ large enough. We may then repeat the
calculations in the proof of Theorem 5.2, specifically equations (D) and (D),
to get

$P\left\\{\tau_{\mathfrak{E}_{\text{bad}}}<\tau_{\textnormal{OPT}_{m}(f^{*},k)}\right\\}\geq
P\left\\{\mathfrak{E}_{i}=\mathfrak{E}^{i}~{}\text{for}~{}i=1,2,\ldots,s\right\\}=\Omega(1).$
(59)

#### BIC lower bound.

Consider
$\mathfrak{E}^{\prime}=(\mathfrak{T}_{1}^{\prime},\mathfrak{T}_{2}^{\prime},\ldots,\mathfrak{T}_{m}^{\prime})\in\mathcal{B}$.
By definition of $\mathcal{B}$, there exists
$\mathfrak{E}=(\mathfrak{T}_{1},\mathfrak{T}_{2},\ldots,\mathfrak{T}_{m})\in\mathcal{A}$
such that $\mathfrak{E}^{\prime}$ is obtained from $\mathfrak{E}$ via a
“prune” move (a “grow” move will now break the defining constraint of
$\mathcal{A}$.) We now show that either
$\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0$ or
$\textnormal{df}(\mathfrak{E}^{\prime})\geq\textnormal{df}(\mathfrak{E}_{\text{bad}})+\min_{1\leq
i\leq m^{\prime}}\dim_{1}(f_{i})-2$.

Let $\mathfrak{T}_{i_{0}}$ be the tree that is pruned, and supposed the prune
split is $(j,t)$, occurring on a node $\mathfrak{t}$. Since
$\mathcal{F}(\mathfrak{T}_{i_{0}}^{\prime})\not\supseteq\mathbb{V}_{i_{0}}$,
$(j,t)$ must be on a feature split on in $\mathfrak{T}_{i_{0}}^{*}$ and on a
knot $\xi_{j,k}$ for $f_{j}$. Furthermore, because only “grow” and “prune”
moves are allowed, and this is the first time
$\mathcal{F}(\mathfrak{T}_{i_{0}}^{\prime})\not\supseteq\mathbb{V}_{i_{0}}$,
$\mathfrak{T}_{i_{0}}^{*}$ must be a subtree of $\mathfrak{T}_{i_{0}}$, and
$\mathfrak{t}$ is an internal node of $\mathfrak{T}_{i_{0}}^{*}$. Using Lemma
F.6, we have
$\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{i_{0}}^{\prime}))\cap\mathfrak{t}^{-j}=\emptyset$.

Suppose that $\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})=0$, i.e.
$f^{*}\in\mathcal{F}(\mathfrak{E}^{\prime})$. Let $I_{1},I_{2},\ldots,I_{m}$
be the subsets of feature indices split on in trees
$\mathfrak{T}_{1}^{*},\mathfrak{T}_{2}^{*},\ldots,\mathfrak{T}_{m}^{*}$
respectively. We claim that there exists some tree $\mathfrak{T}_{i}$, $i\neq
i_{0}$ such that for all choices of coordinates $\mathbf{x}_{I_{i}}$ in the
index set $I_{i}$, there exists a choice of coordinates
$\mathbf{z}_{-I_{i}\cup\\{j\\}}$ in the index set
$\left\\{1,2,\ldots,b\right\\}\backslash(I_{i}\cup\\{j\\})$ such that
$(\mathbf{x}_{I_{i}},\mathbf{z}_{-I_{i}\cup\\{j\\}})\in\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{i}))$.
This claim is proved as Lemma H.1 below. Assuming it for now, let
$\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{L}$ be the leaves of
$\mathfrak{T}_{i}^{*}$. Consider one such leaf $\mathcal{L}_{l}$. Since
$\mathcal{L}_{l}$ does not depend on the features in $I_{i}$, we may pick
$(\mathbf{x}_{I_{i}},\mathbf{z}_{-I_{i}})\in\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{i}))$
such that $(\mathbf{x}_{I_{i}},\mathbf{z}_{-I_{i}})\in\mathcal{L}_{l}$. By
Lemma F.6, $\mathcal{L}_{l}$ in $\mathfrak{T}_{i}$ must contain a descendent
that uses the splitting rule $(j,t)$. In particular, $\mathcal{L}_{l}$ is
split in $\mathfrak{T}_{i}$, and this split can be represented by a local
decision stump $\psi_{l}$. In this manner, we obtain
$\psi_{1},\psi_{2},\ldots,\psi_{L}$. Denote
$\mathbb{U}=\textnormal{span}(\psi_{1},\psi_{2},\ldots,\psi_{L-1})$. We claim
that $\mathbb{U}\cap\mathbb{V}=\emptyset$. To see this, take any
$f=\sum_{l=1}^{L-1}a_{l}\mathbf{1}_{\mathcal{L}_{l}}\in\mathbb{U}$ and assume
that $f\neq 0$. First note that $f\perp\mathbb{V}_{i}$ by orthogonality of
local decision stump features from a single tree. Furthermore, $f$ has jump
locations with respect to features in $I_{i}$. But no function in
$\mathbb{V}_{-i}$ depends on features in $I_{i}$, which means that
$f\notin\mathbb{V}_{-i}$. This gives $f\notin\mathbb{V}$.

Let $\psi^{\prime}$ denote the local decision stump associated to the pruned
split, and let $\mathbb{V}^{\prime}$ denote its orthogonal complement in
$\mathbb{V}$. We have
$\mathbb{V}^{\prime}\subset\mathcal{F}(\mathfrak{E}^{\prime})$ and have
further shown that $\mathbb{U}\subset\mathcal{F}(\mathfrak{E}^{\prime})$. We
therefore have

$\displaystyle\textnormal{df}(\mathfrak{E}^{\prime})$
$\displaystyle=\dim(\mathcal{F}(\mathfrak{E}^{\prime}))$
$\displaystyle\geq\dim(\mathbb{V}^{\prime})+\dim(\mathbb{U})$
$\displaystyle=\textnormal{df}(\mathfrak{E}_{\text{bad}})-1+L-1$
$\displaystyle\geq\textnormal{df}(\mathfrak{E}_{\text{bad}})+\min_{1\leq i\leq
m^{\prime}}\dim_{1}(f_{i})-2.$

Here, the first inequality follows from the trivial intersection of
$\mathbb{V}^{\prime}$ and $\mathbb{U}$.

Using Proposition 4.1 and Proposition 4.2, there is a $1-\delta/2$ event over
which

$\displaystyle\Delta\textnormal{BIC}(\mathfrak{E}^{\prime},\mathfrak{E})$
$\displaystyle\quad=\begin{cases}\frac{n}{\sigma^{2}}\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})+O\left(\sqrt{n\log(|\mathcal{B}|/\delta)}\right)&\text{if}~{}\textnormal{Bias}^{2}(\mathfrak{E}^{\prime};f^{*})>0\\\
\log
n\left(\textnormal{df}(\mathfrak{E}^{\prime})-\textnormal{df}(\mathfrak{E}_{\text{bad}})\right)+O\left(\sqrt{\log(|\mathcal{B}|/\delta)}\right)&\text{otherwise}.\end{cases}$
(60)

Condition further on this event.

#### Conclusion.

Applying Proposition 6.1 together with equations (59) and (H), while taking
$n$ large enough, we get a $1-2\delta$ probability event over which

$E\left\\{\tau_{\textnormal{OPT}_{m}(f^{*},k)}\right\\}=\Omega\left(n^{a/2-1}\right),$

where $k=\max_{1\leq i\leq m^{\prime}}\dim_{1}(f_{i})-\min_{1\leq i\leq
m^{\prime}}\dim_{1}(f_{i})-1$ and $a=\min_{1\leq i\leq
m^{\prime}}\dim_{1}(f_{i})$.

######  Lemma H.1 (Existence of tree covering a cylinder).

There exists some tree $\mathfrak{T}_{i}$, $i\neq i_{0}$ such that for all
choices of coordinates $\mathbf{x}_{I_{i}}$ in the index set $I_{i}$, there
exists a choice of coordinates $\mathbf{z}_{-I_{i}\cup\\{j\\}}$ in the index
set $\left\\{1,2,\ldots,b\right\\}\backslash(I_{i}\cup\\{j\\})$ such that
$(\mathbf{x}_{I_{i}},\mathbf{z}_{-I_{i}\cup\\{j\\}})\in\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{i}))$.

###### Proof.

Let $r_{1},r_{2},\ldots,r_{m}$ be a permutation of $\\{1,2,\ldots,m\\}$, with
$r_{1}=i_{0}$ (this implies that $j\in I_{r_{1}}$). For $k=2,3,\ldots,m-1$,
set $J_{k}=\cup_{i\geq k}I_{r_{i}}$, and set
$\mathbb{V}^{k}=\mathcal{F}(\mathfrak{T}_{r_{k}})+\mathcal{F}(\mathfrak{T}_{r_{k+1}})+\cdots+\mathcal{F}(\mathfrak{T}_{r_{m}})$.

We make the following observation: For some $k$, suppose there exists a
cylinder set $\mathcal{C}_{k}\subset\textnormal{coverage}(j,t;\mathbb{V}^{k})$
that does not depend on any feature in $J_{k}$. Suppose that there exists some
$\mathbf{x}_{I_{r_{k}}}$ in the projection of $\mathcal{C}$ to coordinates in
$I_{r_{k}}$ such that
$(\mathbf{x}_{I_{i}},\mathbf{z}_{-I_{i}\cup\\{j\\}})\notin\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{r_{k}}))$
for all choices of $\mathbf{z}_{-I_{i}\cup\\{j\\}}$. Then taking the
intersection of $\mathcal{C}_{k}$ and
$\\{\mathbf{x}_{I_{r_{k}}}\\}\times\left\\{1,2,\ldots,b\right\\}^{-I_{r_{k}}\cup\\{j\\}}$
gives a cylinder set $\mathcal{C}_{k+1}$ that does not depend on any feature
in $J_{k+1}$ and such that
$\mathcal{C}_{k+1}\subset\textnormal{coverage}(j,t;\mathbb{V}^{k+1})$.

Now, since
$\mathfrak{t}^{-j}\cap\textnormal{coverage}(j,t;\mathcal{F}(\mathfrak{T}_{r_{1}}^{\prime}))=\emptyset$,
we have $\mathfrak{t}^{-j}\subset\textnormal{coverage}(j,t;\mathbb{V}^{2})$.
Since $\mathfrak{t}^{-j}$ is an internal node of $\mathfrak{T}_{r_{1}}^{*}$,
it is a cylinder set that does not depend on any feature in $J_{2}$. By
applying the above observation inductively on $k=2,3,\ldots,m-1$, we obtain
the statement of the lemma. ∎

##  Appendix I Proof of Proposition 6.1

Proposition 6.1 will follow almost immediately from the following more general
result.

######  Proposition I.1 (General statement for recipe).

Let $X_{0},X_{1},\ldots$ be an irreducible and aperiodic discrete time Markov
chain on a finite state space $\Omega$, with stationary distribution $\pi$.
Let $x\in\Omega$ be a state and $\mathcal{C}\subset\Omega$ be a subset such
that their hitting times from an initial state $x_{0}\in\Omega$ satisfy

$P\left\\{\tau_{x}<\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0}\right\\}\geq c$

for some constant $c$. Let $\mathcal{B}\subset\Omega$ be a subset such that
every path from $x$ to $\mathcal{C}$ intersects $\mathcal{B}$. Then the
hitting time of $\mathcal{C}$ satisfies

$E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0}\right\\}\geq\frac{c\pi(x)}{\pi(\mathcal{B})}.$

###### Proof.

By conditioning on the event $\\{\tau_{x}<\tau_{\mathcal{C}}\\}$, we calculate

$\displaystyle E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0}\right\\}$
$\displaystyle\geq
E\left\\{\tau_{\mathcal{C}}\mathbf{1}\left\\{\tau_{x}<\tau_{\mathcal{C}}\right\\}~{}|~{}X_{0}=x_{0}\right\\}$
$\displaystyle=E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0},\tau_{x}<\tau_{\mathcal{C}}\right\\}P\left\\{\tau_{x}<\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0}\right\\}.$

The second multiplicand on the right is lower bounded by $c$ by assumption, so
we just need to bound the first one. Using the strong Markov property, we
first lower bound this as:

$\displaystyle
E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x_{0},\tau_{x}<\tau_{\mathcal{C}}\right\\}$
$\displaystyle=E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x\right\\}+E\left\\{\tau_{x}|\tau_{x}<\tau_{\mathcal{C}}\right\\}$
$\displaystyle\geq E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x\right\\}.$ (61)

Let $Z$ denote the number of times $(X_{t})$ returns to $x$ before hitting
$\mathcal{B}$. Then, assuming that $X_{0}=x$, we have the inequalities

$\tau_{\mathcal{C}}\geq\tau_{\mathcal{B}}\geq Z+1.$

Note that $Z+1$ is a geometric random variable with success probability

$p=\left\\{\tau_{x}^{+}>\tau_{\mathcal{B}}~{}|~{}X_{0}=x\right\\},$

where $\tau_{x}^{+}$ is the first return time to $x$, i.e.

$\min\left\\{t>0\colon X_{t}=x\right\\}.$

We therefore continue (I) to get

$E\left\\{\tau_{\mathcal{C}}~{}|~{}X_{0}=x\right\\}\geq\frac{1}{P\left\\{\tau_{x}^{+}>\tau_{\mathcal{B}}~{}|~{}X_{0}=x\right\\}}.$
(62)

We next write this probability in terms of another random variable $W$, which
we define to be the number of visits to states in $\mathcal{B}$ before
returning to $x$, when the chain is started at $X_{0}=x$. We then have

$P\left\\{\tau_{x}^{+}>\tau_{\mathcal{B}}~{}|~{}X_{0}=x\right\\}=P\left\\{W\geq
1\right\\}\leq E\left\\{W\right\\}.$ (63)

To bound this expectation, for each $y\in\mathcal{B}$, let $W_{y}$ denote the
number of visits to $y$ before returning to $x$, and observe that
$W=\sum_{y\in\mathcal{B}}W_{y}$. Let $\pi$ denote the unique stationary
distribution of $(X_{t})$. Using Lemma I.2, we then have
$E\\{W_{y}\\}\leq\pi(y)/\pi(x)$. Adding up these inequalities, we get

$E\\{W\\}=\sum_{y\in\mathcal{B}}E\\{W_{y}\\}\leq\frac{\pi(y)}{\pi(x)}=\frac{\pi(\mathcal{B})}{\pi(x)}.$
(64)

Combining equations (62), (63), and (64) completes the proof. ∎

###### Proof of Proposition 6.1.

It is clear that the Markov chain induced by a run of the BART sampler is
irreducible and aperiodic, with stationary distribution given by the marginal
posterior $p(\mathfrak{E}|\mathbf{y})$. We hence use Proposition I.1 to get

$E\left\\{\tau_{\textnormal{OPT}_{m}(f^{*},k)}\right\\}=\Omega\left(\frac{p(\mathfrak{E}_{\text{bad}}|\mathbf{y})}{p(\mathcal{B}|\mathbf{y})}\right).$

We now compute

$\displaystyle\frac{p(\mathfrak{E}_{\text{bad}}|\mathbf{y})}{p(\mathcal{B}|\mathbf{y})}$
$\displaystyle\geq\frac{1}{\left|\mathcal{B}\right|}\min_{\mathfrak{E}\in\mathcal{B}}\frac{p(\mathfrak{E}_{\text{bad}}|\mathbf{y})}{p(\mathfrak{E}|\mathbf{y})}$
$\displaystyle=\frac{1}{\left|\mathcal{B}\right|}\exp\left(\min_{\mathfrak{E}\in\mathcal{B}}\left\\{\log
p(\mathfrak{E}_{\text{bad}}|\mathbf{y})-\log
p(\mathfrak{E}|\mathbf{y})\right\\}\right)$
$\displaystyle\geq\frac{1}{\left|\mathcal{B}\right|}\exp\left(\frac{1}{2}\min_{\mathfrak{E}\in\mathcal{B}}\Delta\textnormal{BIC}(\mathfrak{E},\mathfrak{E}_{\text{bad}})-O\left(\sqrt{\log(\left|\mathcal{B}\right|/\delta)}\right)\right)$
$\displaystyle=\Omega\left(\exp\left(\frac{1}{2}\min_{\mathfrak{E}\in\mathcal{B}}\Delta\textnormal{BIC}(\mathfrak{E},\mathfrak{E}_{\text{bad}})\right)\right),$

where the second inequality follows from Proposition 4.2 and holds with
probability at least $1-\delta$. ∎

######  Lemma I.2 (Bounding number of visits).

Let $X_{0},X_{1},\ldots$ be an irreducible and aperiodic discrete time Markov
chain on a finite state space $\Omega$, with stationary distribution $\pi$.
For any two states $x,y\in\Omega$, we have

$\mathbb{E}\left\\{\textnormal{number of visits to $y$ before returning to
$x$}|X_{0}=x\right\\}=\frac{\pi(y)}{\pi(x)}.$ (65)

###### Proof.

Fix $x$ and denote the quantity on the left side of equation (65) by
$\tilde{\pi}(y)$. We may then rewrite equations (1.25) and (1.26) of Levin et
al., (2006) in our notation as follows:

$\pi(y)=\frac{\tilde{\pi}(y)}{E\left\\{\tau_{x}^{+}|X_{0}=x\right\\}},$
$\pi(x)=\frac{1}{E\left\\{\tau_{x}^{+}|X_{0}=x\right\\}},$

where $\tau_{x}^{+}$ is the first return time to $x$. Taking the ratio of the
two equations completes the proof. ∎

##  Appendix J Invariance of PEM Dimension to Change of Measure

######  Lemma J.1 (Characterization of subspace dimension).

Let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ be vectors in an
inner product space. Let $\mathbf{G}$ be the Gram matrix of these vectors, in
other words, its $(i,j)$ entry satisfies
$G_{ij}=\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle$ for $1\leq i,j\leq n$.
Then the dimension of the subspace spanned by
$\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is equal to the number
of nonzero eigenvalues of $\mathbf{G}$.

###### Proof.

By restricting to a linearly independent set, it suffices to show that
$\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ are linearly independent
if and only if $\mathbf{G}$ is invertible. For the forward direction, suppose
$\mathbf{G}$ is not invertible, then there exists a vector of coefficients
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})$ such that
$\boldsymbol{\alpha}^{T}\mathbf{G}\boldsymbol{\alpha}=0$. But in that case, we
have

$0=\boldsymbol{\alpha}^{T}\mathbf{G}\boldsymbol{\alpha}=\left\langle\sum_{i=1}^{n}\alpha_{i}\mathbf{v}_{i},\sum_{i=1}^{n}\alpha_{i}\mathbf{v}_{i}\right\rangle.$

By definition of the inner product, this means that
$\sum_{i=1}^{n}\alpha_{i}\mathbf{v}_{i}=0$, contradicting linear independence.
The reverse direction is similar. ∎

######  Lemma J.2 (Invariance of dimension to covariate distribution).

Let $\nu$ and $\nu^{\prime}$ be two measures on a compact covariate space
$\mathcal{X}$ that are absolutely continuous with respect to each other. Let
$v_{1},v_{2},\ldots,v_{n}\in L^{2}(\mathcal{X},\nu)$. Then
$v_{1},v_{2},\ldots,v_{n}$ span the same subspace in both
$L^{2}(\mathcal{X},\nu)$ and $L^{2}(\mathcal{X},\nu^{\prime})$.

###### Proof.

By restricting to a linearly independent set, it suffices to show that
$v_{1},v_{2},\ldots,v_{n}$ are linearly independent in
$L^{2}(\mathcal{X},\nu)$ if and only if they are linearly independent in
$L^{2}(\mathcal{X},\nu^{\prime})$. By definition of absolute continuity, there
exists a constant $c>0$ such that

$c^{-1}\int_{\mathcal{X}}f(x)d\nu(x)\leq\int_{\mathcal{X}}f(x)d\nu^{\prime}(x)\leq
c\int_{\mathcal{X}}f(x)d\nu(x)$

for any $f\in$ Let $\mathbf{G}$ and $\mathbf{G}^{\prime}$ be their Gram
matrices in $L^{2}(\mathcal{X},\nu)$ and $L^{2}(\mathcal{X},\nu^{\prime})$
respectively. Let $\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})$ be any
vector of coefficients. Then we have

$\displaystyle\boldsymbol{\alpha}^{T}\mathbf{G}\boldsymbol{\alpha}$
$\displaystyle=\int_{\mathcal{X}}\left(\sum_{i=1}^{n}\alpha_{i}v_{i}(x)\right)^{2}d\nu(x)$
$\displaystyle\leq
c\int_{\mathcal{X}}\left(\sum_{i=1}^{n}\alpha_{i}v_{i}(x)\right)^{2}d\nu^{\prime}(x)$
$\displaystyle=c\boldsymbol{\alpha}^{T}\mathbf{G}^{\prime}\boldsymbol{\alpha}.$

Similarly, we get
$\boldsymbol{\alpha}^{T}\mathbf{G}^{\prime}\boldsymbol{\alpha}\leq
c\boldsymbol{\alpha}^{T}\mathbf{G}\boldsymbol{\alpha}$. ∎

This shows that whenever the covariate distribution $\nu$ has full support, it
is equivalent to the uniform measure.

##  Appendix K Real Data Simulations

We further investigated the effect of training sample size on the mixing
performance of BART as we fit it to a number of real world regression
datasets. We studied several datasets used in the random forest paper along
with three of the largest non-redundant datasets from the PMLB benchmark.
Details on the datasets are provided below in Table 2.

Name | Samples | Features
---|---|---
Breast tumor (Romano et al.,, 2021) | 116640 | 9
California housing (Pace and Barry,, 1997) | 20640 | 8
Echo months (Romano et al.,, 2021) | 17496 | 9
Satellite image (Romano et al.,, 2021) | 6435 | 36
Abalone (Nash et al.,, 1994) | 4177 | 8
Diabetes (Efron et al.,, 2004) | 442 | 10
Table 2: Real world datasets studied.

Furthermore, a heuristic estimate of the signal-to-noise ratio present in each
dataset can be obtained by inspecting the simulation results in Tan et al.,
2022b . California housing and Satellite image have relatively high SNR (the
$R^{2}$ of random forest is larger than 0.8), whereas all other datasets have
relatively low SNR (the $R^{2}$ of random forest is lower than 0.6.)

For each dataset we set aside 15% of the overall dataset as a test set. The
remaining data is used as the training data set and is subsampled to create a
variety of sample sizes. For each subsample proportion, we sample a random set
of the training data and fit the BART algorithm on this subset of the training
data with 1, 2, and 5 chains. This is repeated for 100 Monte Carlo iterations
for each sample size and the RMSE on the test set is evaluated each time. The
remainder of the simulation set-up is the same as that of Experiment 3, as
described in Section 8.

#### Results.

The results are displayed in Figure 8. Note that instead of plotting RMSE, we
have chosen to plot relative RMSE, which measures the ratio between the RMSE
obtained from multiple chains and that obtained for a single chain for a given
data setting. Since we are working with real datasets, error is measured with
respect to the observed responses, rather than a true regression function. In
almost all of the real data sets, we see that increasing the number of chains
in the BART algorithm consistently decreases the RMSE of the predictions, and
the performance gap grows with the training sample size. This provides further
evidence that the poor mixing performance of BART applies to real world
datasets. On the other hand, the effect seems to be much less significant
compared to that for the simulated datasets studied in Experiment 3. This is
unsurprising as the RMSE for real datasets incorporates and hence is inflated
by aleatoric uncertainty in the responses. Notably, in the data sets with
higher SNR (California housing and Satellite image), the performance gap
remains significant.

Figure 8:  RMSE for the predictions from BART run with several different
numbers of chains relative to the RMSE obtained from running BART with a
single chain. The X axis displays the percentage of the training data that is
sampled for each Monte Carlo replication. The RMSE is calculated over an
independent test set consisting of 15% of the overall data.

##  Appendix L Additional results for Experiment 3

In order to further explore the effect of the number of chains on mixing
performance, we also repeated Experiment 3 using 20 chains. The results are
shown in Figure 9

---
Figure 9:  The RMSE (top panel) and empirical coverage (bottom panel) of BART
improve if we average posterior samples from multiple sampler chains, given a
fixed total budget of posterior samples. The relative performance gaps
increases with the number of training samples, providing evidence that the
tendency of HPDR hitting time to grow with training sample size is consistent
across a wide range of DGPs. The biggest improvement seems to occur when
increasing the number of chains from 1 to 2 and there seems to be diminishing
returns thereafter. Both RMSE and coverage are calculated on an independent
test set and are averaged over 100 experimental replicates, with error bars
representing $\pm 1.96$SE.