Finite-Class Aggregation · Tutorial 319 of 989

Calculating Finite-Class Penalties From Sample Size

Learn to calculate a finite-class oracle penalty, determine the sample size needed for a target accuracy, and interpret what the bound does—and does not—guarantee.

Intermediate 10 min read

What You'll Learn

State the assumptions behind a bounded-loss finite-class oracle bound.
Calculate the penalty for specified dictionary size, sample size, and confidence level.
Convert a desired penalty into a sufficient sample-size requirement.
Assess how dictionary size and confidence level affect the numerical guarantee.
Recognize when a valid finite-class bound is too loose to be practically useful.

Why Calculate the Penalty?

A finite-class oracle bound compares a selected predictor with the best candidate in a fixed dictionary. Its penalty quantifies the price of selecting from several candidates using the same data. The formula is simple, but its numerical size can be easy to misread: a bound can be valid and still too large to distinguish a useful procedure from a trivial one.

This tutorial works with one standard bounded-loss guarantee and focuses on its calculation and interpretation. The numerical penalty depends on the number of candidates, the sample size, the loss range, and the desired confidence level. It does not depend on knowing which candidate is best.

The Bound and Its Assumptions

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations. Fix $M$ measurable candidate predictors $f_1,\ldots,f_M$ before observing these data. Suppose the loss $\ell(f_j,Z)$ is measurable and lies in $[0,B]$ almost surely for every candidate, where $B>0$. Define the risk and empirical risk by $R_j=E[\ell(f_j,Z)]$ and $\widehat R_j=n^{-1}\sum_{i=1}^n\ell(f_j,Z_i)$. An empirical risk minimizer is any $\hat j\in\{1,\ldots,M\}$ satisfying $\widehat R_{\hat j}=\min_j\widehat R_j$. The oracle risk is $R_*=\min_j R_j$.

Theorem: Under the conditions above, for any $0<\delta<1$, with probability at least $1-\delta$, $$ R_{\hat j}\leq R_*+ \min\left\{B,\;B\sqrt{\frac{2\log(M/\delta)}{n}}\right\}. $$ For $M=1$, the excess risk is exactly zero.

The second term is the finite-class penalty. The logarithm is the natural logarithm. When $M\geq 2$, the calculation to make is $$ \text{penalty}=B\sqrt{\frac{2\log(M/\delta)}{n}}. $$

The bound compares selection with the best risk among these $M$ fixed candidates; it does not claim that the best candidate is optimal among all possible predictors. It is a high-probability statement: the displayed risk guarantee holds on an event whose probability is at least $1-\delta$. Since both risks are in $[0,B]$, the excess risk cannot exceed $B$, which explains the minimum with $B$. If the formula gives a penalty larger than $B$, using $B$ is valid but provides no improvement over that automatic limit.

Here is a proof that also explains why the dictionary size enters through $\log M$. Fix an oracle index $j_*$ such that $R_{j_*}=R_*$, and write $\Delta_j=R_j-R_*$. For any fixed candidate $j$, define $W_i=\ell(f_j,Z_i)-\ell(f_{j_*},Z_i)$. Then $W_i\in[-B,B]$, the variables are independent, and $E[W_i]=\Delta_j$. Hoeffding's inequality for independent variables in intervals of length $2B$ gives $$ P\left(\frac{1}{n}\sum_{i=1}^n W_i-E[W_i]\leq -t\right) \leq \exp\left(-\frac{nt^2}{2B^2}\right),\qquad t>0. $$

If the selected candidate has excess risk greater than $u>0$, then for some $j$, $\Delta_j>u$. Since $\hat j$ minimizes empirical risk, $\widehat R_{\hat j}\leq\widehat R_{j_*}$. Thus, for that $j=\hat j$, the empirical mean of $W_i$ is at most zero, even though its expectation is greater than $u$. Hoeffding's inequality bounds the probability of this event for each fixed $j$ by $\exp(-nu^2/(2B^2))$. Taking a union bound over at most $M$ candidates gives $$ P(R_{\hat j}-R_*>u)\leq M\exp\left(-\frac{nu^2}{2B^2}\right). $$

Set $u=B\sqrt{2\log(M/\delta)/n}$. Substitution makes the right-hand side $\delta$, proving the stated high-probability bound with this penalty. Independently, $R_{\hat j}-R_*\leq B$, because both risks lie in $[0,B]$. Combining these two guarantees gives the minimum in the theorem. If $M=1$, the only candidate is necessarily the oracle, so its excess risk is zero. $\square$

Worked Calculations

Worked Example: Ten Candidates and Two Hundred Observations

Suppose the loss lies in $[0,1]$, so $B=1$, the dictionary contains $M=10$ candidates, the sample size is $n=200$, and the desired confidence level is 95%, so $\delta=0.05$. The penalty is $$ \sqrt{\frac{2\log(10/0.05)}{200}} =\sqrt{\frac{2\log(200)}{200}}. $$

Since $\log(200)\approx 5.2983$, the quantity under the square root is $10.5966/200=0.052983$, and the penalty is approximately $0.2302$. If the best candidate has risk $0.12$, the bound says that, with probability at least $0.95$, the selected candidate has risk at most $0.12+0.2302=0.3502$.

This is a valid guarantee, but its practical informativeness depends on the scale of risks in the application. A bound of $0.3502$ may be useful when risks around $0.35$ are acceptable; it may be weak when the important distinction is between risks of $0.12$ and $0.15$.

Worked Example: A Thousand Candidates

Now take $M=1000$, $n=500$, $B=1$, and again $\delta=0.05$. Here $M/\delta=20{,}000$, so $$ \text{penalty} =\sqrt{\frac{2\log(20{,}000)}{500}}. $$

Using $\log(20{,}000)\approx 9.9035$, the squared penalty is $19.8070/500=0.039614$. Taking the square root gives approximately $0.1990$. If the oracle risk is $0.08$, the resulting 95% guarantee is risk at most $0.2790$.

The increase from 10 to 1000 candidates does not multiply the penalty by 100. The candidate count appears inside a logarithm: for fixed $n$, the penalty changes in proportion to the square root of $\log(M/\delta)$. That is a relatively slow increase, although it can still matter when the sample is modest.

Worked Example: Finding the Sample Size for a Target Penalty

Suppose the loss lies in $[0,1]$, there are $M=1000$ candidates, and a 95% guarantee is required. How large must $n$ be to make the penalty at most $0.10$?

Start from the required inequality and square both nonnegative sides: $$ \sqrt{\frac{2\log(M/\delta)}{n}}\leq 0.10 \quad\Longleftrightarrow\quad n\geq \frac{2\log(M/\delta)}{0.10^2}. $$

Here $M/\delta=1000/0.05=20{,}000$, giving $$ n\geq \frac{2\log(20{,}000)}{0.01} =\frac{19.8070}{0.01} =1980.70. $$

Because the sample size must be a whole number, $n=1981$ is sufficient. Checking it directly gives a squared penalty of $19.8070/1981\approx0.0099985$, whose square root is approximately $0.09999$, just below $0.10$. At $n=1980$, the penalty is approximately $0.10002$, just above the target. In general, the sufficient sample-size threshold for target penalty $\varepsilon>0$ is $$ n\geq \frac{2B^2\log(M/\delta)}{\varepsilon^2}. $$

Worked Example: When the Bound Is Too Loose to Guide a Decision

Consider $M=10{,}000$ candidates, $n=100$, $B=1$, and $\delta=0.05$. Then $M/\delta=200{,}000$, and $$ \text{penalty} =\sqrt{\frac{2\log(200{,}000)}{100}}. $$

Since $\log(200{,}000)\approx12.2061$, the squared penalty is $24.4122/100=0.244122$, giving a penalty of approximately $0.4941$. If the oracle risk is $0.30$, the direct sum is $0.7941$. The automatic upper limit on excess risk is $B=1$, so clipping the penalty at $1$ does not improve this calculation.

The guarantee is mathematically correct, but it may not answer a practical question about whether selection achieves risk near $0.30$. This is a signal to examine the assumptions, the sample size, or the relevance of this worst-case guarantee—not evidence that the calculated bound is false.

How to Read Changes in the Penalty

For fixed $M$, $\delta$, and $B$, doubling the sample size divides the penalty by $\sqrt{2}$, provided the penalty is not clipped at $B$. More generally, multiplying $n$ by a factor $c>0$ multiplies the formula by $1/\sqrt{c}$. To halve the penalty while keeping the other quantities fixed therefore requires four times the sample size.

Increasing $M$ increases the penalty, but only through $\log M$. Tightening the confidence requirement means decreasing $\delta$, which increases $\log(M/\delta)$ and therefore the penalty. These effects are real: a very high confidence level and a large candidate dictionary are not free. At the same time, reporting only $M$ is incomplete. The practical size of the guarantee depends on its relationship to the loss scale $B$, the sample size, and the risk differences that matter in the application.

Derived sample-size rule: For $M\geq2$, a sufficient condition for the displayed penalty to be at most a target $\varepsilon>0$ is $$ n\geq \frac{2B^2\log(M/\delta)}{\varepsilon^2}. $$ This follows by requiring $B\sqrt{2\log(M/\delta)/n}\leq\varepsilon$, dividing by $B>0$, squaring, and rearranging. If $\varepsilon\geq B$, the deterministic excess-risk limit already gives a penalty at most $\varepsilon$.

Common Mistake: Treating the Penalty as a Data-Dependent Score

A common mistake is to read the penalty as the observed gap between the selected candidate and the oracle, or as a prediction of how much worse selection will be on a particular sample. It is neither. It is an upper bound on excess risk that holds with a stated probability under the theorem's assumptions. The actual excess risk can be much smaller, including zero.

Another mistake is to apply the formula unchanged when the candidates were constructed using the same observations, or when the loss is unbounded. The proof used a fixed dictionary and bounded candidate losses; without those conditions, the probability calculation above does not establish this guarantee. Likewise, do not omit $\delta$ when reporting a confidence-specific penalty: changing the desired confidence changes the numerical result.

A useful calculation therefore reports all four ingredients—$B$, $M$, $n$, and $\delta$—alongside the penalty and oracle risk. Then compare the upper bound with the scale of risks that would change the substantive conclusion. A large penalty is informative about the limits of this guarantee, even if it is not informative enough to rank candidates for a particular decision.

Check Your Understanding

Use the bounded-loss finite-class formula and show the main calculation in each answer.

For $B=1$, $M=20$, $n=400$, and $\delta=0.05$, calculate the penalty to three decimal places.
With $B=1$, $M=100$, and $\delta=0.05$, derive the sufficient sample size for a penalty no greater than $0.15$.
At fixed $M$, $B$, and $\delta$, what happens to the penalty if the sample size is multiplied by four?
Why does a penalty greater than $B$ fail to improve on the automatic upper bound for excess risk?
Name two assumptions that would need reconsideration before applying this calculation to a dictionary chosen using the same data.

Back to Tutorials