Fixed-Partition Oracle Bounds

Why Fixed-Partition Bounds Matter

A partition turns a regression problem into a collection of local mean-estimation problems: one mean for each cell. A useful risk bound must account for two distinct costs. A partition can be too coarse to represent the regression function well, while a partition with many or rarely occupied cells can estimate its means unreliably. Fixed-partition oracle bounds put these costs on the same scale and show how cell probabilities and noise enter the comparison.

Here “fixed” means that the partition is specified independently of the training sample. This matters: a bound for one fixed partition does not by itself control a partition chosen after looking at the data. The focus here is the prediction risk of the leafwise sample-mean estimator and its comparison with the best piecewise-constant predictor on that same partition.

Setup and the Partition Oracle

Let \((X_i,Y_i)\), \(i=1,\ldots,n\), be independent and identically distributed training observations, with a fresh test pair \((X,Y)\) from the same distribution. Write \(m(x)=E[Y\mid X=x]\), and assume \(E[Y^2]<\infty\), \(|m(X)|\le M\) almost surely, and \(E[Y-m(X)\mid X]=0\), with \(\operatorname{Var}(Y\mid X)\le \sigma^2\) almost surely. The last two conditions describe mean-zero regression noise with bounded conditional variance.

Fix a measurable partition \(\mathcal P=\{C_1,\ldots,C_K\}\) of the feature space. Write \(p_j=P(X\in C_j)\), and assume \(p_j>0\) for each cell. The best squared-error predictor that is constant on each cell uses that cell’s conditional mean. This is the fixed-partition oracle.

The empty-cell convention makes the estimator defined for every sample. Since \(|m(X)|\le M\), we also have \(|\mu_j|\le M\), so the cost of this convention can be bounded. Define \(N_j=\sum_{i=1}^n \mathbf 1\{X_i\in C_j\}\) and \(v_j=\operatorname{Var}(Y\mid X\in C_j)\). By the law of total variance, \(v_j=E[\operatorname{Var}(Y\mid X)\mid X\in C_j]+\operatorname{Var}(m(X)\mid X\in C_j)\le \sigma^2+M^2\).

Risk Decomposition for a Fixed Partition

For a predictor \(g\), define its squared-error risk by \(R(g)=E[(Y-g(X))^2]\). The regression function \(m\) minimizes this risk. The next identity separates the fixed partition’s approximation cost from the additional error caused by estimating its cell means.

To prove the identity, first condition on the training data, so that \(\hat f_{\mathcal P}\) is a fixed function. The conditional-mean property gives \(R(\hat f_{\mathcal P})-R(m)=E_X[(\hat f_{\mathcal P}(X)-m(X))^2]\): expanding \(Y-\hat f=(Y-m)+(m-\hat f)\), the cross term has expectation zero because \(E[Y-m(X)\mid X]=0\). Now, within cell \(C_j\), \(\hat f_{\mathcal P}(X)-m(X)=(\hat\mu_j-\mu_j)+(\mu_j-m(X))\). The cross term between these two terms has conditional expectation zero given the training data and \(X\in C_j\), because \(E[m(X)-\mu_j\mid X\in C_j]=0\). Summing over cells gives the displayed decomposition, and averaging over training samples proves the identity. \(\square\)

A Bound That Accounts for Cell Occupancy

The risk decomposition reduces the problem to bounding the error of each estimated cell mean. Conditional on \(N_j=k>0\), the \(k\) responses in cell \(C_j\) have mean \(\mu_j\) and variance \(v_j\); their average therefore has conditional squared error \(v_j/k\). If \(N_j=0\), our estimator predicts zero, whose squared error relative to the oracle is \(\mu_j^2\). Since \(N_j\) has a \(\operatorname{Binomial}(n,p_j)\) distribution, this yields an exact expression.

For the exact expression, apply the risk decomposition and condition on each cell’s count. A fresh \(X\) lands in \(C_j\) with probability \(p_j\); on a nonempty cell the conditional mean-squared error of the sample average is \(v_j/N_j\), and on an empty cell it is \(\mu_j^2\). The probability of an empty cell is \((1-p_j)^n\). Combining these contributions gives the formula.

For the bound, if \(N\sim\operatorname{Binomial}(n,p)\), then \(1/k\le 2/(k+1)\) for every integer \(k\ge1\). Also, \[ E\left[\frac{1}{N+1}\right] =\sum_{k=0}^n\frac{1}{k+1}{n\choose k}p^k(1-p)^{n-k} =\frac{1-(1-p)^{n+1}}{(n+1)p} \le\frac{1}{(n+1)p}. \] The equality follows by using \({n\choose k}/(k+1)={n+1\choose k+1}/(n+1)\) and summing the resulting binomial terms. Consequently, \(p_jE[\mathbf 1\{N_j>0\}/N_j]\le 2/(n+1)\). For the empty-cell terms, \((1-p_j)^n\le e^{-np_j}\), so \[ \sum_{j=1}^K p_j\mu_j^2(1-p_j)^n \le M^2e^{-np_{\min}}\sum_{j=1}^K p_j =M^2e^{-np_{\min}}. \] Finally, \(v_j\le\sigma^2+M^2\) for each cell. Substitution proves both inequalities. \(\square\)

Comparing Fixed-Partition Predictors

For a partition \(\mathcal P\), the bound consists of its approximation error \(A_{\mathcal P}\) plus terms that penalize estimating its cell means. A coarse partition may have substantial approximation error but few means to estimate. A finer partition can reduce approximation error, while increasing the sum of cellwise variance contributions and making rare or empty cells more consequential.

For any predetermined collection of candidate partitions, the theorem applies separately to each candidate. In particular, if \(\mathcal P_*\) is a fixed candidate with the smallest displayed bound, the corresponding estimator has expected excess risk bounded by that candidate’s approximation and estimation terms. This is a comparison with a fixed oracle choice; it does not say that one may select the partition using the same data and retain the same bound without further analysis.

Common Pitfall: Ignoring Rare and Empty Cells

A tempting argument is to say that each cell mean has variance \(v_j/N_j\), replace \(N_j\) by its average \(np_j\), and conclude that the estimation contribution is roughly \(\sum_j v_j/n\). This skips the event \(N_j=0\), on which the sample mean is not defined, and treats a random denominator as though it were constant. The correction is to average over the binomial count, as in the theorem, and to include the empty-cell contribution. A lower bound on cell probabilities makes that contribution small: if \(np_{\min}\) is large, \(e^{-np_{\min}}\) is small. If some cells are rare, the bound correctly warns that the sample may not support reliable estimation on those cells.

The result also depends on the partition being fixed independently of the training data. Applying it to a partition chosen after examining the responses requires additional control of the selection process; the fixed-partition calculation alone does not provide that control.