Selecting Resolution: Worked Rate Calculations

Why Resolution Must Be Chosen

A partition estimator divides the predictor domain into cells and estimates the regression function separately, or locally, within each cell. The resolution controls a basic tradeoff: smaller cells can represent a changing regression function more accurately, but the observations are spread across more cells, making estimation noisier. The practical question is not simply whether to use a fine partition. It is how fine to make it for the available sample size and the smoothness and dimension of the problem.

We will work with a \(d\)-dimensional predictor \(X\) on \([0,1]^d\). Let \(K\) denote the number of subdivisions along each coordinate axis. The cells then have side length \(h=1/K\), and there are \(K^d\) cells in total. For a locally polynomial estimator of adequate degree on a Hölder-smooth regression function, the squared approximation error is of order \(K^{-2\alpha}\), while the estimation term is of order \(K^d/n\). The first term decreases as the cells get finer; the second increases.

These expressions describe the usual integrated squared-error upper bound, under conditions ensuring the partition estimator is well behaved. In particular, take a fixed dimension \(d\), smoothness \(\alpha>0\), a design distribution with a density bounded above and away from zero on the domain, and errors with conditional mean zero and bounded conditional variance. The approximation order also requires a local polynomial degree sufficient for the stated Hölder smoothness. We use positive constants \(A\) and \(B\), independent of \(n\) and \(K\), to write the bound as \(A K^{-2\alpha}+B K^d/n\). The constants can depend on the class and estimator; rate calculations track the powers of \(n\), not those constants.

Deriving the Balanced Resolution

First ignore constants and treat \(K\) as a positive real number. The balance equation is

Multiplying by \(nK^{2\alpha}\) gives \(n=K^{2\alpha+d}\). Therefore the balanced resolution and its associated rate are

The resolution \(K_{\mathrm{bal}}\) is a number of subdivisions per coordinate, not the total number of cells. At this choice, the total number of cells is \(K_{\mathrm{bal}}^d=n^{d/(2\alpha+d)}\). Confusing these two quantities changes the exponent and leads to an incorrect variance calculation.

Proof. Substituting \(K_{\mathrm{bal}}=n^{1/(2\alpha+d)}\) gives

and

Thus both terms have the stated order. For integer resolution, write \(K=\lceil K_{\mathrm{bal}}\rceil\). Since \(K_{\mathrm{bal}}\geq1\), we have \(K_{\mathrm{bal}}\leq K\leq 2K_{\mathrm{bal}}\). Consequently,

Both terms are therefore bounded by constant multiples of \(n^{-2\alpha/(2\alpha+d)}\), which proves the claim. \(\square\)

This balance also gives a simple justification for the choice. If \(K\leq K_{\mathrm{bal}}\), the approximation term is at least \(K_{\mathrm{bal}}^{-2\alpha}\). If \(K\geq K_{\mathrm{bal}}\), the estimation term is at least \(K_{\mathrm{bal}}^d/n\). Since these two quantities agree, moving to either side of the balance cannot make both terms smaller. This argument concerns the stated upper-bound terms; by itself it does not prove a minimax lower bound.

Worked Rate Calculations

How Dimension and Smoothness Change the Choice

Taking logarithms of the balanced resolution makes its dependencies transparent:

For fixed \(d\) and \(n>1\), increasing \(\alpha\) increases the denominator, so \(K_{\mathrm{bal}}\) decreases. In other words, greater smoothness calls for a coarser balanced partition. This may seem counterintuitive if one thinks only about approximation: smooth functions can indeed be approximated accurately with relatively wide cells. Fewer cells also reduce estimation variance, and the balance is reached at a smaller resolution.

For fixed \(\alpha\) and \(n>1\), increasing \(d\) also decreases \(K_{\mathrm{bal}}\). Each additional subdivision along every axis multiplies the total cell count by a factor that depends on the dimension: \(K^d\) grows rapidly when \(d\) is large. The balanced choice therefore uses fewer subdivisions per axis to control estimation variance. Larger sample sizes have the opposite effect: increasing \(n\) increases \(K_{\mathrm{bal}}\), allowing a finer partition.

The risk rate improves as smoothness increases, even though the balanced resolution decreases. The exponent \(2\alpha/(2\alpha+d)\) increases with \(\alpha\), so \(n^{-2\alpha/(2\alpha+d)}\) decreases for \(n>1\). Resolution and risk are different quantities: a coarser balanced partition can still yield a faster rate when the underlying function is smoother.

A Reusable Calculation

For a new rate problem, keep the three quantities separate: per-coordinate resolution \(K\), total number of cells \(K^d\), and squared-error rate. The following sequence prevents most exponent errors.

Common Mistakes

• Calling \(K\) the total number of cells. Here \(K\) counts subdivisions along each coordinate, so the total is \(K^d\).
• Using the bias order without squaring it. If the approximation error in norm is of order \(K^{-\alpha}\), its squared-error contribution is of order \(K^{-2\alpha}\).
• Reversing the smoothness effect on resolution. At fixed \(n>1\) and \(d\), \(K_{\mathrm{bal}}=n^{1/(2\alpha+d)}\) decreases as \(\alpha\) increases. Greater smoothness permits a coarser balanced partition, not a finer one.
• Reading the risk exponent as the resolution exponent. The resolution exponent is \(1/(2\alpha+d)\); the squared-error rate exponent is \(2\alpha/(2\alpha+d)\).
• Treating equal-order terms as numerically identical after rounding. Integer rounding can change the two values, but it does not change their rate when the rounded resolution stays within a constant factor of the balanced one.