Empirical Risk Gaps and Overfitting in ERM

Why Training Risk Can Mislead

Empirical risk minimization chooses a model that performs well on the observed data. That is useful only if performance on those observations tells us something about performance on new data. When the same sample is used both to choose a model and to evaluate its training risk, the choice can exploit accidental features of the sample. A model can fit the observations well without having low population risk.

The central distinction is between a pointwise empirical-to-population comparison, for one specified model, and a uniform comparison that holds for every model in the class. The latter continues to hold for a model chosen after seeing the sample. We will use bounded losses to make the distinction precise.

Definition: Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$, and let $\mathcal H$ be a class of models. For $h\in\mathcal H$, suppose the loss $\ell_h(Z)$ is measurable and takes values in $[0,1]$. Its population risk and empirical risk are $$ R(h)=E[\ell_h(Z)], \qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell_h(Z_i). $$ The empirical-to-population deviation of $h$ is $\widehat R_n(h)-R(h)$. The uniform deviation over the class is $$ \Delta_n=\sup_{h\in\mathcal H}\left|\widehat R_n(h)-R(h)\right|. $$ We assume this supremum is measurable; for a finite class this holds automatically.

A small training risk means that $\widehat R_n(h)$ is small. A small absolute deviation means that $\widehat R_n(h)$ is close to $R(h)$. Neither statement by itself implies the other: a model may have small training risk but a large deviation, or a small deviation while both risks are large. The relevant question for generalization is whether the deviation is controlled for the model selected from the data.

A Fixed Model and a Data-Selected Model

For a model fixed independently of the observations, the empirical risk is an average of independent bounded random variables with mean $R(h)$. Concentration results can therefore control its deviation. But ERM selects $h$ by comparing empirical risks across the class. A model that happens to fit the particular sample unusually well can be selected, even if it performs poorly on new observations.

Worked Example: A Fixed Classifier’s Observed Gap

Suppose a classifier is fixed before data collection, and its error indicator on each observation is Bernoulli with success probability $0.20$. In a sample of $n=100$, suppose it makes 18 errors. Its empirical risk is $$ \widehat R_{100}(h)=\frac{18}{100}=0.18. $$

Its population risk is $R(h)=0.20$, so its empirical-to-population deviation is $0.18-0.20=-0.02$, with absolute value $0.02$. This calculation describes the gap for this fixed classifier on this sample. It does not establish that a classifier chosen by searching a large class will also have a small gap. The selection step is precisely where a uniform comparison becomes important.

Definition: An empirical risk minimizer (ERM) is a data-dependent choice $\hat h\in\mathcal H$ satisfying $\widehat R_n(\hat h)=\inf_{h\in\mathcal H}\widehat R_n(h)$, when the infimum is attained. Its training-to-population gap is $R(\hat h)-\widehat R_n(\hat h)$. Its excess risk relative to the best population risk in the class is $R(\hat h)-\inf_{h\in\mathcal H}R(h)$. These are different quantities.

The training-to-population gap compares the selected model’s two risks. Excess risk compares its population risk with the best population risk available in the class. A model can have zero training risk but a large gap; it can also have a population risk worse than the best-in-class risk. The next construction displays both effects and keeps track of the distinction.

Worked Example: Zero Training Risk and a Large Population Risk

Let $X$ be uniform on $\{1,\ldots,1000\}$, and let the response be $Y=1$ with probability one. Use zero-one classification loss and the class $\mathcal H=\{h_A:A\subseteq\{1,\ldots,1000\},\ |A|\leq20\}$, where $h_A(x)=1$ if $x\in A$ and $h_A(x)=0$ otherwise. Take a sample of $n=20$ observations. For a set $A$, the loss is one exactly when $X\notin A$, so $$ R(h_A)=P(X\notin A)=\frac{1000-|A|}{1000}. $$

Let $S$ be the set of distinct feature values appearing in the sample, and let $k=|S|$. Since $k\leq20$, $A=S$ is in the class and contains every observed feature value. Thus $h_S$ predicts 1 on every sample observation, giving $\widehat R_{20}(h_S)=0$. Zero is the smallest possible empirical risk, so this is an ERM.

For this particular ERM, $|S|=k$, and hence its population risk and its gap are $$ R(h_S)=\frac{1000-k}{1000}, \qquad R(h_S)-\widehat R_{20}(h_S)=\frac{1000-k}{1000}\geq\frac{980}{1000}=0.98. $$ The best population risk in the class is attained by every set of size 20 and equals $980/1000=0.98$. Therefore the ERM’s excess risk over the best-in-class risk is $$ R(h_S)-\inf_{h\in\mathcal H}R(h) =\frac{1000-k}{1000}-\frac{980}{1000} =\frac{20-k}{1000}. $$ In particular, the selected ERM attains the best population risk only if the sample contains 20 distinct feature values. If all 20 observations have the same feature value, then $k=1$, its population risk is $999/1000=0.999$, and its excess risk is $19/1000=0.019$. The class’s best risk remains $0.98$; it is not necessarily attained by this sample-fitted ERM.

This construction is possible because the ERM uses the data to define the set on which it predicts 1. For any fixed $A$, predicting 1 only on $A$ has a substantial population error unless $A$ is large. But the data-selected set contains every observed value, producing zero training error. In particular, the uniform deviation $\Delta_n$ for this sample is at least the deviation of $h_S$, which is at least $0.98$. There is no useful uniform control in this example.

Uniform Deviation Controls the ERM Risk

Uniform deviation is useful because it compares empirical and population risk for every model at once. On an event where $\Delta_n$ is small, the comparison applies to $\hat h$ even though $\hat h$ depends on the data. The next result translates that comparison into a bound on excess risk.

Theorem: Suppose $\mathcal H$ is nonempty, the risks are defined, and an ERM $\hat h$ exists. On any sample for which $\Delta_n\leq\varepsilon$, $$ R(\hat h)-\inf_{h\in\mathcal H}R(h)\leq 2\varepsilon. $$ More generally, if $\hat h$ is an approximate ERM satisfying $\widehat R_n(\hat h)\leq\inf_{h\in\mathcal H}\widehat R_n(h)+\eta$ for some $\eta\geq0$, then $$ R(\hat h)-\inf_{h\in\mathcal H}R(h)\leq 2\varepsilon+\eta. $$

Here is the complete argument. First compare the population risk of the selected model to its empirical risk. Next use the ERM property to compare that empirical risk to a population-risk competitor, with the uniform deviation applied on both sides.

Move from population to empirical risk for the selected model.
Since $\Delta_n\leq\varepsilon$, $R(\hat h)\leq\widehat R_n(\hat h)+\varepsilon$.

Use empirical minimization.
For an approximate ERM, $\widehat R_n(\hat h)\leq\widehat R_n(h)+\eta$ for every $h\in\mathcal H$.

Move back to population risk.
For every $h$, $\widehat R_n(h)\leq R(h)+\varepsilon$. Combining the inequalities gives $R(\hat h)\leq R(h)+2\varepsilon+\eta$ for every $h$.

Take the best comparator.
Taking the infimum over $h\in\mathcal H$ proves the asserted excess-risk bound.

Equivalently, for any $a>0$, one can first choose a comparator $h_a$ with $R(h_a)\leq\inf_{h\in\mathcal H}R(h)+a$, apply the preceding inequalities to $h_a$, and then let $a$ decrease to zero. This handles a class whose best population risk is an infimum that is not attained. For an exact ERM, set $\eta=0$. $\square$

The factor of two has a direct source: one deviation allowance compares $R(\hat h)$ with $\widehat R_n(\hat h)$, and a second compares the empirical risk of a competitor with its population risk. The theorem does not say that the selected model’s own gap is $2\varepsilon$; the uniform event gives the sharper pointwise statement $|R(\hat h)-\widehat R_n(\hat h)|\leq\varepsilon$. The two-sided excess-risk comparison needs to account for both ends.

Result: If $\Delta_n\leq\varepsilon$, then every $h\in\mathcal H$, including a data-dependent choice, satisfies $|R(h)-\widehat R_n(h)|\leq\varepsilon$. Consequently, an exact ERM also satisfies $R(\hat h)\leq\widehat R_n(\hat h)+\varepsilon$.

This statement follows directly from the definition of a supremum: each absolute deviation is no larger than its supremum. Its importance is not the algebra but the quantifier. A bound established for every $h$ on the same event remains valid after the data are used to select $\hat h$.

Worked Example: Turning Uniform Control into a Risk Bound

Suppose a sample has an ERM with empirical risk $0.14$, and a uniform analysis establishes $\Delta_n\leq0.06$ on an event of interest. The selected model’s population risk is at most $$ R(\hat h)\leq\widehat R_n(\hat h)+0.06=0.14+0.06=0.20. $$

If the best population risk in the class is $0.10$, the theorem also gives $$ R(\hat h)-0.10\leq2(0.06)=0.12, $$ so $R(\hat h)\leq0.22$. The direct gap calculation gives the sharper upper bound $0.20$ in this particular case. The excess-risk theorem remains useful when the ERM’s empirical risk is not separately supplied, or when the goal is to compare it with the class’s best risk.

When This Control Matters

Uniform deviation is a bridge between training performance and generalization. If, for example, a probabilistic argument establishes $P(\Delta_n\leq\varepsilon)\geq1-\alpha$, then the ERM excess-risk bound holds on that same event and therefore with probability at least $1-\alpha$. The probabilistic work is in establishing the uniform event; once it is available, the ERM comparison is deterministic.

A common mistake is to show that each fixed model has a small deviation with high probability and then conclude that the same statement holds for the model selected by ERM. A fixed-model probability statement has the model chosen before seeing the sample. ERM’s choice depends on the sample, and a separate fixed-model statement does not automatically apply to that random choice. A valid argument must control the deviations uniformly over the class, or otherwise account for the selection. Uniform bounds may be established using tools such as VC bounds; the key point here is the role such a bound plays, not a particular method for obtaining it.

Training risk: performance on the observed sample, possibly optimized using that sample.
Population risk: expected loss on a fresh observation from the data distribution.
Training-to-population gap: the difference between those two risks for a chosen model.
Excess risk: the chosen model’s population risk minus the best population risk in the class.
Uniform deviation: a simultaneous bound that controls the gap for all models and therefore also for the data-selected ERM.

A small empirical risk is evidence of good population performance only when the empirical-to-population discrepancy is controlled. The bounded-loss construction shows why the training fit alone cannot provide that assurance; the ERM inequality shows exactly how a uniform deviation bound supplies it.

Check Your Understanding

Use the definitions and inequalities above to answer the following.

In the 1000-point construction, what are the population risk and excess risk of the specified ERM when the sample has $k=12$ distinct feature values?
Why can a fixed-model deviation statement fail to justify a deviation claim for an ERM chosen from the same sample?
If $\Delta_n\leq0.04$ and an approximate ERM is within $0.01$ of the empirical infimum, what excess-risk bound follows?
Does a uniform deviation bound of $\varepsilon$ imply that the ERM’s training risk is at most $\varepsilon$? Explain.
State the difference between the training-to-population gap and excess risk, and identify which one is bounded by $\varepsilon$ directly under $\Delta_n\leq\varepsilon$.

Empirical Risk Gaps and Overfitting in ERM

What You'll Learn