\[sec:preliminaries\].

\[thm:main\] Let ${\mathcal{H}}\subseteq\{\pm 1\}^X$ be a class with Littlestone dimension $d$, let ${\varepsilon},\delta \in (0, 1)$ be privacy parameters, and let $\alpha,\beta \in (0, 1/2)$ be accuracy parameters. For $$n = O\left(\frac{16^d \cdot d^2 \cdot (d + \log(1/\beta\delta))}{\alpha{\varepsilon}}\right) = O_d\left(\frac{\log(1/\beta\delta)}{\alpha{\varepsilon}}\right)$$ there exists an $({\varepsilon},\delta)$-DP learning algorithm such that for every realizable distribution ${\mathcal{D}}$, given an input sample $S\sim {\mathcal{D}}^n$, the output hypothesis $f={\mathcal{A}}(S)$ satisfies ${\operatorname{loss}}_{{\mathcal{D}}}(f)\leq \alpha$ with probability at least $1-\beta$, where the probability is taken over $S\sim {\mathcal{D}}^n$ as well as the internal randomness of ${\mathcal{A}}$.

A similar result holds in the agnostic setting:

\[thm:agnostic\] Let ${\mathcal{H}}\subseteq\{\pm 1\}^X$ be a class with Littlestone dimension $d$, let ${\varepsilon}$, and $\delta \in (0, 1)$ be privacy parameters, and let $\alpha,\beta \in (0, 1/2)$ be accuracy parameters. For $$n = O\left(\frac{16^d \cdot d^2 \cdot (d + \log(1/\beta\delta))}{\alpha\epsilon} +\frac{\textrm{VC}({\mathcal{H}})+\log 1/\beta}{\alpha^2\epsilon} \right)$$ there exists an $({\varepsilon},\delta)$-DP learning algorithm such that for every distribution ${\mathcal{D}}$, given an input sample $S\sim {\mathcal{D}}^n$, the output hypothesis $f={\mathcal{A}}(S)$ satisfies $${\operatorname{loss}}_{{\mathcal{D}}}(f)\leq \min_{h\in {\mathcal{H}}} {\operatorname{loss}}_{{\mathcal{D}}}(h)+ \alpha$$ with probability at least $1-\beta$, where the probability is taken over $S\sim {\mathcal{D}}^n$ as well as the internal randomness of ${\mathcal{A}}$.

follows from by Theorem 2.3 in [@alon2020closure] which provides a general mechanism 