Journal
THEORY OF COMPUTING
Volume 12, Issue -, Pages -Publisher
UNIV CHICAGO, DEPT COMPUTER SCIENCE
DOI: 10.4086/toc.2016.v012a001
Keywords
differential privacy; sample complexity; private learning; sanitization
Categories
Funding
- Israeli Science and Technology ministry
- Israel Science Foundation [938/09, 2761/12]
- NSF [CNS-1237235]
- Ministry of Science and Technology (Israel)
- Check Point Institute for Information Security
- IBM PhD Fellowship Awards Program
Ask authors/readers for more resources
We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization [Blum et al. 2008] under pure epsilon-differcntial privacy [Dwork et al. TCC 2006] and approximate (epsilon, delta)-differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy. We define a family of optimization problems, which we call Quasi-Concave Promise Problems, that generalizes some of the tasks we consider. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm to solve such problems privately. Specifically, we construct private learners for point functions, threshold functions, and axis-aligned rectangles in high dimension. Similarly, we construct sanitizers for point functions and threshold functions. We also examine the sample complexity of label-private learners, a relaxation of private learning where the learner is required to only protect the privacy of the labels in the sample. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available