Uniform Risk Bounds for Empirical Risk Minimizers

From Uniform Deviation to Generalization

An empirical risk minimizer chooses a candidate with the smallest loss on the observed sample. The quantity of real interest, however, is its population risk: its expected loss on a new observation from the same distribution. These two risks need not agree for any one candidate. A uniform deviation bound addresses the gap across the whole class at once, which makes it possible to control the risk of a candidate selected using the data.

The key comparison is with a candidate that minimizes population risk. The empirical minimizer can be worse than this benchmark only to the extent that their empirical and population risks differ. The comparison yields a simple oracle inequality: the minimizer’s excess risk is at most twice the largest uniform deviation.

Risks and Uniform Deviation

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$ on a measurable space $\mathcal Z$. Let $\mathcal H$ be a class of candidates, and let $\ell_h:\mathcal Z\to\mathbb R$ be the measurable loss associated with $h\in\mathcal H$. Assume each loss is integrable, so its population risk is finite.

Definition: The population risk of $h$ and its empirical risk on the sample are $$ R(h)=E[\ell_h(Z)], \qquad R_n(h)=\frac{1}{n}\sum_{i=1}^{n}\ell_h(Z_i). $$ The uniform deviation is $$ \Delta_n=\sup_{h\in\mathcal H}|R_n(h)-R(h)|. $$ For the statements below, assume this supremum is measurable and finite almost surely. For example, measurability holds when $\mathcal H$ is countable and the losses are measurable.

The supremum is important: a candidate chosen after seeing the data is random, so a deviation bound for one fixed candidate alone does not automatically apply to it. By definition, whenever $\Delta_n$ is finite, every candidate in the class satisfies $|R_n(h)-R(h)|\leq\Delta_n$, including a sample-dependent choice.

Assume a population-risk minimizer $h^*\in\mathcal H$ exists, so $R(h^*)=\inf_{h\in\mathcal H}R(h)$. An empirical risk minimizer is a measurable sample-dependent choice $\hat h\in\mathcal H$ satisfying $R_n(\hat h)=\inf_{h\in\mathcal H}R_n(h)$. These existence assumptions matter: an infimum need not be attained for an arbitrary class.

The Exact Empirical Minimizer Bound

Theorem: Under the assumptions above, if $h^*$ is a population-risk minimizer and $\hat h$ is an empirical risk minimizer, then almost surely $$ R(\hat h)-R(h^*)\leq 2\Delta_n. $$

This is a deterministic comparison on each sample for which the quantities are defined. It does not require $\hat h$ to be independent of the observations; indeed, $\hat h$ is usually selected using them.

Replace the selected candidate’s population risk.
The definition of $\Delta_n$ gives $R(\hat h)\leq R_n(\hat h)+\Delta_n$.

Use empirical minimization.
Since $\hat h$ minimizes empirical risk, $R_n(\hat h)\leq R_n(h^*)$.

Return to population risk.
The deviation bound gives $R_n(h^*)\leq R(h^*)+\Delta_n$. Combining the three inequalities proves the claim.

In full, for each sample,

R(\hat h) \leq R_n(\hat h)+\Delta_n \leq R_n(h^*)+\Delta_n \leq R(h^*)+2\Delta_n.

Subtracting $R(h^*)$ gives the theorem. Because $h^*$ minimizes population risk, the left-hand side is nonnegative. $\square$

Worked Example: Two Constant Classifiers

Let $Y\in\{0,1\}$ with $P(Y=1)=0.6$, and consider predicting either 0 or 1 using zero-one loss. The loss for predicting 0 is $\ell_0(Y)=\mathbf{1}\{Y=1\}$; for predicting 1 it is $\ell_1(Y)=\mathbf{1}\{Y=0\}$. Suppose $n=10$ and the observed sample contains seven ones and three zeros.

The population risks are $R(0)=0.6$ and $R(1)=0.4$, so $h^*=1$. The empirical risks are $R_n(0)=7/10=0.7$ and $R_n(1)=3/10=0.3$, so $\hat h=1$ as well. The uniform deviation over these two candidates is

\Delta_n=\max\{|0.7-0.6|,\ |0.3-0.4|\}=0.1.

The excess risk is $R(\hat h)-R(h^*)=0.4-0.4=0$, and the theorem bounds it by $2\Delta_n=0.2$. In this sample the bound is valid but not tight: the empirical and population minimizers happen to be the same.

Approximate Empirical Minimization

An algorithm may not find an exact empirical minimizer. It may instead return a candidate whose empirical risk is within a tolerance $\varepsilon\geq0$ of the smallest empirical risk. The same comparison applies, with the optimization error added to the bound.

Theorem: If $R_n(\hat h)\leq\inf_{h\in\mathcal H}R_n(h)+\varepsilon$, where $\varepsilon\geq0$, then $$ R(\hat h)-R(h^*)\leq 2\Delta_n+\varepsilon. $$

Indeed, $R_n(\hat h)\leq R_n(h^*)+\varepsilon$, since an infimum is no larger than the empirical risk of $h^*$. Therefore,

R(\hat h) \leq R_n(\hat h)+\Delta_n \leq R_n(h^*)+\varepsilon+\Delta_n \leq R(h^*)+2\Delta_n+\varepsilon.

Subtracting $R(h^*)$ proves the result. Exact minimization is the special case $\varepsilon=0$. $\square$

Worked Example: An Approximate Minimizer on a Finite Support

Let $Z$ take values $A$ and $B$, with $P(A)=0.75$ and $P(B)=0.25$. Three candidates have the following losses:

Candidate	Loss at A	Loss at B	Population risk
$h_1$	0	1	0.25
$h_2$	0.1	0.5	0.20
$h_3$	0.15	0.2	0.1625

For instance, $R(h_2)=0.75(0.1)+0.25(0.5)=0.075+0.125=0.20$. Similarly, $R(h_1)=0.25$ and $R(h_3)=0.75(0.15)+0.25(0.2)=0.1125+0.05=0.1625$, making $h^*=h_3$. Now take $n=4$ and suppose all four observations are $A$. The empirical risks are $0$, $0.1$, and $0.15$, respectively, so $\Delta_n=\max\{0.25,0.10,0.0125\}=0.25$.

Candidate $h_2$ is an approximate empirical minimizer with $\varepsilon=0.1$: its empirical risk $0.1$ is exactly $0.1$ above the minimum $R_n(h_1)=0$. Its excess risk is $R(h_2)-R(h_3)=0.20-0.1625=0.0375$, while the theorem gives $2(0.25)+0.1=0.6$. The bound is loose for this sample, but it accounts for both sources of error: deviation between empirical and population risk, and imperfect empirical optimization.

Probability Guarantees and Sharpness

The deterministic inequality transfers any available control of $\Delta_n$ into control of excess risk. In particular, for every $t\geq0$,

P\{R(\hat h)-R(h^*)>2t\}\leq P\{\Delta_n>t\}.

To verify this, the pointwise theorem implies that $R(\hat h)-R(h^*)>2t$ can hold only if $2\Delta_n>2t$, or equivalently $\Delta_n>t$. The first event is therefore a subset of the second, and taking probabilities gives the inequality. Likewise, if $E[\Delta_n]<\infty$, taking expectations of the pointwise bound yields $E[R(\hat h)-R(h^*)]\leq2E[\Delta_n]$.

Worked Example: Why the Factor of Two Can Be Necessary

Let $Z$ take values $A$ and $B$ with probability $1/2$ each. Consider two candidates with losses $\ell_{h^*}(A)=0.5$, $\ell_{h^*}(B)=0.1$, $\ell_{h_{\mathrm{bad}}}(A)=0.5$, and $\ell_{h_{\mathrm{bad}}}(B)=0.9$. Their population risks are

R(h^*)=\tfrac12(0.5)+\tfrac12(0.1)=0.3,\qquad R(h_{\mathrm{bad}})=\tfrac12(0.5)+\tfrac12(0.9)=0.7.

Take a sample of size one and suppose the observation is $A$. Both candidates then have empirical risk $0.5$, so either one is an empirical minimizer. If the tie is resolved in favor of $h_{\mathrm{bad}}$, its excess risk is $0.7-0.3=0.4$. The uniform deviation is

\Delta_1=\max\{|0.5-0.3|,\ |0.5-0.7|\}=0.2.

Thus the excess risk equals $2\Delta_1=0.4$. The factor of two cannot in general be reduced in this comparison: one deviation raises the selected candidate’s population risk above its empirical risk, while another lowers the benchmark’s empirical risk below its population risk.

Why the Bound Matters—and a Common Pitfall

Uniform deviation is useful because it is a single quantity that controls every candidate at once, including candidates selected adaptively from the data. Earlier results on symmetrization and uniform convergence can provide bounds on this quantity; the oracle inequality then converts such a bound into a statement about the performance of empirical risk minimization. The argument itself does not require a particular method for bounding $\Delta_n$.

Common mistake: It is tempting to write $R(\hat h)-R(h^*)\leq\Delta_n$, reasoning that the empirical minimizer is “within $\Delta_n$” of the population minimizer. But the two candidates each have a risk that may differ from its empirical value by as much as $\Delta_n$. The correct comparison is $R(\hat h)\leq R_n(\hat h)+\Delta_n$, followed by empirical minimization, and then $R_n(h^*)\leq R(h^*)+\Delta_n$. Both deviations are needed, which gives $2\Delta_n$, not $\Delta_n$.

A small uniform deviation is therefore a sufficient guarantee of small excess risk, not a claim that every empirical minimizer is exactly optimal or that the bound is tight on a particular sample. If minimization is approximate, the optimization tolerance must also be included.

Check Your Understanding

Use the definitions and inequalities above to answer the following questions.

Why does a deviation bound for a single fixed candidate not, by itself, control the risk of a candidate selected using the sample?
State the exact empirical minimizer bound and identify the two comparisons that produce its factor of two.
If $\Delta_n=0.04$ and an algorithm returns a candidate within $0.03$ of the minimum empirical risk, what upper bound does the approximate-minimizer result give for its excess risk?
Why is existence of a population-risk minimizer a separate assumption from existence of an empirical risk minimizer?
In the two-candidate example with a tie, why can choosing the worse population-risk candidate still satisfy the empirical minimization condition?