Show simple item record

dc.contributor.authorBun, Mark
dc.contributor.authorNissim, Kobbi
dc.contributor.authorStemmer, Uri
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2018-01-09T16:18:53Z
dc.date.issued2015
dc.identifier.citationBun, Mark, Kobbi Nissim, Uri Stemmer, Salil Vadhan. 2015. Differentially private release and learning of threshold functions. IEEE 56th Annual Symposium on Foundations of Computer Science: 634-649. doi:10.1109/FOCS.2015.45.en_US
dc.identifier.isbn978-1-4673-8191-8en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:34614372
dc.description.abstractWe prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function cx over a totally ordered domain X evaluates to cx(y)=1 if y ≤ x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (ε, δ) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n ≥ Ω(log∗ |X|), 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+o(1)) log∗ |X| samples. This improves the previous best upper bound of 8(1+o(1)) log∗ |X| (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 (ε, δ) differential privacy and learning without privacy. For properly learning thresholds in dimensions, this lower bound extends to n ≥ Ω( · log∗ |X|). 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.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.relation.isversionofdoi:10.1109/FOCS.2015.45en_US
dash.licenseOAP
dc.subjectdifferential privacyen_US
dc.subjectPAC learningen_US
dc.subjectlower boundsen_US
dc.subjectthreshold functionsen_US
dc.subjectfingerprinting codesen_US
dc.titleDifferentially Private Release and Learning of Threshold Functionsen_US
dc.typeConference Paperen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journal2015 IEEE 56th Annual Symposium on Foundations of Computer Scienceen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2018-01-09T16:18:53Z
dc.identifier.doi10.1109/FOCS.2015.45*
workflow.legacycommentsoap.needman (MM) Vadhan emailed 2016-04-27 MMen_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record