Union-Bound Proof Of A Finite-Class SRM Guarantee

Why a Simultaneous Bound Is Needed

Structural risk minimization compares candidate classes of different complexity. A deviation bound for one class controls the gap between empirical and population risk within that class. But the selected class depends on the data, so a bound that holds for each fixed class separately is not, by itself, a guarantee for the data-selected class. The key step is to arrange that the bounds hold for all candidate classes at once.

For a finite collection, the union bound gives this simultaneous control. The resulting penalties can account for the confidence level assigned to each class. Once the simultaneous event holds, a direct comparison of the penalized empirical risks gives a risk guarantee for the selected predictor.

Modelwise Deviation Bounds

Let $Z_1,\ldots,Z_n$ be independent, identically distributed observations with common distribution $P$. A predictor $f$ has loss $\ell_f(Z)$, population risk $R(f)=E[\ell_f(Z)]$, and empirical risk $ \widehat R(f)=n^{-1}\sum_{i=1}^n\ell_f(Z_i) $. Consider a fixed, finite collection of candidate classes $\mathcal F_1,\ldots,\mathcal F_M$. Assume the risks and suprema below are measurable. Define the modelwise deviation $D_m=\sup_{f\in\mathcal F_m}|R(f)-\widehat R(f)|$.

Definition: A modelwise deviation bound for class $\mathcal F_m$ is a deterministic function $b_m(t)$ such that, for every $t>0$, $$ P\{D_m>b_m(t)\}\leq e^{-t}. $$ The function $b_m$ may depend on the sample size, the class, and the form of the available concentration result.

The bounds for different classes need not have the same size. A more complex class may have a larger deviation bound and therefore require a larger penalty. Nor must every class receive the same share of the total failure probability: any positive weights $w_1,\ldots,w_M$ summing to one can be used.

The Finite-Collection Union-Bound Guarantee

Theorem: Suppose each class has a modelwise deviation bound $b_m(t)$. Choose deterministic weights $w_m>0$ with $\sum_{m=1}^M w_m=1$. For any $0<\delta<1$, set $$ t_m=\log\!\left(\frac{1}{\delta w_m}\right), \qquad a_m=b_m(t_m). $$ Then, with probability at least $1-\delta$, simultaneously for every $m$ and every $f\in\mathcal F_m$, $$ |R(f)-\widehat R(f)|\leq a_m. $$

Proof. For each $m$, the modelwise bound at $t_m$ gives $P\{D_m>a_m\}\leq e^{-t_m}=\delta w_m$. The event that at least one class violates its bound is the union of these $M$ events. Therefore, $$ P\{\text{some }D_m>a_m\} \leq \sum_{m=1}^M P\{D_m>a_m\} \leq \sum_{m=1}^M\delta w_m =\delta. $$ The complementary event has probability at least $1-\delta$, and on it every classwise deviation is at most its assigned $a_m$. Since $D_m$ is the supremum over $\mathcal F_m$, the assertion holds for every predictor in every class. $\square$

With equal weights $w_m=1/M$, the bound uses $t_m=\log(M/\delta)$ for every class. The factor $M$ is the price of requiring simultaneous control of $M$ classes. Unequal weights can assign more of the failure probability to some classes and less to others; the chosen weights must still be positive and sum to one.

Worked Example: Equal Confidence Allocation Across Five Models

Suppose there are $M=5$ candidate classes, $n=1000$, and a modelwise bound $b_m(t)=\sqrt{(d_m+t)/n}$, where the five complexity values are $d_m=1,4,9,16,25$. We want simultaneous coverage at least $0.95$, so $\delta=0.05$. With equal weights, $t_m=\log(5/0.05)=\log(100)\approx4.605$.

The five deviation levels are $$ \begin{aligned} a_1&=\sqrt{(1+4.605)/1000}\approx0.0749,\\ a_2&=\sqrt{(4+4.605)/1000}\approx0.0928,\\ a_3&=\sqrt{(9+4.605)/1000}\approx0.1166,\\ a_4&=\sqrt{(16+4.605)/1000}\approx0.1435,\\ a_5&=\sqrt{(25+4.605)/1000}\approx0.1721. \end{aligned} $$

Thus, with probability at least $0.95$, all predictors in class $m$ have empirical and population risks within $a_m$, for each of the five classes. The larger bounds for classes with larger $d_m$ are retained rather than replaced by a single bound based on the most complex class.

From Simultaneous Control to a Selection Guarantee

For each class, let $\widehat f_m$ minimize empirical risk over $\mathcal F_m$, and write $\widehat R_m=\widehat R(\widehat f_m)$. Assume these minima are attained. Select a model by minimizing penalized empirical risk: $$ \widehat m\in\arg\min_{1\leq m\leq M}\{\widehat R_m+\operatorname{pen}_m\}, \qquad \widehat f=\widehat f_{\widehat m}. $$ The penalties are deterministic and may use the deviation levels $a_m$. A particularly direct choice is $\operatorname{pen}_m=a_m$.

Theorem: On the simultaneous event $|R(f)-\widehat R(f)|\leq a_m$ for all $m$ and $f\in\mathcal F_m$, suppose $\operatorname{pen}_m\geq a_m$ for every $m$. Then $$ R(\widehat f)\leq \inf_{1\leq m\leq M} \left\{\inf_{f\in\mathcal F_m}R(f)+a_m+\operatorname{pen}_m\right\}. $$ Consequently, with probability at least $1-\delta$, this inequality holds when $a_m=b_m(\log(1/(\delta w_m)))$. In particular, if $\operatorname{pen}_m=a_m$, the right-hand side is $\inf_m\{\inf_{f\in\mathcal F_m}R(f)+2a_m\}$.

Proof. On the simultaneous event, for the selected predictor, $$ R(\widehat f) \leq \widehat R_{\widehat m}+a_{\widehat m} \leq \widehat R_{\widehat m}+\operatorname{pen}_{\widehat m}. $$ The second inequality uses $\operatorname{pen}_{\widehat m}\geq a_{\widehat m}$. By the definition of $\widehat m$, for every candidate index $m$, $$ \widehat R_{\widehat m}+\operatorname{pen}_{\widehat m} \leq \widehat R_m+\operatorname{pen}_m. $$ For any $f\in\mathcal F_m$, empirical minimization gives $\widehat R_m\leq\widehat R(f)$, and simultaneous control gives $\widehat R(f)\leq R(f)+a_m$. Combining these inequalities yields $$ R(\widehat f)\leq R(f)+a_m+\operatorname{pen}_m. $$ Taking the infimum over $f\in\mathcal F_m$, and then over $m$, proves the result. If a population-risk infimum is not attained, apply the inequality to predictors whose risks approach that infimum and take the limit. $\square$

The comparison is against the best population-risk predictor in each candidate class, with an additional term reflecting that class’s deviation level and penalty. This is a risk guarantee, not a claim that the selected class is the class that generated the data. In particular, it remains meaningful when all candidate classes are approximations.

Worked Example: Finite Classes and Hoeffding’s Inequality

Suppose losses are in $[0,1]$ and each of three candidate classes is finite, with sizes $N_1=2$, $N_2=8$, and $N_3=32$. For a fixed predictor, Hoeffding’s inequality gives $P\{|R(f)-\widehat R(f)|>\epsilon\}\leq2e^{-2n\epsilon^2}$. A union bound over the $N_m$ predictors therefore gives $$ P\{D_m>\epsilon\}\leq 2N_m e^{-2n\epsilon^2}. $$

Set this upper bound equal to $\delta/M$, with $M=3$, $n=200$, and $\delta=0.1$. Solving for $\epsilon$ gives $$ a_m=\sqrt{\frac{\log(2N_mM/\delta)}{2n}}. $$ For the three classes, the calculations are $$ \begin{aligned} a_1&=\sqrt{\log(120)/400}\approx0.1094,\\ a_2&=\sqrt{\log(480)/400}\approx0.1242,\\ a_3&=\sqrt{\log(1920)/400}\approx0.1375. \end{aligned} $$

Indeed, for each class the failure probability is at most $\delta/3$, so the probability that any class fails is at most $3(\delta/3)=0.1$. Using penalties equal to these three deviation levels, the selection theorem gives a simultaneous risk comparison with an additive term $2a_m$ for each comparator class.

Worked Example: Comparing Penalized Empirical Risks

Suppose a simultaneous event holds for three classes, with deviation levels and penalties $a_m=\operatorname{pen}_m=(0.03,0.06,0.09)$. Their minimized empirical risks are $\widehat R_m=(0.31,0.26,0.23)$. The penalized values are $$ 0.31+0.03=0.34,\qquad 0.26+0.06=0.32,\qquad 0.23+0.09=0.32. $$ Choose class 2 in the tie, so $\widehat m=2$.

The direct risk bound for the selected predictor is $R(\widehat f)\leq\widehat R_2+a_2=0.26+0.06=0.32$. The comparison to each class’s best population risk is also explicit: the theorem gives bounds of $\inf_{f\in\mathcal F_1}R(f)+0.06$, $\inf_{f\in\mathcal F_2}R(f)+0.12$, and $\inf_{f\in\mathcal F_3}R(f)+0.18$; the guarantee is the smallest of these. The calculation shows how a class with a lower empirical risk can lose to a less complex class after its larger uncertainty penalty is included.

Common Pitfall and Interpretation

A common error is to give every model a failure probability $\delta$, then conclude that all $M$ bounds hold with probability $1-\delta$. The union bound only gives $P\{\text{some bound fails}\}\leq M\delta$ in that case, so the claimed confidence level does not follow. The correction is to allocate failure probabilities whose sum is at most the desired total $\delta$, for example $\delta/M$ per model or $\delta w_m$ with weights summing to one.

A related mistake is to apply a single-model guarantee only after observing which model was selected. The selected index is data-dependent, so that reasoning does not ensure that the guarantee holds for it. Simultaneous control avoids this problem: on the common event, every possible selected class is already covered. The finite union bound is what pays for searching over the collection.

Key takeaway: Convert each modelwise deviation bound into a class-specific penalty using a confidence allocation, use the union bound to make the controls simultaneous, and compare penalized empirical risks on that event. The selected predictor’s risk is then bounded by the best candidate-class risk plus its deviation and penalty terms.

Check Your Understanding

Work through these questions using the definitions and guarantees above.

With $M=8$ equally weighted classes and total failure probability $\delta$, what value of $t_m$ is used for each class?
Why does a modelwise bound for each fixed class not automatically establish a bound for a data-selected class?
For weights $w_m$, what condition must hold for the finite-collection union-bound guarantee to have total failure probability at most $\delta$?
In the selection theorem, where is the condition $\operatorname{pen}_m\geq a_m$ used?
If penalties equal deviation levels, what additive term appears alongside a comparator class’s best population risk?