generalizes “Occam’s Razor" for finite hypothesis classes to show that global stability is enough to imply similar generalization bounds in the realizable setting.

\[prop:gs\] Let ${\mathcal{H}}\subseteq\{\pm 1\}^X$ be a class, and assume that ${\mathcal{A}}$ is a learner for ${\mathcal{H}}$ (i.e. ${\operatorname{loss}}_S({\mathcal{A}}(S))=0$ for every realizable sample $S$). Let ${\mathcal{D}}$ be a realizable distribution such that ${\mathcal{A}}$ is $(n,\eta)$-globally-stable with respect to ${\mathcal{D}}$, and let $h$ be a hypothesis such that $\Pr_{S\sim{\mathcal{D}}^n}[A(S) = h] \geq \eta$, as guaranteed by the definition of global stability. Then, $${\operatorname{loss}}_{\mathcal{D}}(h) \leq \frac{\ln(1/\eta)}{n}.$$

Let $\alpha$ denote the loss of $h$, i.e. ${\operatorname{loss}}_{\mathcal{D}}(h) = \alpha$, and let $E_1$ denote the event that $h$ is consistent with the input sample $S$. Thus, $\Pr[E_1] = (1-\alpha)^n$. Let $E_2$ denote the event that ${\mathcal{A}}(S)=h$. By assumption, $\Pr[E_2]\geq \eta$. Now, since ${\mathcal{A}}$ is consistent we get that $E_2\subseteq E_1$, and hence that $\eta\leq(1-\alpha)^n$. This finishes the proof (using the fact that $1-\alpha \leq e^{-\alpha}$ and taking the logarithm of both sides).

Another way to view global stability is in the context of *pseudo-deterministic algorithms* [@Gat11pseudo]. A pseudo-deterministic algorithm is a randomized algorithm which yields some fixed output with high probability. Thinking of a realizable distribution ${\mathcal{D}}$ as an instance on which PAC 