Oracle Decomposition For Sieve Risk

Why Sieve Risk Has Two Sources

A sieve estimator is fitted within a model class whose richness can increase with the sample size. A small class can be difficult to approximate the target with, while a large class can be difficult to estimate reliably from finite data. Its excess risk therefore reflects two distinct questions: how well the class can represent the target, and how well the estimator learns within that class.

Separating these contributions is useful even before deciding how to choose a model size. It identifies the benchmark associated with each candidate class and shows what a successful choice would need to balance. The benchmark is called an oracle benchmark because it compares classes using their population approximation and estimation properties, quantities that need not be available to a data-driven procedure.

Risk, Sieve Classes, and the Decomposition

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$. For a predictor $f$, let $L(f;Z)$ be its loss, and define its risk by $R(f)=E[L(f;Z)]$. Write $P_n L(f)=n^{-1}\sum_{i=1}^n L(f;Z_i)$ for empirical risk. Assume the risks under consideration are finite.

Let $\mathcal F$ be an ambient class containing a risk minimizer $f^\star$, so $R(f^\star)=\inf_{f\in\mathcal F}R(f)$. A sieve is a sequence of candidate classes $\mathcal F_1\subseteq\mathcal F_2\subseteq\cdots$, each contained in $\mathcal F$. For a given class $\mathcal F_m$, assume a risk minimizer $f_m^\star\in\mathcal F_m$ exists.

Definition: The approximation error of $\mathcal F_m$ is $A_m=R(f_m^\star)-R(f^\star)$. For an estimator $\hat f_m\in\mathcal F_m$, its estimation error within that class is $R(\hat f_m)-R(f_m^\star)$. The first quantity measures the limitation of the class; the second measures the estimator’s excess risk relative to the best member of that class.

Since $f_m^\star$ minimizes risk over $\mathcal F_m$, both terms are nonnegative. Adding and subtracting $R(f_m^\star)$ gives an exact identity, not an approximation:

R(\hat f_m)-R(f^\star) = \underbrace{R(f_m^\star)-R(f^\star)}_{A_m} + \underbrace{R(\hat f_m)-R(f_m^\star)}_{\text{estimation error within }\mathcal F_m}.

This decomposition does not require $\hat f_m$ to be an empirical risk minimizer. It applies to any estimator in the class. What does depend on how $\hat f_m$ is constructed is a useful bound on the estimation term.

Worked Example: A Sieve in a Gaussian Sequence Model

Suppose the observations are $Y_j=\theta_j+\varepsilon_j$, $j=1,2,3$, where the errors are independent with mean zero and variance $0.25$. Use squared error risk $R(\hat\theta)=E[\sum_{j=1}^3(\hat\theta_j-\theta_j)^2]$, and consider classes that estimate the first $m$ coordinates and set the rest to zero. Let $\theta=(2,1,0.5)$.

The best approximation in class $m$ retains the first $m$ coordinates exactly. Its approximation error is the sum of the squared omitted coordinates. The estimation variance for the $m$ estimated coordinates is $0.25m$. Thus the total expected excess risk is the sum of these two terms.

For $m=1$, the approximation error is $1^2+0.5^2=1.25$, and the estimation error is $0.25$. Total excess risk is $1.25+0.25=1.50$.

For $m=2$, the approximation error is $0.5^2=0.25$, and the estimation error is $2(0.25)=0.50$. Total excess risk is $0.25+0.50=0.75$.

For $m=3$, the approximation error is zero, and the estimation error is $3(0.25)=0.75$. Total excess risk is $0+0.75=0.75$. The example shows why increasing model richness need not decrease total risk: it reduces approximation error here, but increases estimation error.

A Bound for Empirical Risk Minimization Within a Class

For a fixed $m$, let $\hat f_m$ minimize empirical risk over $\mathcal F_m$: $P_nL(\hat f_m)\leq P_nL(f)$ for every $f\in\mathcal F_m$. Assume this minimizer exists and is measurable. Define the empirical-process fluctuation relative to the best class member by

D_m = \sup_{f\in\mathcal F_m} \left|(P_n-P)\{L(f)-L(f_m^\star)\}\right|,

where $P\{L(f)-L(g)\}=R(f)-R(g)$. Assume the displayed supremum is measurable and integrable. These conditions can be replaced by corresponding outer-expectation formulations for more general classes.

Theorem: Under the conditions above, empirical risk minimization within $\mathcal F_m$ satisfies $$ R(\hat f_m)-R(f_m^\star)\leq D_m $$ for every sample. Consequently, $$ E[R(\hat f_m)-R(f^\star)]\leq A_m+E[D_m]. $$ Also, if $\Delta_m=\sup_{f\in\mathcal F_m}|(P_n-P)L(f)|$ is measurable and integrable, then $D_m\leq 2\Delta_m$, so the expected excess risk is at most $A_m+2E[\Delta_m]$.

Proof. Empirical minimization gives $P_n\{L(\hat f_m)-L(f_m^\star)\}\leq 0$, because $f_m^\star$ belongs to $\mathcal F_m$. Add and subtract this empirical contrast:

\begin{aligned} R(\hat f_m)-R(f_m^\star) &=(P-P_n)\{L(\hat f_m)-L(f_m^\star)\}\\ &\quad+P_n\{L(\hat f_m)-L(f_m^\star)\}\\ &\leq (P-P_n)\{L(\hat f_m)-L(f_m^\star)\}\\ &\leq D_m. \end{aligned}

The last inequality follows from the definition of the supremum of the absolute centered contrasts. Adding the deterministic approximation error $A_m$ and taking expectations proves the expected-risk bound. Finally, for any $f\in\mathcal F_m$, the triangle inequality gives

\left|(P_n-P)\{L(f)-L(f_m^\star)\}\right| \leq |(P_n-P)L(f)|+|(P_n-P)L(f_m^\star)| \leq 2\Delta_m.

Taking the supremum over $f$ proves $D_m\leq2\Delta_m$, completing the proof. $\square$

Worked Example: Exact Decomposition Under Misspecification

Let $X$ take values $0$ and $1$ with probability $1/2$ each, and let the response be $Y=0$ when $X=0$ and $Y=2$ when $X=1$. Use squared loss $L(f;(X,Y))=(Y-f(X))^2$. Suppose $\mathcal F_1$ consists of constant predictors.

For a constant $c$, its risk is

R(c)=\tfrac12(0-c)^2+\tfrac12(2-c)^2 =\tfrac12c^2+\tfrac12(4-4c+c^2) =(c-1)^2+1.

The best constant is $f_1^\star(x)=1$, with risk $R(f_1^\star)=1$. The ambient target predictor $f^\star(x)=Y$ has risk zero, so $A_1=1-0=1$. Now consider the class member $\hat f_1(x)=1.2$. Its risk is $R(\hat f_1)=(1.2-1)^2+1=1.04$. Its within-class estimation error is $1.04-1=0.04$, and its excess risk over the ambient target is $1.04-0=1.04$. The identity checks: $1+0.04=1.04$.

The predictor $1.2$ here illustrates the decomposition; it need not be the output of a particular sample-based algorithm. The calculation also shows that estimation error can be small even when the total excess risk is not: the constant class itself incurs approximation error $1$.

Consistency Along a Sieve

The decomposition gives a direct sufficient condition for risk consistency when a sequence of classes is used. Let $m_n$ be a deterministic class index, and let $\hat f_{m_n}$ be an empirical risk minimizer in $\mathcal F_{m_n}$. If $A_{m_n}\to0$ and $D_{m_n}\xrightarrow{p}0$, the theorem’s samplewise bound implies that the excess risk converges to zero in probability. The same conclusion follows from the bound in expectation if $A_{m_n}\to0$ and $E[D_{m_n}]\to0$.

Corollary: Under the theorem’s conditions, if $A_{m_n}\to0$ and $D_{m_n}\xrightarrow{p}0$, then $R(\hat f_{m_n})-R(f^\star)\xrightarrow{p}0$. If instead $A_{m_n}+E[D_{m_n}]\to0$, then $E[R(\hat f_{m_n})-R(f^\star)]\to0$.

Proof. For every $n$, the decomposition and theorem give

0\leq R(\hat f_{m_n})-R(f^\star)\leq A_{m_n}+D_{m_n}.

The first term on the right is deterministic and tends to zero; the second tends to zero in probability. Their sum therefore tends to zero in probability, and the same inequality gives the expectation conclusion under the stated expectation condition. $\square$

Worked Example: Comparing Candidate-Class Benchmarks

Suppose three candidate classes have approximation errors and available expected estimation-error bounds as follows. The second column is $A_m$, and the third is a bound $U_m$ on the expected within-class estimation error.

Class $m$	$A_m$	$U_m$	$A_m+U_m$
1	0.90	0.10	1.00
2	0.40	0.25	0.65
3	0.15	0.50	0.65

For class 1, the bound is $0.90+0.10=1.00$. For class 2, it is $0.40+0.25=0.65$. For class 3, it is $0.15+0.50=0.65$. The best bound across these candidates is therefore $0.65$, attained by classes 2 and 3. This calculation identifies a benchmark, not an automatic guarantee for an estimator that chooses its class from the data. A fixed choice of class 1, for example, still has the bound $1.00$.

The Oracle Benchmark and a Common Pitfall

For a finite or countable collection of candidate classes, associate a bound $U_m$ with the expected estimation error in class $m$. The oracle benchmark is

Definition: The approximation-estimation oracle benchmark over candidate indices $\mathcal M$ is $\inf_{m\in\mathcal M}\{A_m+U_m\}$. It is the smallest candidate-class risk bound when the index is chosen with knowledge of the approximation and estimation tradeoff.

For instance, the fixed-class theorem permits $U_m=E[D_m]$, or the potentially looser choice $U_m=2E[\Delta_m]$. The oracle index minimizes a population benchmark, not necessarily the true risk of every fitted predictor. In particular, it need not be identifiable from the observed sample. Comparing an estimator with this benchmark requires a separate argument showing that the estimator’s risk is controlled by it.

A common mistake is to argue that because the oracle benchmark is an infimum over $m$, any sieve estimator automatically satisfies the bound associated with that infimum. The inference is invalid: the theorem for a fixed class bounds $\hat f_m$ using that class’s own $A_m$ and estimation term. An estimator run at a particular index $m_n$ has a bound for $m_n$, not for an index it did not use. The correction is to distinguish the benchmark—the best bound among candidates—from a guarantee that a specific procedure achieves that benchmark.

The decomposition matters because it makes the source of risk explicit. Approximation error describes what is lost by restricting the class; estimation error describes what is lost by learning from a finite sample within it. A sieve can be risk consistent when both contributions vanish along its chosen sequence, while the oracle benchmark summarizes the best tradeoff among the candidate classes under consideration.

Check Your Understanding

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

Why is the decomposition of excess risk an identity even when $\hat f_m$ is not an empirical risk minimizer?
In the within-class ERM theorem, where is empirical minimization used in the proof?
If $A_{m_n}\to0$ but $D_{m_n}$ does not converge to zero, what part of the consistency argument is missing?
Using the table in the worked example, what is the oracle benchmark and which candidate classes attain it?
Why does knowing the oracle benchmark not, by itself, establish that a data-driven estimator attains it?