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

Abstract

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 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?