Total: 1
We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class H, we define the contradiction graph G of H. Its vertices are realizable datasets and two datasets S,S′ are connected by an edge if they contradict each other (i.e., there is a point x that is labeled differently in S and S′). Our main finding is that the combinatorial structure of G is deeply related to learning H under DP. Learning H under pure DP is captured by the fractional clique number of G. Learning H under approximate DP is captured by the clique number of G. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.