Request for examples regarding PAC learnability

Question

I am searching for 2 examples. At the bottom I give definitions I am using.

1. An example for H that is PAC learnable (according to 3.1) but not Agnostic PAC learnable (according to 3.3). We learned that such should exist. I saw in another post a comment that 3.1 and 3.3 are equivalent but i can't comment there (permissions) and don't see why - any way if you know such example or have a proof there is no, i'll be glad to read.

2. An example of H with 2 different non trivial loss functions (if one of them can be the 0-1 loss it will be great), which give as according to definition 3.4 that H is Agnostic PAC Learnable with one but not with the other.

definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t. $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have $L_S(h*) = 0$. $$$$ Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and for every labeling function $f \colon X \mapsto \{0,1\}$, if the realizability assumption holds with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

Definition 3.3 (Agnostic PAC Learnability) A hypothesis class $H$ is agnostic PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X\times Y$, when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the $m$ training examples), $$L_D(h) \leq \min_{h' \in H} L_D(h') + \varepsilon. $$

Definition 3.4 (Agnostic PAC Learnability for General Loss Functions) A hypothesis class H is agnostic PAC learnable with respect to a set Z=$X \times Y$ and a loss function $l : H \times Z \mapsto R_+$, if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$ and for every distribution D over Z, when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. examples generated by D, the algorithm returns $h \in H$ such that, with probability of at least $1 - \delta$ (over the choice of the m training examples), $L_D(h) \leq \min_{h' \in H} L_D(h') + \varepsilon.$ where $L_D(h) = E_{z \sim D}[l(h,z)]$.

Thank you!

Answer 1

You can find a proof for the equivalence between PAC and agnostic PAC learning in theorem 6.7 of "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz. The proof goes through showing:

1. $\mathcal{H}$ is PAC learnable $\Rightarrow$ $\mathcal{H}$ has finite VC dimension (lower bound on sample complexity).

2. $\mathcal{H}$ has finite VC dimension $\Rightarrow$ $\mathcal{H}$ is agnostic PAC learnable (upper bound on sample complexity)

If you don't care about the bounds being sharp, $1$ is not too hard, but $2$ is definitely beyond the scope of this site. Combining the above results with the fact that agnostic PAC learnability implies PAC learnability concludes the proof.

In regard to your second question, let $l_1$ be the 0-1 loss function and $l_2$ be a loss function which is nonzero only on a finite subset of $\mathcal{X}$ and is the 0-1 loss in that region (suppose you only care about very specific mistakes). Take any class with infinite VC dimension, then it is not agnostic PAC learnable with respect to $l_1$, but is learnable with respect to $l_2$ (If the loss function is nonzero only on a finite region, you can treat this case like having a finite hypothesis class).