3.6 Exercises

3.1 Growth function of intervals in $\mathbb{R}$

让 $\mathcal{H}$ 为 $\mathbb{R}$ 中的区间集合。$\mathcal{H}$ 的VC维度为2。计算其打碎系数 ${\Pi }_{\mathcal{H}}\left(m\right),m\ge 0$。将你的结果与增长函数的一般界限进行比较。

3.2 Growth function and Rademacher complexity of thresholds in $\mathbb{R}$

让 $\mathcal{H}$ 为实数线上的阈值函数族：$\mathcal{H}=\left\{x\mapsto 1_{x\le \theta }:\theta \in \mathbb{R}\right\}\cup \{x\mapsto$ $1_{x\ge \theta }:\theta \in \mathbb{R}\}$。 给出增长函数 ${\Pi }_m\left(\mathcal{H}\right)$ 的上界。 利用该上界推导出 ${\mathfrak{R}}_m\left(\mathcal{H}\right)$ 的上界。

3.3 Growth function of linear combinations

A linearly separable labeling of a set $\mathcal{X}$ of vectors in ${\mathbb{R}}^d$ is a classification of $\mathcal{X}$ into two sets ${\mathcal{X}}^{+}$ and ${\mathcal{X}}^{-}$ with ${\mathcal{X}}^{+}=$ $\{\mathbf{x}\in \mathcal{X}:\mathbf{w}\cdot \mathbf{x}>0\}$ and ${\mathcal{X}}^{-}=\{\mathbf{x}\in \mathcal{X}:\mathbf{w}\cdot \mathbf{x}<0\}$ for some $\mathbf{w}\in {\mathbb{R}}^d$ .

Let $\mathcal{X}=\left\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\right\}$ be a subset of ${\mathbb{R}}^d$ .

1. Let $\left\{{\mathcal{X}}^{+},{\mathcal{X}}^{-}\right\}$ be a dichotomy of $\mathcal{X}$ and let ${\mathbf{x}}_{m+1}\in {\mathbb{R}}^d$ . Show that $\{{\mathcal{X}}^{+}\cup \left\{{\mathbf{x}}_{m+1}\right\},{\mathcal{X}}^{-}\}$ and $\left\{{\mathcal{X}}^{+},{\mathcal{X}}^{-}\cup \left\{{\mathbf{x}}_{m+1}\right\}\right\}$ are linearly separable by a hyperplane going through the origin if and only if $\left\{{\mathcal{X}}^{+},{\mathcal{X}}^{-}\right\}$ is linearly separable by a hyperplane going through the origin and ${\mathbf{x}}_{m+1}$ .
2. Let $\mathcal{X}=\left\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\right\}$ be a subset of ${\mathbb{R}}^d$ such that any $k$ -element subset of $x$ with $k\le d$ is linearly independent. Then, show that the number of linearly separable labelings of $X$ is $C\left(m,d\right)=2\sum _{k=0}^{d-1}\left(\begin{array}{c}m-1\\ k\end{array}\right)$.
   • Hint: prove by induction that $C\left(m+1,d\right)=C\left(m,d\right)+C\left(m,d-1\right)$
3. Let $f_1,\dots ,f_p$ be $p$ functions mapping ${\mathbb{R}}^d$ to $\mathbb{R}$ . Define $\mathcal{F}$ as the family of classifiers based on linear combinations of these functions: $\mathcal{F}=\left\{x\mapsto \mathrm{sgn}\left(\sum _{k=1}^p{a}_k{f}_k\left(x\right)\right):a_1,\dots ,a_p\in \mathbb{R}\right\}.$
   • Define $\Psi$ by $\Psi \left(x\right)=\left(f_1\left(x\right),\dots ,f_p\left(x\right)\right)$. Assume that there exists $x_1,\dots ,x_m\in {\mathbb{R}}^d$ such that every $p$-subset of $\left\{\Psi \left(x_1\right),\dots ,\Psi \left(x_m\right)\right\}$ is linearly independent. Then, show that ${\Pi }_{\mathcal{F}}\left(m\right)=2\sum _{i=0}^{p-1}\left(\begin{array}{c}m-1\\ i\end{array}\right).$

3.4 Lower bound on growth function.

Prove that Sauer’s lemma (theorem 3.17) is tight, i.e., for any set $x$ of $m>d$ elements, show that there exists a hypothesis class $\mathcal{H}$ of VC-dimension $d$ such that ${\Pi }_{\mathcal{H}}\left(m\right)=\sum _{i=0}^d\left(\begin{array}{c}m\\ i\end{array}\right)$ .

3.5 Finer Rademacher upper bound. Show that a finer upper bound on the Rademacher complexity of the family $\mathcal{G}$ can be given in terms of ${\mathbb{E}}_S\left[\Pi \left(\mathcal{G},S\right)\right]$ , where $\Pi \left(\mathcal{G},S\right)$ is the number of ways to label the points in sample $S$ .

3.6 Singleton hypothesis class. Consider the trivial hypothesis set $\mathcal{H}=\left\{h_0\right\}$ .

(a) Show that ${\mathfrak{R}}_m\left(\mathcal{H}\right)=0$ for any $m>0$ .

(b) Use a similar construction to show that Massart’s lemma (theorem 3.7) is tight.

3.7 Two function hypothesis class. Let $\mathcal{H}$ be a hypothesis set reduced to two functions: $\mathcal{H}=\left\{h_{-1},h_{+1}\right\}$ and let $S=\left(x_1,\dots ,x_m\right)\subseteq \mathfrak{X}$ be a sample of size $m$ .

(a) Assume that $h_{-1}$ is the constant function taking value -1 and $h_{+1}$ the constant function taking the value +1 . What is the VC-dimension $d$ of $\mathcal{H}$ ? Upper bound the empirical Rademacher complexity ${\hat{\Re }}_S\left(\mathcal{H}\right)$ (Hint: express ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$ in terms of the absolute value of a sum of Rademacher variables and apply Jensen’s inequality) and compare your bound with $\sqrt{d/m}$ .

(b) Assume that $h_{-1}$ is the constant function taking value -1 and $h_{+1}$ the function taking value -1 everywhere except at $x_1$ where it takes the value +1. What is the VC-dimension $d$ of $\mathcal{H}$ ? Compute the empirical Rademacher complexity ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$ .

3.8 Rademacher identities. Fix $m\ge 1$ . Prove the following identities for any $\alpha \in \mathbb{R}$ and any two hypothesis sets $\mathcal{H}$ and ${\mathcal{H}}^{\prime }$ of functions mapping from $\mathcal{X}$ to $\mathbb{R}$ :

(a) ${\Re }_m\left(\alpha \mathcal{H}\right)=\left|\alpha \right|{\Re }_m\left(\mathcal{H}\right)$ .

(b) ${\Re }_m\left(\mathcal{H}+{\mathcal{H}}^{\prime }\right)={\Re }_m\left(\mathcal{H}\right)+{\Re }_m\left({\mathcal{H}}^{\prime }\right)$ .

(c) ${\mathfrak{R}}_m\left(\left\{\max \left(h,h^{\prime }\right):h\in \mathcal{H},h^{\prime }\in {\mathcal{H}}^{\prime }\right\}\right)\le {\mathfrak{R}}_m\left(\mathcal{H}\right)+{\mathfrak{R}}_m\left({\mathcal{H}}^{\prime }\right)$ ,

where $\max \left(h,h^{\prime }\right)$ denotes the function $x\mapsto \underset{x\in X}{\max }\left(h\left(x\right),h^{\prime }\left(x\right)\right)$ (Hint: you could use the identity $\max \left(a,b\right)=\frac{1}{2}\left[a+b+\left|a-b\right|\right]$ valid for all $a,b\in \mathbb{R}$ and Talagrand’s contraction lemma (see lemma 5.7)).

3.9 Rademacher complexity of intersection of concepts. Let ${\mathcal{H}}_1$ and ${\mathcal{H}}_2$ be two families of functions mapping $X$ to $\{0,1\}$ and let $\mathcal{H}=\{h_1{h}_2:h_1\in {\mathcal{H}}_1,h_2\in$ ${\mathcal{H}}_2\}$ . Show that the empirical Rademacher complexity of $\mathcal{H}$ for any sample $S$ of size $m$ can be bounded as follows:

${\hat{\mathfrak{R}}}_S\left(H\right)\le {\hat{\mathfrak{R}}}_S\left({\mathcal{H}}_1\right)+{\hat{\mathfrak{R}}}_S\left({\mathcal{H}}_2\right)$

Hint: use the Lipschitz function $x\mapsto \max \left(0,x-1\right)$ and Talagrand’s contraction lemma.

Use that to bound the Rademacher complexity ${\mathfrak{R}}_m\left(\mathcal{U}\right)$ of the family $\mathcal{U}$ of intersections of two concepts $c_1$ and $c_2$ with $c_1\in {\mathcal{C}}_1$ and $c_2\in {\mathcal{C}}_2$ in terms of the Rademacher complexities of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ .

3.10 Rademacher complexity of prediction vector. Let $S=\left(x_1,\dots ,x_m\right)$ be a sample of size $m$ and fix $h:\mathcal{X}\to \mathbb{R}$ .

(a) Denote by $\mathbf{u}$ the vector of predictions of $h$ for $S:\mathbf{u}=\left[\begin{array}{c}h\left(x_1\right)\\ ⋮\\ h\left(x_m\right)\end{array}\right]$ . Give an upper bound on the empirical Rademacher complexity ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$ of $\mathcal{H}=$ $\{h,-h\}$ in terms of $\parallel \mathbf{u}{\parallel }_2$ (Hint: express ${\hat{\Re }}_S\left(\mathcal{H}\right)$ in terms of the expectation of an absolute value and apply Jensen’s inequality). Suppose that $h\left(x_i\right)\in$ $\{0,-1,+1\}$ for all $i\in \left[m\right]$ . Express the bound on the Rademacher complexity in terms of the sparsity measure $n=\left|\left\{i\mid h\left(x_i\right)\ne 0\right\}\right|$ . What is that upper bound for the extreme values of the sparsity measure?

(b) Let $\mathcal{F}$ be a family of functions mapping $x$ to $\mathbb{R}$ . Give an upper bound on the empirical Rademacher complexity of $\mathcal{F}+h=\{f+h:f\in \mathcal{F}\}$ and that of $\mathcal{F}\pm h=\left(\mathcal{F}+h\right)\cup \left(\mathcal{F}-h\right)$ in terms of ${\hat{\mathfrak{R}}}_S\left(\mathcal{F}\right)$ and $\parallel \mathbf{u}{\parallel }_2$ .

3.11 Rademacher complexity of regularized neural networks. Let the input space be $\mathcal{X}={\mathbb{R}}^{n_1}$ . In this problem, we consider the family of regularized neural networks defined by the following set of functions mapping $X$ to $\mathbb{R}$ :

$\mathcal{H}=\left\{\mathbf{x}\mapsto \sum _{j=1}^{n_2}{w}_j\sigma \left({\mathbf{u}}_j\cdot \mathbf{x}\right):\parallel \mathbf{w}{\parallel }_1\le {\Lambda }^{\prime },{\Vert \begin{array}{c}{\mathbf{u}}_j\end{array}\Vert }_2\le \Lambda ,\forall j\in \left[n_2\right]\right\},$

where $\sigma$ is an $L$ -Lipschitz function. As an example, $\sigma$ could be the sigmoid function which is 1-Lipschitz.

(a) Show that ${\hat{\Re }}_S\left(\mathcal{H}\right)=\frac{{\Lambda }^{\prime }}{m}{\mathbb{E}}_{\sigma }\left[\underset{\parallel \mathbf{u}{\parallel }_2\le \Lambda }{\sup }\left|\sum _{i=1}^m{\sigma }_i\sigma \left(\mathbf{u}\cdot {\mathbf{x}}_i\right)\right|\right]$ .

(b) Use the following form of Talagrand’s lemma valid for all hypothesis sets $\mathcal{H}$ and $L$ -Lipschitz function $\Phi$ :

$\frac{1}{m}\mathbb{E}\left[\underset{h\in \mathcal{H}}{\sup }\left|\sum _{i=1}^m{\sigma }_i\left(\Phi \circ h\right)\left(x_i\right)\right|\right]\le \frac{L}{m}\mathbb{E}\left[\underset{h\in \mathcal{H}}{\sup }\left|\sum _{i=1}^m{\sigma }_{i}h\left(x_i\right)\right|\right],$

to upper bound ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$ in terms of the empirical Rademacher complexity of ${\mathcal{H}}^{\prime }$ , where ${\mathcal{H}}^{\prime }$ is defined by

${\mathcal{H}}^{\prime }=\left\{\mathbf{x}\mapsto s\left(\mathbf{u}\cdot \mathbf{x}\right):\parallel \mathbf{u}{\parallel }_2\le \Lambda ,s\in \{-1,+1\}\right\}.$

(c) Use the Cauchy-Schwarz inequality to show that

${\hat{\mathfrak{R}}}_S\left({\mathcal{H}}^{\prime }\right)=\frac{\Lambda }{m}\underset{\sigma }{\mathbb{E}}\left[{\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert }_2\right].$

(d) Use the inequality ${\mathbb{E}}_{\mathbf{y}}\left[\parallel \mathbf{v}{\parallel }_2\right]\le \sqrt{{\mathbb{E}}_{\mathbf{v}}\left[\parallel \mathbf{v}{\parallel }_2^2\right]}$ , which holds by Jensen’s inequality to upper bound ${\hat{\mathfrak{R}}}_S\left({\mathcal{H}}^{\prime }\right)$ .

(e) Assume that for all $\mathbf{x}\in S,\parallel \mathbf{x}{\parallel }_2\le r$ for some $r>0$ . Use the previous questions to derive an upper bound on the Rademacher complexity of $\mathcal{H}$ in terms of $r$ .

3.12 Rademacher complexity. Professor Jesetoo claims to have found a better bound on the Rademacher complexity of any hypothesis set $\mathcal{H}$ of functions taking values in $\{-1,+1\}$ , in terms of its VC-dimension VCdim $\left(\mathcal{H}\right)$ . His bound is of the form ${\mathfrak{R}}_m\left(\mathcal{H}\right)\le O\left(\frac{\mathrm{VCdim}\left(\mathcal{H}\right)}{m}\right)$ . Can you show that Professor Jesetoo’s claim cannot be correct? (Hint: consider a hypothesis set $\mathcal{H}$ reduced to just two simple functions.)

3.13 VC-dimension of union of $k$ intervals. What is the VC-dimension of subsets of the real line formed by the union of $k$ intervals?

3.14 VC-dimension of finite hypothesis sets. Show that the VC-dimension of a finite hypothesis set $\mathcal{H}$ is at most ${\log }_2\left|\mathcal{H}\right|$ .

3.15 VC-dimension of subsets. What is the VC-dimension of the set of subsets $I_{\alpha }$ of the real line parameterized by a single parameter $\alpha :I_{\alpha }=\left[\alpha ,\alpha +1\right]\cup [\alpha +2,+\infty )$ ?

3.16 VC-dimension of axis-aligned squares and triangles.

(a) What is the VC-dimension of axis-aligned squares in the plane?

(b) Consider right triangles in the plane with the sides adjacent to the right angle both parallel to the axes and with the right angle in the lower left corner. What is the VC-dimension of this family?

3.17 VC-dimension of closed balls in ${\mathbb{R}}^n$ . Show that the VC-dimension of the set of all closed balls in ${\mathbb{R}}^n$ , i.e., sets of the form $\left\{x\in {\mathbb{R}}^n:{\Vert \begin{array}{c}x-x_0\end{array}\Vert }^2\le r\right\}$ for some $x_0\in {\mathbb{R}}^n$ and $r\ge 0$ , is less than or equal to $n+2$ .

3.18 VC-dimension of ellipsoids. What is the VC-dimension of the set of all ellipsoids in ${\mathbb{R}}^n$ ?

3.19 VC-dimension of a vector space of real functions. Let $F$ be a finite-dimensional vector space of real functions on ${\mathbb{R}}^n,\dim \left(F\right)=r<\infty$ . Let $\mathcal{H}$ be the set of hypotheses:

$\mathcal{H}=\{\{x:f\left(x\right)\ge 0\}:f\in F\}.$

Show that $d$ , the VC-dimension of $\mathcal{H}$ , is finite and that $d\le r$ . (Hint: select an arbitrary set of $m=r+1$ points and consider linear mapping $u:F\to {\mathbb{R}}^m$ defined by: $u\left(f\right)=\left(f\left(x_1\right),\dots ,f\left(x_m\right)\right)$ .)

3.20 VC-dimension of sine functions. Consider the hypothesis family of sine functions (Example 3.16): $\{x\to \sin \left(\omega x\right):\omega \in \mathbb{R}\}$ .

(a) Show that for any $x\in \mathbb{R}$ the points $x,2x,3x$ and $4x$ cannot be shattered by this family of sine functions.

(b) Show that the VC-dimension of the family of sine functions is infinite. (Hint: show that $\left\{2^{-i}:i\le m\right\}$ can be shattered for any $m>0$ .)

3.21 VC-dimension of union of halfspaces. Provide an upper bound on the VC-dimension of the class of hypotheses described by the unions of $k$ halfspaces.

3.22 VC-dimension of intersection of halfspaces. Consider the class ${\mathcal{C}}_k$ of convex intersections of $k$ halfspaces. Give lower and upper bound estimates for $\mathrm{VCdim}\left({\mathcal{C}}_k\right)$ .

3.23 VC-dimension of intersection concepts.

(a) Let ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ be two concept classes. Show that for any concept class $\mathcal{C}=\left\{c_1\cap c_2:c_1\in {\mathcal{C}}_1,c_2\in {\mathcal{C}}_2\right\}$

{\Pi }_{\mathcal{C}}\left( m\right) \leq {\Pi }_{{\mathcal{C}}_{1}}\left( m\right) {\Pi }_{{\mathcal{C}}_{2}}\left( m\right) \tag{3.53}

(b) Let $\mathcal{C}$ be a concept class with VC-dimension $d$ and let ${\mathcal{C}}_s$ be the concept class formed by all intersections of $s$ concepts from $\mathcal{C},s\ge 1$ . Show that the VC-dimension of ${\mathcal{C}}_s$ is bounded by $2ds{\log }_2\left(3s\right)$ . (Hint: show that ${\log }_2\left(3x\right)<$ $9x/\left(2e\right)$ for any $x\ge 2$ .)

3.24 VC-dimension of union of concepts. Let $\mathcal{A}$ and $\mathcal{B}$ be two sets of functions mapping from $X$ into $\{0,1\}$ , and assume that both $\mathcal{A}$ and $\mathcal{B}$ have finite VC-dimension, with $\mathrm{VCdim}\left(\mathcal{A}\right)=d_{\mathcal{A}}$ and $\mathrm{VCdim}\left(\mathcal{B}\right)=d_{\mathcal{B}}$ . Let $\mathcal{C}=\mathcal{A}\cup \mathcal{B}$ be the union of $\mathcal{A}$ and $\mathcal{B}$ .

(a) Prove that for all $m,{\Pi }_{\mathcal{C}}\left(m\right)\le {\Pi }_{\mathcal{A}}\left(m\right)+{\Pi }_{\mathcal{B}}\left(m\right)$ .

(b) Use Sauer’s lemma to show that for $m\ge d_{\mathcal{A}}+d_{\mathcal{B}}+2,{\Pi }_{\mathcal{C}}\left(m\right)<2^m$ , and give a bound on the VC-dimension of $\mathcal{C}$ .

3.25 VC-dimension of symmetric difference of concepts. For two sets $\mathcal{A}$ and $\mathcal{B}$ , let $\mathcal{A}\Delta \mathcal{B}$ denote the symmetric difference of $\mathcal{A}$ and $\mathcal{B}$ , i.e., $\mathcal{A}\Delta \mathcal{B}=\left(\mathcal{A}\cup \mathcal{B}\right)-\left(\mathcal{A}\cap \mathcal{B}\right)$ . Let $\mathcal{H}$ be a non-empty family of subsets of $x$ with finite VC-dimension. Let $\mathcal{A}$ be an element of $\mathcal{H}$ and define $\mathcal{H}\Delta \mathcal{A}=\{X\Delta \mathcal{A}:X\in \mathcal{H}\}$ . Show that

$\mathrm{VCdim}\left(\mathcal{H}\Delta \mathcal{A}\right)=\mathrm{VCdim}\left(\mathcal{H}\right)$

3.26 Symmetric functions. A function $h:\{0,1{\}}^n\to \{0,1\}$ is symmetric if its value is uniquely determined by the number of 1’s in the input. Let $\mathcal{C}$ denote the set of all symmetric functions.

(a) Determine the VC-dimension of $\mathcal{C}$ .

(b) Give lower and upper bounds on the sample complexity of any consistent PAC learning algorithm for $\mathcal{C}$ .

(c) Note that any hypothesis $h\in \mathcal{C}$ can be represented by a vector $\left(y_0,y_1,\dots ,y_n\right)$ $\in \{0,1{\}}^{n+1}$ , where $y_i$ is the value of $h$ on examples having precisely $i1$ ‘s. Devise a consistent learning algorithm for $\mathcal{C}$ based on this representation.

3.27 VC-dimension of neural networks. {#vc-dimension-of-neural-networks. .unnumbered}

Let $\mathcal{C}$ be a concept class over ${\mathbb{R}}^r$ with VC-dimension $d$ . A $\mathcal{C}$ -neural network with one intermediate layer is a concept defined over ${\mathbb{R}}^n$ that can be represented by a directed acyclic graph such as that of Figure 3.7, in which the input nodes are those at the bottom and in which each other node is labeled with a concept $c\in \mathcal{C}$ .

The output of the neural network for a given input vector $\left(x_1,\dots ,x_n\right)$ is obtained as follows. First, each of the $n$ input nodes is labeled with the corresponding value $x_i\in \mathbb{R}$ . Next, the value at a node $u$ in the higher layer and labeled with $c$ is obtained by applying $c$ to the values of the input nodes admitting an

::: center {width=“30%”} :::

Figure 3.7

A neural network with one intermediate layer.

edge ending in $u$ . Note that since $c$ takes values in $\{0,1\}$ , the value at $u$ is in $\{0,1\}$ . The value at the top or output node is obtained similarly by applying the corresponding concept to the values of the nodes admitting an edge to the output node.

(a) Let $\mathcal{H}$ denote the set of all neural networks defined as above with $k\ge 2$ internal nodes. Show that the growth function ${\Pi }_{\mathcal{H}}\left(m\right)$ can be upper bounded in terms of the product of the growth functions of the hypothesis sets defined at each intermediate layer.

(b) Use that to upper bound the VC-dimension of the C-neural networks (Hint: you can use the implication $m=2x{\log }_2\left(xy\right)\Rightarrow m>x{\log }_2\left(ym\right)$ valid for $m\ge 1$ , and $x,y>0$ with $xy>4$ ).

(c) Let $\mathcal{C}$ be the family of concept classes defined by threshold functions $\mathcal{C}=$ $\left\{\mathrm{sgn}\left(\sum _{j=1}^r{w}_j{x}_j\right):\mathbf{w}\in {\mathbb{R}}^r\right\}$ . Give an upper bound on the VC-dimension of $\mathcal{H}$ in terms of $k$ and $r$ .

3.28 VC-dimension of convex combinations. Let $\mathcal{H}$ be a family of functions mapping from an input space $X$ to $\{-1,+1\}$ and let $T$ be a positive integer. Give an upper bound on the VC-dimension of the family of functions ${\mathcal{F}}_T$ defined by

$\mathcal{F}=\left\{\mathrm{sgn}\left(\sum _{t=1}^T{\alpha }_t{h}_t\right):h_t\in \mathcal{H},{\alpha }_t\ge 0,\sum _{t=1}^T{\alpha }_t\le 1\right\}.$

(Hint: you can use exercise 3.27 and its solution).

3.29 Infinite VC-dimension.

(a) Show that if a concept class $\mathcal{C}$ has infinite VC-dimension, then it is not PAC-learnable.

(b) In the standard PAC-learning scenario, the learning algorithm receives all examples first and then computes its hypothesis. Within that setting, PAC-learning of concept classes with infinite VC-dimension is not possible as seen in the previous question.

Imagine now a different scenario where the learning algorithm can alternate between drawing more examples and computation. The objective of this problem is to prove that PAC-learning can then be possible for some concept classes with infinite VC-dimension.

Consider for example the special case of the concept class $\mathcal{C}$ of all subsets of natural numbers. Professor Vitres has an idea for the first stage of a learning algorithm $L$ PAC-learning $\mathcal{C}$ . In the first stage, $L$ draws a sufficient number of points $m$ such that the probability of drawing a point beyond the maximum value $M$ observed be small with high confidence. Can you complete Professor Vitres’ idea by describing the second stage of the algorithm so that it PAC-learns $\mathcal{C}$ ? The description should be augmented with the proof that $L$ can PAC-learn C.

3.30 VC-dimension generalization bound - realizable case. In this exercise we show that the bound given in corollary 3.19 can be improved to $O\left(\frac{d\log \left(m/d\right)}{m}\right)$ in the realizable setting. Assume we are in the realizable scenario, i.e. the target concept is included in our hypothesis class $\mathcal{H}$ . We will show that if a hypothesis $h$ is consistent with a sample $S\sim {\mathcal{D}}^m$ then for any $ϵ>0$ such that $mϵ\ge 8$

\mathbb{P}\left\lbrack {R\left( h\right) > \epsilon }\right\rbrack \leq 2{\left\lbrack \frac{2em}{d}\right\rbrack }^{d}{2}^{-{m\epsilon }/2}. \tag{3.54}

(a) Let ${\mathcal{H}}_S\subseteq \mathcal{H}$ be the subset of hypotheses consistent with the sample $S$ , let ${\hat{R}}_S\left(h\right)$ denote the empirical error with respect to the sample $S$ and define $S^{\prime }$ as another independent sample drawn from ${\mathcal{D}}^m$ . Show that the following inequality holds for any $h_0\in {\mathcal{H}}_S$ :

$\mathbb{P}\left[\underset{h\in {\mathcal{H}}_S}{\sup }\left|{\hat{R}}_S\left(h\right)-{\hat{R}}_{S^{\prime }}\left(h\right)\right|>\frac{ϵ}{2}\right]\ge \mathbb{P}\left[B\left(m,ϵ\right)>\frac{mϵ}{2}\right]\mathbb{P}\left[R\left(h_0\right)>ϵ\right],$

where $B\left(m,ϵ\right)$ is a binomial random variable with parameters $\left(m,ϵ\right)$ . (Hint: prove and use the fact that $\mathbb{P}\left[{\hat{R}}_S\left(h\right)\ge \frac{ϵ}{2}\right]\ge \mathbb{P}\left[{\hat{R}}_S\left(h\right)>\frac{ϵ}{2}\wedge R\left(h\right)>ϵ\right]$ .)

(b) Prove that $\mathbb{P}\left[B\left(m,ϵ\right)>\frac{mϵ}{2}\right]\ge \frac{1}{2}$ . Use this inequality along with the result from (a) to show that for any $h_0\in {\mathcal{H}}_S$

$\mathbb{P}\left[R\left(h_0\right)>ϵ\right]\le 2\mathbb{P}\left[\underset{h\in {\mathcal{H}}_S}{\sup }\left|{\hat{R}}_S\left(h\right)-{\hat{R}}_{S^{\prime }}\left(h\right)\right|>\frac{ϵ}{2}\right].$

(c) Instead of drawing two samples, we can draw one sample $T$ of size $2m$ then uniformly at random split it into $S$ and $S^{\prime }$ . The right hand side of part (b) can then be rewritten as:

$\mathbb{P}\left[\underset{h\in {\mathcal{H}}_S}{\sup }\left|{\hat{R}}_S\left(h\right)-{\hat{R}}_{S^{\prime }}\left(h\right)\right|>\frac{ϵ}{2}\right]=\underset{\begin{array}{c}T\sim {\mathcal{D}}^{2m},\\ T\to \left[S,S^{\prime }\right]\end{array}}{\mathbb{P}}\left[\exists h\in \mathcal{H}:{\hat{R}}_S\left(h\right)=0\wedge {\hat{R}}_{S^{\prime }}\left(h\right)>\frac{ϵ}{2}\right].$

Let $h_0$ be a hypothesis such that ${\hat{R}}_T\left(h_0\right)>\frac{ϵ}{2}$ and let $l>\frac{mϵ}{2}$ be the total number of errors $h_0$ makes on $T$ . Show that the probability of all $l$ errors falling into $S^{\prime }$ is upper bounded by $2^{-l}$ .

(d) Part (b) implies that for any $h\in \mathcal{H}$

$\underset{\begin{array}{c}T\sim {\mathcal{D}}^{2m}:\\ T\to \left(S,S^{\prime }\right)\end{array}}{\mathbb{P}}\left[{\hat{R}}_S\left(h\right)=0\wedge {\hat{R}}_{S^{\prime }}\left(h\right)>\frac{ϵ}{2}\mid {\hat{R}}_T\left(h_0\right)>\frac{ϵ}{2}\right]\le 2^{-l}.$

Use this bound to show that for any $h\in \mathcal{H}$

$\underset{\begin{array}{c}T\sim {\mathcal{D}}^{2m};\\ T\to \left(S,S^{\prime }\right)\end{array}}{\mathbb{P}}\left[{\hat{R}}_S\left(h\right)=0\wedge {\hat{R}}_{S^{\prime }}\left(h\right)>\frac{ϵ}{2}\right]\le 2^{-\frac{ϵm}{2}}.$

(e) Complete the proof of inequality (3.54) by using the union bound to upper bound ${\mathbb{P}}_{T\sim {\mathcal{D}}^{2}m}:\left[\exists h\in \mathcal{H}:{\hat{R}}_S\left(h\right)=0\wedge {\hat{R}}_{S^{\prime }}\left(h\right)>\frac{ϵ}{2}\right]$ . Show that we can achieve a high probability generalization bound that is of the order $O\left(\frac{d\log \left(m/d\right)}{m}\right)$ .

3.31 Generalization bound based on covering numbers. Let $\mathcal{H}$ be a family of functions mapping $x$ to a subset of real numbers $y\subseteq \mathbb{R}$ . For any $ϵ>0$ , the covering number $\mathcal{N}\left(\mathcal{H},ϵ\right)$ of $\mathcal{H}$ for the $L_{\infty }$ norm is the minimal $k\in \mathbb{N}$ such that $\mathcal{H}$ can be covered with $k$ balls of radius $ϵ$ , that is, there exists $\left\{h_1,\dots ,h_k\right\}\subseteq \mathcal{H}$ such that, for all $h\in \mathcal{H}$ , there exists $i\le k$ with ${\Vert \begin{array}{c}h-h_i\end{array}\Vert }_{\infty }=\underset{x\in X}{\max }\left|h\left(x\right)-h_i\left(x\right)\right|\le ϵ$ . In particular, when $\mathcal{H}$ is a compact set, a finite covering can be extracted from a covering of $\mathcal{H}$ with balls of radius $ϵ$ and thus $\mathcal{N}\left(\mathcal{H},ϵ\right)$ is finite.

Covering numbers provide a measure of the complexity of a class of functions: the larger the covering number, the richer is the family of functions. The objective of this problem is to illustrate this by proving a learning bound in the case of the squared loss. Let $\mathcal{D}$ denote a distribution over $X\times \mathcal{Y}$ according to which

labeled examples are drawn. Then, the generalization error of $h\in \mathcal{H}$ for the squared loss is defined by $R\left(h\right)={\mathbb{E}}_{\left(x,y\right)\sim \mathcal{D}}\left[{\left(h\left(x\right)-y\right)}^2\right]$ and its empirical error for a labeled sample $S=\left(\left(x_1,y_1\right),\dots ,\left(x_m,y_m\right)\right)$ by ${\hat{R}}_S\left(h\right)=\frac{1}{m}\sum _{i=1}^m{\left(h\left(x_i\right)-y_i\right)}^2$ . We will assume that $\mathcal{H}$ is bounded, that is there exists $M>0$ such that $\left|h\left(x\right)-y\right|\le M$ for all $\left(x,y\right)\in X\times y$ . The following is the generalization bound proven in this problem:

\underset{S \sim {\mathcal{D}}^{m}}{\mathbb{P}}\left\lbrack {\mathop{\sup }\limits_{{h \in \mathcal{H}}}\left| {R\left( h\right) - {\widehat{R}}_{S}\left( h\right) }\right| \geq \epsilon }\right\rbrack \leq \mathcal{N}\left( {\mathcal{H},\frac{\epsilon }{8M}}\right) 2\exp \left( \frac{-m{\epsilon }^{2}}{2{M}^{4}}\right) . \tag{3.55}

The proof is based on the following steps.

(a) Let $L_S=R\left(h\right)-{\hat{R}}_S\left(h\right)$ , then show that for all $h_1,h_2\in \mathcal{H}$ and any labeled sample $S$ , the following inequality holds:

$\left|L_S\left(h_1\right)-L_S\left(h_2\right)\right|\le 4M{\Vert \begin{array}{c}{h}_1-h_2\end{array}\Vert }_{\infty }.$

(b) Assume that $\mathcal{H}$ can be covered by $k$ subsets ${\mathcal{B}}_1,\dots ,{\mathcal{B}}_k$ , that is $\mathcal{H}={\mathcal{B}}_1\cup$ $\dots \cup {\mathcal{B}}_k$ . Then, show that, for any $ϵ>0$ , the following upper bound holds:

$\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\underset{h\in \mathcal{H}}{\sup }\left|L_S\left(h\right)\right|\ge ϵ\right]\le \sum _{i=1}^k\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\underset{h\in {\mathcal{B}}_i}{\sup }\left|L_S\left(h\right)\right|\ge ϵ\right].$

(c) Finally, let $k=\mathcal{N}\left(\mathcal{H},\frac{ϵ}{8M}\right)$ and let ${\mathcal{B}}_1,\dots ,{\mathcal{B}}_k$ be balls of radius $ϵ/\left(8M\right)$ centered at $h_1,\dots ,h_k$ covering $\mathcal{H}$ . Use part (a) to show that for all $i\in \left[k\right]$ ,

$\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\underset{h\in {\mathcal{B}}_i}{\sup }\left|L_S\left(h\right)\right|\ge ϵ\right]\le \underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\left|L_S\left(h_i\right)\right|\ge \frac{ϵ}{2}\right],$

and apply Hoeffding’s inequality (theorem D.2) to prove (3.55).