Fixed-Design And Random-Design Rate Comparisons

Why Compare the Two Design Regimes?

In nonparametric regression, the observations may be collected at locations chosen in advance, or the locations may themselves be random. These designs affect which parts of the regression function are observed and how much information the data contain there. Under suitable regularity conditions, however, the two regimes have the same order of difficulty for estimating a smooth function in integrated squared error.

The comparison is useful because a matching rate does not mean the designs are identical. It means that regular placement of fixed locations and sufficiently even random sampling provide comparable information at the spatial scale relevant to estimation. The assumptions matter: a fixed-design gap or a random design that rarely samples part of the domain can change the conclusion.

Models, Risk, and Design Conditions

Let the domain be \([0,1]^d\), and consider the regression model \(Y_i=f(X_i)+\varepsilon_i\). The errors are independent \(N(0,\sigma^2)\), with \(\sigma^2>0\), and are independent of the locations when those locations are random. We measure error by Lebesgue integrated squared error, \(\|\hat f-f\|_2^2=\int_{[0,1]^d}(\hat f(x)-f(x))^2\,dx\).

We use a Hölder class of smoothness \(s>0\), with \(s\) noninteger, and radius \(L\). Write \(k=\lfloor s\rfloor\) and \(\alpha=s-k\). The class consists of functions with derivatives through order \(k\) bounded by \(L\), whose derivatives of order \(k\) are \(\alpha\)-Hölder with constant at most \(L\). In particular, functions in the class admit local polynomial approximations of degree \(k\) with pointwise error bounded by a constant times \(h^s\) on cubes of side \(h\).

For fixed locations, we consider regular designs: at the estimation scale, each cube of side \(h\) contains between constant multiples of \(nh^d\) locations, and the rescaled local polynomial design matrices are uniformly well-conditioned. More precisely, for a fixed basis of polynomials of degree at most \(k\), the eigenvalues of the sum of basis-vector outer products within each cube are bounded above and below by positive constants times the number of locations in that cube. Regular grids are standard examples.

For random locations, assume \(X_i\) are independent and identically distributed with density \(q\) on the domain, where \(0<c\le q(x)\le C<\infty\) almost everywhere. This condition ensures both that no region is undersampled arbitrarily badly and that the random-design integrated risk is comparable to Lebesgue integrated risk.

Deriving the Common Rate

Partition the domain into cubes of side length \(h\). A piecewise polynomial estimator of degree \(k\) has squared approximation error of order \(h^{2s}\). There are order \(h^{-d}\) cubes. With order \(nh^d\) observations in each cube, estimating a fixed number of polynomial coefficients per cube contributes integrated variance of order \(h^{-d}/n\). Thus the two leading terms are

The first term decreases as the cubes become smaller; the second increases because smaller cubes contain fewer observations. Balancing them gives \(h^{2s}=1/(nh^d)\), or \(h\asymp n^{-1/(2s+d)}\). Substitution yields \(n^{-2s/(2s+d)}\).

Why the Upper Rates Match

The upper-rate argument can be made with local polynomial least squares on the partition. On each cube, fit a polynomial of degree \(k\), and clip the fitted values to a fixed interval containing the Hölder class, so that estimation error on an exceptional design event remains bounded. Taylor approximation supplies a polynomial whose error throughout that cube is at most \(C_1h^s\). If the local polynomial design matrix is well-conditioned, the fitted coefficients therefore have squared integrated error bounded by a constant times \(h^{2s}\) for approximation and \(1/N_j\) for noise, where \(N_j\) is the number of observations in cube \(j\). Summing over the cubes gives the stated approximation and variance orders when \(N_j\asymp nh^d\).

For a regular fixed design, the local count and matrix conditions hold by assumption. For the random design, the density bounds imply that each cube has expected count between \(cnh^d\) and \(Cnh^d\). The expected local polynomial design matrix is also well-conditioned after rescaling: its quadratic form is bounded above and below by constant multiples of the unweighted polynomial quadratic form, since \(c\le q\le C\). Because the polynomial basis has fixed finite dimension and bounded entries on a rescaled cube, concentration of the counts and matrix entries gives an exponentially small probability of failure when \(nh^d\) grows. At \(h\asymp n^{-1/(2s+d)}\), it does grow: \(nh^d\asymp n^{2s/(2s+d)}\). The number of cubes grows only polynomially in \(n\), so the probability that any cube fails is negligible compared with the rate. On the exceptional event, clipping bounds the loss. This proves the matching upper order in both regimes.

Why the Lower Rates Match

The same spatial scale also limits how accurately either design can estimate the function. To see this, place \(M\asymp h^{-d}\) disjoint smooth bumps inside the domain, each supported on a cube of side \(h\). For binary choices \(\omega_j\in\{0,1\}\), form functions by adding the selected bumps, each with amplitude \(a h^s\), where \(a\) is a sufficiently small fixed constant. The Hölder norm remains bounded when \(a\) is small. Two functions differing in just one bump have squared \(L^2\) separation

where \(\phi\) is the fixed nonzero bump shape. For neighboring alternatives, the Gaussian Kullback–Leibler divergence is \((2\sigma^2)^{-1}\) times the squared difference of their regression means at the observed locations. In a regular fixed design, the bump's support contains at most a constant times \(nh^d\) locations, so this divergence is at most \(C_2a^2nh^{2s+d}\). In the random design, its expected value is bounded by the same expression because \(q\le C\). Taking \(h\asymp n^{-1/(2s+d)}\) and \(a\) small makes the neighboring divergences bounded by a fixed constant.

Assouad's argument now gives a lower bound of order \(M\delta^2\): for each bump, distinguishing its two possible values has error probability bounded away from zero when the neighboring distributions have bounded divergence. Summing the resulting loss over the disjoint supports yields \(h^{-d}h^{2s+d}=h^{2s}\), which is \(n^{-2s/(2s+d)}\). Hence neither design regime can have a faster minimax rate over the stated class.

Together, the polynomial-estimation upper bound and the localized-alternative lower bound establish the claimed minimax order. The proof also clarifies the roles of the assumptions: local design stability controls estimation, while a bounded density and regular fixed-design counts control the information available for the lower bound.

When the Comparison Breaks Down

The density bounds are not cosmetic. If a random design has \(q(x)=0\) on a region of positive Lebesgue measure, observations never reveal the regression function there. For example, on \([0,1]\), let the design be supported on \([0,1/2]\). Choose two smooth functions that agree on \([0,1/2]\) but differ on part of \((1/2,1]\). They induce identical distributions of all observations, yet their Lebesgue integrated squared distance is positive. No estimator can distinguish them, so the unweighted minimax risk cannot tend to zero over a class containing both.

A related failure occurs for fixed designs with a gap of nonvanishing width: smooth functions can agree at every observed location and still differ between locations. Conversely, if the target loss were weighted by the random design density, a region with very small density would contribute very little to that loss. The choice of integrated risk and the design assumptions must therefore be read together.

Common Mistake

• Wrong reasoning: “Fixed and random designs have the same rate because both have \(n\) observations.” The sample size alone says nothing about how observations cover the domain.
• Correction: The rate comparison also needs spatial regularity. Fixed designs need adequate local counts and stable local polynomial fits; random designs need a density bounded above and away from zero. Under these conditions, both designs provide order \(nh^d\) information per cube at the balancing scale. Without them, gaps or sparse regions can change the risk or prevent consistent estimation.