Calibrating Penalties With Uniform Deviation Bounds

Why a Uniform Deviation Bound Calibrates a Penalty

An empirical risk is useful because it can be computed from the observed sample. The risk of a predictor under the population distribution is the quantity we ultimately want to control, but it is not directly observed. The gap between these two risks can be small for one predictor and large for another. A penalty intended to protect a risk criterion must therefore account for the gap over the predictors that could be selected, not just at one predictor chosen in advance.

This tutorial derives such a penalty for losses bounded between zero and one. The main ingredients are an expected supremum bound, which measures the average size of the largest gap, and a concentration inequality, which converts that average into a high-probability guarantee. The result is a penalty level that can be added to empirical risk to control population risk simultaneously over a fixed predictor class.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed observations with distribution $F$. For a predictor $f$ in a fixed class $\mathcal F$, let $\ell_f(X)\in[0,1]$ be its loss. Define its population risk and empirical risk by $$ R(f)=E[\ell_f(X)],\qquad R_n(f)=\frac{1}{n}\sum_{i=1}^n \ell_f(X_i). $$ The uniform deviation over $\mathcal F$ is $$ Z_{\mathcal F}=\sup_{f\in\mathcal F}|R(f)-R_n(f)|. $$

For the results below, assume that $\mathcal F$ is finite, so the supremum is measurable and finite. The same arguments extend to suitably measurable classes with finite expected suprema. The class and its loss functions are fixed independently of the observed sample. A class constructed using the same data needs additional care; a bound for a fixed class does not automatically cover that construction.

Symmetrization and Expected Complexity

The population risk in $Z_{\mathcal F}$ is an expectation, so it is not immediately a sample-based quantity. Symmetrization introduces an independent sample to express the expected deviation in terms of random signs. For this tutorial, define the expected absolute Rademacher complexity of the loss class by

\mathfrak R_n^{\mathrm{abs}}(\mathcal F) = E_{X,\varepsilon}\left[ \sup_{f\in\mathcal F} \left|\frac{1}{n}\sum_{i=1}^n\varepsilon_i\ell_f(X_i)\right| \right],

where $\varepsilon_1,\ldots,\varepsilon_n$ are independent signs, each equal to $1$ or $-1$ with probability $1/2$, independent of the observations. The absolute value convention is stated explicitly because Rademacher complexity is also commonly defined without an absolute value.

Theorem (Symmetrization): Under the assumptions above, $$ E[Z_{\mathcal F}]\leq 2\mathfrak R_n^{\mathrm{abs}}(\mathcal F). $$

Proof. Let $X_1',\ldots,X_n'$ be an independent sample from $F$, also independent of $X_1,\ldots,X_n$. For each fixed observed sample, Jensen's inequality for the supremum of absolute values gives

\begin{aligned} E_X\sup_{f\in\mathcal F} \left|E_{X'}\left[\frac1n\sum_{i=1}^n\ell_f(X_i')-R_n(f)\right]\right| &\leq E_{X,X'}\sup_{f\in\mathcal F} \left|\frac1n\sum_{i=1}^n\bigl(\ell_f(X_i')-\ell_f(X_i)\bigr)\right|. \end{aligned}

Each pair $(X_i,X_i')$ has the same distribution after its two entries are exchanged. Consequently, inserting independent signs $\varepsilon_i$ into the pairwise differences does not change the expectation on the right. The triangle inequality for the supremum then yields

\begin{aligned} E[Z_{\mathcal F}] &\leq E_{X,X',\varepsilon}\sup_{f\in\mathcal F} \left|\frac1n\sum_{i=1}^n \varepsilon_i\bigl(\ell_f(X_i')-\ell_f(X_i)\bigr)\right|\\ &\leq E_{X',\varepsilon}\sup_{f\in\mathcal F} \left|\frac1n\sum_{i=1}^n\varepsilon_i\ell_f(X_i')\right| +E_{X,\varepsilon}\sup_{f\in\mathcal F} \left|\frac1n\sum_{i=1}^n\varepsilon_i\ell_f(X_i)\right|\\ &=2\mathfrak R_n^{\mathrm{abs}}(\mathcal F). \end{aligned}

The last equality holds because the primed and unprimed samples have the same distribution. This proves the claim. $\square$

Worked Example: Computing a Small Rademacher Complexity

Let $X\sim\operatorname{Bernoulli}(1/2)$, take $n=2$, and consider two losses $\ell_0(x)=0$ and $\ell_1(x)=x$. Compute the expected absolute Rademacher complexity and the symmetrization bound.

For a fixed sample, the supremum is the larger of $0$ and $\left|\varepsilon_1X_1+\varepsilon_2X_2\right|/2$. Let $K=X_1+X_2$. Its probabilities are $P(K=0)=1/4$, $P(K=1)=1/2$, and $P(K=2)=1/4$. When $K=0$, the absolute signed sum is zero. When $K=1$, it is one. When $K=2$, it is $|\varepsilon_1+\varepsilon_2|$, whose expectation is $$ \frac12(0)+\frac12(2)=1. $$

Thus $E|\varepsilon_1X_1+\varepsilon_2X_2|=\frac12\cdot1+\frac14\cdot1=\frac34$, and division by $n=2$ gives $\mathfrak R_2^{\mathrm{abs}}(\mathcal F)=3/8$. Symmetrization therefore gives $E[Z_{\mathcal F}]\leq 3/4$. This bound is valid but loose: the actual uniform deviation is just $|1/2-(X_1+X_2)/2|$, which is $1/2$ when $K=0$ or $2$ and zero when $K=1$. Its expectation is $1/4$.

From Expected Deviation to High Probability

The expected deviation alone does not guarantee that the observed sample has a small deviation. Concentration supplies an additional margin. Replacing one observation changes $R_n(f)$ by at most $1/n$, for every $f$, because each loss lies in $[0,1]$. The supremum of absolute deviations changes by no more than the largest change among its terms. Therefore replacing one observation changes $Z_{\mathcal F}$ by at most $1/n$.

Theorem (McDiarmid's bounded differences inequality): If a function $g(X_1,\ldots,X_n)$ changes by at most $c_i$ when only coordinate $i$ is replaced, then for independent inputs and $t>0$, $$ P\{g-E[g]\geq t\}\leq \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$

For completeness, the inequality follows by exposing the independent coordinates one at a time and forming the Doob martingale of conditional expectations of $g$. Its $i$th martingale difference, conditional on the previous coordinates, lies in an interval of length at most $c_i$: changing coordinate $i$ changes the conditional expectation by at most $c_i$. Hoeffding's lemma states that a mean-zero random variable supported on an interval of length $c$ has moment generating function at most $\exp(\lambda^2c^2/8)$. Applying this conditional bound successively to the martingale differences gives $$ E\exp\{\lambda(g-E[g])\} \leq \exp\left(\frac{\lambda^2}{8}\sum_{i=1}^n c_i^2\right). $$ Markov's inequality bounds the upper-tail probability by the right side multiplied by $\exp(-\lambda t)$. Minimizing over $\lambda>0$, with $\lambda=4t/\sum_i c_i^2$, gives the stated inequality.

For $g=Z_{\mathcal F}$, each $c_i=1/n$, so $\sum_i c_i^2=1/n$. Combining bounded differences with symmetrization gives the following penalty calibration.

Corollary: For any $0<\delta<1$, with probability at least $1-\delta$, $$ \sup_{f\in\mathcal F}|R(f)-R_n(f)| \leq 2\mathfrak R_n^{\mathrm{abs}}(\mathcal F) +\sqrt{\frac{\log(1/\delta)}{2n}}. $$ In particular, a uniform upper-deviation penalty can be set to the right-hand side: simultaneously for every $f\in\mathcal F$, $R(f)\leq R_n(f)+2\mathfrak R_n^{\mathrm{abs}}(\mathcal F)+\sqrt{\log(1/\delta)/(2n)}$.

This corollary separates two sources of penalty. The complexity term controls the expected largest deviation across the class; the confidence term increases the penalty when a stronger probability guarantee is required. Neither term is a variance-sensitive refinement.

Worked Example: A Direct Penalty for Eight Predictors

Suppose a fixed class contains $M=8$ predictors, each with losses in $[0,1]$. Use a direct finite-class bound to calibrate a penalty for $n=100$ and $\delta=0.05$.

For any fixed predictor, Hoeffding's inequality gives $P(|R(f)-R_n(f)|>t)\leq 2e^{-2nt^2}$. A union bound over eight predictors gives $P(Z_{\mathcal F}>t)\leq16e^{-200t^2}$. Setting this upper bound equal to $0.05$ and solving yields $$ t=\sqrt{\frac{\log(16/0.05)}{200}} =\sqrt{\frac{\log(320)}{200}} =\sqrt{\frac{5.76832}{200}} \approx 0.16983. $$

Thus $0.16983$ is a valid simultaneous penalty with confidence at least $0.95$. This calculation uses the finite size of the class directly; a Rademacher-based penalty may be smaller when the loss functions have structure that the class size does not capture.

Finite-Class Expected Bounds and Classwise Penalties

A finite class also gives a bound on the expected supremum. For each $f$, the moment-generating function of $R(f)-R_n(f)$, and of its negative, is bounded by $\exp(\lambda^2/(8n))$. Hence, for $\lambda>0$,

E e^{\lambda Z_{\mathcal F}} \leq 2M\exp\left(\frac{\lambda^2}{8n}\right).

Jensen's inequality implies $E[Z_{\mathcal F}]\leq \log E[e^{\lambda Z_{\mathcal F}}]/\lambda$. Minimizing the resulting upper bound $\log(2M)/\lambda+\lambda/(8n)$ over $\lambda>0$ gives

E[Z_{\mathcal F}]\leq\sqrt{\frac{\log(2M)}{2n}}.

Adding the bounded-differences margin gives a second finite-class penalty: $$ \sqrt{\frac{\log(2M)}{2n}}+\sqrt{\frac{\log(1/\delta)}{2n}}. $$ The direct union-bound penalty in the preceding example combines the logarithms and can be sharper in that setting. Expected-complexity bounds are especially useful when the class has structure not represented by its raw number of members.

Worked Example: Allocating Confidence Across Candidate Classes

Suppose there are countably many fixed candidate classes $\mathcal F_m$, indexed by $m=1,2,\ldots$, with $|\mathcal F_m|=M_m$. Set $M_1=2$, $M_2=8$, and $M_3=32$, and use $n=500$. For an overall error probability $\delta=0.05$, allocate $\delta_m=\delta/[m(m+1)]$. Since $\sum_{m=1}^{\infty}1/[m(m+1)]=1$, the allocated error probabilities sum to $0.05$.

For class $m$, the finite-class union bound gives a simultaneous deviation penalty $$ \operatorname{pen}_m =\sqrt{\frac{\log(2M_m/\delta_m)}{2n}}. $$ For the first three classes, the calculations are $$ \begin{aligned} \operatorname{pen}_1 &=\sqrt{\frac{\log(4/0.025)}{1000}} =\sqrt{\frac{\log(160)}{1000}} \approx 0.07124,\\ \operatorname{pen}_2 &=\sqrt{\frac{\log(16/(0.05/6))}{1000}} =\sqrt{\frac{\log(1920)}{1000}} \approx 0.08695,\\ \operatorname{pen}_3 &=\sqrt{\frac{\log(64/(0.05/12))}{1000}} =\sqrt{\frac{\log(15360)}{1000}} \approx 0.09818. \end{aligned} $$

A union bound over all classes shows that, with probability at least $0.95$, every predictor in every class satisfies $R(f)\leq R_n(f)+\operatorname{pen}_m$ for its class index $m$. The increasing penalties reflect both larger class sizes and the decreasing error probability allocated to higher indices. This calculation calibrates simultaneous deviations; it does not by itself establish an oracle inequality for a particular selection rule.

Common Pitfall and Practical Interpretation

Pitfall: Choose a predictor after inspecting the sample, compute a deviation bound that holds for one fixed predictor, and then claim that the same guarantee holds for the selected predictor. This reverses the logic: the selected predictor may be the one with an unusually favorable empirical risk among many candidates. A fixed-predictor bound does not control that selection effect.

Correction: Control the supremum over the entire fixed class, or otherwise justify a bound for the selection procedure. The uniform bounds here do exactly that: on their stated event, every predictor in the class is covered at once, so a predictor selected from that class is covered as well. For multiple candidate classes, confidence allocation or another valid simultaneous argument is necessary. The class must be specified independently of the sample for the results given here to apply directly.

The penalty should be interpreted as a protection against population-to-empirical optimism, not as a universal constant. It depends on sample size, confidence level, and the complexity of the predictor or loss class. A useful calibration is large enough to dominate the relevant uniform deviation while not being inflated beyond what the available complexity bound supports.

Check Your Understanding

Use the definitions and assumptions stated above to answer the following.

Why is a bound for one fixed predictor insufficient when the predictor is selected by minimizing empirical risk over a class?
In the symmetrization proof, what role does the independent sample $X_1',\ldots,X_n'$ play?
For losses in $[0,1]$, by how much can $Z_{\mathcal F}$ change when one observation is replaced, and why?
How do the expected-complexity and confidence terms in the penalty respond to increasing $n$ or decreasing $\delta$?
Why must the error probabilities allocated to countably many classes sum to no more than the desired overall error probability?