(the next one would be that $\Pr[M=d-2] \geq \frac{1}{2d}$, and so on). The proof we present in Section \[sec:LSstable\] is based on a similar idea of performing “random contests,” although the construction becomes more complex to handle other issues, such as generalization, which were not addressed here. For more details we refer the reader to the complete argument in Section \[sec:LSstable\].

Step 2: Globally-Stable Learning $\implies$ Differentially-Private Learning
---------------------------------------------------------------------------

Given a globally-stable learner ${\mathcal{A}}$ for a concept class ${\mathcal{H}}$, we can obtain a differentially-private learner using standard techniques in the literature on private learning and query release. If ${\mathcal{A}}$ is a $(\eta, m)$-globally stable learner with respect to a distribution ${\mathcal{D}}$, we obtain a differentially-private learner using roughly $m/\eta$ samples from that distribution as follows. We first run ${\mathcal{A}}$ on $k \approx 1/\eta$ independent samples, non-privately producing a list of $k$ hypotheses. We then apply a differentially-private “Stable Histograms” algorithm [@KorolovaKMN09; @BunNS16] to this list which allows us to privately publish a short list of hypotheses that appear with frequency $\Omega(\eta)$. Global stability of the learner ${\mathcal{A}}$ guarantees that with high probability, this list contains *some* hypothesis $h$ with small population loss. We can then apply a generic differentially-private learner 