Does Differential Privacy Make PAC Learning Much Harder?

For a concept class $\mathcal C$, let $\operatorname{SC}_{\mathrm{DP}}(\mathcal C)$ denote its approximate-differentially-private PAC sample complexity, suppressing dependence on fixed privacy, accuracy, and confidence parameters. Let $\log^*$ denote the iterated logarithm.

1. Characterize the sample complexity of private learning: identify a combinatorial measure of $\mathcal C$ that determines $\operatorname{SC}_{\mathrm{DP}}(\mathcal C)$, analogously to the characterization of non-private learning by VC dimension. In particular, can private PAC learning be tightly characterized in terms of $\operatorname{VC}(\mathcal C)$ and $\operatorname{LD}(\mathcal C)$? An intermediate goal is a generic upper bound such as

$$\operatorname{poly}\!\left( \operatorname{VC}(\mathcal C), \log^*\!\operatorname{LD}(\mathcal C) \right),$$

or even $\operatorname{poly}(\operatorname{VC}(\mathcal C),\log\operatorname{LD}(\mathcal C))$.

1. Does there exist a sequence of finite concept classes $\{\mathcal C_k\}_{k\in\mathbb N}$ such that

2. $\lim_{k\to\infty}|\mathcal C_k|=\infty$;

3. $\log|\mathcal C_k|$ is superpolynomial in $\operatorname{VC}(\mathcal C_k)$; and

4. $\operatorname{SC}_{\mathrm{DP}}(\mathcal C_k)=\Omega(\log|\mathcal C_k|)$?

For the second question, an intermediate step is a sequence satisfying the first two conditions whose private sample complexity is closer to $\log|\mathcal C|$ than to $\operatorname{VC}(\mathcal C)$ on a logarithmic, or even a log-logarithmic, scale. The reference quantity $\log|\mathcal C|$ may also be replaced by $\operatorname{LD}(\mathcal C)$ or $\operatorname{poly}(\operatorname{LD}(\mathcal C))$.