Approximation Error from Cell Diameter

Why Cell Size Controls Approximation

A partition-based regression function assigns one constant prediction to each cell. Even if that constant is chosen optimally for the population distribution, it generally cannot match a regression function that changes within the cell. The resulting discrepancy is the approximation error of the partition. If the regression function is Lipschitz, its values cannot change rapidly over short distances, so the largest cell diameters provide a direct bound on this error.

The bound concerns the population piecewise-constant approximation, not a prediction formed by estimating a cell mean from a finite sample. It isolates how much error can arise from representing a smooth function by constants on a fixed partition.

Definition of the Approximation Error

Let $X$ take values in a subset of $\mathbb{R}^d$, equipped with Euclidean distance, and let $m(x)=E[Y\mid X=x]$ be the regression function. Assume $E[m(X)^2]<\infty$. Consider a fixed, finite, measurable partition $\mathcal{P}=\{A_1,\ldots,A_M\}$ of the covariate space. For each cell with $P(X\in A_j)>0$, define its population mean by $\mu_j=E[m(X)\mid X\in A_j]$. On any zero-probability cell, the value assigned to the piecewise-constant function does not affect its error.

Definition: The population piecewise-constant approximation associated with $\mathcal{P}$ is $m_{\mathcal{P}}(x)=\mu_j$ when $x\in A_j$ and $P(X\in A_j)>0$. Its squared approximation error is $$ \mathcal{A}(\mathcal{P})=E\left[\{m(X)-m_{\mathcal{P}}(X)\}^2\right] =\sum_{j:P(X\in A_j)>0}P(X\in A_j)\operatorname{Var}\{m(X)\mid X\in A_j\}. $$

The equality follows by conditioning on the cell containing $X$: within a cell, $m_{\mathcal{P}}(X)$ is the conditional mean of $m(X)$. This quantity measures variation in the true regression function inside cells. It is not the conditional variance of the outcome $Y$ around $m(X)$, nor does it include error from estimating $\mu_j$.

The Diameter Bound

For a set $A$, its diameter is $\operatorname{diam}(A)=\sup_{x,z\in A}\|x-z\|_2$. Suppose $m$ is $L$-Lipschitz: for every pair $x,z$ in the covariate space, $|m(x)-m(z)|\leq L\|x-z\|_2$. Thus the range of $m$ within a cell cannot exceed $L$ times that cell’s diameter.

Theorem: Suppose $m$ is $L$-Lipschitz and every positive-probability cell $A_j$ has finite diameter. Then $$ \mathcal{A}(\mathcal{P}) \leq \frac{L^2}{4}\sum_{j:P(X\in A_j)>0}P(X\in A_j)\operatorname{diam}(A_j)^2. $$ In particular, $$ \mathcal{A}(\mathcal{P}) \leq \frac{L^2}{4}\max_{j:P(X\in A_j)>0}\operatorname{diam}(A_j)^2. $$

The factor $1/4$ comes from Popoviciu’s variance inequality: a random variable whose values lie in an interval of length $r$ has variance at most $r^2/4$. Here is a proof of the bound, including that inequality.

Bound the range on a cell.
Fix a positive-probability cell $A_j$. For any $x,z\in A_j$, Lipschitz continuity gives $|m(x)-m(z)|\leq L\operatorname{diam}(A_j)$. Therefore the essential range of $m(X)$, conditional on $X\in A_j$, lies in an interval $[a_j,b_j]$ of length at most $L\operatorname{diam}(A_j)$.

Apply the range-to-variance inequality.
If $Z\in[a,b]$ almost surely and $\nu=E[Z]$, then $(Z-a)(b-Z)\geq0$. Taking expectations and rearranging yields $E[Z^2]\leq(a+b)\nu-ab$, so $\operatorname{Var}(Z)\leq(\nu-a)(b-\nu)\leq(b-a)^2/4$. The last inequality follows from $(\nu-a-(b-\nu))^2\geq0$.

Weight and sum the cell bounds.
Use $Z=m(X)$ conditional on $X\in A_j$. Its conditional variance is at most $L^2\operatorname{diam}(A_j)^2/4$. Multiplying by $P(X\in A_j)$ and summing over positive-probability cells gives the first inequality. Since the weighted cell probabilities sum to one, replacing each squared diameter by their maximum gives the second inequality. $\square$

This argument does not assume that $X$ is uniformly distributed, or that a cell is convex. It uses only the maximum distance between points in each cell and the probability weight of that cell.

Worked Example: An Unequal Partition of an Interval

Let $X\sim\operatorname{Uniform}(0,1)$, $m(x)=1+3x$, and partition the interval into $A_1=[0,0.4)$ and $A_2=[0.4,1]$. The Lipschitz constant is $L=3$, the diameters are $0.4$ and $0.6$, and the cell probabilities are $0.4$ and $0.6$. The theorem gives $$ \mathcal{A}(\mathcal{P})\leq \frac{9}{4}\{0.4(0.4)^2+0.6(0.6)^2\} =\frac{9}{4}(0.064+0.216)=0.63. $$

The exact error can also be computed. A uniform variable on an interval of width $w$ has variance $w^2/12$. Because $m(X)=1+3X$, its conditional variance in a cell of width $w$ is $9w^2/12$. Thus $$ \mathcal{A}(\mathcal{P})=0.4\frac{9(0.4)^2}{12}+0.6\frac{9(0.6)^2}{12} =0.048+0.162=0.21. $$ The bound is valid but not exact: it uses the full possible range of $m$ within each cell to control its variance.

Regular Grid Partitions

For the unit cube $[0,1]^d$, divide each coordinate axis into $k$ intervals of width $h=1/k$. The resulting partition has $k^d$ cells. Each cell has Euclidean diameter $\sqrt{d}\,h$, because its largest coordinate-wise separation is $h$ in all $d$ coordinates.

Corollary: If $m$ is $L$-Lipschitz on $[0,1]^d$, the piecewise-constant approximation on a regular grid with $k$ intervals per coordinate satisfies $$ \mathcal{A}(\mathcal{P})\leq \frac{L^2d}{4k^2}. $$

To obtain this result, substitute $\operatorname{diam}(A_j)^2=d/k^2$ into the theorem. The probabilities of all grid cells sum to one, so no assumption about the distribution of $X$ is needed. More generally, if the common side length is $h$, the same argument gives $\mathcal{A}(\mathcal{P})\leq L^2dh^2/4$. The $k^{-2}$ behavior follows from the fact that halving the side length halves the maximum change in a Lipschitz function, and squared error squares that change.

Worked Example: A Two-Dimensional Grid

Let $X$ have any distribution on $[0,1]^2$, let $m(x_1,x_2)=2x_1$, and divide each axis into $k=5$ equal intervals. The gradient has Euclidean norm $2$, so $m$ is $L=2$ Lipschitz. Each square has side $h=1/5=0.2$ and diameter $\sqrt{2}(0.2)$, whose square is $2(0.2)^2=0.08$. Therefore $$ \mathcal{A}(\mathcal{P})\leq \frac{2^2}{4}(0.08)=0.08. $$

For comparison, if $X$ is uniform on the square, then conditional on any grid cell, $X_1$ is uniform on an interval of width $0.2$. The within-cell variance of $2X_1$ is $4(0.2)^2/12=0.013\overline{3}$. This is also the overall approximation error, since every cell has that same conditional variance. The diameter bound is larger, but it applies even when the distribution of $X$ is not uniform.

Worked Example: A Single Cell Under a Nonuniform Distribution

Let $X$ have density $f(x)=2x$ on $[0,1]$, take $m(x)=x^2$, and use one cell $A=[0,1]$. The function is $2$-Lipschitz because $|x^2-z^2|=|x-z|(x+z)\leq2|x-z|$. The cell diameter is $1$, so the bound is $\mathcal{A}(\mathcal{P})\leq2^2/4=1$.

For the exact error, $E[X^2]=\int_0^1x^2(2x)\,dx=1/2$ and $E[X^4]=\int_0^1x^4(2x)\,dx=1/3$. With one cell, the fitted population constant is $E[m(X)]=1/2$. Hence $$ \mathcal{A}(\mathcal{P})=\operatorname{Var}(X^2)=E[X^4]-\{E[X^2]\}^2 =\frac{1}{3}-\frac{1}{4}=\frac{1}{12}. $$ The bound remains valid despite the nonuniform covariate distribution; the distribution affects the exact error but is not needed to calculate this diameter-based upper bound.

Interpretation and a Common Pitfall

The bound explains why small cells are useful for approximating a smooth regression function: reducing the largest cell diameters reduces an upper bound on the population approximation error. For a regular grid, using twice as many intervals per coordinate reduces this bound by a factor of four. This is a statement about the approximation component only; it does not by itself establish that a fitted estimator has lower total error.

Common mistake: treating the bound as an exact error or as a statement about sample leaf means. The theorem does not say that the approximation error equals $L^2\operatorname{diam}(A_j)^2/4$ in every cell. It bounds a conditional variance using the widest range allowed by the assumptions, and the actual variance can be much smaller, as the examples show. Nor does it account for the error from estimating a cell mean using observed responses. To use the result correctly, identify the fixed cells, their diameters, and a valid Lipschitz constant; then interpret the result as an upper bound on the population piecewise-constant approximation error.

Key takeaway: For a fixed partition and an $L$-Lipschitz regression function, the squared error of the population cell-mean approximation is at most $L^2/4$ times the probability-weighted average of squared cell diameters. On a regular grid in $[0,1]^d$, this gives the bound $L^2d/(4k^2)$.

Check Your Understanding

Work through these questions using the definitions and bound above.

Why is the population cell mean the conditional mean of $m(X)$, rather than necessarily the conditional mean of $Y$ itself?
A one-dimensional partition has two positive-probability cells with probabilities $0.25$ and $0.75$, and diameters $0.2$ and $0.4$. For an $L=2$ Lipschitz function, calculate the weighted diameter bound.
What is the squared approximation-error bound for a regular grid with $k=10$ intervals per coordinate in dimension $d=3$, when $L=1$?
Which assumption allows the cellwise range of $m$ to be bounded by its diameter?
Explain why a valid diameter bound need not equal the exact within-cell squared approximation error.