n_0$.

Then there exists a constant $C_{\mathcal{H}}$ such that for every $\alpha, \beta, {\varepsilon}, \delta \in (0, 1)$ there exists an $({\varepsilon}, \delta)$-differentially private learner for ${\mathcal{H}}$ with $$\Pr_{S\sim {\mathcal{D}}^{n}}[{\operatorname{loss}}_{{\mathcal{D}}}({{\mathcal{A}}}(S)) > \alpha] < \beta$$ whenever $n \ge C_{\mathcal{H}}\cdot \log(1/\beta\delta)/\alpha{\varepsilon}$.

Given a weak learner $\cal W$ as in the statement of Theorem \[thm:adp-boost\], the results of [@AlonLMM19] imply that ${\operatorname{Ldim}}({\mathcal{H}})$ is finite. Hence Theorem \[thm:main\] allows us to construct a learner for ${\mathcal{H}}$ with arbitrarily small privacy and accuracy, yielding Theorem \[thm:adp-boost\]. The constant $C_{{\mathcal{H}}}$ in the last line of the theorem statement suppresses a factor depending on ${\operatorname{Ldim}}({\mathcal{H}})$.

Prior to our work, it was open whether arbitrary learning algorithms satisfying approximate differential privacy could be boosted in this strong a manner. We remark, however, that in the case of *pure* differential privacy, such boosting can be done algorithmically and efficiently. Specifically, given an $({\varepsilon}_0, 0)$-differentially private weak learner as in the statement of Theorem \[thm:adp-boost\], one can first apply random sampling to improve the privacy guarantee to $(p{\varepsilon}_0, 0)$-differential privacy at the expense of increasing its sample complexity to roughly $n_0 /p$ for any $p \in (0, 1)$. The Boosting-for-People construction of Dwork, Rothblum, and Vadhan [@DworkRV10] (see also [@BunCS20]) 