Journal
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE
Volume -, Issue -, Pages 634-649Publisher
IEEE
DOI: 10.1109/FOCS.2015.45
Keywords
differential privacy; PAC learning; lower bounds; threshold functions; fingerprinting codes
Categories
Funding
- Direct For Computer & Info Scie & Enginr
- Division Of Computer and Network Systems [1237235] Funding Source: National Science Foundation
Ask authors/readers for more resources
We prove new upper and lower bounds on the sample complexity of (epsilon, delta) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c(x) over a totally ordered domain X evaluates to c(x) (y) = 1 if y <= x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (epsilon, delta) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n >= Omega(log*vertical bar X vertical bar), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n <= 2((1+0(1))) log* vertical bar x vertical bar samples. This improves the previous best upper bound of 8(1 +0(1)) log* PC (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with (epsilon, delta) differential privacy and learning without privacy. For properly learning thresholds in l dimensions, this lower bound extends to n >= Omega(l . log* vertical bar X vertical bar). To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential 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