I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).
Is it true that PAC is a subset of agnostic PAC?
machine learning;learning theory
The trivial implication is:$\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnableIntuitively, being agnostic PAC learnable is a stronger condition, since you can, for all distributions on $\mathcal{X}\times\{-1,1\}$, get close to the optimal error (in particular, you can do so when the labels are forced to be consistent with some $c\in\mathcal{C}$).To see this formally, suppose a concept class $\mathcal{H}\subseteq 2^{\mathcal{X}}$ is agnostic PAC learnable. This means that there exists an algorithm $A$, such that for all $\epsilon,\delta>0$ there exists $m\in\mathbb{N}$ such that for all distributions $\mathcal{D}$ over $\mathcal{X}\times\{-1,1\}$, and a set of labeled samples $(x_i,y_i)_{i=1}^{n\ge m}$ drawn from $\mathcal{D}$, $A$ outputs $h\in\mathcal{H}$ such that:$err(h)\le err^*(\mathcal{D})+\epsilon$, with probability $\ge 1-\delta$, where $err^*(\mathcal{D})$ is the error rate of the optimal hypothesis relative to $\mathcal{D}$.To show that $\mathcal{H}$ is PAC learnable, let $h\in\mathcal{H}$ be some target concept, and let $\mathcal{D}$ be any distribution over $\mathcal{X}$. Examine the distribution $\mathcal{D}'$ on $\mathcal{X}\times\{-1,1\}$ obtained by drawing $x\in\mathcal{X}$ according to $\mathcal{D}$, and taking the pair $\left(x,h(x)\right)$. Note that $err^*\left(\mathcal{D}'\right)=0$, which means there exists an algorithm $A$ which produces a hypothesis in $\mathcal{H}$ with small generalization error (you can complete the details yourself, this shows you that all you need to do is unfold the definitions).The opposite implication (agnostic PAC learnability follows from PAC learnability) is also true, since they are both equivalent to $\mathcal{C}$ having a finite VC dimension, but this is much harder to show.