# 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? – Ariel Apr 10 '17 at 15:32

## 1 Answer

$\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? – Josef 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. – Josef 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. – Josef 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). – Ariel 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. – Ariel Apr 11 '17 at 10:26