# PAC learnability given information about the expectation of the training/true error

Let $\mathcal{X}$ be a domain set, $\mathcal{Y}=\{0,1\}$ and $\mathcal{H}$ an arbitary hypothesis class.

Assuming that there's an algorithm $\mathcal{A}$ such that for every distribution $\mathcal{D}$ realizable by $\mathcal{H}$, it holds that $\mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))] \leq \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_S(\mathcal{A}(S))]+\epsilon_m$ where $\epsilon_m \rightarrow0$.

Does that mean that $\mathcal{H}$ is PAC-learnable?

($L_\mathcal{D}(h)$ is the true error of hypothesis $h$ with respect to the 0-1 loss function)

Well, I think that it's not, but I lack the knowledge to put a finger on the exact reason why.

My intuition is that even though $\epsilon_m \rightarrow 0$, there still may be an arbitrary gap between $\mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))]$ and $\mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{S}}(\mathcal{A}(S))]$. Thus, we still don't know how approximately good $\mathcal{A}(S)$ is.

Can I deduce any promises whether $\mathcal{A}(S)$ "probably" good (something about $\delta$)?

There's no need for formal proof. Rather, intuition will be appriciated.

• By "every distribution realizable by $\mathcal{H}$" do you mean that the distribution is over $\mathcal{X}\times\mathcal{Y}$, i.e. we're in the agnostic model? Apr 10 '17 at 15:32

$\mathcal{H}$ is not necessarily pac learnable.
Lets break down your statement, you have an algorithm $\mathcal{A}$, which given a set of labeled samples $S\subseteq \mathcal{X}\times \mathcal{Y}$, generates a hypothesis in $\mathcal{H}$. You also know that $\mathcal{A}(S)$ achieves a generalization error which is close to its sample error (the closeness is determined by $\epsilon_m$).
If $\mathcal{A}$ was guaranteeing low sample error, then we were safe. However, this is not necessarily the case, take for example the rather stupid learning algorithm which always outputs some constant $h\in \mathcal{H}$ (and ignores the samples). This algorithm has equal sample/generalization error (so the condition is satisfied), but this obviously does not mean $\mathcal{H}$ is pac learnable (you can implement this algorithm even for $\mathcal{H}$ with infinite VC dimension).
• 1) " $\mathcal{A}(S)$ achieves a generalization error which is close to its sample error" - how do we know that it's close? Isnt there an unknown gap (which can be great) between this two, as i said? 2) "If $\mathcal{A}$ was guaranteeing low sample error" - do you mean $\mathcal{A} (S)$? 3) "This algorithm has equal sample/generalization error (so the condition is satisfied)" - why? Apr 11 '17 at 9:43
• In addition, how do we know what is the generalization error of $\mathcal{A}(S)$? We know the expectation of the generalization error of $\mathcal{A}(S)$ with respect to all S sampled at random. $\mathcal{A}(S)$ is a specific hypothesis that correspond to some sample set S. Apr 11 '17 at 9:57
• You said that "If $\mathcal{A}$ was guaranteeing low sample error, then we were safe.". Safe in what sense? We don't have any promises how "probably" the hypothesis is correct. Apr 11 '17 at 10:07
• The random variable $\Delta_m(S) = \sup\limits_{h\in\mathcal{H}} \left|\mathcal{L}_S(h) - \mathcal{L}_\mathcal{D}(h)\right|$ is concentrated around its expectation (this is a result of McDiarmid’s inequality), this is why you can actually focus on the expected generalization error (if it is low, then with high probability the generalization error itself is low). Apr 11 '17 at 10:26
• Regarding your first questions, I simply put your statement in an intuitive (at least for me) formulation, nothing formal about it. I use the word "close" since $\epsilon_m$ is close to zero for large sample size. I think you have enough information to complete the details yourself, so I encourage you to compare the "stupid" algorithm sample/generalization error. Apr 11 '17 at 10:26