Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: A Unified Characterization Of Private Learning
event speaker icon
Hilla Schefler (Technion)
event date icon
Wednesday, 13.03.2024, 12:15
event location icon
Taub 201
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.