Oracle Inequalities for Adaptive Tree Selection

Why Adaptive Tree Selection Needs an Oracle Comparison

A tree-selection procedure compares several candidate partitions and chooses one using data. A useful guarantee should account for two distinct costs: a candidate may approximate the regression function poorly, or it may have many leaves whose predictions are estimated noisily. Selection itself adds another issue: if the same data both determine a candidate tree and assess it, an apparent winner can simply have benefited from that reuse.

We will use an independent validation sample to assess fitted candidates. The resulting oracle inequality compares the selected tree with the best candidate in the available collection, while a separate calculation explains how the candidates’ expected risks reflect approximation and leafwise estimation. Keeping these statements separate is essential: a high-probability validation comparison controls realized fitted risks, not the fitting-noise expectation of each candidate.

Setup and Risk Decomposition

Let \((X,Y)\) be a test observation, with regression function \(m(x)=E[Y\mid X=x]\). For a predictor \(f\), define its prediction risk relative to \(m\) by \(R(f)=E[(f(X)-m(X))^2]\). The corresponding squared validation loss is \((Y-f(X))^2\), whose expectation is \(R(f)+E[\operatorname{Var}(Y\mid X)]\). The second term is the same for every predictor, so comparing expected squared validation losses is equivalent to comparing \(R(f)\).

Suppose an independent structure sample determines a finite collection of candidate tree partitions. A separate fitting sample of size \(n\) estimates the leaf predictions, and a validation sample of size \(m_v\) selects among the fitted candidates. Conditional on the structure sample, the partitions are fixed independently of the fitting responses. The validation observations are independent of both samples. Write \(T\) for a candidate tree, \(K_T\) for its number of leaves, and \(\hat f_T\) for its fitted predictor. Assume every candidate considered for leaf-mean estimation has a positive fitting count in each leaf.

For the expectation calculation below, assume the fitting observations are independent and identically distributed, \(E[Y^2]<\infty\), and \(v_{Tj}=\operatorname{Var}(Y\mid X\in A_{Tj})<\infty\). Conditional on the vector of fitting counts, the responses in leaf \(j\) are independent draws from the distribution of \(Y\) conditional on that leaf. This follows by conditioning an independent identically distributed sample on its cell memberships. In particular, the partition must not have been chosen using these fitting responses.

Proof. In leaf \(j\), the fitted mean has conditional expectation \(\mu_{Tj}\) and conditional variance \(v_{Tj}/n_{Tj}\). For any fixed \(x\) in that leaf, expand the squared error around \(\mu_{Tj}\). The cross term has expectation zero because the fitted mean is conditionally centered at \(\mu_{Tj}\):

Integrate this identity over \(X\). On leaf \(j\), the first term contributes the corresponding part of \(A(T)\), and the constant variance term contributes \(q_{Tj}v_{Tj}/n_{Tj}\). Summing over leaves proves the claim. \(\square\)

This proposition is an expectation over fitting responses conditional on counts. It is not a statement that the realized risk of a particular fitted tree equals, or is bounded by, that expectation.

A Validation Oracle Inequality

Condition on the structure and fitting samples, so the fitted candidates \(f_T\) are fixed. Let the collection contain \(M\) candidates. Assume \(|Y|\leq B_Y\) almost surely and \(|f_T(X)|\leq B_f\) almost surely for every candidate. Then each validation loss lies in \([0,C]\), where \(C=(B_Y+B_f)^2\). For a nonnegative penalty \(\operatorname{pen}(T)\), define the selected tree by minimizing validation mean squared loss plus penalty:

Proof. Let \(Q_T=E[(Y-f_T(X))^2\mid\text{structure and fitting samples}]\), and let \(\hat Q_T\) be its validation average. Hoeffding’s inequality gives, for each fixed candidate, \(P(|\hat Q_T-Q_T|>u)\leq 2\exp(-2m_vu^2/C^2)\). A union bound over the \(M\) candidates shows that, with probability at least \(1-\delta\), every candidate satisfies \(|\hat Q_T-Q_T|\leq\epsilon\), where \(\epsilon=C\sqrt{\log(2M/\delta)/(2m_v)}\). On this event, use the minimizing property of \(\hat T\), for any candidate \(T\):

The last inequality uses \(\operatorname{pen}(\hat T)\geq0\) and \(\hat Q_T\leq Q_T+\epsilon\). Since \(Q_T=R(f_T)+E[\operatorname{Var}(Y\mid X)]\), the common irreducible-noise term cancels from both sides. Taking the minimum over \(T\) proves the result. \(\square\)

A useful choice is \(\operatorname{pen}(T)=\lambda K_T/n\), with \(\lambda\geq0\). This charges candidate trees for leaf complexity relative to the fitting-sample size. The theorem allows any nonnegative penalty; it does not assert that this particular scale is optimal. The validation term also depends on the number \(M\) of candidates, so considering a larger collection requires stronger validation control.

From the Realized Oracle to Approximation and Estimation

The theorem compares the selected fitted tree with the candidates’ realized risks. To express the comparison in approximation-error terms, average over fitting data only after applying the high-probability result correctly. Suppose the validation bound holds conditionally on the structure and fitting samples, the risk is bounded by \(C_R\) for all candidates, and the stated leaf-mean decomposition applies. On the validation event, use the theorem; on its complement, use \(R(f_{\hat T})\leq C_R\). Taking expectations gives

The first inequality follows because the eventwise oracle bound contains \(\min_T\{R(f_T)+\operatorname{pen}(T)\}\), and \(E[\min_T Z_T]\leq\min_T E[Z_T]\). The second uses the proved fitting-risk decomposition, with expectations interpreted over the structure and fitting samples under its stated conditions. The bounded-risk condition controls the failure event. This expected-risk statement is therefore not obtained by replacing a realized candidate risk with its expectation inside the conditional validation theorem; it follows by averaging a valid eventwise inequality and separately controlling the failure event.

Common Pitfalls and Practical Meaning

The bound clarifies the role of adaptation. Independent validation permits selection among data-fitted candidates because, conditional on the fitting data, validation losses are evaluated on fresh observations. The penalty encourages simpler candidates, while the uniform deviation term accounts for selecting from a finite collection. Meanwhile, approximation error and leafwise variance explain why a candidate with more leaves may or may not have lower expected risk.

• Conditioning on a response-adaptive partition as if it were fixed. If the same responses choose the partition and estimate its leaf means, the conditional mean and variance of those means need not be the ordinary ones. Use an independent structure sample, or provide a separate argument that justifies the claimed distribution.
• Replacing realized risk by expected fitting risk in a validation theorem. The theorem controls \(R(f_T)\) for the fitted candidate actually observed. A candidate’s realized risk can exceed its fitting-noise expectation. The expected-risk comparison requires the separate averaging and failure-event argument given above.
• Ignoring the candidate count. A guarantee uniform over \(M\) candidates pays a term involving \(\log M\). A large search can increase selection uncertainty even if the final tree is small.
• Reading an oracle inequality as a claim that selection finds the exact best tree. The result bounds the selected risk relative to a penalized candidate oracle, up to a validation deviation. It need not identify the risk-minimizing tree, and the bound can be loose.