Empirical Risk Minimization

Why the training error of a learned classifier understates its error on new data, and what the best possible error is. Risk and empirical risk defined; the training error of a rule fixed in advance proved unbiased with variance L(1 − L)/m; the training error of the empirical risk minimizer proved optimistic on average, and a rule that memorizes its sample proved to have zero training error and the error of a guess; the Bayes classifier proved optimal, with the excess risk of any classifier as an expected margin; the excess risk split into approximation, estimation and optimization error, with the estimation error bounded by twice the largest deviation over the class; and surrogate losses whose minimizers have the Bayes classifier's sign. Worked on threshold rules for diagnosed diabetes from HbA1c among 5,210 NHANES adults, with 30 seeds of 1,000 training samples at each of seven sizes. Worked problems on two competing rules, the variance of a training error, the memorizer on the whole population and the surrogate minimizers at one HbA1c value.

Among the 5,210 adults of the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 who had a glycohemoglobin (HbA1c) test and answered the question about diabetes (pregnant women excluded), 806 said a doctor or health professional had told them they have diabetes (National Center for Health Statistics, 2020). Draw a training sample of 100 of these adults at random, and choose the rule "diagnosed if HbA1c is at least $\theta$" whose $\theta$ makes the fewest mistakes on the sample. On the first such training sample drawn by this article's script, the chosen threshold is 7.5%, and it misclassifies 6 of the 100 adults, an error rate of 0.06. On all 5,210 adults the same rule errs at the rate 0.1061, worse than the training sample promised by three quarters, and worse than the threshold 6.7% that is best for the whole population. How far can the error on the data used to choose a rule be trusted, and what decides how good the chosen rule can be?

The risk of a rule is its error rate on the population the data come from, and its empirical risk is its error rate on the training sample. Empirical risk minimization (ERM) chooses, from a fixed class of rules, the one with the smallest empirical risk. This article is the first of the unit Statistical Learning Theory, and the later articles build on its definitions and its decomposition of the error.

First we set up risk and empirical risk and prove that, for a rule fixed before the data are seen, the training error is an unbiased estimate of the risk with a variance we can compute. Then we prove that for the rule chosen by ERM the training error is biased downward, measure the bias on the NHANES thresholds, and show what happens when the class of rules is not restricted at all. Next we find the best possible rule, the Bayes classifier, and split the excess error of a learned rule into the part due to the class and the part due to the sample. Finally we treat the surrogate losses that practical methods minimize in place of the error rate. The article assumes Conditional Expectation and the Laws of Total Expectation and Variance and Expectation, Variance and Covariance.

Risk and empirical risk

A classifier (or hypothesis) is a function $h : \mathcal{X} \to \mathcal{Y}$ from an instance space $\mathcal{X}$ to a label space $\mathcal{Y}$. Here $\mathcal{X}$ holds HbA1c values in percent and $\mathcal{Y} = \{0, 1\}$, with 1 for diagnosed diabetes. An example is a pair $z = (x, y)$, and the examples come from a distribution $\mathcal{D}$ on $\mathcal{X} \times \mathcal{Y}$ that the learner does not know. The loss $\ell(h, z) \ge 0$ measures how badly $h$ does on $z$. For classification it is the 0-1 loss

$$\ell_{0\text{-}1}(h, (x, y)) = \mathbf{1}\{h(x) \ne y\},$$

which is 1 for a mistake and 0 otherwise.

The risk of $h$ (also called its true risk or generalization error) is its expected loss on a new example,

$$L_{\mathcal{D}}(h) = E_{z \sim \mathcal{D}}[\ell(h, z)],$$

which for the 0-1 loss is the probability $P(h(X) \ne Y)$ of a mistake. A training sample is $S = ((x_1, y_1), \ldots, (x_m, y_m))$, $m$ examples drawn independently from $\mathcal{D}$, written $S \sim \mathcal{D}^m$. The letter $m$ for the training sample size follows Shalev-Shwartz and Ben-David (2014), the unit's main text; the unit keeps $n$ for a held-out test set. The empirical risk (training error) of $h$ is its average loss on the sample,

$$L_S(h) = \frac{1}{m}\sum_{i=1}^m \ell(h, z_i).$$

The difference $L_{\mathcal{D}}(h) - L_S(h)$ is the generalization gap of $h$ on $S$. A positive gap means that the sample flatters the rule.

The running example. We take the 5,210 adults themselves as the population. The distribution $\mathcal{D}$ is a draw of one adult at random, so that every risk is an exact fraction of 5,210, and a training sample of size $m$ is $m$ draws with replacement, which makes the examples exactly independent with distribution $\mathcal{D}$. HbA1c is reported to one decimal and runs from 3.8% to 16.2% over 94 distinct values. The class of rules is the threshold classifiers

$$h_\theta(x) = \mathbf{1}\{x \ge \theta\},$$

one for each threshold $\theta$. Since HbA1c takes values on a grid of tenths, a threshold acts on the data like the smallest grid value at or above it, so the class has one distinct rule per grid value, plus the rule that never predicts diabetes. NHANES is a complex survey, and its sampling weights are not used: the risks describe these examined adults, not the U.S. population, as on the course pages.

Three risks on the population set the scale. The rule that never predicts diabetes errs on every diagnosed adult, at the rate $806/5{,}210 = 0.1547$. The threshold 6.5%, the American Diabetes Association's diagnostic cutoff (American Diabetes Association Professional Practice Committee, 2025, Table 2.1) that Sensitivity and Specificity studies as a screening test, makes 442 mistakes, a risk of 0.0848. The best threshold for this population is 6.7%, with 437 mistakes and risk 0.0839; the thresholds 6.6% and 6.8% make 449 and 450. The risk is a population quantity. A learner sees only a sample, and the rest of the article asks what the sample's error says about it.

The training error of a rule fixed in advance

Before any choosing, consider one rule $h$ fixed without looking at the sample, such as "HbA1c at least 6.5%". Its training error is an average of independent losses, and that makes it an honest estimate.

Theorem 1 (the empirical risk of a fixed rule). Let $h$ be fixed, let the loss $\ell(h, z)$ have finite variance $v(h)$ under $\mathcal{D}$, and let $S \sim \mathcal{D}^m$. Then

$$E_S[L_S(h)] = L_{\mathcal{D}}(h), \qquad \operatorname{Var}_S(L_S(h)) = \frac{v(h)}{m}.$$

For the 0-1 loss, $v(h) = L_{\mathcal{D}}(h)\,(1 - L_{\mathcal{D}}(h))$ and $m L_S(h)$ is binomial with $m$ trials and success probability $L_{\mathcal{D}}(h)$.

Proof. The losses $\ell(h, z_1), \ldots, \ell(h, z_m)$ are functions of independent examples with the same distribution, and $h$ does not depend on them, so they are independent and identically distributed with mean $L_{\mathcal{D}}(h)$ and variance $v(h)$. The mean of their average is $L_{\mathcal{D}}(h)$ by linearity, and its variance is $m\,v(h)/m^2 = v(h)/m$, because variances of independent variables add (Expectation, Variance and Covariance). For the 0-1 loss each loss is a Bernoulli variable with success probability $L_{\mathcal{D}}(h)$, whose variance is $L_{\mathcal{D}}(h)(1 - L_{\mathcal{D}}(h))$, and a sum of $m$ independent such variables is binomial (The Binomial Distribution). $\square$

So for a fixed rule the generalization gap has mean zero and standard deviation $\sqrt{v(h)/m}$, and by the weak law of large numbers (The Laws of Large Numbers) the training error converges in probability to the risk. The best threshold $h^*$, with risk 0.0839, has training error with standard deviation 0.0277 on samples of 100 (Problem 3 below). Theorem 1 gives a mean and a variance; Concentration Inequalities: Hoeffding and Bernstein turns them into a probability bound that holds at every sample size, which is what a guarantee needs.

Empirical risk minimization

The learner does not know which rule is good, so it chooses by the sample. Given a hypothesis class $\mathcal{H}$, empirical risk minimization outputs a rule with the smallest training error,

$$h_S \in \operatorname*{argmin}_{h \in \mathcal{H}} L_S(h),$$

with some fixed rule for ties. The thresholds make the computation simple. Sort the distinct HbA1c values; the threshold at a value $t$ misclassifies the diagnosed adults below $t$ and the undiagnosed adults at or above $t$, and moving $t$ to the next value changes both counts only by the adults at one value. One pass over cumulative counts gives the training error of every threshold, and the script breaks ties toward the smallest threshold. The best rule in the class for the population is written $h^* \in \operatorname{argmin}_{h \in \mathcal{H}} L_{\mathcal{D}}(h)$, assuming the minimum is attained, as it is for every finite class and for the thresholds; here $h^* = h_{6.7}$. For a class where it is not attained, the results below hold with $h^*$ replaced by any $h \in \mathcal{H}$ with $L_{\mathcal{D}}(h) \le \inf_{\mathcal{H}} L_{\mathcal{D}} + \gamma$ and $\gamma$ added to the right-hand side; the bounds by the supremum do not involve $h$, so letting $\gamma \to 0$ gives them for the infimum.

Left: the share of adults with diagnosed diabetes at each HbA1c value from 5.0% to 9.0% (dot area proportional to the number of adults at that value), with the line at one half. Notice that the share crosses one half at 6.5%, falls back below it at 6.6%, and stays above it from 6.7%. Right: the error rate of every threshold rule on the whole population (solid) and on the opening training sample of 100 adults (steps). The population curve is lowest at 6.7%; the sample's curve is lowest at 7.5%, where the population error is 0.1061.
Left: the share of adults with diagnosed diabetes at each HbA1c value from 5.0% to 9.0% (dot area proportional to the number of adults at that value), with the line at one half. Notice that the share crosses one half at 6.5%, falls back below it at 6.6%, and stays above it from 6.7%. Right: the error rate of every threshold rule on the whole population (solid) and on the opening training sample of 100 adults (steps). The population curve is lowest at 6.7%; the sample's curve is lowest at 7.5%, where the population error is 0.1061.

The right panel shows what happened in the opening sample. The training error curve is a noisy copy of the risk curve, and its minimum sits where the noise happened to dip. The sample held only 8 diagnosed adults among its 100 draws, so a few adults decide where the curve is lowest. Minimizing a noisy curve picks out the noise, which is the subject of the next theorem.

The chosen rule's training error is optimistic

Theorem 1 does not apply to $h_S$, because $h_S$ was chosen by looking at the same sample. The choice selects a rule whose losses on this sample happened to be few.

Here is the idea in one sentence: the minimum of the training errors is at most the training error of the best rule, which is unbiased, so the minimum is biased downward. The formal statement assumes that $h_S$ is a random variable, so that its risk has an expected value; that holds for every finite class and for the thresholds, where only finitely many rules are distinct on the data.

Theorem 2 (ERM is optimistic). Let $\mathcal{H}$ be a class with a bounded loss and let $h_S$ be an empirical risk minimizer. Then

$$E_S[L_S(h_S)] \;\le\; \inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h) \;\le\; E_S[L_{\mathcal{D}}(h_S)],$$

so that $E_S[L_{\mathcal{D}}(h_S) - L_S(h_S)] \ge 0$: on average the training error of the chosen rule understates its risk.

Proof. Fix any $h \in \mathcal{H}$. For every sample, $h_S$ has the smallest training error, so $L_S(h_S) \le L_S(h)$. Taking expectations and applying Theorem 1 to the fixed rule $h$ gives $E_S[L_S(h_S)] \le L_{\mathcal{D}}(h)$. This holds for every $h$ in $\mathcal{H}$, so it holds for the infimum, which is the first inequality. For the second, $h_S$ belongs to $\mathcal{H}$, so $L_{\mathcal{D}}(h_S) \ge \inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ for every sample, and taking expectations keeps the inequality. Subtracting the outer terms gives the last statement. $\square$

For a finite class this is the winner's curse of Selective Inference and the Garden of Forking Paths (its Theorem 1) applied to the negative training errors, which are unbiased estimates of the negative risks. The theorem says nothing about how large the bias is. It needs no assumption on the class beyond the one just stated, and the two inequalities show that the bias has two sources: the minimum training error falls below the best risk in the class, and the chosen rule's risk rises above it.

The same direction holds for regression. Optimism and Effective Degrees of Freedom proves for squared error at fixed inputs that the optimism of any fitting rule equals twice the average covariance between fitted values and responses. That result gives an exact size where Theorem 2 gives only a sign; Theorem 2 needs no squared loss, no fixed inputs and no structure in the class.

How large is the bias on the thresholds? The script draws training samples of sizes $m$ from 20 to 2,000. For each size and each of 30 seeds it draws 1,000 training samples, runs ERM on each, and averages over the 1,000. The table gives the median over the 30 seeds of these averages. For the training error, the risk and the estimation error, the interquartile range over the seeds lies within 0.0008 of the median; for the gap it is given in parentheses.

$m$ Training error $L_S(h_S)$ Risk $L_{\mathcal{D}}(h_S)$ Gap (interquartile range) Estimation error Gap of $h^*$ Share of samples with a positive gap
20 0.0513 0.1129 0.0616 (0.0605 to 0.0626) 0.0290 −0.0006 0.857
50 0.0636 0.0963 0.0327 (0.0320 to 0.0336) 0.0124 −0.0001 0.849
100 0.0706 0.0910 0.0203 (0.0198 to 0.0210) 0.0071 0.0001 0.797
200 0.0757 0.0882 0.0125 (0.0120 to 0.0128) 0.0043 −0.0001 0.760
500 0.0795 0.0863 0.0068 (0.0064 to 0.0070) 0.0024 0.0001 0.712
1,000 0.0815 0.0855 0.0040 (0.0038 to 0.0042) 0.0016 −0.0001 0.675
2,000 0.0825 0.0849 0.0024 (0.0023 to 0.0026) 0.0010 0.0000 0.655

The estimation error column is $L_{\mathcal{D}}(h_S) - L_{\mathcal{D}}(h^*)$, the excess of the chosen rule's risk over the best threshold's 0.0839.

Three observations of this experiment. First, both inequalities of Theorem 2 show: the average training error lies below 0.0839 at every size, and the average risk above it. Second, the gap of the fixed rule $h^*$ is zero within simulation noise at every size, as Theorem 1 requires, while the gap of the chosen rule is positive and shrinks as the sample grows, from 0.0616 at 20 to 0.0024 at 2,000. Third, the gap is an average, not a rule for each sample: in about a seventh of the samples of 20 and a third of those of 2,000 the chosen rule did at least as well on the population as on its sample. The individual training samples spread widely. Over the first sample of each of the 30 seeds at $m = 100$, the training error had median 0.0700 with interquartile range 0.0500 to 0.0900, and the chosen threshold ranged from 6.2% to 7.5%.

Training error and risk of the threshold chosen by ERM against the training sample size (logarithmic scale), each the median over 30 seeds of the average over 1,000 samples. Notice that the training error rises toward the best threshold's risk 0.0839 from below while the risk falls toward it from above, and that neither reaches the Bayes risk 0.0820, the lowest line.
Training error and risk of the threshold chosen by ERM against the training sample size (logarithmic scale), each the median over 30 seeds of the average over 1,000 samples. Notice that the training error rises toward the best threshold's risk 0.0839 from below while the risk falls toward it from above, and that neither reaches the Bayes risk 0.0820, the lowest line.

The gap shrinks because the thresholds form a small class: one rule per HbA1c value, all ordered along one axis. What happens without any restriction is the next question.

Without a restricted class: the memorizer

Suppose the class holds every function from $\mathcal{X}$ to $\{0, 1\}$. Then a rule that simply looks up its training sample has training error zero, and ERM may choose it. Shalev-Shwartz and Ben-David (2014, §2.2.1, eq. 2.3) use this rule to show that ERM without a restricted class can fail completely.

Theorem 3 (the memorizer). Define the memorizer of a sample $S$ by $h_S(x) = y_i$ if $x = x_i$ for some $i$ (the first such $i$), and $h_S(x) = 0$ otherwise.

  1. If no two examples of $S$ have the same instance with different labels, then $L_S(h_S) = 0$.
  2. Suppose that $X$ has a density, so that $P(X = x) = 0$ for every $x$. Then with probability 1 the instances of $S$ are distinct, $L_S(h_S) = 0$, and $L_{\mathcal{D}}(h_S) = P(Y = 1)$ for every sample. If the memorizer instead flips a fair coin, independent of everything else, at each instance not in $S$, then $L_{\mathcal{D}}(h_S) = 1/2$.

Proof. (1) Each training example $(x_i, y_i)$ is predicted as the label of the first example with instance $x_i$, which by assumption is $y_i$, so there are no training mistakes.

(2) For $i \ne j$, condition on $X_i$: given $X_i = x$, the independent instance $X_j$ equals $x$ with probability 0, so $P(X_i = X_j) = 0$ by the law of total probability, and a union over the finitely many pairs shows that the instances are distinct with probability 1. Part (1) then gives zero training error. Now fix the sample, and let $A = \{x_1, \ldots, x_m\}$. A new instance falls in $A$ with probability at most $\sum_i P(X = x_i) = 0$. Off $A$ the memorizer predicts 0, which is a mistake exactly when $Y = 1$, so $L_{\mathcal{D}}(h_S) = P(Y = 1, X \notin A) = P(Y = 1)$. With the coin, a new example with $X \notin A$ is misclassified with probability 1/2 whatever its label, because the coin is independent of the label, so the risk is 1/2. $\square$

The memorizer fits its sample perfectly and has learned nothing: off the sample it predicts as well as a rule that never looked. Theorem 2's gap here is the whole risk. The fault is not in ERM, which did what it was asked, but in a class so rich that every labeling of the sample has a rule with zero training error. Restricting the class is the remedy, and how much restriction is enough is the subject of PAC Learning and Finite Hypothesis Classes and The VC Dimension. The first of these also proves the no-free-lunch theorem of learning (Shalev-Shwartz and Ben-David, 2014, Theorem 5.1): for every learner and every sample size below half the size of the instance space, there is a distribution on which some rule is perfect but the learner's rule has risk at least 1/8 with probability at least 1/7. Some restriction, chosen before the data, is unavoidable. It is a different result from the No Free Lunch Theorems of search and optimization.

Example (memorizing respondent numbers). NHANES gives each participant a respondent number. A memorizer with the respondent number as its only input fits any training sample perfectly, since one adult has one label. On the population, though, the respondent numbers are atoms: a new draw repeats a training adult with positive probability, so part 2 of Theorem 3 does not apply. With the population of $N = 5{,}210$ adults and $P = 806$ diagnosed, an adult is missing from a sample of $m$ independent draws with probability $(1 - 1/N)^m$. The memorizer is wrong exactly on the diagnosed adults it has not seen, so

$$E_S[L_{\mathcal{D}}(h_S)] = \frac{1}{N}\sum_{j=1}^{N} y_j\,P(\text{adult } j \notin S) = \frac{P}{N}\Big(1 - \frac{1}{N}\Big)^m.$$

For $m = 100$ the probability of being unseen is 0.9810 and the expected risk 0.1518, nearly that of never predicting diabetes. For $m = 1{,}000$ the risk is 0.1277. With the coin in place of the default 0, the risks are 0.4905 and 0.4127. Over 30 seeds of one sample each, the simulated risk with the default 0 had median 0.1516 at $m = 100$ and 0.1276 at $m = 1{,}000$. At $m = 5{,}210$ the memorizer's expected risk falls to 0.0569, below the best threshold's 0.0839 (Problem 4). That is no paradox. A memorizer predicts well exactly when new cases repeat old ones, which a finite population drawn with replacement guarantees and a population with a density rules out.

The best possible classifier

Restriction costs something too: no threshold can do better than 0.0839 on this population. What is the best error any rule can reach?

Write $\eta(x) = P(Y = 1 \mid X = x)$, the regression function: the probability of the label 1 among examples with instance $x$. The Bayes classifier predicts the more probable label,

$$f_{\mathcal{D}}(x) = \mathbf{1}\{\eta(x) \ge 1/2\},$$

(some texts, including Introduction to Supervised Learning, predict 1 only when $\eta(x) > 1/2$; at $\eta(x) = 1/2$ either label is optimal, as shown below), and its risk is the Bayes risk $L^*_{\mathcal{D}}$. The name and the notation $f_{\mathcal{D}}$ are those of Shalev-Shwartz and Ben-David (2014, §3.2.1), who state its optimality and leave the proof as an exercise. Introduction to Supervised Learning gives the argument for any number of classes in words; here it is in full, together with the size of the loss of any other rule, which the later sections need.

Theorem 4 (the Bayes classifier is optimal). Let $Y \in \{0, 1\}$, and let $X$ be discrete or have a density. For every classifier $f$,

$$L_{\mathcal{D}}(f) - L_{\mathcal{D}}(f_{\mathcal{D}}) = E\big[\,\lvert 2\eta(X) - 1\rvert\;\mathbf{1}\{f(X) \ne f_{\mathcal{D}}(X)\}\big] \;\ge\; 0,$$

and the Bayes risk is $L^*_{\mathcal{D}} = E[\min(\eta(X), 1 - \eta(X))]$.

Here is the idea: at each instance a rule makes one choice, and the Bayes choice has the smaller conditional probability of error there; averaging over instances keeps the comparison.

Proof. By the law of total expectation (Conditional Expectation), $L_{\mathcal{D}}(f) = P(f(X) \ne Y) = E[P(f(X) \ne Y \mid X)]$. Given $X = x$ the prediction $f(x)$ is a fixed label, so the conditional probability of a mistake is

$$P(f(X) \ne Y \mid X = x) = \eta(x)\,\mathbf{1}\{f(x) = 0\} + (1 - \eta(x))\,\mathbf{1}\{f(x) = 1\}.$$

Compare $f$ with $f_{\mathcal{D}}$ at a single $x$. Where they agree, the two conditional error probabilities are equal. Where $f_{\mathcal{D}}(x) = 1$ and $f(x) = 0$, we have $\eta(x) \ge 1/2$, and the difference is $\eta(x) - (1 - \eta(x)) = 2\eta(x) - 1 = \lvert 2\eta(x) - 1\rvert$. Where $f_{\mathcal{D}}(x) = 0$ and $f(x) = 1$, we have $\eta(x) < 1/2$, and the difference is $(1 - \eta(x)) - \eta(x) = \lvert 2\eta(x) - 1\rvert$. So the difference of the conditional error probabilities is $\lvert 2\eta(x) - 1\rvert\,\mathbf{1}\{f(x) \ne f_{\mathcal{D}}(x)\} \ge 0$ at every $x$, and taking the expectation over $X$ gives the identity and its sign. The conditional error probability of $f_{\mathcal{D}}$ at $x$ is $\min(\eta(x), 1 - \eta(x))$, by the same display, and its expectation is the Bayes risk. $\square$

The identity says more than optimality. A rule loses nothing by disagreeing with the Bayes classifier where $\eta$ is near 1/2, and loses most where the label is nearly certain. Where $\eta(x) = 1/2$ both predictions are optimal, so the Bayes classifier is not unique there.

Corollary (plug-in rules). If $\hat\eta$ is any estimate of $\eta$ and $\hat f(x) = \mathbf{1}\{\hat\eta(x) \ge 1/2\}$, then $L_{\mathcal{D}}(\hat f) - L^*_{\mathcal{D}} \le 2\,E\lvert\hat\eta(X) - \eta(X)\rvert$.

Proof. Where $\hat f(x) = 1$ and $f_{\mathcal{D}}(x) = 0$, $\hat\eta(x) \ge 1/2 > \eta(x)$, so $\lvert 2\eta(x) - 1\rvert = 2(1/2 - \eta(x)) \le 2(\hat\eta(x) - \eta(x))$. Where $\hat f(x) = 0$ and $f_{\mathcal{D}}(x) = 1$, $\hat\eta(x) < 1/2 \le \eta(x)$, so $\lvert 2\eta(x) - 1\rvert = 2(\eta(x) - 1/2) \le 2(\eta(x) - \hat\eta(x))$. In both cases the integrand of Theorem 4 is at most $2\lvert\hat\eta(x) - \eta(x)\rvert$, and elsewhere it is 0. $\square$

A good probability estimate therefore gives a good classifier, which is why probability models such as logistic regression are used for classification, and why Calibration and Proper Scoring Rules matters to classification as well as to forecasting.

The Bayes classifier on NHANES. On the population, $\eta$ at each HbA1c value is the share diagnosed among the adults with that value. The share is 30 of 53 (0.566) at 6.5%, 26 of 64 (0.406) at 6.6% and 32 of 51 (0.627) at 6.7%. It is at least one half from 6.7% on (exactly one half at 11.1, 11.3, 11.4, 11.6, 11.7 and 13.3%, where either prediction is optimal), except at the values 13.1, 13.2 and 14.3, each held by one undiagnosed adult. So the Bayes classifier is not a threshold rule: it says yes at 6.5%, no at 6.6%, and yes from 6.7% on with those three exceptions. Summing $\min(\eta, 1 - \eta)$ over the adults, it makes 427 mistakes, a Bayes risk of 0.0820, against 437 for the best threshold. The irregularity is real for this finite population and would not be for a population with a smooth regression function; a rule that copied it would be fitting the labels of ten particular adults.

Approximation, estimation and optimization error

The distance between a learned rule and the Bayes classifier now splits into two pieces with different causes. For the ERM rule $h_S$,

$$L_{\mathcal{D}}(h_S) - L^*_{\mathcal{D}} \;=\; \underbrace{\min_{h \in \mathcal{H}} L_{\mathcal{D}}(h) - L^*_{\mathcal{D}}}_{\varepsilon_{\mathrm{app}}} \;+\; \underbrace{L_{\mathcal{D}}(h_S) - \min_{h \in \mathcal{H}} L_{\mathcal{D}}(h)}_{\varepsilon_{\mathrm{est}}}.$$

The approximation error $\varepsilon_{\mathrm{app}}$ is the price of the class: how much the best rule in $\mathcal{H}$ loses to the best rule of all. It does not depend on the sample. The estimation error $\varepsilon_{\mathrm{est}}$ is the price of the sample: how much the chosen rule loses to the best one in its class. Both are nonnegative, the first by Theorem 4 and the second because $h_S \in \mathcal{H}$. Shalev-Shwartz and Ben-David (2014, §5.2) define the approximation error as $\min_{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ itself, which includes the Bayes risk, and note in a footnote that the literature also uses the excess over the Bayes risk, as here.

When $h_S$ is computed only approximately, as it is for any class fitted by an iterative method, the rule actually returned, $\hat h$, adds a third term. Bottou and Bousquet (2007, §2.2, eq. 2) call $\varepsilon_{\mathrm{opt}} = L_{\mathcal{D}}(\hat h) - L_{\mathcal{D}}(h_S)$ the optimization error and write the expected excess risk as the sum of the three expected errors. Their point is that when computing time, rather than the number of examples, is the binding limit, a rougher optimization can give a better rule, because the time saved lets more examples be processed. For the thresholds the minimization is exact, and $\varepsilon_{\mathrm{opt}} = 0$.

On the thresholds the approximation error is $(437 - 427)/5{,}210 = 0.0019$: ten adults. The estimation error, the fifth column of the table above, falls from 0.0290 at $m = 20$ to 0.0010 at $m = 2{,}000$. Only from about $m = 1{,}000$ on is the estimation error smaller than the approximation error. A richer class, such as rules with two cut points, contains the thresholds and so can only lower the approximation error, but it gives more rules the chance to fit the noise of a sample and typically raises the estimation error; this bias-complexity tradeoff (Shalev-Shwartz and Ben-David, 2014, §5.2) is the classification counterpart of The Bias-Variance Tradeoff, which splits the squared error of one fitted function rather than the excess risk of a class.

The estimation error is the part a sample-size argument can control, and one inequality connects it to the training error.

Proposition 1 (estimation error and uniform deviation). For every sample,

$$\varepsilon_{\mathrm{est}} \;\le\; \big[L_{\mathcal{D}}(h_S) - L_S(h_S)\big] + \big[L_S(h^*) - L_{\mathcal{D}}(h^*)\big] \;\le\; 2\sup_{h \in \mathcal{H}}\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert.$$

If $\hat h$ satisfies $L_S(\hat h) \le L_S(h_S) + \rho$, then $L_{\mathcal{D}}(\hat h) - L_{\mathcal{D}}(h^*) \le 2\sup_{h \in \mathcal{H}}\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert + \rho$.

Proof. Write $L_{\mathcal{D}}(h_S) - L_{\mathcal{D}}(h^*) = [L_{\mathcal{D}}(h_S) - L_S(h_S)] + [L_S(h_S) - L_S(h^*)] + [L_S(h^*) - L_{\mathcal{D}}(h^*)]$. The middle bracket is at most 0 because $h_S$ minimizes $L_S$, which gives the first inequality, and each remaining bracket is at most the supremum, which gives the second. For $\hat h$ the middle bracket becomes $L_S(\hat h) - L_S(h^*) \le L_S(h_S) + \rho - L_S(h^*) \le \rho$. $\square$

The first bound involves the gap of the chosen rule, which Theorem 2 showed to be biased, and the gap of the fixed rule $h^*$, which Theorem 1 showed to be unbiased. The second bound replaces the chosen rule by the worst case over the class, which no longer depends on how the rule was chosen. A guarantee for ERM is therefore a bound on $\sup_{h \in \mathcal{H}}\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert$: uniform convergence. Shalev-Shwartz and Ben-David (2014, Lemma 4.2) state the same reduction in terms of "$\varepsilon$-representative" samples. For one fixed rule the deviation is controlled by Hoeffding's inequality; for a finite class a union bound over its rules gives PAC Learning and Finite Hypothesis Classes; for the thresholds, an infinite class with finitely many behaviors on any sample, The VC Dimension counts the behaviors; and Rademacher Complexity measures the supremum directly.

Surrogate losses

The 0-1 loss is discontinuous and not convex. For halfspaces, the linear rules in several inputs, Shalev-Shwartz and Ben-David (2014, §12.3) note that empirical risk minimization with the 0-1 loss is NP-hard when no rule fits the sample perfectly. Practical methods choose a real-valued score $g : \mathcal{X} \to \mathbb{R}$, classify by its sign, and minimize a convex surrogate loss in place of the error rate. With the labels written as signs $\tilde y = 2y - 1 \in \{-1, +1\}$, the surrogate charges $\phi(\tilde y\,g(x))$, a function of the margin $\tilde y\,g(x)$, which is positive for a correct sign. Four common choices:

Surrogate $\phi(u)$ Used by
Hinge $\max(0, 1 - u)$ support vector machines
Logistic $\ln(1 + e^{-u})$ logistic regression
Exponential $e^{-u}$ AdaBoost
Squared $(1 - u)^2$ least squares on $\pm 1$ labels

Each is at least $\mathbf{1}\{u \le 0\}$ for the hinge, exponential and squared losses, and at least $\ln 2 \cdot \mathbf{1}\{u \le 0\}$ for the logistic loss, so a small surrogate risk forces a small error rate. The question is whether minimizing the surrogate leads to the right signs. Since the surrogate risk is an average over instances, it is enough to look at one instance. At an instance with $\eta(x) = \eta$, a score $\alpha$ has conditional surrogate risk

$$C_\eta(\alpha) = \eta\,\phi(\alpha) + (1 - \eta)\,\phi(-\alpha).$$

Proposition 2 (the surrogates' minimizers have the Bayes sign). Let $0 < \eta < 1$. The conditional risk $C_\eta$ is minimized by

  • $\alpha^* = \ln\frac{\eta}{1 - \eta}$ for the logistic loss;
  • $\alpha^* = \frac12\ln\frac{\eta}{1 - \eta}$ for the exponential loss;
  • $\alpha^* = 2\eta - 1$ for the squared loss;
  • $\alpha^* = 1$ if $\eta > 1/2$ and $\alpha^* = -1$ if $\eta < 1/2$ for the hinge loss, with minimum value $2\min(\eta, 1 - \eta)$, and by every $\alpha \in [-1, 1]$ if $\eta = 1/2$.

For $\eta > 1/2$ every minimizer is positive, and for $\eta < 1/2$ every minimizer is negative, so the sign of the minimizer is the Bayes classifier's prediction wherever $\eta \ne 1/2$. At $\eta = 1/2$ both labels are optimal (Theorem 4), and the minimizers carry no information about the sign.

Proof. Logistic: $C_\eta(\alpha) = \eta\ln(1 + e^{-\alpha}) + (1 - \eta)\ln(1 + e^{\alpha})$, and differentiating, $C_\eta'(\alpha) = -\eta\frac{e^{-\alpha}}{1 + e^{-\alpha}} + (1 - \eta)\frac{e^{\alpha}}{1 + e^{\alpha}} = \frac{(1 - \eta)e^{\alpha} - \eta}{1 + e^{\alpha}}$, using $\frac{e^{-\alpha}}{1 + e^{-\alpha}} = \frac{1}{1 + e^{\alpha}}$. The numerator is increasing in $\alpha$ and vanishes at $e^{\alpha} = \eta/(1 - \eta)$, so $C_\eta$ decreases before that point and increases after it. Exponential: $C_\eta'(\alpha) = -\eta e^{-\alpha} + (1 - \eta)e^{\alpha}$, increasing in $\alpha$, zero where $e^{2\alpha} = \eta/(1 - \eta)$. Squared: $C_\eta'(\alpha) = -2\eta(1 - \alpha) + 2(1 - \eta)(1 + \alpha) = 2(\alpha - (2\eta - 1))$, zero at $2\eta - 1$ and increasing. Hinge: for $\alpha \ge 1$, $C_\eta(\alpha) = (1 - \eta)(1 + \alpha)$, strictly increasing since $\eta < 1$; for $\alpha \le -1$, $C_\eta(\alpha) = \eta(1 - \alpha)$, strictly decreasing since $\eta > 0$; between them $C_\eta(\alpha) = \eta(1 - \alpha) + (1 - \eta)(1 + \alpha) = 1 + \alpha(1 - 2\eta)$, linear. The minimum is therefore at an end of $[-1, 1]$: at $\alpha = 1$, with value $2(1 - \eta)$, when $\eta > 1/2$; at $\alpha = -1$, with value $2\eta$, when $\eta < 1/2$; and the function is constant on $[-1, 1]$ when $\eta = 1/2$. For the first three losses the minimizer is unique, and $\ln(\eta/(1 - \eta))$ and $2\eta - 1$ are positive when $\eta > 1/2$ and negative when $\eta < 1/2$; for the hinge loss the unique minimizer is 1 or $-1$ in those two cases. $\square$

A surrogate with this property for every $\eta \ne 1/2$, in the strict form that the smallest conditional risk over scores of the wrong sign or zero exceeds the smallest over all scores, is called classification-calibrated. Bartlett, Jordan and McAuliffe (2006) prove that a convex $\phi$ is classification-calibrated if and only if it is differentiable at 0 with $\phi'(0) < 0$. They also prove a quantitative version: there is a function $\psi$, computed from $\phi$, with $\psi(L_{\mathcal{D}}(g) - L^*_{\mathcal{D}}) \le L_\phi(g) - L^*_\phi$ for every score $g$, where $L_\phi$ is the surrogate risk and $L^*_\phi$ its minimum over all scores; for the hinge loss $\psi(\theta) = \lvert\theta\rvert$, and for the exponential loss $\psi(\theta) = 1 - \sqrt{1 - \theta^2}$. So driving the surrogate risk to its minimum over all functions drives the error rate to the Bayes risk. Proposition 2 is the pointwise core of these results. The four losses in the table are convex with derivatives $-1$, $-1/2$, $-1$ and $-2$ at 0, so all four are calibrated by that criterion.

Example (the surrogate in a restricted class). Calibration is a statement about minimizing over all scores. Restricted to a class, the surrogate's best member need not be the class's best classifier. Logistic regression of diagnosis on HbA1c alone fits the score $g(x) = \beta_0 + \beta_1 x$ by minimizing the logistic loss, the negative log-likelihood, over the 5,210 adults. The fitted score changes sign at $x = 6.963$, so the rule is the threshold at 7.0% on the HbA1c grid. It makes 483 mistakes, a risk of 0.0927, against 0.0839 for the best threshold, which ERM with the 0-1 loss approaches as the sample grows. One reason is that the logistic model is misspecified for this $\eta$, which is not even monotone near 6.5% to 6.7%. Its fit is dominated by the 73.5% of adults with values below 6.0%, well short of the boundary, while the error rate depends only on where the boundary falls. A correctly specified model would estimate $\eta$ itself, and by the corollary of Theorem 4 (excess risk at most $2E\lvert\hat\eta - \eta\rvert$) its plug-in rule would approach the Bayes rule. The price of the surrogate is an added error, measured with respect to the 0-1 loss. Shalev-Shwartz and Ben-David (2014, §12.3) bound the 0-1 risk of a rule learned with the hinge loss by three terms, one of which is the difference between the smallest hinge risk and the smallest 0-1 risk in the class; they call that term the optimization error, a different use of the name from Bottou and Bousquet's above.

What is proved here, what is cited, what the experiment shows

Proved here, in full: the unbiasedness and variance of the training error of a fixed rule (Theorem 1); the optimism of empirical risk minimization in both of its forms (Theorem 2); the memorizer's zero training error and its risk of a guess when the instances have a density, and its exact expected risk on a finite population (Theorem 3 and the example after it); the optimality of the Bayes classifier with the excess risk of any rule as an expected margin, and the plug-in bound (Theorem 4 and its corollary); the decomposition into approximation and estimation error and the bound of the estimation error by the uniform deviation, with an approximate minimizer (Proposition 1); the minimizers of the conditional hinge, logistic, exponential and squared risks (Proposition 2). The proofs treat discrete variables and variables with densities, as in Conditional Expectation, and assume that the chosen rule is a random variable, which holds for finite classes and for the thresholds; the general case needs measurability conditions that Shalev-Shwartz and Ben-David (2014) also set aside.

Taken from other pages: linearity of expectation and the variance of a sum of independent variables (Expectation, Variance and Covariance); the law of total expectation (Conditional Expectation); the binomial distribution (The Binomial Distribution); the weak law of large numbers (The Laws of Large Numbers).

Cited: the characterization of classification-calibrated convex losses and the $\psi$-transform bound (Bartlett, Jordan and McAuliffe, 2006); the optimization error and the three-term decomposition (Bottou and Bousquet, 2007); the definitions, the memorizer example and the approximation-estimation terminology (Shalev-Shwartz and Ben-David, 2014).

What the experiment shows: on threshold rules for diagnosed diabetes among 5,210 NHANES adults, with 1,000 training samples for each of 30 seeds at seven sizes, the training error of the ERM threshold understated its risk on average by 0.0616 at 20 examples and 0.0024 at 2,000, while the best fixed threshold showed no gap; the estimation error fell from 0.0290 to 0.0010, against an approximation error of 0.0019. These are observations of this population and this class, not general rates; the rates that hold in general are the subject of the next articles.

Worked problems

These problems were written for this article; none comes from a textbook. They are posed on the NHANES population of the article and on small exact cases, and the script tools/experiments/statistics/empirical-risk-minimization.py computes every number in them and asserts it.

Problem 1 (Bayes classifier and best threshold on four values). Restrict attention to the adults with HbA1c from 6.4% to 6.7%: 31 of 68 diagnosed at 6.4%, 30 of 53 at 6.5%, 26 of 64 at 6.6% and 32 of 51 at 6.7%. (a) Which predictions does the Bayes classifier make on these four values, and how many mistakes does it make there? (b) Which threshold rule makes the fewest mistakes on these 236 adults, and how many?

Solution. (a) By Theorem 4, the Bayes classifier predicts 1 where the share diagnosed is at least one half: $\eta = 31/68 = 0.456$ at 6.4%, $30/53 = 0.566$ at 6.5%, $26/64 = 0.406$ at 6.6% and $32/51 = 0.627$ at 6.7%. It predicts 0, 1, 0, 1, and its mistakes are the smaller count at each value: $31 + 23 + 26 + 19 = 99$.

(b) A threshold rule predicts 0 below its threshold and 1 at and above it, so on four ordered values it can only produce the patterns 0000, 0001, 0011, 0111 and 1111. Their mistakes are the diagnosed adults predicted 0 plus the undiagnosed adults predicted 1:

  • 0000: $31 + 30 + 26 + 32 = 119$;
  • 0001 (threshold 6.7%): $31 + 30 + 26 + 19 = 106$;
  • 0011 (threshold 6.6%): $31 + 30 + 38 + 19 = 118$;
  • 0111 (threshold 6.5%): $31 + 23 + 38 + 19 = 111$;
  • 1111: $37 + 23 + 38 + 19 = 117$.

The threshold 6.7% is best, with 106 mistakes, 7 more than the Bayes classifier: no threshold can say yes at 6.5% and no at 6.6%. These seven adults, with the three at 13.1%, 13.2% and 14.3%, are the ten of the approximation error.

Problem 2 (two rules, two examples). A class holds two fixed rules with risks 0.3 and 0.4 whose losses on a random example are independent. ERM sees $m = 2$ examples and picks the rule with fewer training mistakes, breaking ties toward the first. Find the probability that ERM picks the better rule, the expected training error of the chosen rule and its expected risk.

Solution. The training mistakes $K_1$ and $K_2$ of the two rules are independent binomial counts with 2 trials and probabilities 0.3 and 0.4 (Theorem 1). Their distributions are $(0.49, 0.42, 0.09)$ and $(0.36, 0.48, 0.16)$ on 0, 1, 2. ERM picks the second rule only when $K_1 > K_2$:

$$P(K_1 > K_2) = 0.42 \times 0.36 + 0.09 \times 0.36 + 0.09 \times 0.48 = 0.2268,$$

so it picks the better rule with probability 0.7732. The training error of the chosen rule is $\min(K_1, K_2)/2$, and for counts, $E[\min(K_1, K_2)] = P(\min \ge 1) + P(\min \ge 2) = 0.51 \times 0.64 + 0.09 \times 0.16 = 0.3408$, so $E[L_S(h_S)] = 0.1704$. The expected risk is $0.3 \times 0.7732 + 0.4 \times 0.2268 = 0.3227$. Both inequalities of Theorem 2 hold, $0.1704 \le 0.3 \le 0.3227$, and the expected gap is 0.1523: the training error of the chosen rule understates its risk by half.

Problem 3 (the spread of a fixed rule's training error). What is the standard deviation of the training error of the best threshold $h_{6.7}$ on samples of 100, and how does it compare with the simulation?

Solution. By Theorem 1 the variance is $L(1 - L)/m$ with $L = 437/5{,}210$, which is 0.000768 for $m = 100$, a standard deviation of 0.0277. Over the 1,000 samples of each of 30 seeds at $m = 100$, the median of the per-seed variances of $L_S(h_{6.7})$ was 0.000776. The standard deviation is a third of the risk itself: on 100 examples a single training error locates a risk near 0.08 only to within a few hundredths, which is the scale of the gaps in the table.

Problem 4 (the memorizer on the whole population). Find the expected risk of the respondent-number memorizer trained on $m = 5{,}210$ draws, and the share of adults it has never seen.

Solution. The share of adults never drawn is $(1 - 1/5{,}210)^{5{,}210} = 0.3678$, close to $e^{-1} = 0.3679$, since $(1 - 1/N)^N$ tends to $e^{-1}$. By the formula of the example, the expected risk is $(806/5{,}210) \times 0.3678 = 0.0569$. It is below the best threshold's 0.0839 because 63% of the population is in the training sample and is classified perfectly. The comparison does not carry over to new people: for a population whose instances have a density, Theorem 3 puts the memorizer's risk at $P(Y = 1) = 0.1547$ here, whatever the sample size.

Problem 5 (surrogate minimizers at one value). At HbA1c 6.5%, $\eta = 30/53$. Find the minimizing score for the logistic, exponential and squared losses and the minimal conditional hinge risk, and check that all agree with the Bayes prediction.

Solution. By Proposition 2, the logistic minimizer is $\ln(30/23) = 0.2657$, the exponential minimizer half of it, 0.1329, and the squared-loss minimizer $2 \times 30/53 - 1 = 7/53 = 0.1321$. The hinge minimizer is $\alpha = 1$, since $\eta > 1/2$, with conditional risk $2 \times 23/53 = 0.868$. All are positive, so each surrogate predicts diabetes at 6.5%, as the Bayes classifier does. The scores are small because $\eta$ is close to one half: by Theorem 4, a wrong prediction here costs only $\lvert 2\eta - 1\rvert = 7/53$ per adult.

Summary

Quantity Definition Property proved
Risk $L_{\mathcal{D}}(h) = E[\ell(h, z)]$ the target
Empirical risk $L_S(h) = \frac1m\sum \ell(h, z_i)$ unbiased, variance $v(h)/m$, for $h$ fixed (Theorem 1)
ERM rule $h_S \in \operatorname{argmin}_{\mathcal{H}} L_S$ $E[L_S(h_S)] \le \inf_{\mathcal{H}} L_{\mathcal{D}} \le E[L_{\mathcal{D}}(h_S)]$ (Theorem 2)
Memorizer look up the sample, else 0 $L_S = 0$, $L_{\mathcal{D}} = P(Y = 1)$ without atoms (Theorem 3)
Bayes classifier $f_{\mathcal{D}}(x) = \mathbf{1}\{\eta(x) \ge 1/2\}$ excess risk $E[\lvert 2\eta - 1\rvert\mathbf{1}\{f \ne f_{\mathcal{D}}\}] \ge 0$ (Theorem 4)
Approximation error $\min_{\mathcal{H}} L_{\mathcal{D}} - L^*_{\mathcal{D}}$ 0.0019 for the NHANES thresholds
Estimation error $L_{\mathcal{D}}(h_S) - \min_{\mathcal{H}} L_{\mathcal{D}}$ at most $2\sup_{\mathcal{H}}\lvert L_{\mathcal{D}} - L_S\rvert$ (Proposition 1)
Surrogate loss $\phi(\tilde y\,g(x))$ minimizers have the Bayes sign (Proposition 2)

What we have learned

A rule chosen by its training error is judged by a biased witness. For a rule fixed in advance the training error is unbiased, with the binomial variance; for the rule that minimizes it, the training error is biased downward and the risk upward, and on the NHANES thresholds the gap ran from 0.0616 with 20 examples to 0.0024 with 2,000. Without a restricted class the gap can be total: the memorizer has no training error and the risk of a guess. The best any rule can do is the Bayes classifier's risk, 0.0820 on this population. The thresholds come within 0.0019 of it, and the rest of a learned threshold's excess is estimation error, which is at most twice the largest gap between training error and risk over the class. Surrogate losses replace the error rate by a convex function whose minimizers have the Bayes classifier's sign.

What remains is to control the gap with a probability statement that holds at a given sample size, not only on average. For one fixed rule that is a statement about a mean of bounded independent variables, and Concentration Inequalities: Hoeffding and Bernstein proves the bounds that make it, before PAC Learning and Finite Hypothesis Classes extends them to every rule of a class at once.

Every number in this article is computed by tools/experiments/statistics/empirical-risk-minimization.py in the site's repository, which downloads the NHANES files from the CDC and checks their checksums (loader tools/experiments/statistics/sltdata.py). The figures are drawn by tools/figures/empirical-risk-minimization.py from the script's results.

References