Cell Geometry and Tree Approximation Rates

Why the Shape of a Leaf Matters

A tree partitions the predictor space into leaves and assigns a prediction within each leaf. For a smooth regression function, nearby points have similar regression values, so leaves with small diameter tend to approximate the function well. But a leaf can have small volume and still stretch a long distance in one direction. Such a leaf may have poor approximation error despite its small volume.

The distinction matters because volume also enters the estimation problem: small-probability leaves receive fewer observations. A useful rate argument must therefore control both the number of leaves and their geometry. We study a fixed partition of \([0,1]^d\) into axis-aligned rectangular cells, with a random predictor \(X\) and regression function \(m(x)=E[Y\mid X=x]\). Assume \(Y\) is bounded, \(|Y|\le M\), and \(m\) is Lipschitz: \( |m(x)-m(x')|\le L\|x-x'\|_2\).

For a rectangle, \(v(C)=\prod_{j=1}^d a_j\), while \(\operatorname{diam}(C)^2=\sum_{j=1}^d a_j^2\). Volume measures total size; diameter measures the largest spatial separation that a single leaf must treat as having one prediction. Aspect ratio detects whether the cell is balanced or elongated.

How Volume and Aspect Ratio Control Diameter

A lower bound on volume alone cannot give an upper bound on diameter: a rectangle may become very thin in some coordinates while remaining long in another. A bound on aspect ratio rules out this geometry.

Proof. Let \(a=\max_j a_j\) be the longest side. The aspect-ratio condition implies \(a_j\ge a/\kappa\) for every side. Hence \(v=\prod_{j=1}^d a_j\ge a(a/\kappa)^{d-1}=a^d/\kappa^{d-1}\), so \(a\le \kappa^{(d-1)/d}v^{1/d}\). Since each \(a_j\le a\), \(\operatorname{diam}(C)^2=\sum_j a_j^2\le da^2\le d\,\kappa^{2(d-1)/d}v^{2/d}\). This proves the claim. \(\square\)

Approximation Error on a Partition

Let \(\mathcal P=\{C_1,\ldots,C_K\}\) be a fixed partition, and write \(p_j=P(X\in C_j)\). For cells with \(p_j>0\), define the best constant prediction in a cell by \(m_j=E[m(X)\mid X\in C_j]\). The population cellwise predictor is \(m_{\mathcal P}(x)=m_j\) for \(x\in C_j\). Its squared approximation error is \(E[(m(X)-m_{\mathcal P}(X))^2]\).

Proof. Fix a cell \(C_j\) and \(x\in C_j\). Conditional on \(X\in C_j\), let \(X'\) have the conditional distribution of \(X\) in that cell. Then \(m_j=E[m(X')\mid X'\in C_j]\), and the Lipschitz condition gives \[ |m(x)-m_j| =\left|E[m(x)-m(X')\mid X'\in C_j]\right| \le E[L\|x-X'\|_2\mid X'\in C_j] \le L\operatorname{diam}(C_j) \le L\Delta. \] Squaring and integrating over \(X\) yields the stated bound. \(\square\)

This argument does not require a uniform predictor density: the conditional mean is taken under the actual distribution of \(X\). The geometry enters through the largest diameter of any cell carrying probability. For shape-regular rectangles, the preceding theorem converts a volume bound into a diameter bound and therefore into an approximation bound.

Estimation Error and the Number of Leaves

Approximation error is only one part of risk. A cellwise sample mean is noisy when it contains few observations, and a cell with no observations requires a default prediction. The following calculation isolates this effect for a fixed partition independent of the estimation sample.

Proof. In cell \(C_j\), let \(N_j\) be the number of training predictors in the cell. It has a \(\operatorname{Binomial}(n,p_j)\) distribution. Conditional on \(N_j=r>0\), the observations in that cell are independent draws from the conditional distribution given \(X\in C_j\). Their responses have mean \(m_j\) and variance at most \(M^2\), since \(|Y|\le M\). Thus the conditional mean squared error of their average is at most \(M^2/r\). If \(N_j=0\), the squared error of the default prediction is \(m_j^2\le M^2\). In either case the conditional error is at most \(M^2/(N_j\vee1)\).

For every integer \(r\ge0\), \(1/(r\vee1)\le2/(r+1)\). Also, for \(N_j\sim\operatorname{Binomial}(n,p_j)\) with \(p_j>0\), \[ E\left[\frac{1}{N_j+1}\right] =\frac{1-(1-p_j)^{n+1}}{(n+1)p_j} \le \frac{1}{(n+1)p_j}. \] Consequently \(E[1/(N_j\vee1)]\le 2/((n+1)p_j)\). Weighting cell \(j\)'s error by the probability \(p_j\) that the test predictor falls there gives at most \(2M^2/(n+1)\). Summing over the \(K\) positive-probability cells proves the bound. \(\square\)

Because \(m_{\mathcal P}\) is the conditional mean within each cell, its approximation residual has conditional mean zero in that cell. Therefore its integrated squared error and the estimator's error around \(m_{\mathcal P}\) add in expectation: the cross term is zero. Combining the two results gives the useful fixed-partition risk bound \[ E[(\hat m(X)-m(X))^2]\le L^2\Delta^2+\frac{2M^2K}{n+1}. \] The first term is controlled by geometry; the second is controlled by the number of leaves and the sample size.

When the Standard Smooth-Regression Rate Applies

For a shape-regular partition with \(K\) cells of volume at most \(c/K\), the diameter theorem gives \(\Delta^2\le d\,\kappa^{2(d-1)/d}(c/K)^{2/d}\). Thus the risk bound has the form \(A K^{-2/d}+B K/n\), where \(A\) and \(B\) do not depend on \(n\) or \(K\). The first term decreases with more leaves; the second increases.

Common Mistake: Treating Volume as a Diameter Bound

A tempting but incorrect argument is: “Each leaf has volume at most \(1/K\), so each leaf has diameter at most a constant times \(K^{-1/d}\).” The implication fails without a shape condition. For example, in two dimensions, a rectangle with sides \(1/2\) and \(1/(2K)\) has area \(1/(4K)\), yet its diameter is at least \(1/2\) for every \(K\). Its volume tends to zero while its longest side does not.

The correction is to control the maximum diameter directly, or to impose geometry that implies such control. For axis-aligned rectangles, bounded aspect ratio together with a volume bound does the job. Balanced side lengths are not merely a technical convenience: for smooth functions that vary along the long direction, they can determine whether approximation error actually vanishes.