Nonparametric Convergence Rates

Fit a straight line to data and the estimate of its slope gets more precise at a predictable, fast rate as you collect more data — error shrinks proportional to $1/\sqrt{n}$, regardless of how many input dimensions you have. Fit a flexible, assumption-free curve (a kernel smoother, a nearest-neighbor regressor) instead, and that guarantee evaporates: the error shrinks much more slowly, and the rate gets worse the more input features you add. That gap — the price of not assuming the model's shape in advance — is what nonparametric convergence rates quantify.

The analogy: mapping a shape versus mapping a country

Estimating a straight line's slope is like measuring a person's height from a handful of measurements — you already know "the answer has one number," so each new measurement sharpens that one number efficiently. Estimating an arbitrary curve or surface with no assumed shape is like mapping unknown terrain: doubling the resolution of a 1D coastline needs twice the sample points, but doubling the resolution of a 2D landscape needs four times as many sample points to cover the same density of coverage, and a 3D volume needs eight times as many. Nonparametric estimation is terrain-mapping — the "resolution" you need per unit of accuracy compounds with every extra dimension, because there's no assumed shape to fall back on; you have to observe every region of the space directly.

The rates, stated

For a parametric model (fixed number of parameters, correctly specified), the mean squared error of the fitted parameters shrinks as

$$\text{MSE} = O\left(\frac{1}{n}\right)$$

— i.e., error (not squared) shrinks as $1/\sqrt{n}$, independent of the input dimension $d$. For a nonparametric regression estimator (like a kernel smoother) trying to estimate a function assumed only to be smooth (say, twice differentiable) in $d$ dimensions, the optimal achievable rate is

$$\text{MSE} = O\left(n^{-\frac{4}{4+d}}\right)$$

Plain English: nonparametric error shrinks with a dimension-dependent exponent that gets closer to zero as $d$ grows — meaning you need exponentially more data to get the same accuracy in higher dimensions. This is the formal version of the "curse of dimensionality."

Worked example 1: comparing rates at d=1 versus d=10

At $d = 1$: the exponent is $4/(4+1) = 0.8$, so MSE $\propto n^{-0.8}$ — close to the fast parametric-like rate. With $n = 10{,}000$, MSE shrinks by a factor of $10{,}000^{0.8} \approx 1585$ compared to $n=1$.

At $d = 10$: the exponent drops to $4/(4+10) \approx 0.286$, so MSE $\propto n^{-0.286}$. With the same $n = 10{,}000$, MSE only shrinks by a factor of $10{,}000^{0.286} \approx 10.7$ — roughly 148 times worse an improvement than the 1D case, for the identical sample size. Ten times more dimensions turned a 1585x error reduction into an 11x error reduction.

Worked example 2: data needed to match a target accuracy

Suppose you want MSE to fall below a target $\tau$ using a nonparametric estimator. Solving $n^{-4/(4+d)} = \tau$ for $n$ gives $n = \tau^{-(4+d)/4}$. Fix $\tau = 0.01$: at $d=1$, $n = 0.01^{-1.25} \approx 316$. At $d=5$, $n = 0.01^{-2.25} \approx 31{,}623$. At $d=10$, $n = 0.01^{-3.5} \approx 3.16$ million. Each additional dimension multiplies the required sample size by a large constant factor to hit the same accuracy — going from 316 points to over 3 million points as $d$ moves from 1 to 10, for the identical target error.

Adjust the exponent and watch how a small change in the power bends the curve — the exponent $4/(4+d)$ plays exactly this role: a slightly smaller exponent (higher $d$) flattens the error-reduction curve dramatically, which is the visual form of the curse of dimensionality above.

What this means in practice

This is why nonparametric methods (kernel regression, k-nearest-neighbors, unstructured Gaussian processes) are used with only a handful of features in practice, and why quants reach for parametric or semi-parametric models (linear factor models, additive models) once feature counts climb past single digits — the convergence rate makes flexible, assumption-free fitting infeasible at high dimension without impractical data. It's also why feature selection matters more for flexible models than linear ones: cutting $d$ from 10 to 3 can turn an intractable data requirement into a modest one.