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.
$\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).