perspective, and should not be regarded as an efficient transformation between online and private learning. Indeed, the Littlestone dimension dependencies concealed by the $\tilde \Theta_d(\cdot)$ in the above bounds on the regret and sample complexities may be very different from one another. For example, there are classes for which the $\Theta_d(\frac{\log({1}/(\beta\delta))}{\alpha{\varepsilon}})$ bound hides a $\mathrm{poly}(\log^*(d))$ dependence, and the $\tilde \Theta_d(\sqrt{T})$ bound hides a $\Theta(d)$ dependence. One example which attains both of these dependencies is the class of thresholds over a linearly ordered domain of size $2^d$ [@AlonLMM19; @kaplan2019privately].

### Global Stability {#sec:stability}

Our proof of Theorem \[thm:main\], which establishes that every Littlestone class can be learned privately, hinges on an intermediate property which we call [*global stability*]{}:

Let $n\in\mathbb{N}$ be a sample size and $\eta > 0$ be a global stability parameter. An algorithm ${\mathcal{A}}$ is $(n,\eta)$-globally-stable with respect to a distribution ${\mathcal{D}}$ if there exists an hypothesis $h$ such that $$\Pr_{S\sim{\mathcal{D}}^n}[A(S) = h] \geq \eta.$$

While global stability is a rather strong property, it holds automatically for learning algorithms using a finite hypothesis class. By an averaging argument, every learner using $n$ samples which produces a hypothesis in a finite hypothesis class ${\mathcal{H}}$ is $(n, 1/|{\mathcal{H}}|)$-globally-stable. The following proposition 