learning algorithm has oracle access, a globally-stable learner is one which is “weakly” pseudo-deterministic in that it produces some fixed output with probability bounded away from zero. A different model of pseudo-deterministic learning, in the context of learning from membership queries, was defined and studied by Oliveira and Santhanam [@OliveiraS18].

We prove Theorem \[thm:main\] by constructing, for a given Littlestone class ${\mathcal{H}}$, an algorithm ${\mathcal{A}}$ which is globally stable with respect to realizable distribution.

### Boosting for Approximate Differential Privacy {#sec:boosting}

Our characterization of private learnability in terms of the Littlestone dimension has new consequences for boosting the privacy and accuracy guarantees of differentially-private learners. Specifically, it shows that the existence of a learner with weak (but non-trivial) privacy and accuracy guarantees implies the existence of a learner with any desired privacy and accuracy parameters — in particular, one with $\delta(n) = \exp(-\Omega(n))$.

\[thm:adp-boost\] There exists a constant $c > 0$ for which the following holds. Suppose that for some sample size $n_0$ there is an $({\varepsilon}_0, \delta_0)$-differentially private learner $\cal W$ for a class ${\mathcal{H}}$ satisfying the guarantee $$\Pr_{S\sim {\mathcal{D}}^{n_0}}[{\operatorname{loss}}_{{\mathcal{D}}}({\cal W}(S)) > \alpha_0 ] < \beta_0$$ for ${\varepsilon}_0 = 0.1, \alpha_0 = \beta_0 = 1/16$, and $\delta_0 \le c/n_0^2\log 