In this talk, we ask what types of *learning* problems can be solved (and their results, published) while preserving differential privacy privacy. Learning problems form an important category of computational tasks that includes many of the computations applied to large, real-life datasets.
Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. Specifically, we provide:
(1) A generic, distribution-free private learning algorithm that uses approximately log|C| samples to learn a concept class C. This is a private analogue of Occam's razor. The generic learner is not always computationally efficient.
(2) A computationally efficient, distribution-free private PAC learner for the class of parity functions.
(3) A precise characterization of local, or randomized response, private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model.
(4) A separation between the power of interactive and noninteractive local learning algorithms. Because of the equivalence to SQ learning, this result also separates adaptive and nonadaptive SQ learning.
Based on joint work with Shiva Kasivswanathan, Homin Lee, Kobbi Nissim and Adam Smith
Copyright. All Rights Reserved.