Sieve Sequences And Density

Why a Sequence of Model Classes?

A statistical model is often too restrictive if it is fixed in advance, but allowing every conceivable predictor can make estimation impractical. A sieve provides a structured compromise: begin with a simple class, then enlarge it in an ordered sequence. The mathematical question here is about approximation, not about how to estimate a predictor or choose a class from data. We ask whether the sequence eventually contains predictors close to a desired target, or at least predictors with risk close to the best risk available in the union.

These are two related but distinct claims. A target predictor may be approximable in a distance such as an \(L^1(P_X)\) or \(L^2(P_X)\) distance. Risk approximation instead asks whether the infimum of the risks over the growing classes approaches the infimum over their union. To pass from the first claim to the second, one needs a condition ensuring that small predictor distance controls changes in risk.

Let \(\mathcal{X}\) be the predictor domain, and let \(\mathcal{F}\) be a collection of measurable predictors \(f:\mathcal{X}\to\mathbb{R}\). A sequence \((\mathcal{F}_k)_{k\geq 1}\) is nested if \(\mathcal{F}_k\subseteq\mathcal{F}_{k+1}\) for every \(k\). Nestedness means that a model available at one stage remains available at every later stage.

Definition: A sieve sequence is a sequence of model classes \((\mathcal{F}_k)_{k\geq 1}\) satisfying \(\mathcal{F}_k\subseteq\mathcal{F}_{k+1}\). Its union is \(\mathcal{F}_\infty=\bigcup_{k\geq 1}\mathcal{F}_k\). For a target predictor \(f_0\) and a distance \(d\), the sieve approximates \(f_0\) in \(d\) if \(\inf_{f\in\mathcal{F}_k}d(f,f_0)\to 0\) as \(k\to\infty\). If this holds for every target in a specified class \(\mathcal{G}\), the union is dense in \(\mathcal{G}\) with respect to \(d\).

A common choice is \(d_1(f,g)=E[|f(X)-g(X)|]\), where \(X\) has the predictor distribution \(P_X\); this is the \(L^1(P_X)\) distance when the expectation is finite. Another is \(d_2(f,g)=\{E[(f(X)-g(X))^2]\}^{1/2}\), when the squared difference is integrable. These distances identify predictors that agree \(P_X\)-almost surely: changes on a set of predictor probability zero do not change the distance.

For a nested sequence, approximation at every sufficiently large stage is equivalent to approximation using its union, in the following precise sense. If \(\inf_{f\in\mathcal{F}_k}d(f,f_0)\to0\), then for every \(\epsilon>0\), some \(k\) and \(f\in\mathcal{F}_k\) satisfy \(d(f,f_0)<\epsilon\), so \(f\in\mathcal{F}_\infty\). Conversely, if for every \(\epsilon>0\) there is a \(g\in\mathcal{F}_\infty\) with \(d(g,f_0)<\epsilon\), then \(g\in\mathcal{F}_j\) for some \(j\); nestedness puts \(g\) in every \(\mathcal{F}_k\) for \(k\geq j\). Thus the approximation error is at most \(\epsilon\) for all such \(k\), which proves it tends to zero.

Worked Example: Dyadic Step Functions Approximate a Smooth Target

Let \(X\) be uniform on \([0,1]\), and let \(f_0(x)=x^2\). Define \(\mathcal{F}_k\) to contain all functions that are constant on each of the \(2^k\) intervals of equal length partitioning \([0,1]\). (The value at the final endpoint can be assigned to the last interval.) Each partition refines the previous one, so \(\mathcal{F}_k\subseteq\mathcal{F}_{k+1}\).

On an interval of width \(h=2^{-k}\), let \(c\) be its midpoint and define \(f_k(x)=c^2\) throughout that interval. For any \(x\) in the interval, \(|x-c|\leq h/2\) and \(0\leq x,c\leq1\). Therefore

|f_k(x)-f_0(x)|=|c^2-x^2| =|c-x|(c+x)\leq \frac{h}{2}\cdot 2=h=2^{-k}.

The bound holds on every interval, so \(\sup_{x\in[0,1]}|f_k(x)-f_0(x)|\leq2^{-k}\). In particular, \(d_1(f_k,f_0)\leq2^{-k}\to0\), and also \(d_2(f_k,f_0)\leq2^{-k}\to0\). This proves approximation of this target in both distances; it does not by itself establish density for every possible target function.

From Predictor Approximation to Risk Approximation

For a predictor \(f\), define its risk by \(R(f)=E[\ell(Y,f(X))]\), where \(\ell\) is a loss function and the expectation is under the joint distribution of \((X,Y)\). Risk approximation concerns the best achievable values \(r_k=\inf_{f\in\mathcal{F}_k}R(f)\) and \(r=\inf_{f\in\mathcal{F}_\infty}R(f)\). Infima need not be attained: a class can have a best limiting risk without containing a predictor that achieves it.

Theorem: Suppose the classes \(\mathcal{F}_k\) are nonempty and nested, every \(R(f)\) for \(f\in\mathcal{F}_\infty\) is a finite real number, and, for a distance \(d\) and a constant \(L<\infty\), \( |R(f)-R(g)|\leq Ld(f,g) \) for all \(f,g\in\mathcal{F}_\infty\). Then \(r_k\) decreases to \(r\), where \(r\) is permitted to equal \(-\infty\). If \(f_0\in\mathcal{F}_\infty\) and the sieve approximates \(f_0\) in \(d\), then predictors in the sieve can have risks converging to \(R(f_0)\).

The first conclusion follows from nestedness and the definition of the infimum. Since \(\mathcal{F}_k\subseteq\mathcal{F}_{k+1}\), \(r_{k+1}\leq r_k\). Also, every \(\mathcal{F}_k\) is a subset of \(\mathcal{F}_\infty\), so \(r\leq r_k\). Thus \(r_k\) is decreasing and bounded below by \(r\) when \(r\) is finite, and its limit exists in the extended real numbers. We now verify that it equals \(r\), including the case where \(r=-\infty\).

If \(r\) is finite, fix \(\epsilon>0\). By the definition of infimum, there is an \(f_\epsilon\in\mathcal{F}_\infty\) such that \(R(f_\epsilon)<r+\epsilon/2\). This use of the infimum is valid because \(r\) is a real number. Since \(f_\epsilon\in\mathcal{F}_\infty\), it belongs to some \(\mathcal{F}_j\), and hence to every \(\mathcal{F}_k\) for \(k\geq j\). For such \(k\),

r\leq r_k\leq R(f_\epsilon)<r+\epsilon/2<r+\epsilon.

Consequently \(r_k\to r\). If \(r=-\infty\), fix any real number \(M\). By the definition of an infimum equal to \(-\infty\), choose \(f\in\mathcal{F}_\infty\) with \(R(f)<M-1\). There is a finite \(j\) with \(f\in\mathcal{F}_j\). For all \(k\geq j\), \(r_k\leq R(f)<M-1<M\). Since this holds for every real \(M\), \(r_k\to-\infty=r\). This argument does not add a finite lower bound that the assumptions do not provide.

For the last conclusion, choose \(f_k\in\mathcal{F}_k\) with \(d(f_k,f_0)\to0\), which is possible by the approximation assumption (choosing within \(1/k\) of the infimum distance, for example). The risk condition gives

|R(f_k)-R(f_0)|\leq Ld(f_k,f_0)\longrightarrow0.

Thus \(R(f_k)\to R(f_0)\). The theorem's risk conclusion requires continuity over the relevant union; density alone is not enough to control a possibly discontinuous risk functional. \(\square\)

Worked Example: Polynomial Sieve and Squared Prediction Risk

Let \(X\) be uniform on \([0,1]\), let \(f_0(x)=e^x\), and define \(\mathcal{F}_k\) as the polynomials of degree at most \(k\). These classes are nested. Use the Taylor polynomial \(p_k(x)=\sum_{j=0}^k x^j/j!\), which belongs to \(\mathcal{F}_k\).

For \(0\leq x\leq1\), the Taylor series has nonnegative terms, so

0\leq e^x-p_k(x)=\sum_{j=k+1}^{\infty}\frac{x^j}{j!} \leq\sum_{j=k+1}^{\infty}\frac{1}{j!} \leq\frac{1}{(k+1)!}\sum_{r=0}^{\infty}\frac{1}{r!} =\frac{e}{(k+1)!}.

For the penultimate inequality, write \(j=k+1+r\); then \((k+1+r)!\geq(k+1)!r!\). Hence \(\sup_x|p_k(x)-f_0(x)|\leq e/(k+1)!\). If the response is \(Y=f_0(X)\) and the loss is squared error, then \(R(f)=E[(Y-f(X))^2]\), and

R(p_k)=E[(p_k(X)-f_0(X))^2]\leq \frac{e^2}{((k+1)!)^2}\longrightarrow0=R(f_0).

More generally, on the range \([-B,B]\) the squared loss as a function of prediction \(u\) satisfies \(|(y-u)^2-(y-v)^2|=|u-v||u+v-2y|\leq4B|u-v|\) whenever \(y,u,v\in[-B,B]\). This illustrates a sufficient Lipschitz condition for risk continuity when predictions and responses are bounded.

Risk Density Can Hold Without Approximating a Particular Target

The best risk over the union is a separate approximation notion. It can be meaningful even when the target predictor is not close to any member of the sieve. Conversely, if a target is approximable and risk is continuous in the chosen distance, the theorem ensures its risk is approachable. Do not treat these statements as interchangeable without checking their assumptions.

Worked Example: A Constant Sieve Misses a Linear Target

Let \(X\) be uniform on \([0,1]\), \(Y=X\), and \(\ell(y,u)=(y-u)^2\). Take \(\mathcal{F}_k\) to be the class of all constant predictors \(f_c(x)=c\), for every \(k\). This is nested, but its union is still just the constants. For any constant \(c\), direct integration gives

R(f_c)=\int_0^1(x-c)^2\,dx =\frac{1}{3}-c+\!c^2 =\left(c-\frac12\right)^2+\frac{1}{12}.

The best risk in every class is therefore \(1/12\), attained at \(c=1/2\). In particular, \(r_k=1/12\) for all \(k\), and the target predictor \(f_0(x)=x\) has risk zero but cannot be approximated arbitrarily closely in \(L^2(P_X)\) by constants. Indeed, the same calculation yields \(\inf_c E[(X-c)^2]=1/12\), so the squared \(L^2\) distance is bounded away from zero. The classes do not become richer, despite their indexing by \(k\).

A Lower-Bound Pitfall

A common proof mistake is to write “choose \(f_\epsilon\) with \(R(f_\epsilon)<r+\epsilon\)” without establishing that \(r=\inf_{f\in\mathcal{F}_\infty}R(f)\) is finite. Individual risks can all be finite while their infimum is \(-\infty\). In that case \(r+\epsilon\) is not a real number and the finite-infimum argument cannot be used. The theorem above handles this case separately by testing against an arbitrary real threshold \(M\).

Worked Example: Finite Risks with an Infinite Negative Infimum

Let \(X\) be constant, let predictors be constant real numbers, and set \(\ell(y,u)=u\). Define \(\mathcal{F}_k=\{f_c:c\in[-k,k]\}\). Each risk is finite and equals \(R(f_c)=c\). Also, \(|R(f_c)-R(f_d)|=|c-d|=d_1(f_c,f_d)\), so risk is Lipschitz in predictor distance with \(L=1\).

The union contains every constant, and its risk infimum is \(-\infty\). At stage \(k\), the smallest risk is \(-k\), hence \(r_k=-k\to-\infty\). The correct limiting conclusion is valid, but a proof that substitutes \(r=-\infty\) into a real-valued expression such as \(r+\epsilon\) is not. This example shows why the lower-bound case must be stated and treated explicitly.

What Density Does—and Does Not—Say

Sieve density is an approximation property of a sequence of classes relative to a specified target set and a specified notion of distance or risk. The metric matters: approximation in \(L^1(P_X)\) does not automatically imply approximation in \(L^2(P_X)\), and neither is necessarily uniform approximation. The target set matters too: a sequence can be dense among continuous functions but not among all measurable functions in a chosen norm.

For risk approximation, a convenient sufficient condition is a Lipschitz bound such as \(|R(f)-R(g)|\leq Ld(f,g)\). It is not a definition of density, nor is it always necessary. Its role is to transfer a predictor approximation guarantee into a risk guarantee. Keeping that logical step visible prevents a frequent overclaim: a union may be rich in a chosen predictor distance, while the risk behavior remains uncontrolled unless the loss and its integrability provide suitable continuity.

Key takeaway: A sieve is a nested sequence of model classes. Density means approximation in a stated metric, while risk density means convergence of best-in-class risks. Nestedness and a lower-bound-safe infimum argument establish convergence of the latter; continuity of risk is what connects it to predictor approximation.

Check Your Understanding

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

Why does nestedness imply that the best-in-class risks \(r_k\) cannot increase?
State the difference between density of \(\mathcal{F}_\infty\) in a predictor metric and convergence of \(r_k\) to \(r\).
In the dyadic step-function example, which bound proves uniform approximation of \(x^2\)?
What continuity condition lets predictor approximation imply convergence of risks?
Why does the finite-infimum proof not apply directly when \(r=-\infty\), and what threshold-based argument replaces it?

Sieve Sequences And Density

What You'll Learn

Why a Sequence of Model Classes?