then produces a strong learner by making roughly $T \approx \log(1/\beta)/\alpha^2$ calls to the weak learner. By composition of differential privacy, this gives an $({\varepsilon}, 0)$-differentially private strong learner with sample complexity roughly $n_0 \cdot \log(1/\beta)/\alpha^2{\varepsilon}$.

What goes wrong if we try to apply this argument using an $({\varepsilon}_0, \delta_0)$-differentially private weak learner? Random sampling still gives a $(p{\varepsilon}_0, p\delta_0)$-differentially private weak learner with sample complexity $n_0 / p$. However, this is not sufficient to improve the $\delta$ parameter of the learner *as a function of the number of samples $n$*. Thus the strong learner one obtains using Boosting-for-People still at best guarantees $\delta(n) = \tilde{O}(1/n^2)$. Meanwhile, Theorem \[thm:adp-boost\] shows that the existence of a $(0.1, \tilde{O}(1/n^2))$-differentially private learner for a given class implies the existence of a $(0.1, \exp(-\Omega(n))$-differentially private learner for that class.

We leave it as an interesting open question to determine whether this kind of boosting for approximate differential privacy can be done algorithmically.

Proof Overview {#sec:overview}
==============

We next give an overview of the main arguments used in the proof of Theorem \[thm:main\]. The proof consist of two parts: (i) we first show that every class with a finite Littlestone dimension can be learned by 