The Curse Of Dimension In Minimax Rates

Why Dimension Changes the Rate

In nonparametric regression, the function to be estimated may vary over several input coordinates. More coordinates create more opportunities for variation, so a fixed sample must cover a more complex domain. The isotropic Hölder minimax rate makes this cost visible in a single exponent: dimension appears alongside smoothness in the denominator. This tutorial examines what that exponent implies for comparisons and sample-size planning; it does not treat a rate formula as an exact finite-sample prediction.

We use the standard random-design regression model on $[0,1]^d$: $Y=f(X)+\varepsilon$, where $X$ is uniform on the cube and independent errors satisfy $\varepsilon\sim N(0,\sigma^2)$, with fixed $\sigma^2>0$. The regression function $f$ belongs to an isotropic Hölder ball $\mathcal H^\beta(L)$, where $\beta>0$, $L>0$, and the same smoothness order applies in each coordinate. The loss is integrated squared error with respect to Lebesgue measure on the cube.

Definition: The integrated squared-error risk of an estimator $\hat f$ at $f$ is $E_f\int_{[0,1]^d}(\hat f(x)-f(x))^2\,dx$. The minimax risk over $\mathcal H^\beta(L)$ is $$ \mathcal R_n(\mathcal H^\beta(L))=\inf_{\hat f}\sup_{f\in\mathcal H^\beta(L)} E_f\int_{[0,1]^d}(\hat f(x)-f(x))^2\,dx, $$ where the infimum is over estimators based on $n$ observations.

For fixed $d,\beta,L,\sigma$, and a nondegenerate Hölder ball, the standard isotropic Hölder minimax rate is

\mathcal R_n(\mathcal H^\beta(L))\asymp n^{-r(d,\beta)}, \qquad r(d,\beta)=\frac{2\beta}{2\beta+d}.

Here $\asymp$ means that, for all sufficiently large $n$, the minimax risk lies between positive constant multiples of the displayed power of $n$. Those constants may depend on the model and on $d,\beta,L,\sigma$. The exponent describes the power-law part of the rate, not the whole risk. In particular, the standard rate statement is for fixed dimension and smoothness; it does not claim that its constants behave uniformly as dimension grows.

Reading the Exponent

The exponent $r(d,\beta)$ is positive and less than one. A larger exponent means faster decay as sample size grows: for $n>1$, a larger $r$ makes $n^{-r}$ smaller. At a fixed smoothness, adding dimensions lowers $r$. At a fixed dimension, increasing smoothness raises $r$. These directions follow directly from the formula.

Result: For positive $d$ and $\beta$, $r(d,\beta)$ decreases as $d$ increases and increases as $\beta$ increases. More precisely, $$ \frac{\partial r}{\partial d}=-\frac{2\beta}{(2\beta+d)^2}<0, \qquad \frac{\partial r}{\partial \beta}=\frac{2d}{(2\beta+d)^2}>0. $$

Proof. Differentiate $r(d,\beta)=2\beta/(2\beta+d)$, holding the other argument fixed. With respect to $d$, the numerator is constant and the quotient rule gives $-2\beta/(2\beta+d)^2$, which is negative. With respect to $\beta$, the quotient rule gives \[ \frac{2(2\beta+d)-4\beta}{(2\beta+d)^2} =\frac{2d}{(2\beta+d)^2}, \] which is positive. Thus the exponent moves in the stated directions. $\square$

The limits help clarify what these comparisons do and do not say. For fixed $\beta$, $r(d,\beta)$ tends to zero as $d$ grows. For fixed $d$, it tends to one as $\beta$ grows. The latter does not mean arbitrarily smooth functions have an exact risk of $n^{-1}$ in every model; it is a limiting statement about this exponent. Likewise, a small exponent means slow power-law decay, not that estimation is impossible.

Worked Example: Comparing Two Dimensions

Take $\beta=1$, and compare $d=2$ with $d=8$. For $d=2$, \[ r(2,1)=\frac{2}{2+2}=\frac12. \] For $d=8$, \[ r(8,1)=\frac{2}{2+8}=\frac15. \] Thus the corresponding rate orders are $n^{-1/2}$ and $n^{-1/5}$. For $n>1$, $n^{-1/5}$ is larger than $n^{-1/2}$, so it decays more slowly. For example, at $n=10^5$, the powers themselves are $10^{-1}$ and $10^{-2.5}$, respectively. These are rate terms, not claims that the risks equal those numbers: the unknown multiplicative constants also matter.

From a Risk Target to a Sample Size

Suppose the desired integrated squared-error risk is at most $\delta$, where $0<\delta<1$. Inverting the power in the minimax rate gives the sample-size order

n\asymp \delta^{-1/r(d,\beta)} =\delta^{-(2\beta+d)/(2\beta)} =\delta^{-1}\delta^{-d/(2\beta)}.

This inversion is an order statement, just as the minimax rate is. To see why it follows from a two-sided rate bound, suppose $c n^{-r}\leq \mathcal R_n\leq C n^{-r}$ for fixed positive constants $c,C$. If $n\geq (C/\delta)^{1/r}$, then the upper bound guarantees $\mathcal R_n\leq\delta$. Conversely, if $\mathcal R_n\leq\delta$, the lower bound requires $n\geq(c/\delta)^{1/r}$. Integer rounding and the constants affect the precise threshold, but not the sample-size order.

Result: At fixed smoothness $\beta$ and target $0<\delta<1$, increasing dimension by one multiplies the rate-based sample-size order by $$ \frac{\delta^{-(2\beta+d+1)/(2\beta)}}{\delta^{-(2\beta+d)/(2\beta)}} =\delta^{-1/(2\beta)}>1. $$

Derivation. Write the sample-size order at dimension $d$ as $N_d(\delta)=\delta^{-(2\beta+d)/(2\beta)}$. At dimension $d+1$, the exponent in this expression increases by $1/(2\beta)$. Dividing gives $\delta^{-1/(2\beta)}$. Since $0<\delta<1$, this factor exceeds one. Repeating the argument, increasing dimension by $k$ multiplies the order by $\delta^{-k/(2\beta)}$. This geometric growth in the target’s inverse is one precise sense of the curse of dimension. It is a comparison of rate orders, not a universal multiplier for exact sample sizes. $\square$

Worked Example: A Fixed Error Target Across Dimensions

Let $\beta=1$, target $\delta=0.01$, and compare $d=2$ with $d=8$. The sample-size exponent is $1/r=(2\beta+d)/(2\beta)$. At $d=2$, it is $4/2=2$, so the normalized rate calculation gives \[ n\asymp 0.01^{-2}=100^2=10{,}000. \] At $d=8$, it is $10/2=5$, giving \[ n\asymp 0.01^{-5}=100^5=10{,}000{,}000{,}000. \] The ratio of these rate-based orders is $10^{10}/10^4=10^6$. Equivalently, six additional dimensions contribute a factor $0.01^{-6/2}=100^3=10^6$. The numerical values normalize the unspecified constants to one; actual required sample sizes can differ substantially because the constants are not known from the exponent alone.

Worked Example: How Smoothness Changes the Requirement

Fix dimension $d=4$ and target $\delta=0.04$. Compare smoothness levels $\beta=0.5,1,2$. For $\beta=0.5$, $r=1/(1+4)=1/5$, so $1/r=5$ and \[ n\asymp 0.04^{-5}=25^5=9{,}765{,}625. \] For $\beta=1$, $r=2/(2+4)=1/3$, so $1/r=3$ and \[ n\asymp 0.04^{-3}=25^3=15{,}625. \] For $\beta=2$, $r=4/(4+4)=1/2$, so $1/r=2$ and \[ n\asymp 0.04^{-2}=25^2=625. \] The rate calculation requires less sample size at higher smoothness. This conclusion assumes the same target and dimension, and compares the power orders; different Hölder radii or constants can change the finite-sample comparison.

Worked Example: The Cost of One More Coordinate

Take $\beta=1.5$ and target $\delta=0.05$. The sample-size exponent is $1+d/(2\beta)=1+d/3$. At $d=2$, this is $5/3$, giving \[ n\asymp 0.05^{-5/3}=20^{5/3}\approx147.36. \] At $d=3$, it is $2$, giving \[ n\asymp 0.05^{-2}=20^2=400. \] The ratio is $400/20^{5/3}=20^{1/3}\approx2.714$, exactly the one-coordinate factor $\delta^{-1/(2\beta)}=0.05^{-1/3}$. Since these are asymptotic orders, fractional or small normalized values should not be read as literal required sample counts; constants and integer rounding are omitted.

What the Curse Does and Does Not Mean

The formula shows why a problem can become demanding even when each coordinate has the same smoothness: at a small target $\delta$, each added coordinate contributes a factor $\delta^{-1/(2\beta)}$ to the sample-size order. If $\delta=0.01$ and $\beta=1$, that factor is $10$ per coordinate. For a larger $\beta$, the factor is smaller, which expresses the value of stronger smoothness assumptions.

The exponent alone does not give an exact sample-size prescription. Rate constants can depend on the Hölder radius, noise level, dimension, and other model details. Moreover, the theorem is stated for fixed dimension and smoothness; extrapolating it to a sequence where dimension grows with sample size requires results that control constants and remainders in that regime. These qualifications do not erase the rate comparison. They define what the comparison supports.

Common Mistake

A frequent error is to say that higher dimension improves the rate because $2\beta+d$ is larger. That reasoning looks only at the denominator in the sample-size expression and overlooks what a rate exponent means. In $n^{-r}$, a smaller positive exponent means slower decay when $n>1$. Increasing $d$ makes $r=2\beta/(2\beta+d)$ smaller, so the risk decreases more slowly; equivalently, $1/r$ increases, so reaching a fixed small target takes a larger sample-size order. Always distinguish the risk exponent $r$ from its reciprocal $1/r$, the exponent governing the target-based sample size.

Key takeaway: For isotropic Hölder regression, dimension reduces the minimax risk exponent $2\beta/(2\beta+d)$. At a fixed integrated squared-error target, the corresponding sample-size order is $\delta^{-1-d/(2\beta)}$; each added coordinate multiplies that order by $\delta^{-1/(2\beta)}$, up to model-dependent constants.

Check Your Understanding

Use the rate exponent and keep risk powers distinct from sample-size powers.

For fixed $\beta>0$, does $r(d,\beta)$ increase or decrease as $d$ increases? What does that imply for $n^{-r(d,\beta)}$ when $n>1$?
For $d=3$ and $\beta=1$, calculate $r$ and the sample-size exponent $1/r$ for a fixed risk target.
At fixed $\delta$ and $\beta$, what factor in sample-size order corresponds to adding two dimensions?
Why should a rate-based sample-size calculation not be reported as an exact required sample count?
Explain the error in claiming that a larger denominator in $2\beta/(2\beta+d)$ makes the minimax risk decay faster.