Document Open Access Logo

Finite Sample Differentially Private Confidence Intervals

Authors Vishesh Karwa, Salil Vadhan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.44.pdf
  • Filesize: 466 kB
  • 9 pages

Document Identifiers

Author Details

Vishesh Karwa
Salil Vadhan

Cite As Get BibTex

Vishesh Karwa and Salil Vadhan. Finite Sample Differentially Private Confidence Intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 44:1-44:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.44

Abstract

We study the problem of estimating finite sample confidence intervals of the mean of a normal population under the constraint of differential privacy. We consider both the known and unknown variance cases and construct differentially private algorithms to estimate confidence intervals. Crucially, our algorithms guarantee a finite sample coverage, as opposed to an asymptotic coverage.  Unlike most previous differentially private algorithms, we do not require the domain of the samples to be bounded. We also prove lower bounds on the expected size of any differentially private confidence set showing that our the parameters are optimal up to polylogarithmic factors.

Subject Classification

Keywords
  • Differential Privacy
  • Confidence Intervals
  • Lower bounds
  • Finite Sample

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451, 2014. Google Scholar
  2. Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128-138. ACM, 2005. Google Scholar
  3. Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it: Private and sample efficient identity testing. arXiv preprint arXiv:1703.10127, 2017. Google Scholar
  4. John Duchi, Martin J Wainwright, and Michael I Jordan. Local privacy and minimax bounds: Sharp rates for probability estimation. In Advances in Neural Information Processing Systems, pages 1529-1537, 2013. Google Scholar
  5. John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 429-438. IEEE, 2013. Google Scholar
  6. Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380. ACM, 2009. Google Scholar
  7. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284. Springer, 2006. Google Scholar
  8. Stephen E. Fienberg, Alessandro Rinaldo, and Xiaolin Yang. Differential privacy and the risk-utility tradeoff for multi-dimensional contingency tables. In Proceedings of the 2010 international conference on Privacy in statistical databases, PSD'10, pages 187-199, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1888848.1888869.
  9. Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing. In USENIX Security Symposium, pages 17-32, 2014. Google Scholar
  10. Marco Gaboardi, James Honaker, Gary King, Kobbi Nissim, Jonathan Ullman, and Salil Vadhan. Psi ($$1Psi): a private data sharing interface. arXiv preprint arXiv:1609.04340, 2016. Google Scholar
  11. Marco Gaboardi, Hyun-Woo Lim, Ryan M. Rogers, and Salil P. Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2111-2120. JMLR.org, 2016. URL: http://jmlr.org/proceedings/papers/v48/rogers16.html.
  12. Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. Journal of Machine Learning Research, 14(Feb):703-727, 2013. Google Scholar
  13. Vishesh Karwa, Dan Kifer, and Aleksandra B Slavković. Private posterior distributions from variational approximations. arXiv preprint arXiv:1511.07896, 2015. Google Scholar
  14. Vishesh Karwa and Aleksandra Slavković. Differentially private graphical degree sequences and synthetic graphs. In Privacy in Statistical Databases, pages 273-285. Springer, 2012. Google Scholar
  15. Vishesh Karwa and Aleksandra Slavković. Inference using noisy degrees: Differentially private β-model and synthetic graphs. The Annals of Statistics, 44(1):87-112, 2016. Google Scholar
  16. Vishesh Karwa, Aleksandra B Slavković, and Pavel Krivitsky. Differentially private exponential random graphs. In International Conference on Privacy in Statistical Databases, pages 143-155. Springer, 2014. Google Scholar
  17. Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908, 2017. Google Scholar
  18. Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011. Google Scholar
  19. Daniel Kifer and Ryan Rogers. A new class of private chi-square tests. arXiv preprint arXiv:1610.07662, 2016. Google Scholar
  20. Erich L Lehmann and Joseph P Romano. Testing statistical hypotheses. Springer Science &Business Media, 2006. Google Scholar
  21. Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 3105-3114, 2017. Google Scholar
  22. Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 813-822. ACM, 2011. Google Scholar
  23. Eftychia Solea. Differentially private hypothesis testing for normal random variables. Master’s thesis, Pennsylvania State University, 2014. URL: https://etda.libraries.psu.edu/catalog/21486.
  24. Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In Data Mining Workshops, 2009. ICDMW'09. IEEE International Conference on, pages 138-143. IEEE, 2009. Google Scholar
  25. Yue Wang, Jaewoo Lee, and Daniel Kifer. Differentially private hypothesis testing, revisited. arXiv preprint arXiv:1511.03376, 2015. Google Scholar
  26. Larry Wasserman. Minimaxity, statistical thinking and differential privacy. Journal of Privacy and Confidentiality, 4(1):3, 2012. Google Scholar
  27. Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. J. Amer. Statist. Assoc., 105(489):375-389, 2010. URL: http://dx.doi.org/10.1198/jasa.2009.tm08651.
  28. Oliver Williams and Frank McSherry. Probabilistic inference and differential privacy. In Advances in Neural Information Processing Systems, pages 2451-2459, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact