The Taub Faculty of Computer Science Events and Talks

Differential Privacy (DP) is a mathematical framewirk for ensuring the privacy of individuals in a dataset. Roughly speaking, it guarantees that privacy is protected in data analysis by ensuring that the output of an analysis does not reveal sensitive information about any specific individual, regardless of whether their data is included in the dataset or not.

This talk presents a unified framework for characterizing both pure and approximate differentially private learnabiliity under the PAC model. 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 clique dimension and fractional clique dimension.