Proving Consistency for Random Partition Regressors

Why Two Conditions Are Needed

A regression tree predicts by averaging the responses in the leaf containing a query point. For this prediction to approach the regression function, two different sources of error must be controlled. A leaf must be small enough that its points have similar regression means, and it must contain enough observations for its sample average to be stable. These requirements are distinct: a very large leaf can be well populated but blur meaningful differences, while very small leaves can localize well but have too few observations.

We give a consistency result for partitions that may be random but are generated independently of the training observations. The proof makes the two requirements explicit. The independence assumption is important: it lets us calculate the occupancy of a query leaf using a binomial distribution. Partitions chosen using the training observations require additional arguments.

Setup and Definitions

The bound on \(Y\) implies \(|m(x)|\leq B\). For a cell \(C\) with positive probability, write \(m_C=E[Y\mid X\in C]\). By iterated expectation, \(m_C=E[m(X')\mid X'\in C]\). Thus \(m_C\) is the population regression mean for the leaf, while the observed leaf average estimates it.

Consistency Theorem and Proof

The proof compares the estimate first with the population mean of its cell, then compares that cell mean with the regression value at the query point. The first difference is estimation error; the second is approximation error. If \(p_n(X)=0\), the event that the query lies in such a cell has probability zero under the joint distribution, so the cell mean below is needed only for positive-mass cells.

For the approximation term, define the modulus of continuity \(\omega(\delta)=\sup\{|m(u)-m(v)|:\|u-v\|\leq\delta,\ u,v\text{ in the support of }X\}\). Uniform continuity gives \(\omega(\delta)\to0\) as \(\delta\downarrow0\). If \(X\) lies in a positive-mass cell \(C\), then \[ |m_C-m(X)| =\left|E[m(X')-m(X)\mid X'\in C,\mathcal{P}_n]\right| \leq \omega(\operatorname{diam}(C)). \] Also \(|m_C-m(X)|\leq2B\). Since the diameter tends to zero in probability, the squared difference tends to zero in probability and is bounded by \(4B^2\); its expectation therefore tends to zero. Indeed, for any bounded nonnegative \(Z_n\) tending to zero in probability, \(E[Z_n]\leq\epsilon+M P(Z_n>\epsilon)\) when \(Z_n\leq M\), so \(E[Z_n]\to0\).

For the estimation term, condition on \(\mathcal{P}_n\) and \(X=x\), and abbreviate the cell probability by \(p\). Then \(N_n(x)\sim\operatorname{Binomial}(n,p)\). Given \(N_n(x)=k>0\), the \(k\) responses in the cell are independent draws from the response distribution conditional on \(X_i\in C_n(x)\). Their mean is \(m_{C_n(x)}\), and their variance is at most \(B^2\), because \(|Y|\leq B\). Consequently, \[ E[(\hat m_n(x)-m_{C_n(x)})^2\mid N_n(x)=k,\mathcal{P}_n,x]\leq \frac{B^2}{k}. \] When \(N_n(x)=0\), the estimate is zero and \(|m_{C_n(x)}|\leq B\), so the squared difference is at most \(B^2\).

To see why these bounds vanish with occupancy, for \(N\sim\operatorname{Binomial}(n,p)\) and \(p>0\), \[ E\!\left[\frac{\mathbf{1}\{N>0\}}{N}\right] \leq 2E\!\left[\frac{1}{N+1}\right] = \frac{2[1-(1-p)^{n+1}]}{(n+1)p} \leq \frac{2}{(n+1)p}. \] The inequality uses \(1/k\leq2/(k+1)\) for integers \(k\geq1\). The equality follows by expanding the binomial probabilities, or integrating \(E[t^N]=(1-p+pt)^n\) from \(0\) to \(1\). In addition, \(P(N=0)=(1-p)^n\leq e^{-np}\). Combining the empty and nonempty cases gives the conditional bound \[ E[(\hat m_n(x)-m_{C_n(x)})^2\mid\mathcal{P}_n,x] \leq B^2\left(e^{-np}+\min\left\{1,\frac{2}{(n+1)p}\right\}\right). \]

Set \(\mu=np\). The right-hand side is bounded by \(2B^2\) and tends to zero whenever \(\mu\to\infty\), since \(2/((n+1)p)\leq2/\mu\). The assumed convergence \(n p_n(X)\xrightarrow{p}\infty\) therefore makes the conditional bound tend to zero in probability. Its boundedness implies that its expectation tends to zero by the bounded-convergence-in-probability argument given above. Finally, applying \((a+b)^2\leq2a^2+2b^2\) to the two error components shows that \(R_n\) is at most twice the expected estimation error plus twice the expected approximation error. Both vanish, proving the theorem. \(\square\)

What Happens When a Condition Fails?

Common Pitfall

A tempting but incorrect argument is: “The leaves shrink, so the tree is consistent.” Shrinking leaves control only the difference between the cell’s population regression mean and \(m(X)\). They do not show that the observed leaf average estimates that population mean. In the last example, the approximation error is zero because \(m\) is constant, yet the prediction is usually zero. The correction is to verify both conditions: cell diameters shrink in probability and expected query-leaf occupancy diverges. Neither condition can replace the other.

The theorem is a sufficient result for an independent random partition and a bounded response. Its proof identifies the roles of localization and occupancy without asserting that every data-adaptive tree satisfies the same binomial calculation. In particular, the independence assumption is used when deriving the conditional distribution of the leaf count.