Minimax Rate Comparison Workshop

Why Compare Rates?

A nonparametric rate is not a property of a regression method alone. It describes how quickly estimation error can decrease as the sample size grows, under a specified smoothness class, loss, and sampling design. Changing any of these can change the exponent or introduce a logarithmic factor. Comparing rates is therefore useful only after checking that the underlying problems are genuinely comparable.

This tutorial organizes the standard comparisons for isotropic Hölder and Sobolev classes. The aim is to calculate each rate explicitly and to keep separate three questions that are often conflated: how smooth the regression function is, what error is measured, and how the design points are obtained.

Rate Notation and the Regression Setting

Unless stated otherwise, take the regression model \(Y_i=f(X_i)+\varepsilon_i\), \(i=1,\ldots,n\), on the domain \([0,1]^d\). For random design, assume the \(X_i\) are independent with a density bounded above and bounded away from zero on the domain. Assume independent Gaussian errors \(\varepsilon_i\sim N(0,\sigma^2)\), independent of the design, with fixed \(0<\sigma^2<\infty\). The function belongs to a fixed-radius, isotropic smoothness ball.

A Hölder ball \(C^s(L)\), for noninteger \(s=m+\alpha\) with \(0<\alpha<1\), bounds derivatives through order \(m\) and requires derivatives of order \(m\) to be \(\alpha\)-Hölder continuous. A Sobolev ball \(W_2^s(L)\) bounds the function and its weak derivatives, or equivalently uses the corresponding \(L_2\)-based smoothness condition. We use the usual endpoint conventions for integer smoothness. Although these classes impose smoothness in different ways, their standard isotropic integrated squared-error rates have the same exponent under the regular conditions stated here.

The benchmark is for a fixed smoothness level and radius. Its constants can depend on the radius, dimension, noise variance, and design-density bounds. A fixed-design version requires suitably regular, sufficiently space-filling design points; an arbitrary fixed design need not attain the same rate. In random design, a density that approaches zero can leave some regions poorly sampled, so integrated risk and rates may depend on the target measure and the density conditions.

Deriving the Integrated Squared-Error Exponent

The rate exponent can be checked by balancing approximation error against stochastic error. Suppose an estimator uses a spatial resolution \(h\), where smaller \(h\) means finer local approximation. For an isotropic \(s\)-smooth function, a standard squared-bias order is \(h^{2s}\). There are order \(h^{-d}\) local regions, and the variance contribution to integrated squared error has order \(1/(nh^d)\). Thus the risk has the form

The following calculation derives the balancing scale and its resulting order. It explains the rate exponent; the matching minimax lower bound is supplied by the standard lower-bound theory for these smoothness classes, rather than by this bias-variance calculation alone.

The derivation makes the dimension effect visible: as \(d\) increases while \(s\) stays fixed, the exponent \(2s/(2s+d)\) decreases. Greater smoothness increases that exponent, giving faster decay. These are comparisons of asymptotic orders; they do not say which estimator has smaller risk at a particular small sample size.

Changing the Loss Changes the Comparison

Integrated squared error averages the squared discrepancy over the domain. Pointwise squared error evaluates it at one target location. Under regularity conditions, these two risks have the same power of \(n\) in the isotropic setting above, but they are different losses and can have different constants or additional location-specific conditions. In particular, a point near a boundary may require different local assumptions than an interior point.

Supremum loss asks for accuracy everywhere at once. A rough way to see why a logarithm appears is that resolution \(h\) creates order \(h^{-d}\) local regions. Controlling the largest stochastic fluctuation across many regions costs a factor of order \(\sqrt{\log(1/h)}\). A typical uniform-error balance is therefore $$ h^s\asymp \sqrt{\frac{\log(1/h)}{nh^d}}. $$

At the polynomial scale \(h\asymp(\log n/n)^{1/(2s+d)}\), \(\log(1/h)\) is of order \(\log n\). Substitution gives a supremum-error order \((\log n/n)^{s/(2s+d)}\). Squaring that order gives \((\log n/n)^{2s/(2s+d)}\) for squared supremum error. This is a separate risk statement; it should not be confused with integrated squared error.

Hölder Versus Sobolev: What the Exponent Does and Does Not Say

For isotropic classes with comparable smoothness index \(s\), Hölder and Sobolev balls share the integrated squared-error exponent \(2s/(2s+d)\). That agreement does not make the classes identical. Hölder conditions control local continuity of derivatives, while Sobolev conditions control derivatives in an \(L_2\) sense. Different function classes, radii, and boundary conventions can change constants and details of the minimax statement.

The same exponent should not automatically be carried over to anisotropic smoothness, irregular domains, degenerate design densities, or nonstandard noise. Those settings change the effective approximation or information available and require their own assumptions and rate calculations. Also distinguish risk from error: \(n^{-2s/(2s+d)}\) is the integrated squared-error risk, while the square root of that risk has order \(n^{-s/(2s+d)}\).

Common Mistake: Comparing Exponents Without Comparing Problems

• Wrong: “Both rates have an exponent involving \(s\), so they are directly comparable.” Correction: First verify that the smoothness class, dimension, design assumptions, and loss are the same.
• Wrong: “The rate \(n^{-2s/(2s+d)}\) is the \(L_2\) error.” Correction: It is the integrated squared-error risk. Its square root is the root-mean-squared \(L_2\) error order.
• Wrong: “Supremum and integrated squared-error rates differ only by a constant.” Correction: Supremum loss generally carries a logarithmic factor and has a different loss definition.
• Wrong: “The value of a rate expression at \(n=1000\) is the estimator's risk.” Correction: A minimax rate suppresses constants and describes asymptotic order, not a calibrated finite-sample risk.
• Wrong: “Any fixed design has the same rate as regular random design.” Correction: Fixed-design comparisons require adequate coverage and regular spacing; poorly placed design points can obstruct estimation.