As the very first example, we consider the binary classification problem, where the data points have features ${𝒙}_i$ from a domain set $𝒳$ and (deterministic) labels $y_i$ in $\{0,1\}$. We assume that:

• The i.i.d. assumption: The examples in the training set $\{{𝒙}_1,\mathrm{\dots },{𝒙}_m\}$ are independently and identically distributed (i.i.d.) according to an underlying distribution $𝒟$ over the domain set $𝒳$.

• Finiteness of the hypothesis class: The learning algorithm choses the predictor $h$ from a finite hypothesis set $\mathscr{H}$, i.e. .

• The realizable assumption: There exists $h^{*}\in \mathscr{H}$ such that the true loss $L_{(𝒟,f)}(h^{*})$ is zero, where $f$ is the true labeling function (i.e. $y_i=f({𝒙}_i)$). This implies that if we randomly sample a data set $S\sim 𝒟$, the empirical loss $L_S(h^{*})$ is always 0.

Say our training set is $S=\{({𝒙}_1,y_1),\mathrm{\dots },({𝒙}_m,y_m)\}$ (which is drawn from ${𝒟}^m$), and our learning algorithm is $A$. The output of the algorithm is the predictor $h=A(S)$, we measure the performance of $h$ over the training set $S$ using the empirical loss:

$$L_S(h)=\frac{|\{i\in [m]:h({𝒙}_i)\ne y_i\}|}{m}=\frac{1}{m}\sum _{i=1}^m{\mathrm{𝟏}}_{[h({𝒙}_i)\ne y_i]}.$$

Once we obtained the predictor $h$, we care about its general performance in the environment (over the underlying distribution $𝒟$). The generalization loss (or the true error, the risk) is measured by the probability that it predicts wrongly for a random sample:

$$L_{(𝒟,f)}(h)=\underset{𝒙\sim 𝒟}{\mathrm{Pr}}[h(𝒙)\ne f(𝒙)]=𝒟(\{𝒙:h(𝒙)\ne f(𝒙)\}),$$

where $𝒟(S)$ is defined as the probability that we sample a point $𝒙$ in $𝒳$ w.r.t. $𝒟$ and the point $𝒙$ lies in $S$.

Empirical Risk Minimization (ERM)

The objective of a learning algorithm (or a learner) is to minimize the true error w.r.t. $𝒟$ and $f$. However, $𝒟$ and $f$ are unkown. The only thing that we can observe is the training set $S\sim {𝒟}^m$. Thus a natural algorithm is to minimize the empirical loss:

$$h=\underset{h\in \mathscr{H}}{argmin}{L}_S(h).$$

The algorithm is known as the Empirical Risk Minimization (ERM) algorithm, which we denote as ${\mathrm{𝖤𝖱𝖬}}_{\mathscr{H}}$. Though the concept is simple, ERM has a deadly weakness: it may overfit the training set. When the training set $S$ cannot reveal the underlying structure of $𝒟$, the true loss of the ERM predictor will be large. Imagine that if the labels of the samples in $S$ are all one, the ERM predictor may predict everything as positive (though it is a very unlikely situation).

A common solution to this problem is to restrict the search space of ERM (shrink the size/space of the candidate set $\mathscr{H}$). To get some intuition, in the most extreme case, say if the hypothesis class $\mathscr{H}$ is the set of all function from $𝒳$ to $\{0,1\}$, ERM can learn a predictor $h$ with zero emprical loss where $h$ fits perfectly to the training set ($h({𝒙}_i)=y_i,\forall i\in [m]$). However, the true loss can be arbitrarily bad, if $|S|/|𝒳|$ is close to zero. Philosophically, if someone can explain every phenomenon, his explanations are worthless.

Though restricting the space of $\mathscr{H}$ seems helpful in hadling the overfitting problem, it also introduced biases. Therefore, ideally we want the choice of $\mathscr{H}$ to be based on some prior knowledge of the problem. As another extreme case, if $\mathscr{H}$ contains only one predictor (say a threshold function), it will surely not overfit $S$, but the true loss is also unlikely to be small. For now, we simply assume that the realizable assumption holds, which means there exists a $h^{*}\in \mathscr{H}$ such that $L_{(𝒟,f)}(h^{*})=0$. Such an $\mathscr{H}$ has perfect prior knowledge on $𝒟$ and $f$, thus is unrealistic. We will see how to remove this assumption later, but for simplicity let’s keep it for now.

Finite Hypothesis Class

In this section we show that if the i.i.d. assumption and the realizable assumption hold, with sufficient large number of samples, the true loss of the predictor ${\mathrm{𝖤𝖱𝖬}}_{\mathscr{H}}(S)$ learned from a finite $\mathscr{H}$ is small:

$$L_{(𝒟,f)}({\mathrm{𝖤𝖱𝖬}}_{\mathscr{H}}(S))\le \epsilon \mathit{\hspace{1em}}\text{with probability at least }(1-\delta ).$$

Intuitively this is true because the training set can reveal more structure of the underlying distribution with more samples. Suppose the training set $S$ contains $m$ samples drawn i.i.d. from $𝒟$ and let $h_S={\mathrm{𝖤𝖱𝖬}}_{\mathscr{H}}(S)$, we want to upperbound the probabilty

$$\underset{S\sim {𝒟}^m}{\mathrm{Pr}}[L_{(𝒟,f)}(h_S)>\epsilon ].$$

Let ${\mathscr{H}}_B\subset \mathscr{H}$ be the set of all “bad” predictors whoes true loss is greater than $\epsilon$, i.e. for each $h_B\in {\mathscr{H}}_B$ we have $L_{(𝒟,f)}(h_B)>\epsilon$. For each $h_B$, we see that

$$\underset{𝒙\sim 𝒟}{\mathrm{Pr}}[h_B(𝒙)=f(𝒙)]=1-L_{(𝒟,f)}(h_B)\le 1-\epsilon .$$

The probability that we learn the specific bad predictor $h_B$ is the probability that its empirical loss on $S$ is zero:

$$\underset{S\sim {𝒟}^m}{\mathrm{Pr}}[L_S(h_B)=0]\le {(1-\epsilon )}^m\le e^{-\epsilon m}.$$

By the union bound, the probability that we learn any bad predictor $h_B\in {\mathscr{H}}_B$ is:

$$\underset{S\sim {𝒟}^m}{\mathrm{Pr}}[\exists h_B\in {\mathscr{H}}_B:L_S(h_B)=0]\le \sum _{h_B\in {\mathscr{H}}_B}\underset{S\sim {𝒟}^m}{\mathrm{Pr}}[L_S(h_B)=0]\le |{\mathscr{H}}_B|e^{-\epsilon m}\le |\mathscr{H}|e^{-\epsilon m},$$

which is equivalent to:

$$\underset{S\sim {𝒟}^m}{\mathrm{Pr}}[L_{(𝒟,f)}(h_S)>\epsilon ]\le |\mathscr{H}|e^{-\epsilon m}.$$

We conclude that:

Corollary 1.

Let $\mathscr{H}$ be a finite hypothesis class. Let $\delta \mathrm{\in }\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ and $\epsilon \mathrm{>}\mathrm{0}$, and let $m$ be an integer satisfies

$$m\ge \frac{\log (|\mathscr{H}|/\delta )}{\epsilon }.$$

Then, for any distribution $𝒟$ and for any labeling function $f$, if the realizable assumption holds, with probability at least $\mathrm{(}\mathrm{1}\mathrm{-}\delta \mathrm{)}$, we have

$$L_{(𝒟,f)}({\mathrm{𝖤𝖱𝖬}}_{\mathscr{H}}(S))\le \epsilon .$$