Minimax Risk For Nonparametric Regression

Why Minimax Risk Is a Useful Benchmark

A regression method can perform well for one particular function and poorly for another. To assess its performance without knowing the true regression function, we specify a class of plausible functions and ask how well the best procedure can do in the hardest case in that class. This worst-case benchmark is minimax risk.

The benchmark depends on the statistical experiment as well as the function class. In particular, the locations at which responses are observed determine which parts of the domain are well informed by data. The loss must also be stated explicitly: here we use integrated squared error over the domain. These choices make it possible to compare an estimator's upper bound with a lower bound that applies to every estimator.

Regression Model, Loss, and Risk

Let the covariate \(X\) take values in \(\mathcal X=[0,1]^d\), and let \(Y\) be a real-valued response. The regression function is the conditional mean of the response given the covariate. It is defined up to sets having probability zero under the covariate distribution; when needed, we select a measurable version on \(\mathcal X\).

Definition: The regression function is \(f(x)=E[Y\mid X=x]\). Given \(n\) observations \(D_n=((X_1,Y_1),\ldots,(X_n,Y_n))\), an estimator \(\hat f\) is a data-dependent, measurable function on \(\mathcal X\). Its integrated squared-error loss at a realized data set is \(L(\hat f,f)=\int_{\mathcal X}(\hat f(x)-f(x))^2\,dx\), where \(dx\) is Lebesgue measure. Its risk at \(f\) is \(R(\hat f,f)=E_f[L(\hat f,f)]\), with expectation over the data under the model indexed by \(f\).

For this definition, take \(\hat f\) to be a measurable \(L_2(\mathcal X)\)-valued estimator and \(f\in L_2(\mathcal X)\). The risk may be infinite; finite risk is not needed just to define it. Since the loss is nonnegative, Tonelli's theorem gives the useful identity

R(\hat f,f) = \int_{\mathcal X} E_f\!\left[(\hat f(x)-f(x))^2\right]\,dx.

This identity does not require exchanging a signed integral and an expectation: the integrand is nonnegative, which is precisely why Tonelli's theorem applies. If the integral on either side is finite, the risk is finite.

Definition: For a specified function class \(\mathcal F\) and statistical experiment, the minimax risk is \(R_n^*(\mathcal F)=\inf_{\hat f}\sup_{f\in\mathcal F}R(\hat f,f)\). The infimum is over all estimators based on the \(n\) observations. The supremum takes the largest risk within \(\mathcal F\); the infimum then selects the estimator with the smallest such worst-case risk.

The class \(\mathcal F\), the observation model, and the loss are all part of the definition. A minimax claim without them is incomplete. For example, changing the domain's design distribution can change how much information the observations provide about regions that count equally in Lebesgue integrated loss.

Regular Design and the Loss Being Measured

A standard random-design regression experiment has independent observations with \(X_i\) drawn from a density \(p\) on \([0,1]^d\), and responses satisfying \(Y_i=f(X_i)+\varepsilon_i\). A common noise condition is \(E[\varepsilon_i\mid X_i]=0\) and \(E[\varepsilon_i^2\mid X_i]\leq \sigma^2\) almost surely. These conditions specify a conditional mean and bound the conditional variance; they do not by themselves specify the full response distribution.

For Lebesgue integrated loss, a regular-design assumption is that the design density is bounded above and away from zero: there are constants \(0<c\leq C<\infty\) such that \(c\leq p(x)\leq C\) for almost every \(x\in[0,1]^d\). The constants are fixed independently of \(n\). This assumption prevents the design from assigning vanishingly little probability to a region that still contributes to the target loss.

Result: Under the density bounds \(c\leq p\leq C\), every measurable function \(g\) satisfies \(c\int g(x)^2\,dx\leq E[g(X)^2]\leq C\int g(x)^2\,dx\), provided the quantities are interpreted as nonnegative integrals. Thus design-weighted squared error and Lebesgue integrated squared error are comparable, up to fixed constants.

Proof. By the definition of a density, \(E[g(X)^2]=\int g(x)^2p(x)\,dx\). Multiplying the almost-everywhere inequalities \(c\leq p(x)\leq C\) by the nonnegative quantity \(g(x)^2\), and integrating, gives

c\int g(x)^2\,dx \leq \int g(x)^2p(x)\,dx \leq C\int g(x)^2\,dx.

The inequalities remain valid if an integral is infinite, by the corresponding inequalities for nonnegative integrals. This proves the result. \(\square\)

For fixed design, the covariate locations are chosen rather than randomly drawn. A regular grid or a set of points with controlled spacing and adequate coverage can play the role of a regular design, but the exact assumptions depend on the estimator and function class. Random-design density bounds and fixed-design spacing conditions are not interchangeable without further argument.

Worked Example: Design-Weighted Error Can Miss a Region

Let \(X\) have density \(p(x)=2x\) on \([0,1]\), and consider \(g(x)=1\) on \([0,1/2]\) and \(g(x)=0\) elsewhere. Compare its Lebesgue squared norm with its design-weighted squared norm.

The Lebesgue integrated squared error is \(\int_0^1g(x)^2\,dx=\int_0^{1/2}1\,dx=1/2\). The design-weighted quantity is \(E[g(X)^2]=\int_0^{1/2}2x\,dx=[x^2]_0^{1/2}=1/4\).

The design puts less probability near zero, so the two quantities differ. More starkly, for \(g\) equal to one on \([0,\epsilon]\) and zero elsewhere, the Lebesgue integral is \(\epsilon\), whereas the design-weighted integral is \(\epsilon^2\). There is no positive constant \(c\) such that \(2x\geq c\) almost everywhere on \([0,1]\). The lower density bound fails, and the two losses cannot be uniformly compared in the stated way.

Worked Risks in Simple Regression Experiments

Worked Example: Risk for a Constant Regression Function

Suppose \(X_i\) are observed covariates and \(Y_i=\theta+\varepsilon_i\), where \(\theta\in\mathbb R\), and the errors are independent \(N(0,\sigma^2)\), independent of the covariates. The regression function is the constant function \(f(x)=\theta\). Use \(\hat f(x)=\bar Y=n^{-1}\sum_{i=1}^nY_i\).

For every \(x\), \(\hat f(x)-f(x)=\bar Y-\theta=n^{-1}\sum_i\varepsilon_i\). Its mean is zero and its variance is \(\operatorname{Var}(\bar Y-\theta)=n^{-2}\sum_{i=1}^n\sigma^2=\sigma^2/n\). The domain \([0,1]^d\) has volume one, so

R(\hat f,f) = \int_{[0,1]^d}E[(\bar Y-\theta)^2]\,dx = \int_{[0,1]^d}\frac{\sigma^2}{n}\,dx = \frac{\sigma^2}{n}.

This is the risk of this estimator in this constant-function model. It is not, by itself, a minimax statement for a larger nonparametric class: that would require taking a supremum over the specified class and considering all estimators.

Worked Example: Integrated Risk on a Regular Fixed Grid

On \([0,1]\), set fixed design points \(x_i=(i-\tfrac12)/n\), for \(i=1,\ldots,n\). Suppose \(Y_i=\theta x_i+\varepsilon_i\), with independent \(N(0,\sigma^2)\) errors. Estimate the slope through the origin by \(\hat\theta=(\sum_i x_iY_i)/(\sum_i x_i^2)\), and let \(\hat f(x)=\hat\theta x\).

Substituting \(Y_i=\theta x_i+\varepsilon_i\) gives \(\hat\theta-\theta=(\sum_i x_i\varepsilon_i)/(\sum_i x_i^2)\). Independence and the common error variance imply \(\operatorname{Var}(\hat\theta-\theta)=\sigma^2/\sum_i x_i^2\). The integrated squared error is \((\hat\theta-\theta)^2\int_0^1x^2\,dx=(\hat\theta-\theta)^2/3\).

For the grid, direct summation gives \(\sum_{i=1}^n x_i^2=(4n^2-1)/(12n)\). Therefore

R(\hat f,f) = \frac{\sigma^2}{3\sum_{i=1}^n x_i^2} = \frac{4n\sigma^2}{4n^2-1}.

For large \(n\), this is asymptotic to \(\sigma^2/n\), since \(\{4n\sigma^2/(4n^2-1)\}/(\sigma^2/n)=4n^2/(4n^2-1)\to1\). The calculation is for this linear model and estimator; it does not establish a rate over a broader function class.

How Upper and Lower Bounds Establish Minimax Performance

An upper bound is obtained by exhibiting an estimator whose maximum risk over \(\mathcal F\) is small. A lower bound must apply to every estimator. Together, these bounds determine the scale of the minimax risk even when its exact value is unavailable.

Result: If, for positive sequences \(a_n,b_n\), a particular estimator \(\tilde f_n\) satisfies \(\sup_{f\in\mathcal F}R(\tilde f_n,f)\leq b_n\), and every estimator satisfies \(\sup_{f\in\mathcal F}R(\hat f,f)\geq a_n\), then \(a_n\leq R_n^*(\mathcal F)\leq b_n\). If \(a_n\) and \(b_n\) have the same order, the minimax risk has that order.

Proof. By definition, \(R_n^*(\mathcal F)\) is the infimum over estimators of their maximum risks. The lower-bound premise says every member of this set of maximum risks is at least \(a_n\), so its infimum is at least \(a_n\). The estimator \(\tilde f_n\) is one candidate in the infimum, and its maximum risk is at most \(b_n\); hence the infimum is at most \(b_n\). Thus \(a_n\leq R_n^*(\mathcal F)\leq b_n\). If \(a_n\) and \(b_n\) are bounded above and below by positive constant multiples of the same sequence, the same is true of \(R_n^*(\mathcal F)\). \(\square\)

This comparison is the basic logic behind a minimax rate. The upper bound answers whether a procedure can attain a given scale; the lower bound answers whether any procedure can improve that scale uniformly over the class. The rate depends on the regularity encoded by \(\mathcal F\), the dimension, the noise model, and the design assumptions. Different choices can produce different rates, so a rate should always be read together with its assumptions.

Common Pitfall: Confusing the Design Loss With the Target Loss

A frequent mistake is to treat small average error at observed covariates as automatically equivalent to small Lebesgue integrated error. Under random design, an average at observed covariates reflects the density \(p\); the target loss here weights every region by Lebesgue measure. The two are uniformly comparable only under suitable design conditions, such as a density bounded above and away from zero. Without them, a method may perform well where observations are concentrated and still have substantial integrated error elsewhere.

Another mistake is to report the risk of one estimator as the minimax risk. An estimator's risk is evaluated at a particular \(f\); its maximum risk takes a supremum over the class; minimax risk then takes an infimum over estimators. Keeping those operations distinct is essential when interpreting either theoretical bounds or empirical performance.

Key takeaway: Minimax regression analysis begins by specifying the function class, observation model, design, and loss. A valid upper bound comes from an estimator; a valid lower bound constrains all estimators. Regular design assumptions connect the observations to the integrated loss being studied.

Check Your Understanding

Use the definitions and assumptions above to answer the following.

What are the three operations, in order, in the definition of minimax risk?
Why does Tonelli's theorem justify expressing integrated risk as an integral of pointwise mean squared errors?
Which density condition makes design-weighted squared error comparable to Lebesgue integrated squared error?
For the constant regression example, why is the risk of the sample-mean estimator not automatically the minimax risk over a larger function class?
What does it mean for an upper bound and a lower bound to establish a minimax rate?