The PAC learning framework

This blog is a summary of the first part of the course ECE543@UIUC. More materials can be found here.

Problem setup

In this blog, we will focus on the binary classification problem, where the input is $X\in {\mathbb{R}}^D$, and the label is $Y\in \{0,1\}$. A set of i.i.d. training samples $S=\{(X_1,Y_1),\dots ,(X_n,Y_n)\}$ are drawn from a joint distribution $P$ defined over ${\mathbb{R}}^D\times \{0,1\}$. Sometimes, we may also denote $Z=(X,Y)$ and $Z_i=(X_i,Y_i)$. A hypothesis is a mapping $h:{\mathbb{R}}^D\mapsto \{0,1\}$. Moreover, $\mathcal{H}$ denotes the hypotheses class, which consists of all the possible hypotheses that our model (e.g. a neural network) can represent. The learning algorithm is denoted by $\mathcal{A}$, which maps a dataset $S$ to a hypothesis $h_S\in \mathcal{H}$.

Given a hypothesis $h$, we define its true risk as $$L_P(h)={\mathbb{E}}_{(X,Y)\sim P}{\mathbb{I}}_{h(X)\ne Y},$$ and the empirical risk on $S$ as $$L_S(h)=\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(X_i)\ne Y_i}.$$

PAC-learnability

After applying the learning algorithm $\mathcal{A}$ to the dataset $S$, we get a hypothesis $h_S$ which depends on $S$ and minimizes the empirical risk $L_S(h)$. We care about the difference between the true risk of $h_S$ and that of $h^{\ast }$. Here, $h^{\ast }$ is the best hypothesis in the sense of minimizing the true risk, i.e. $h^{\ast }=\text{arg}\underset{h\in \mathcal{H}}{min}{L}_P(h)$. In other words, we want to get some guarantees on $L_P(h_S)-L_P(h^{\ast })$.

However, $L_P(h_S)-L_P(h^{\ast })$ is a random variable since $h_S$ depends on $S$ which is random. Therefore, it is not reasonable to look for a uniform upper bound on $L_P(h_S)-L_P(h^{\ast })$. In the PAC (Probably Approximately Correct) learning framework, instead of a uniform upper bound, we care about guarantees of the form $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le \delta .$$ Here, “Probably” is characterized by $\delta$, and “Approximately” is characterized by $ϵ$. Next, we give the definition of PAC-learnability of a hypothesis class.

Definition 1 (PAC-learnability): A hypothesis class $\mathcal{H}$ is PAC-learnable if there exists an algorithm $\mathcal{A}$ such that for all data distribution $P_{X,Y}$ and all $ϵ,\delta \in {\mathbb{R}}^{+}$, $\mathrm{\exists }n=n(ϵ,\delta )$ such that given any training set $S$ which contains at least $n$ samples, $h_S=\mathcal{A}(S)$ satisfies $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le \delta .$$

Theorem 1 (No free lunch): This theorem shows that we need some restrictions on the hypothesis class. We cannot learn an arbitrary set of hypotheses: there is no free lunch. Please see these lecture notes 1 and 2 for details.

A trick

Using a small trick, $L_P(h_S)–L_P(h^{\ast })$ can be bounded as follows. By doing this, $h_S$ and $h^{\ast }$ are eliminated.

$$\begin{array}{c}{L}_P(h_S)–L_P(h^{\ast })=[L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\hfill \\ +[L_S(h_S)–L_S(h^{\ast }){]}_{(\text{this term}\le 0)}\\ \le [L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\\ \hfill \le 2\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|=2\mathcal{V},\end{array}$$ where $\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|$ is denoted by $\mathcal{V}$.

Thus, $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le Pr(\mathcal{V}\ge \frac{ϵ}{2}).$$

Theorem 2: Finite hypothesis classes are PAC-learnable.

Proof: Since $|\mathcal{H}|<\mathrm{\infty }$, we can first bound $Pr(|L_S(h)-L_P(h)|\ge \frac{ϵ}{2})$ for each $h$ and then apply the union bound. For all $ϵ>0$ and all sets $S$ with $n$ samples, We have that $$\begin{array}{rl}& Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\\ \le & Pr(\underset{h\in \mathcal{H}}{max}|L_S(h)-L_P(h)|\ge \frac{ϵ}{2})\\ =& Pr\left({\cup }_{h\in \mathcal{H}}\{|L_S(h)-L_P(h)|\ge \frac{ϵ}{2}\}\right)\\ \le & \sum _{h\in \mathcal{H}}Pr(|L_S(h)–L_P(h)|\ge \frac{ϵ}{2})\\ =& \sum _{h\in \mathcal{H}}Pr(|\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(x_i)\ne y_i}–L_P(h)|\ge \frac{ϵ}{2})\\ \le & \sum _{h\in \mathcal{H}}\exp (-\frac{2n{ϵ}^2}{4})=|\mathcal{H}|\exp (-\frac{n{ϵ}^2}{2})=\delta ,\end{array}$$ where in the last step we use the Hoeffding’s inequality. Thus, $n(ϵ,\delta )=\frac{2}{{ϵ}^2}\log (\frac{|\mathcal{H}|}{\delta })$.

Theorem 1 is not very useful since almost all hypothesis classes we care about contain infinite hypotheses.

McDiarmid’s inequality

In order to derive PAC bounds for infinite hypothesis classes, we need some more sophisticated concentration inequalities.

Theorem 3 (McDiarmid’s inequality): Let $X_1,\dots ,X_n$ be i.i.d. random variables. Let $f$ be a function of $n$ variables. If $\mathrm{\forall }{x}_i,x_i^{\prime }$, $$|f(x_1,\dots ,x_i,\dots ,x_n)–f(x_1,\dots ,x_i^{\prime },\dots ,x_n)|\le c_i,$$ then $\mathrm{\forall }ϵ>0$, $$Pr(f(X_1,\dots ,X_n)-\mathbb{E}[f(X_1,\dots ,X_n)]\ge ϵ)\le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^n{c}_i}\right).$$ Such a function $f$ is said to have bounded differences.

Proof: TODO.

It can be shown that $\mathcal{V}$ has bounded differences, and thus McDiarmid’s inequality can be applied. Next, we have to derive an upper bound for $\mathbb{E}\left[\mathcal{V}\right]$.

Rademacher complexity

Definition 2 (Rademacher complexity of a set): Let $A\subseteq {\mathbb{R}}^n$, the Rademacher complexity $R(A)$ of set $A$ is defined as follows. $$R(A)={\mathbb{E}}_{\sigma }\left[\underset{a\in A}{sup}\left|\frac{1}{n}\sum _{i=1}^n{\sigma }_i{a}_i\right|\right],$$ where ${\sigma }_i$’s are i.i.d. random variables and $\mathrm{\forall }i$, $Pr({\sigma }_i=1)=Pr({\sigma }_i=-1)=0.5$.

Intuitively, Rademacher complexity characterizes the diversity of a set. If for every direction vector $\sigma =[{\sigma }_1,\cdots ,{\sigma }_n]$, we can always find an element $a\in A$ such that the inner product of $\sigma$ and $a$ is large, then $R(A)$ would be large.

Theorem 4: The expectation of $\mathcal{V}$ can be bounded as follows. $${\mathbb{E}}_S\left[\mathcal{V}\right]\le 2{\mathbb{E}}_S[R(\mathcal{F}(S))],$$ where $\mathcal{F}(S)=\{({\mathbb{I}}_{h(x_1)\ne y_1},\cdots ,{\mathbb{I}}_{h(x_n)\ne y_n}),h\in \mathcal{H}\}.$

Proof: To simplify the notation, the loss term ${\mathbb{I}}_{h(x_i)\ne y_i}$ is denoted by $f(z_i)$. Moreover, the set of all $f$’s is denoted by $\mathcal{F}$. The training set $S=\{Z_i{\}}_{i=1}^n$ is the source of randomness. Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^{n}f(Z_i)–{\mathbb{E}}_Z[f(Z)]|\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^{n}f(Z_i)–\frac{1}{n}\sum _{i=1}^n{\mathbb{E}}_{Z_i^{\prime }}[f(Z_i^{\prime })]|\right],\end{array}$$ where we introduce a virtual validation set or a set of ghost samples $S^{\prime }:=\{Z_i^{\prime }{\}}_{i=1}^n$, which is independent of $S$. This is known as the symmertrization trick. Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}\left|{\mathbb{E}}_{S^{\prime }}\left[\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right]\right|\right]\\ \underset{\text{Jensen’s}}{\le }& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}{\mathbb{E}}_{S^{\prime }}\left[\left|\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right|\right]\right]\\ \le & {\mathbb{E}}_{S,S^{\prime }}\left[\underset{f\in \mathcal{F}}{sup}\left|\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right|\right].\end{array}$$ Since $\mathrm{\forall }i$, $Z_i$ and $Z_i^{\prime }$ are i.i.d., we have that the following three random variables have the same distribution, $$f(Z_i)-f(Z_i^{\prime })\stackrel{\text{d}}{=}f(Z_i^{\prime })-f(Z_i)\stackrel{\text{d}}{=}{\sigma }_i(f(Z_i)-f(Z_i^{\prime })).$$ Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ \le & {\mathbb{E}}_{S,S^{\prime },\sigma }\left[\underset{f\in \mathcal{F}}{sup}\left|\frac{1}{n}\sum _{i=1}^n{\sigma }_i(f(Z_i)–f(Z_i^{\prime }))\right|\right]\\ \le & 2{\mathbb{E}}_{S,\sigma }\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}f(Z_i)|\right]=2{\mathbb{E}}_S[R(\mathcal{F}(S)].\end{array}$$

Some properties of Rademacher complexity

Rademacher calculus:

The following theorem is useful when dealing with the composition of a function and a set.

Theorem 5 (contraction principle): Let $A\subseteq {\mathbb{R}}^n$, $\varphi :\mathbb{R}\mapsto \mathbb{R}$, $\varphi (0)=0$, and $\varphi (\cdot )$ be $M$-Lipschitz continuous. Applying $\varphi$ to the set $A$ leads to a new set $\varphi \circ A=\{(\varphi (a_1),\cdots ,\varphi (a_n)),a\in A\}$. Then, the Rademacher complexity of $\varphi \circ A$ is bounded as follows. $$R(\varphi \circ A)\le 2MR(A).$$

VC-dimension

Theorem 6 (finite class lemma): Suppose $A=\{a^{(1)},\dots ,a^{(N)}\}$ is a finite subset of ${\mathbb{R}}^n$ for $N>2$ and $||a^{(i)}||\le L,\mathrm{\forall }i$, then the Radmacher complexity of $A$ is bounded as follows, $$R_n(A)\le \frac{2L\sqrt{\log N}}{n}.$$

• finite class lemma
• definition of VC-dimension
• VC’s lemma
• relationship of Rademacher complexity and VC-dimension

Others

• surrogate loss function
• contraction principle

Some examples

Now, we consider the separators on ${\mathbb{R}}^d$. Given $\mathrm{\Gamma }\subseteq {\mathbb{R}}^d$ and a data distribution $\mathcal{D}$ over $\mathrm{\Gamma }$. A set of i.i.d. samples $S=\{Z_1,\dots ,Z_n\}$ is sampled from $\mathrm{\Gamma }$ conforming the distribution $\mathcal{D}$. Denoting $\mathcal{H}$ as the hypothesis class, the learning alorithm maps $S$ to a hypothesis $h_S\in \mathcal{H}$. Given a hypothesis $h$, define its true risk as $$L_P(h)={\mathbb{E}}_{Z\sim \mathcal{D}}{\mathbb{I}}_{h(Z)\ne 1},$$ and the empirical risk on $S$ as $$L_S(h)=\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(Z_i)\ne 1}.$$

Then using the VC-theory, we can derive a PAC bound for this learning problem. Here, we assume this case is realizable, i.e. $L_P(h^{\ast })=0$.

$\begin{array}{c}{L}_P(h_S)–L_P(h^{\ast })=[L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\hfill \\ +[L_S(h_S)–L_S(h^{\ast }){]}_{\le 0}\\ \le [L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\\ \hfill \le 2\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|=2\mathcal{V}\end{array}$

Using the Radmacher average to bound $\mathbb{E}[\mathcal{V}]$, $$\mathbb{E}[\mathcal{V}]\le 2\mathbb{E}[R(\mathcal{H}(Z^n))].$$

Then, we use the finite class lemma to bound the Radmacher average. Let $S_n(\mathcal{H})=\underset{z^n}{sup}|\mathcal{H}(z^n)|$, then $$\mathbb{E}[R(\mathcal{H}(Z^n))]\le \mathbb{E}\left[2\sqrt{\frac{\log S_n(\mathcal{H})}{n}}\right]=2\sqrt{\frac{\log S_n(\mathcal{H})}{n}}.$$

Next, we use the VC-dimension and the Sauer–Shelah lemma to bound $S_n(\mathcal{H})$. The Sauer-Shelah lemma, $$S_n(\mathcal{H})\le \sum _{i=1}^{VC(\mathcal{H})}(\genfrac{}{}{0ex}{}{n}{i})\le {\left(\frac{ne}{d}\right)}^{VC(\mathcal{H})}.$$ Thus, we finally have $$\mathbb{E}[L_P(h_S)]=\mathbb{E}[L_P(h_S)–L_P(h^{\ast })]\le 8\sqrt{\frac{VC(\mathcal{H})(1+\log \frac{n}{d})}{n}}.$$

Finally we use the McDiarmid’s inequality to derive a concentration property. We have $$Pr(L_P(h_S)–\mathbb{E}[L_P(h_S)]\le \frac{1}{2n}\sqrt{\log \frac{1}{\delta }})\ge 1-\delta$$ which with the above results implies that with probability higher than $1-\delta$, $$L_P(h_S)\le 8\sqrt{\frac{VC(\mathcal{H})(1+\log \frac{n}{d})}{n}}+\frac{1}{2n}\sqrt{\log \frac{1}{\delta }}.$$

With Dudley’s theorem, we can construct the so-called Dudley classes whose VC-dimension is known. Specifically, we can choose a basis of $n$ linearly independent functions to construct a $n$-dimensional Hilbert space of which the VC-dimension is $n$. For example, $\{1,x,\dots ,x^n\}$ is a valid basis.