$\delta=0$ is also referred to as [*pure differential privacy*]{}. Thus, a class ${\mathcal{H}}$ is privately learnable if it is PAC learnable by an algorithm $A$ that is $({\varepsilon}(n),\delta(n))$-differentially private with ${\varepsilon}(n) \leq 0.1$, and $\delta(n) \leq n^{-\omega(1)} $.

Globally-Stable Learning of Littlestone Classes {#sec:LSstable}
===============================================

Theorem Statement
-----------------

The following statement any class ${\mathcal{H}}$ with a bounded Littlestone dimension can be learned by a globally-stable algorithm.

\[thm:littlestone-frequent\] Let ${\mathcal{H}}$ be a hypothesis class with Littlestone dimension $d\geq 1$, let $\alpha>0$, and set $$m = (8^{d+1}+1)\cdot\Bigl\lceil\frac{d}{\alpha}\Bigr\rceil.$$ Then there exists a randomized algorithm $G : (X \times \{\pm 1\})^m \to \{\pm 1\}^X$ with the following properties. Let ${\mathcal{D}}$ be a realizable distribution and let $S\sim {\mathcal{D}}^m$ be an input sample. Then there exists a hypothesis $f$ such $$\Pr[G(S) = f] \geq \frac{1}{(d+1)2^{d+1}} \text{ and } {\operatorname{loss}}_{{\mathcal{D}}}(f) \leq \alpha.$$

The distributions ${\mathcal{D}}_k$
-----------------------------------

The Algorithm $G$ is obtained by running the ${\mathsf{SOA}}$ on a sample drawn from a carefully tailored distribution. This distribution belongs to a family of distributions which we define next. Each of these distributions can be sampled from using black-box access to i.i.d. samples from ${\mathcal{D}}$. Recall that for a pair of samples $S,T$, we denote by $S\circ T$ the 