following form of stability: for $\eta > 0$ and $n\in\mathbb{N}$, a learning algorithm ${\mathcal{A}}$ is [*$(n,\eta)$-globally stable*]{}[^4] with respect to a distribution ${\mathcal{D}}$ over examples if there exists an hypothesis $h$ whose frequency as an output is at least $\eta$. Namely, $$\Pr_{S\sim {\mathcal{D}}^n}[{\mathcal{A}}(S) = h] \geq \eta.$$ Our argument follows by showing that every ${\mathcal{H}}$ can be learned by a globally-stable algorithm with parameters $\eta = \exp(-d), n=\exp(d)$, where $d$ is the Littlestone dimension of ${\mathcal{H}}$. As a corollary, we get an equivalence between global stability and differential privacy (which can be viewed as a form of local stability). That is, the existence of a globally stable learner for ${\mathcal{H}}$ is equivalent to the existence of a differentially-private learner for it (and both are equivalent to having a finite Littlestone dimension).

#### Littlestone Classes.

It is natural to ask which classes have finite Littlestone dimension. First, note that every finite class ${\mathcal{H}}$ has Littlestone dimension $d \leq \log\lvert {\mathcal{H}}\rvert$. There are also many natural and interesting infinite classes with finite Littlestone dimension. For example, let $X=\mathbb{F}^n$ be an $n$-dimensional vector space over a field $\mathbb{F}$ and let ${\mathcal{H}}\subseteq\{\pm 1\}^X$ consist of all (indicators of) affine subspaces of dimension $\leq d$. 