Finite-Class ERM Bounds

Why a Finite Class Changes the Problem

An empirical risk minimizer is selected using the observed sample, so it is not enough to know that each fixed predictor usually has a reasonable empirical risk. The selected predictor may be the one whose empirical risk happened to look unusually favorable. A finite predictor class lets us control this selection effect directly: bound the risk-estimation error for every member, then use a union bound to make the control simultaneous.

The resulting guarantee is nonasymptotic. It describes the probability that the chosen predictor’s population risk exceeds the best population risk available within the class, and it makes the roles of class size and sample size explicit. Throughout, the loss is bounded; this condition is what allows Hoeffding’s inequality to provide the needed concentration.

Risks and the Finite-Class ERM

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$, and let $\mathcal H$ be a nonempty finite set of predictors with $M=|\mathcal H|$. For a loss function $\ell(h,z)$ satisfying $0\leq \ell(h,z)\leq 1$, define the population risk and empirical risk by $$ R(h)=E_{Z\sim P}[\ell(h,Z)], \qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell(h,Z_i). $$ An empirical risk minimizer, denoted $\hat h$, satisfies $\widehat R_n(\hat h)=\min_{h\in\mathcal H}\widehat R_n(h)$. A population minimizer $h^*$ satisfies $R(h^*)=\min_{h\in\mathcal H}R(h)$.

Both minimizers exist because the class is finite and nonempty. To make $\hat h$ unambiguous, fix an ordering of $\mathcal H$ in advance and choose the first empirical minimizer in that ordering whenever there is a tie. This tie-breaking rule makes the selected predictor a measurable function of the data when the losses are measurable. The population minimizer $h^*$ is fixed independently of the sample; if there is a tie in population risk, choose any one of the minimizers.

The quantity of interest is the excess risk within the class, $R(\hat h)-R(h^*)$. It compares the selected predictor with the best available predictor in $\mathcal H$, not with a predictor outside that class.

From Concentration to Simultaneous Control

For a fixed $h$, the losses $\ell(h,Z_i)$ are independent, identically distributed random variables in $[0,1]$, with mean $R(h)$. Hoeffding’s inequality states that for independent random variables $W_1,\ldots,W_n$ with $a\leq W_i\leq b$, and with $\overline W=n^{-1}\sum_i W_i$, $$ P\bigl(|\overline W-E[\overline W]|\geq t\bigr) \leq 2\exp\left(-\frac{2nt^2}{(b-a)^2}\right), \qquad t>0. $$ Applying this inequality to each fixed predictor controls its empirical risk. A union bound then accounts for all $M$ predictors at once.

Theorem: For any $0<\delta<1$, with probability at least $1-\delta$, $$ \sup_{h\in\mathcal H}\left|\widehat R_n(h)-R(h)\right| \leq \sqrt{\frac{\log(2M/\delta)}{2n}}. $$ Consequently, every empirical risk minimizer $\hat h$ satisfies, on the same event, $$ R(\hat h)-R(h^*) \leq \sqrt{\frac{2\log(2M/\delta)}{n}}. $$

Proof. Fix $h\in\mathcal H$. Hoeffding’s inequality with $a=0$, $b=1$, and $t>0$ gives $$ P\left(\left|\widehat R_n(h)-R(h)\right|\geq t\right) \leq 2\exp(-2nt^2). $$ The event that at least one predictor has deviation at least $t$ is a union of $M$ events. The union bound therefore gives $$ P\left(\sup_{h\in\mathcal H}\left|\widehat R_n(h)-R(h)\right|\geq t\right) \leq 2M\exp(-2nt^2). $$ Set $t=\sqrt{\log(2M/\delta)/(2n)}$. Then $2M\exp(-2nt^2)=\delta$, which proves the simultaneous deviation statement.

On the event in that statement, write $t=\sqrt{\log(2M/\delta)/(2n)}$. By the definition of the event, $R(\hat h)\leq\widehat R_n(\hat h)+t$. Empirical minimization gives $\widehat R_n(\hat h)\leq\widehat R_n(h^*)$, and the same event gives $\widehat R_n(h^*)\leq R(h^*)+t$. Chaining these inequalities yields $$ R(\hat h)\leq\widehat R_n(\hat h)+t \leq\widehat R_n(h^*)+t \leq R(h^*)+2t. $$ Since $2t=\sqrt{2\log(2M/\delta)/n}$, the excess-risk bound follows. $\square$

Worked Example: Evaluating a High-Probability Bound

Suppose $\mathcal H$ contains $M=16$ predictors, the sample size is $n=500$, and the desired failure probability is $\delta=0.05$. The excess-risk bound is $$ \sqrt{\frac{2\log(2M/\delta)}{n}} = \sqrt{\frac{2\log(32/0.05)}{500}} = \sqrt{\frac{2\log(640)}{500}}. $$ Since $\log(640)\approx 6.461$, this is $\sqrt{12.922/500}=\sqrt{0.025844}\approx 0.161$. Thus, with probability at least $0.95$, the ERM’s population risk is at most about $0.161$ above the best population risk in the class. This is a guarantee, not a prediction that the realized excess risk will equal $0.161$.

Sample Size and Class Size

The bound makes the trade-off explicit. Increasing $n$ reduces the bound at the rate $1/\sqrt n$. Increasing $M$ affects it through $\log M$, so enlarging a finite class does not increase the bound linearly. Reducing $\delta$, which asks for higher confidence, increases the bound through $\log(1/\delta)$.

The same theorem can be rearranged to answer a sample-size question. To make the upper bound at most a specified tolerance $\varepsilon>0$, it is sufficient that $$ \sqrt{\frac{2\log(2M/\delta)}{n}}\leq\varepsilon, \qquad\text{or equivalently}\qquad n\geq\frac{2\log(2M/\delta)}{\varepsilon^2}. $$ Because $n$ must be an integer, round this sufficient sample size up.

Worked Example: Choosing a Sample Size

Suppose a finite class has $M=20$ predictors. Find a sufficient sample size for excess risk at most $\varepsilon=0.1$ with probability at least $0.95$. Here $\delta=0.05$, so $$ n\geq\frac{2\log(2(20)/0.05)}{0.1^2} =\frac{2\log(800)}{0.01}. $$ Using $\log(800)\approx6.6846$, the right-hand side is approximately $13.3692/0.01=1336.92$. Therefore $n=1337$ is sufficient under the theorem. This is a sufficient bound from the stated assumptions; it does not claim that 1337 observations are necessary.

A useful equivalent statement follows directly from the proof. If $u>0$, excess risk greater than $u$ implies that the uniform deviation exceeds $u/2$: otherwise the same three-inequality argument would give excess risk at most $u$. Applying the union-bound deviation inequality at $t=u/2$ yields $$ P\bigl(R(\hat h)-R(h^*)>u\bigr) \leq 2M\exp\left(-\frac{nu^2}{2}\right). $$ For any fixed finite class and any fixed $u>0$, this probability tends to zero as $n$ grows. This is risk consistency within the class, expressed as convergence in probability of the excess risk to zero.

Worked Example: A Realized ERM and Its Excess Risk

Let observations take values $u$ and $v$, with $P(Z=u)=0.7$ and $P(Z=v)=0.3$. Consider three predictors with losses $$ \begin{array}{c|cc} &u&v\\ h_1&0&1\\ h_2&0.2&0.2\\ h_3&0.8&0.8 \end{array} $$ The population risks are $R(h_1)=0(0.7)+1(0.3)=0.3$, $R(h_2)=0.2(0.7)+0.2(0.3)=0.2$, and $R(h_3)=0.8(0.7)+0.8(0.3)=0.8$. Thus $h^*=h_2$.

Suppose a sample of size $10$ contains nine observations equal to $u$ and one equal to $v$. The empirical risks are $$ \widehat R_{10}(h_1)=\frac{9(0)+1(1)}{10}=0.1,\qquad \widehat R_{10}(h_2)=0.2,\qquad \widehat R_{10}(h_3)=0.8. $$ The ERM is $h_1$, whose realized excess risk is $R(h_1)-R(h^*)=0.3-0.2=0.1$. This sample is possible under the stated distribution: its probability is $\binom{10}{9}(0.7)^9(0.3)>0$. The bound describes how often excess risk can be large over repeated samples; it need not be tight for a particular sample.

Worked Example: Rescaling the Loss

Suppose instead that the loss lies in $[2,6]$, a range of width $4$. The same Hoeffding and union-bound argument uses $b-a=4$, giving the uniform deviation threshold $$ 4\sqrt{\frac{\log(2M/\delta)}{2n}} $$ and the excess-risk bound $$ 4\sqrt{\frac{2\log(2M/\delta)}{n}}. $$ For example, with $M=4$, $n=1000$, and $\delta=0.05$, the bound is $$ 4\sqrt{\frac{2\log(160)}{1000}} \approx 4\sqrt{0.01015} \approx 0.403. $$ The factor $4$ is the loss range, not the largest loss value. For a loss in $[0,1]$, the range is $1$ and the factor disappears.

Common Pitfall and Interpretation

A common mistake is to apply a concentration inequality only to the predictor that ERM selected, as though that predictor had been fixed before seeing the data. It was selected using the same empirical risks being analyzed. A pointwise bound for one fixed $h$ does not, by itself, control the risk-estimation error of a data-selected $h$. The union bound addresses this issue by controlling deviations for all members of the finite class simultaneously, so the result remains valid whichever member ERM selects.

The class-size factor also needs careful interpretation. The bound depends on the number $M$ of distinct predictors being considered, not directly on how complicated their descriptions look. If two descriptions represent the same predictor with the same loss on every observation, counting both as separate members can make the bound looser, though it remains valid. Finally, boundedness is essential to this particular Hoeffding argument: if losses can be arbitrarily large, this result cannot be applied without additional assumptions or a different concentration method.

Key takeaway: For a finite class of $M$ predictors with loss in $[0,1]$, bounded-loss concentration plus a union bound gives an ERM excess-risk guarantee of $\sqrt{2\log(2M/\delta)/n}$ with probability at least $1-\delta$. The guarantee improves with sample size and worsens only logarithmically with class size and inverse confidence.

Check Your Understanding

Use the theorem and its assumptions to answer the following.

Why does the excess-risk bound contain twice the uniform deviation threshold?
For fixed $M$ and $\delta$, how does the bound change when the sample size is multiplied by four?
What sample size is sufficient for $M=8$, $\delta=0.1$, and excess-risk tolerance $\varepsilon=0.2$?
Why is a concentration bound for one fixed predictor not automatically valid for an ERM selected from the data?
Which part of the argument needs to change if the loss is not bounded?

What You'll Learn