Bias–Variance Bounds For Sieve Estimators

Why a Sieve Has Two Sources of Error

A finite-dimensional regression sieve restricts the fitted regression function to a manageable space. This restriction makes estimation possible from finite data, but it creates two distinct errors. The sieve may not contain the true regression function, and the data may not estimate even the best function in the sieve exactly. A useful bound must keep these effects separate: the first is approximation error, and the second is estimation error.

We study random pairs $(X_i,Y_i)$, $i=1,\ldots,n$, drawn independently from the same distribution as $(X,Y)$. Assume the regression model $Y=m(X)+\varepsilon$, where $m(x)=E[Y\mid X=x]$, $E[\varepsilon\mid X]=0$, and the conditional variance of $\varepsilon$ is finite. The target is integrated squared error under the marginal distribution of a fresh covariate $X$, not error at just the observed design points.

Definition: Let $S_d$ be a $d$-dimensional linear space of measurable functions with basis vector $\phi(x)=(\phi_1(x),\ldots,\phi_d(x))^\mathsf{T}$. A function in the sieve has the form $g_\beta(x)=\phi(x)^\mathsf{T}\beta$, for $\beta\in\mathbb R^d$. The population squared-error norm is $\|h\|_{P_X}^2=E[h(X)^2]$. The population projection $g_*(x)=\phi(x)^\mathsf{T}\beta_*$ minimizes $\|m-g\|_{P_X}^2$ over $g\in S_d$, when this minimizer exists. The least-squares sieve estimator minimizes $n^{-1}\sum_{i=1}^n(Y_i-\phi(X_i)^\mathsf{T}\beta)^2$ over $\beta$.

For a precise coefficient representation, assume the basis is square-integrable and its population Gram matrix is the identity: $E[\phi(X)\phi(X)^\mathsf{T}]=I_d$. This normalization can be obtained by a nonsingular change of basis when the original Gram matrix is positive definite. Then $\beta_*=E[\phi(X)m(X)]$, and the projection residual $r(x)=m(x)-g_*(x)$ satisfies $E[\phi(X)r(X)]=0$. The integrated approximation error is $A_d=\|r\|_{P_X}^2$.

The Error Decomposition and a Design-Dependent Bound

Write $G_n=n^{-1}\sum_{i=1}^n\phi(X_i)\phi(X_i)^\mathsf{T}$ for the empirical Gram matrix. When $G_n$ is invertible, least squares gives $\hat\beta=G_n^{-1}n^{-1}\sum_i\phi(X_i)Y_i$. Subtracting $\beta_*$ and using $Y_i=\phi(X_i)^\mathsf{T}\beta_*+r(X_i)+\varepsilon_i$ gives the exact identity $\hat\beta-\beta_*=G_n^{-1}s_n$, where $s_n=n^{-1}\sum_i\phi(X_i)(r(X_i)+\varepsilon_i)$.

\|g_{\hat\beta}-m\|_{P_X}^2 = A_d+\|\hat\beta-\beta_*\|_2^2 = A_d+s_n^\mathsf{T}G_n^{-2}s_n.

The first equality follows by expanding $g_{\hat\beta}-m=\phi^\mathsf{T}(\hat\beta-\beta_*)-r$. The cross term is zero because $E[\phi(X)r(X)]=0$, and the squared norm of $\phi^\mathsf{T}(\hat\beta-\beta_*)$ is $\|\hat\beta-\beta_*\|_2^2$ under the identity-Gram normalization. Thus approximation and estimation error add exactly in this setting.

Deterministic bound: On any data set for which $\lambda_{\min}(G_n)\ge c>0$, the least-squares estimator is defined and $$ \|g_{\hat\beta}-m\|_{P_X}^2 \le A_d+\frac{\|s_n\|_2^2}{c^2}. $$ Indeed, $\|G_n^{-1}s_n\|_2\le \|s_n\|_2/c$, since the largest eigenvalue of $G_n^{-1}$ is at most $1/c$. Squaring and applying the decomposition proves the bound.

This inequality shows why a small approximation error is not enough: a poorly conditioned empirical Gram matrix can make the coefficient error large. Its other input, $s_n$, is the empirical average of the basis-weighted residual and noise. Its mean is zero, because $E[\phi r]=0$ and $E[\varepsilon\mid X]=0$.

A Probability Bound Under Design and Noise Conditions

The next result turns the deterministic bound into a high-probability guarantee. It states the design requirement directly: the empirical Gram matrix must be well-conditioned with high probability. Such a condition depends on the basis, the distribution of $X$, and the sample size. The noise requirement is a finite weighted second moment; a bounded conditional variance is one convenient way to ensure it.

Theorem: Suppose $(X_i,\varepsilon_i)$ are independent and identically distributed, $E[\varepsilon\mid X]=0$, and $E[\phi(X)r(X)]=0$. Assume $$ V=E\!\left[\|\phi(X)\|_2^2\{r(X)^2+\operatorname{Var}(\varepsilon\mid X)\}\right]<\infty. $$ If $P\{\lambda_{\min}(G_n)\ge c\}\ge 1-\delta_G$, then, for any $0<\delta_s<1$, with probability at least $1-\delta_G-\delta_s$, $$ \|g_{\hat\beta}-m\|_{P_X}^2 \le A_d+\frac{V}{c^2n\delta_s}. $$ The estimator in this statement is used on the event where $G_n$ is invertible.

Proof. Let $Z_i=\phi(X_i)(r(X_i)+\varepsilon_i)$. The assumptions imply $E[Z_i]=0$. Conditional mean zero of the noise also gives $E[r(X)\varepsilon\mid X]=0$, so $E[\|Z_i\|_2^2]=V$. Independence and zero means make the cross terms vanish in the squared norm of the sum:

E[\|s_n\|_2^2] = \frac{1}{n^2}E\!\left[\left\|\sum_{i=1}^n Z_i\right\|_2^2\right] = \frac{1}{n^2}\sum_{i=1}^n E[\|Z_i\|_2^2] = \frac{V}{n}.

Markov's inequality therefore gives $P\{\|s_n\|_2^2>V/(n\delta_s)\}\le\delta_s$. With probability at least $1-\delta_G-\delta_s$, both $\lambda_{\min}(G_n)\ge c$ and $\|s_n\|_2^2\le V/(n\delta_s)$ hold, by the union bound. Substitution into the deterministic inequality proves the claim. $\square$

If the design condition holds almost surely, the same calculation also yields an expectation bound: $E[\|g_{\hat\beta}-m\|_{P_X}^2]\le A_d+V/(c^2n)$. If the Gram condition is only high probability, this argument bounds risk on the well-conditioned event; it does not by itself control the estimator's risk on the complement.

Worked Examples

Worked Example: A Constant Sieve for a Quadratic Regression Function

Let $X$ be uniform on $[0,1]$, let $m(x)=x^2$, and let $\varepsilon\sim N(0,1/4)$ independently of $X$. Use the one-dimensional sieve of constant functions, with $\phi(x)=1$. Find the population approximation error and the exact expected integrated squared error of the least-squares fit.

The population projection is the constant $E[X^2]=1/3$. Thus $r(x)=x^2-1/3$, and direct integration gives $A_1=E[(X^2-1/3)^2]=E[X^4]-(E[X^2])^2=1/5-1/9=4/45$. Here $G_n=1$ for every sample, and $\hat\beta=n^{-1}\sum_iY_i$. Since the sample mean is unbiased for $1/3$, its variance is $(\operatorname{Var}(X^2)+\operatorname{Var}(\varepsilon))/n =(4/45+1/4)/n=61/(180n)$.

The exact expected integrated squared error is therefore $4/45+61/(180n)$. In the theorem, $V=E[r(X)^2+1/4]=61/180$, so the almost-sure Gram bound with $c=1$ gives this same expectation bound. In this example the variance calculation is exact, rather than merely an upper bound.

Worked Example: Two Categories With Balanced Observations

Let $X$ take two values, $a$ and $b$, each with probability $1/2$. Use the basis $\phi(x)=\sqrt{2}(1\{x=a\},1\{x=b\})^\mathsf{T}$, and let $m(a)=1$, $m(b)=-1$. Suppose the noise is independent $N(0,1)$. The sieve contains $m$, so $A_2=0$. For a fixed balanced design with $n/2$ observations at each category, calculate the integrated risk.

The basis has population Gram matrix $I_2$. The balanced design also has $G_n=I_2$: each diagonal entry is $(n/2)(2)/n=1$, and the off-diagonal entries are zero. The fitted value at each category is its sample mean. Each group mean has variance $1/(n/2)=2/n$. Integrated squared error weights the two category errors equally, so its expectation is $\tfrac12(2/n)+\tfrac12(2/n)=2/n$.

Equivalently, each coefficient is the corresponding group mean divided by $\sqrt{2}$, so each coefficient has variance $1/n$; summing the two coefficient variances gives $2/n$. This verifies the estimation contribution for a well-conditioned design with dimension two.

Worked Example: Ill-Conditioning Inflates Estimation Error

Consider a two-dimensional sieve with population Gram matrix $I_2$, true regression function $m(x)=0$, and independent $N(0,1)$ errors. Suppose a fixed design of size $n=100$ has empirical Gram matrix $G_n=\operatorname{diag}(1,1/4)$. Find the exact expected integrated squared error and compare it with the deterministic bound when the score vector is known to be zero except for the noise contribution.

The model lies in the sieve, so $A_2=0$. Conditional on the fixed design, the coefficient error is $G_n^{-1}n^{-1}\sum_i\phi(X_i)\varepsilon_i$. Its covariance matrix is $n^{-1}G_n^{-1}$: this follows from $\operatorname{Var}(n^{-1}\sum_i\phi(X_i)\varepsilon_i)=G_n/n$, followed by multiplication by $G_n^{-1}$ on both sides. Therefore the expected integrated squared error is $n^{-1}\operatorname{tr}(G_n^{-1})=(1+4)/100=0.05$.

The smallest eigenvalue is $c=1/4$, so the deterministic bound multiplies the squared score norm by $1/c^2=16$. The exact risk calculation shows the effect of this conditioning: the second coefficient has four times the variance of the first. A bound based only on the smallest eigenvalue can be substantially looser than the exact trace calculation, but it correctly flags the unstable direction.

How to Read the Bound

The theorem is useful because it isolates what must be controlled to obtain an integrated prediction guarantee. The approximation term $A_d$ depends on how well the chosen sieve represents $m$. The estimation term depends on the empirical design through $c$, and on the residual and noise through $V$. Increasing the sieve dimension may reduce approximation error while making the estimation contribution larger; the bound describes that trade-off without selecting a dimension or asserting a particular smoothness rate.

A common mistake is to write “risk equals bias plus variance” and then use a variance formula for coefficients without checking how the design affects it. The orthogonal decomposition is exact here because the population projection residual is orthogonal to the sieve. But the estimator's coefficient error still involves $G_n^{-1}$. If the design nearly fails to distinguish two basis directions, the inverse Gram matrix amplifies noise in those directions. A small approximation error does not prevent this instability.

Key takeaway: For a finite-dimensional least-squares sieve, integrated squared error separates into population approximation error and coefficient estimation error. A useful finite-sample bound requires both a well-conditioned empirical design and control of the basis-weighted residual-plus-noise score.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why does the cross term between $r$ and $g_{\hat\beta}-g_*$ vanish in the population integrated squared error?
Which part of the theorem's assumptions controls instability from nearly dependent empirical basis directions?
If $G_n$ has smallest eigenvalue $c$, by what factor does the deterministic bound multiply $\|s_n\|_2^2$?
In the constant-sieve example, what are the approximation error and the exact estimation contribution?
Why does a high-probability Gram condition alone not justify an unconditional expected-risk bound?