Estimation Error Within A Fixed Model

Why Estimation Error Depends on the Fixed Model

A model class restricts which predictors an empirical risk minimizer can choose. Even after fixing that class, the selected predictor depends on the observed sample: empirical risks fluctuate around population risks. The resulting estimation error within the class measures how much worse the selected predictor can be than the best predictor that the same class contains.

This is a comparison within one fixed candidate class, not a comparison with an unrestricted target and not a guarantee for choosing among several classes. The distinction matters: the bound below charges for the number of candidates in the fixed class, while searching across models requires additional accounting.

Definition: Let $Z_1,\ldots,Z_n$ be independent, identically distributed observations with the same distribution as $Z$. For a predictor $f$ in a nonempty finite class $\mathcal F$, let $\ell_f(Z)$ be its loss, and suppose it is measurable and takes values in $[0,M]$, where $M>0$. Define the population risk and empirical risk by $$ R(f)=E[\ell_f(Z)], \qquad \widehat R_n(f)=\frac{1}{n}\sum_{i=1}^n \ell_f(Z_i). $$ An empirical risk minimizer (ERM) is a predictor $\hat f\in\mathcal F$ minimizing $\widehat R_n(f)$ over $f\in\mathcal F$. A population risk minimizer $f_{\mathcal F}^*$ minimizes $R(f)$ over $\mathcal F$. The quantity $R(\hat f)-R(f_{\mathcal F}^*)$ is the excess risk within $\mathcal F$.

Since $\mathcal F$ is finite and nonempty, a population minimizer exists. An empirical minimizer exists as well; a fixed rule for resolving ties makes $\hat f$ a well-defined, measurable choice. The class is assumed to be fixed independently of the observed sample. Write $N=|\mathcal F|$ for its cardinality.

A High-Probability Bound for a Fixed Finite Class

Theorem: Under the definition above, for any $0<\delta<1$, an ERM satisfies $$ P\left\{R(\hat f)-R(f_{\mathcal F}^*)\leq M\sqrt{\frac{2\log(2N/\delta)}{n}}\right\}\geq 1-\delta. $$ Because every risk lies in $[0,M]$, the right-hand side can also be replaced by its minimum with $M$.

The ingredients are concentration of each empirical risk and a union bound over the finite class. For a fixed $f$, Hoeffding's inequality applies because the $n$ losses are independent and bounded in an interval of length $M$. It gives $$ P\{|\widehat R_n(f)-R(f)|>t\}\leq 2\exp\left(-\frac{2nt^2}{M^2}\right). $$ The union bound makes this deviation control hold for every member of the class at once. The ERM comparison then costs a factor of two in the uniform deviation.

Control one predictor.
Hoeffding's inequality bounds the probability that the empirical risk of a fixed $f$ differs from its population risk by more than $t$.

Control the whole class.
A union bound over $N$ predictors gives probability at most $2N\exp(-2nt^2/M^2)$ that any predictor has deviation greater than $t$.

Compare ERM with the best class member.
On the event of uniform deviation at most $t$, ERM's excess risk is at most $2t$.

Proof. Define $D=\sup_{f\in\mathcal F}|\widehat R_n(f)-R(f)|$. Since the class is finite, the supremum is a maximum. For any $t>0$, Hoeffding's inequality and the union bound imply $$ P(D>t)\leq 2N\exp\left(-\frac{2nt^2}{M^2}\right). $$ Choose $t=M\sqrt{\log(2N/\delta)/(2n)}$. Substitution gives $P(D>t)\leq\delta$. On the event $D\leq t$, the minimizing property of $\hat f$ yields $$ \begin{aligned} R(\hat f)-R(f_{\mathcal F}^*) &=[R(\hat f)-\widehat R_n(\hat f)] +[\widehat R_n(\hat f)-\widehat R_n(f_{\mathcal F}^*)]\\ &\quad+[\widehat R_n(f_{\mathcal F}^*)-R(f_{\mathcal F}^*)]\\ &\leq |R(\hat f)-\widehat R_n(\hat f)| +| \widehat R_n(f_{\mathcal F}^*)-R(f_{\mathcal F}^*)|\\ &\leq 2D\leq 2t. \end{aligned} $$ The middle empirical-risk difference is nonpositive because $\hat f$ minimizes empirical risk over $\mathcal F$. Thus, with probability at least $1-\delta$, the excess risk is at most $2t=M\sqrt{2\log(2N/\delta)/n}$. It is also at most $M$, since both risks lie in $[0,M]$. $\square$

Worked Risk Calculations

Worked Example: A Confidence Bound for Sixty Candidates

Suppose losses lie in $[0,1]$, the fixed class contains $N=60$ predictors, and $n=500$. At confidence level $1-\delta=0.95$, assume the best predictor in the class has risk $0.27$. Find the resulting upper bound on the risk of an ERM.

Here $M=1$ and $\delta=0.05$. The logarithm's argument is $$ \frac{2N}{\delta}=\frac{2(60)}{0.05}=2400. $$ Thus the excess-risk bound is $$ \sqrt{\frac{2\log(2400)}{500}} =\sqrt{0.031132896\ldots} \approx 0.176445. $$ Consequently, with probability at least $0.95$, $$ R(\hat f)\leq 0.27+0.176445\ldots=0.446445\ldots. $$ For a rounded-up statement, $R(\hat f)\leq 0.447$ with probability at least $0.95$. The bound controls risk relative to the best candidate in these sixty predictors; it does not assert that the best candidate itself has risk $0.27$ because of any particular data realization.

Worked Example: How Class Size Changes the Bound

Compare fixed classes with $N=4$ and $N=64$, using $n=1000$, losses in $[0,1]$, and $\delta=0.10$. The bound on excess risk is $\sqrt{2\log(2N/\delta)/n}$.

For $N=4$, $2N/\delta=80$, so $$ \sqrt{\frac{2\log(80)}{1000}} =\sqrt{0.008764053\ldots} \approx 0.093617. $$ For $N=64$, $2N/\delta=1280$, so $$ \sqrt{\frac{2\log(1280)}{1000}} =\sqrt{0.014309231\ldots} \approx 0.119621. $$ Therefore the respective bounds are at most $0.09362$ and $0.11963$ when rounded upward. The larger class has a larger bound, but increasing its size by a factor of sixteen does not increase the bound by a factor of sixteen: the cardinality appears inside a logarithm.

Worked Example: Choosing a Sample Size for a Target Accuracy

For a class of $N=8$ predictors with losses in $[0,1]$, how large must $n$ be for the theorem to guarantee excess risk at most $0.20$ with probability at least $0.95$?

Require $$ \sqrt{\frac{2\log(2N/\delta)}{n}}\leq 0.20, \qquad \delta=0.05. $$ Squaring both nonnegative sides and rearranging gives $$ n\geq\frac{2\log(2(8)/0.05)}{0.20^2} =\frac{2\log(320)}{0.04} =\frac{11.5366419917\ldots}{0.04} =288.4160498\ldots. $$ The smallest integer meeting this sufficient condition is $n=289$. Indeed, at $n=289$ the bound is $$ \sqrt{\frac{11.5366419917\ldots}{289}}\approx 0.1998<0.20. $$ At $n=288$, it is approximately $0.20014>0.20$, so $288$ does not satisfy the theorem's condition. This calculation identifies the sample size sufficient for this bound, not a necessary sample size for every problem.

An Expected Excess-Risk Bound

The same deviation argument also gives an expectation guarantee. This is useful when performance is summarized by average excess risk rather than by a probability statement at a chosen confidence level.

Result: Under the theorem's assumptions, with $Z=R(\hat f)-R(f_{\mathcal F}^*)$, $$ E[Z]\leq M\sqrt{\frac{2\log(2N)}{n}} +\frac{M}{\sqrt{2n\log(2N)}}. $$ This upper bound is valid even when it exceeds $M$; in that case the direct bound $E[Z]\leq M$ is sharper.

Derivation. For any $x>0$, the proof's comparison $Z\leq 2D$ implies that $Z>x$ only if $D>x/2$. Hence $$ P(Z>x)\leq 2N\exp\left(-\frac{nx^2}{2M^2}\right). $$ Also $0\leq Z\leq M$. For a nonnegative random variable, $E[Z]=\int_0^\infty P(Z>x)\,dx$. Set $a=M\sqrt{2\log(2N)/n}$. Bounding the integral from $0$ to $a$ by $a$, and using the tail bound above $a$, gives $$ E[Z]\leq a+2N\int_a^\infty \exp\left(-\frac{nx^2}{2M^2}\right)\,dx. $$ For $c>0$ and $a>0$, $\int_a^\infty e^{-cx^2}\,dx\leq e^{-ca^2}/(2ca)$; this follows by replacing $1$ in the integrand by $x/a$, which is at least $1$ for $x\geq a$, and integrating $xe^{-cx^2}$. Apply it with $c=n/(2M^2)$. Since $e^{-na^2/(2M^2)}=1/(2N)$, the tail integral, including its factor $2N$, is at most $M^2/(na)$. Substituting the value of $a$ gives the stated result. $\square$

What the Bound Does—and Does Not—Say

The bound makes the estimation trade-off explicit. More observations decrease the bound at rate $1/\sqrt n$, while a larger fixed class increases it through $\log N$. The loss range $M$ scales the guarantee: rescaling all losses rescales the risk and the bound by the same factor. These are finite-sample guarantees; they need not be sharp for a particular distribution or class.

A frequent mistake is to read “ERM minimizes empirical risk” as “ERM has the smallest population risk.” The minimization is over $\widehat R_n$, not $R$. The proof works precisely because empirical and population risks can differ, and the uniform deviation term accounts for that difference. A second pitfall is to treat the displayed bound as automatically informative: if it exceeds $M$, the trivial range bound is better. Finally, the theorem assumes one fixed finite class. Applying it after using the same data to search across many classes without accounting for that search is not justified by this result.

Key takeaway: For bounded loss and a fixed finite class, ERM's excess risk over the best member of that class is at most $M\sqrt{2\log(2N/\delta)/n}$ with probability at least $1-\delta$. The logarithm of the class size measures the cost of controlling all candidates at once.

Check Your Understanding

Use the definitions and bound above to answer these questions.

Why is the comparator $f_{\mathcal F}^*$ a best-in-class predictor rather than necessarily a predictor with the smallest possible risk?
In the theorem, where do independence and the bound $[0,M]$ enter the proof?
For fixed $M$, $N$, and $\delta$, how does the excess-risk bound change when the sample size is multiplied by four?
Why does the class cardinality enter through $\log N$, and which step of the proof introduces it?
If the theorem's bound is larger than $M$, what valid bound on the excess risk is still available?
Why does this fixed-class theorem not by itself justify selecting among many classes using the same observations?