Consistency of Response-Adaptive Partitions

Why Response Adaptation Needs Its Own Condition

A partitioning method may use the observed responses to decide where to split. That can make its leaves well adapted to the training sample, but it also means the partition and the leaf averages are statistically linked. A split chosen because it separates unusually high and low responses can look predictive even when the apparent pattern is noise.

Consequently, conditions that control cell diameter and occupancy do not, by themselves, control the effect of selecting boundaries using the same responses later averaged within those cells. Two broad remedies are to estimate leaf means with responses not used to choose the partition, or to restrict the collection of partitions enough that empirical averages behave uniformly over all candidates.

Here \(X\) is the predictor, \(Y\) is the response, and \(m(x)=E[Y\mid X=x]\) is the regression function. For a measurable cell \(A\) with \(P(X\in A)>0\), write \(\mu_A=E[Y\mid X\in A]\). The population cell predictor for a partition \(\Pi\) is \(m_\Pi(x)=\mu_A\) when \(x\in A\in\Pi\). Its approximation error is \(E[(m_\Pi(X)-m(X))^2]\). This error describes the coarseness of the partition, not the extra error from estimating the cell means with data.

How Selection Creates Optimism

If a partition is fixed before the responses are observed, a leaf average is an ordinary sample average within a fixed region. With response adaptation, the selected region may instead be one where the observed responses happen to be unusually large or small. The resulting leaf average can differ systematically from its population counterpart. A small training error is therefore not enough to establish prediction consistency.

A Sufficient Condition: Uniform Control Over Candidates

A direct way to allow response-guided selection is to prove that empirical leaf averages are close to population leaf means simultaneously over the candidate cells. Then the selected partition inherits the same control, even though its selection used the responses. The following finite-class condition is sufficient. Its minimum cell-probability assumption is deliberately explicit: very rare cells cannot have reliably estimated means without additional structure.

The approximation condition is important: controlling estimation error cannot make a persistently poor partition approximate \(m\). The theorem instead isolates the selection issue. A larger candidate collection raises the uniform estimation cost through \(\log J_n\); smaller cell probabilities raise it through \(1/q_n\).

Proof. For a candidate cell \(A\), set \(p_A=P(X\in A)\) and \(\mu_A=E[Y\mid X\in A]\). Let \(P_n\) denote an empirical average over the sample. Bernstein's inequality, applied to \(\mathbf 1_{\{X\in A\}}\) and \(Y\mathbf 1_{\{X\in A\}}\), gives deviations of orders \(\sqrt{p_A t/n}+t/n\) and \(B\sqrt{p_A t/n}+Bt/n\), respectively. More precisely, with probability at least \(1-\delta\), simultaneously for every candidate cell,

Indeed, each inequality fails with probability at most \(2e^{-t}\); summing these failure probabilities over the two quantities for \(J_n\) cells gives at most \(4J_ne^{-t}=\delta\). Since \(\log(2J_n)/(nq_n)\to0\), for fixed \(\delta\) we have \(t/(nq_n)\to0\). Thus, eventually, the first deviation bound is at most \(p_A/2\) for every cell, so \(P_n\mathbf 1_A\ge p_A/2>0\).

The empirical leaf average on \(A\) is \(P_n(Y\mathbf 1_A)/P_n\mathbf 1_A\). Since \(|\mu_A|\le B\) and \(E[Y\mathbf 1_A]=p_A\mu_A\), its difference from \(\mu_A\) is bounded by

Substituting the simultaneous deviations and \(P_n\mathbf 1_A\ge p_A/2\) shows that, for a universal constant \(C\), the absolute difference is at most \(CB\{\sqrt{t/(nq_n)}+t/(nq_n)\}\) on every candidate cell. This bound holds simultaneously before the data-dependent choice is made, so it also holds on every cell of \(\hat\Pi_n\). Call the bound \(r_n\). For a fresh \(X\), decompose the prediction error into the empirical leaf-mean error and the population approximation error. The inequality \((a+b)^2\le 2a^2+2b^2\) gives

For fixed \(\delta\), \(r_n\to0\), and the second term tends to zero in probability by assumption. The deviation event has probability at least \(1-\delta\); since \(\delta>0\) is arbitrary, the risk converges to zero in probability. \(\square\)

A Sufficient Condition: Honest Estimation

Honesty avoids direct reuse of responses by separating the partition-selection sample from the leaf-estimation sample. Conditional on the selection sample, the chosen partition is fixed, and the estimation responses are independent of its selection. The next bound makes the remaining occupancy requirement explicit.

Derivation. Conditional on the partition, the number \(N\) of estimation observations in \(A\) has a \(\operatorname{Binomial}(m,p)\) distribution. Given \(N=k>0\), the observations in the cell are independent draws from the conditional distribution given \(X\in A\). Their average is unbiased for \(\mu_A\) and has variance at most \(B^2/k\), since \(\operatorname{Var}(Y\mid X\in A)\le B^2\). When \(N=0\), the squared error of the zero default is \(\mu_A^2\le B^2\). Therefore the mean squared error is at most

Now \(P(N=0)=(1-p)^m\le e^{-mp}\). For integers \(k\ge1\), \(1/k\le2/(k+1)\). Also, direct expansion of the binomial probabilities gives

It follows that \(E[\mathbf 1_{\{N>0\}}/N]\le2/((m+1)p)\), proving the bound. \(\square\)

What the Conditions Do—and Do Not—Guarantee

Honesty and complexity control address different parts of the problem. Honesty removes the direct link between the responses used to select a partition and those used to estimate its means. Uniform control allows that link, but requires all candidate-cell means to be sufficiently well estimated at once. Neither remedy alone guarantees that the selected partition has small approximation error, and neither can compensate for cells that remain too sparsely populated.

The finite-class theorem is one concrete complexity restriction, not a claim that every response-adaptive partition is consistent. For a large or continuous candidate collection, a corresponding argument needs a suitable uniform concentration result for that collection. Merely counting leaves in the final fitted tree does not count all the alternative partitions searched to obtain it.

Common Mistake

• Wrong reasoning: “The leaf diameters shrink and the fitted leaves contain many observations, so the response-adaptive estimator is consistent.”
• Correction: Those facts can control approximation and occupancy, but do not by themselves control selection based on the same responses. Also establish honesty or a uniform estimation bound over the candidate partitions, and require the selected partition's population approximation error to vanish.