The Basic Inequality for Empirical Risk Minimization

Why the Basic Inequality Matters

An empirical risk minimizer is chosen to perform well on the observed sample. The quantity of interest, however, is usually its risk on new observations from the underlying population. The basic inequality makes the connection precise: it expresses the population risk difference from a comparator as an empirical risk difference plus a term measuring the discrepancy between empirical and population risks.

The inequality is useful before any particular method for controlling that discrepancy is chosen. It does not require a finite predictor class, bounded losses, or a population risk minimizer. Its essential optimization condition is that the selected predictor exactly minimizes empirical risk over the class.

Risk and Empirical Risk

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$. A predictor $f$ in a class $\mathcal{F}$ incurs loss $\ell_f(Z)$ on an observation $Z$. Assume each loss under consideration is measurable and integrable, so its population risk is finite. Define $P h=E[h(Z)]$ for an integrable function $h$, and define the empirical average $P_n h=n^{-1}\sum_{i=1}^n h(Z_i)$.

Definition: The population risk and empirical risk of $f$ are, respectively, $$ R(f)=P\ell_f=E[\ell_f(Z)] \qquad\text{and}\qquad R_n(f)=P_n\ell_f=\frac{1}{n}\sum_{i=1}^n \ell_f(Z_i). $$ An exact empirical risk minimizer is a sample-dependent choice $\hat f\in\mathcal{F}$ satisfying $R_n(\hat f)\le R_n(f)$ for every $f\in\mathcal{F}$ on that sample.

The choice $\hat f$ can depend on all the observed data. A comparator $f$ below is fixed rather than chosen after seeing the sample. It need not minimize population risk; the inequality compares $\hat f$ with any fixed member of $\mathcal{F}$. For probability statements about a supremum over $\mathcal{F}$, assume the relevant supremum is measurable. The algebraic inequalities themselves hold sample by sample whenever the quantities are defined.

The Basic Inequality

For a fixed comparator $f\in\mathcal{F}$, add and subtract the empirical risks. This gives an identity, not merely an inequality:

R(\hat f)-R(f) = \bigl(R_n(\hat f)-R_n(f)\bigr) + (P-P_n)(\ell_{\hat f}-\ell_f).

The first term on the right is the empirical excess risk relative to $f$. It is nonpositive because $\hat f$ minimizes empirical risk. The second term is the empirical-to-population discrepancy for the difference in losses. This yields the basic inequality.

Theorem (Basic inequality for ERM): Suppose $\hat f\in\mathcal{F}$ is an exact empirical risk minimizer and $f\in\mathcal{F}$ is fixed. Then, for every sample on which the risks are defined, $$ R(\hat f)-R(f) \le R_n(\hat f)-R_n(f) + \sup_{g,h\in\mathcal{F}} \left|(P-P_n)(\ell_g-\ell_h)\right| \le \sup_{g,h\in\mathcal{F}} \left|(P-P_n)(\ell_g-\ell_h)\right|. $$

Proof. Write the population risk difference as the sum of the empirical risk difference and the difference between the population and empirical averages:

\begin{aligned} R(\hat f)-R(f) &= R_n(\hat f)-R_n(f) +\bigl(P-P_n\bigr)(\ell_{\hat f}-\ell_f). \end{aligned}

By the definition of the supremum, the final term is at most $\sup_{g,h\in\mathcal{F}} |(P-P_n)(\ell_g-\ell_h)|$, since $\hat f,f\in\mathcal{F}$. By empirical risk minimization, $R_n(\hat f)-R_n(f)\le 0$. Substituting these two facts proves both inequalities. $\square$

Worked Example: An ERM With Higher Population Risk

Let an observation $Z$ take values $A$ and $B$, each with probability $1/2$. The class contains two predictors, $a$ and $b$, with losses $\ell_a(A)=0,\ \ell_a(B)=4,\ \ell_b(A)=1,\ \ell_b(B)=1$. Suppose the sample is $Z_1=Z_2=A$, and compare the ERM with $b$.

The population risks are $R(a)=(0+4)/2=2$ and $R(b)=(1+1)/2=1$. On this sample, the empirical risks are $R_n(a)=0$ and $R_n(b)=1$, so $a$ is the ERM. Its population risk exceeds $b$'s by $2-1=1$, even though its empirical risk is lower by $0-1=-1$.

For the loss difference $\ell_a-\ell_b$, the value at $A$ is $-1$ and the value at $B$ is $3$. Its population average is $({-1}+3)/2=1$, while its sample average is $-1$. Thus $(P-P_n)(\ell_a-\ell_b)=1-(-1)=2$, and the identity gives $1=-1+2$. The sample has probability $1/4$, so this is a possible realization, not a contradiction: empirical minimization alone does not guarantee that the selected predictor has the lower population risk.

A Bound Using Individual Risk Deviations

A common way to state the deviation term is through the largest absolute empirical-to-population risk error over the class. Define $\Delta_n=\sup_{g\in\mathcal{F}} |R_n(g)-R(g)|$. For any $g,h\in\mathcal{F}$, the triangle inequality gives $\left|(P-P_n)(\ell_g-\ell_h)\right|\le |R(g)-R_n(g)|+|R(h)-R_n(h)|\le 2\Delta_n$. Applying this to the basic inequality gives a familiar, slightly looser bound.

Corollary: Under the hypotheses of the basic inequality, for every fixed $f\in\mathcal{F}$, $$ R(\hat f)-R(f) \le R_n(\hat f)-R_n(f)+2\Delta_n \le 2\Delta_n. $$

Proof. The definitions imply \[ (P-P_n)(\ell_g-\ell_h) = \bigl(R(g)-R_n(g)\bigr)-\bigl(R(h)-R_n(h)\bigr). \] Taking absolute values and applying the triangle inequality bounds this expression by $2\Delta_n$, uniformly over $g,h\in\mathcal{F}$. Substitute that bound into the theorem. The second inequality follows because an exact ERM has $R_n(\hat f)-R_n(f)\le 0$. $\square$

The factor of two arises because the comparison involves two predictors, and each can have its own deviation. A direct bound on the pairwise difference can be sharper than twice the largest individual deviation. The sharper form is the theorem’s supremum over $g,h$, rather than the corollary’s $\Delta_n$.

Worked Example: Comparing With a Nonoptimal Predictor

Let $Z$ be equally likely to be $U$ or $V$, and let $\mathcal{F}=\{a,b,c\}$. Their losses at $(U,V)$ are $a:(0,2)$, $b:(1,1)$, and $c:(3,3)$. Take a one-observation sample $Z_1=U$. Predictor $a$ is the ERM, since its empirical risk is $0$, compared with $1$ for $b$ and $3$ for $c$.

Compare $a$ with the fixed predictor $c$, which is not a population minimizer. The risks are $R(a)=1$ and $R(c)=3$, so $R(a)-R(c)=-2$. The empirical risk difference is $R_n(a)-R_n(c)=0-3=-3$.

The loss difference $\ell_a-\ell_c$ is $-3$ at $U$ and $-1$ at $V$. Its population average is $(-3-1)/2=-2$, and its empirical average is $-3$. Therefore $(P-P_n)(\ell_a-\ell_c)=1$, and the identity reads $-2=-3+1$. The comparator need not be optimal: the inequality is a comparison with any fixed member of the class.

Comparing With the Best Population Risk

If a population risk minimizer exists in $\mathcal{F}$, it is valid to use it as the fixed comparator. The basic inequality then bounds the ERM’s excess population risk by the uniform pairwise discrepancy. A minimizer need not exist for a related conclusion: comparison with every fixed $f\in\mathcal{F}$ gives a bound relative to the infimum risk.

Consequence: If $\inf_{f\in\mathcal{F}}R(f)$ is finite and the pairwise supremum below is defined, then $$ R(\hat f)-\inf_{f\in\mathcal{F}}R(f) \le \sup_{g,h\in\mathcal{F}} \left|(P-P_n)(\ell_g-\ell_h)\right|. $$

Justification. The basic inequality and exact empirical minimization give $R(\hat f)-R(f)\le S$ for every fixed $f\in\mathcal{F}$, where $S=\sup_{g,h\in\mathcal{F}}|(P-P_n)(\ell_g-\ell_h)|$. By the definition of the infimum, for every $\varepsilon>0$ there is an $f_\varepsilon\in\mathcal{F}$ with $R(f_\varepsilon)<\inf_{f\in\mathcal{F}}R(f)+\varepsilon$. Consequently, $R(\hat f)-\inf_{f\in\mathcal{F}}R(f)<S+\varepsilon$. Since this holds for every $\varepsilon>0$, it follows that the difference is at most $S$. This argument does not assume that the infimum is attained. $\square$

Worked Example: Calculating the Uniform-Deviation Bound

Again let $Z$ be equally likely to be $A$ or $B$. Consider predictors $p$ and $q$ with losses $p:(0,2)$ and $q:(0.5,0.5)$ at $(A,B)$. Take the sample $(A,A,A,B)$, and select $p$ as the ERM in the event of a tie.

The population risks are $R(p)=(0+2)/2=1$ and $R(q)=(0.5+0.5)/2=0.5$. The empirical risks are $R_n(p)=(0+0+0+2)/4=0.5$ and $R_n(q)=0.5$, so this tie-breaking choice is an exact ERM. Relative to $q$, the population risk difference is $1-0.5=0.5$, and the empirical risk difference is $0.5-0.5=0$.

For $p$, the absolute deviation is $|0.5-1|=0.5$; for $q$, it is $|0.5-0.5|=0$. Thus $\Delta_n=0.5$, and the corollary gives $0.5\le 0+2(0.5)=1$. The sharper pairwise discrepancy is $0.5$: the difference $\ell_p-\ell_q$ takes values $-0.5$ at $A$ and $1.5$ at $B$, with population average $0.5$ and sample average $0$. The basic identity is therefore $0.5=0+0.5$.

Common Pitfall and Practical Interpretation

A tempting but incorrect argument is: “The ERM has lower empirical risk than every competitor, so it has lower population risk.” The premise concerns $R_n$, not $R$. The first worked example shows the gap: on the observed sample $a$ beats $b$, while in the population $a$ has higher risk. The correction is to keep the two scales separate and account for their difference with $(P-P_n)(\ell_{\hat f}-\ell_f)$.

Another mistake is to use $\Delta_n$ as a bound on the pairwise discrepancy without the factor of two. Each of the two predictors can deviate from its population risk in opposite directions. The triangle inequality gives $2\Delta_n$, not $\Delta_n$, unless additional structure justifies a sharper bound. In practice, the basic inequality identifies the quantity that must be controlled; it does not itself guarantee that this quantity is small.

Key takeaway: Exact empirical minimization controls the empirical risk difference, while a uniform deviation controls the gap between empirical and population comparisons. Together they give a population-risk bound against any fixed predictor in the class.

Check Your Understanding

Work through these questions using the definitions and inequalities above.

Why does the empirical risk difference $R_n(\hat f)-R_n(f)$ have a nonpositive sign when $f\in\mathcal{F}$?
In the basic identity, which term accounts for the difference between population and empirical comparisons?
Explain why a bound using $\Delta_n=\sup_{g\in\mathcal{F}}|R_n(g)-R(g)|$ generally has a factor of two.
Does the basic inequality require $f$ to minimize population risk? What condition on $f$ does it require?
How can the excess-risk bound be stated when the infimum population risk is not attained?