Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?

What is the optimal sample complexity of differentially private (DP) PAC learning? Recent results establish that a concept class $C$ is learnable under approximate DP if and only if it is online learnable. However, in any realistic computational model, $C$ is finite, and it is well known that a sample complexity of $O(\log |C|)$ suffices for both online and DP learning. In contrast, non-private learning is characterized by the VC dimension of $C$, which can be significantly lower than $\log |C|$. While the gap between $\log |C|$ and $\text{VC}(C)$ can be unavoidable for online learning (e.g., when learning thresholds over a finite domain), we currently lack evidence that the same holds true for DP learning. This leads to our central question: Is differentially private PAC learning much harder than non-private learning?