Locating a Small Cluster Privately

ABSTRACT

We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal of outliers. Furthermore, we use it to significantly relax the requirements of the sample and aggregate technique [Nissim, Raskhodnikova, and Smith, 2007], which allows compiling of "off the shelf" (non-private) analyses into analyses that preserve differential privacy.

References

1. P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Geometric approximation via coresets. In COMBINATORIAL AND COMPUTATIONAL GEOMETRY, MSRI, pages 1--30. University Press, 2005.
2. R. Bassily, K. Nissim, A. D. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. STOC (to appear), 2016.
3. A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In APPROX-RANDOM, volume 8096 of Lecture Notes in Computer Science, pages 363--378. Springer, 2013.
4. M. Bun, K. Nissim, U. Stemmer, and S. P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634--649, 2015.
5. C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. Preserving statistical validity in adaptive data analysis. In STOC, pages 117--126. ACM, 2015.
6. C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In S. Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 486--503. Springer, 2006.
7. C. Dwork and J. Lei. Differential privacy and robust statistics. In M. Mitzenmacher, editor, STOC, pages 371--380. ACM, 2009.
8. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876 of Lecture Notes in Computer Science, pages 265--284. Springer, 2006.
9. C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In M. Mitzenmacher, editor, STOC, pages 381--390. ACM, 2009.
10. C. Dwork, G. N. Rothblum, and S. P. Vadhan. Boosting and differential privacy. In FOCS, pages 51--60. IEEE Computer Society, 2010.
11. W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space. 1984.
12. S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM J. Comput., 40(3):793--826, 2011.
13. B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302--1338, 10 2000.
14. F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94--103. IEEE Computer Society, 2007.
15. P. Mohan, A. Thakurta, E. Shi, D. Song, and D. E. Culler. GUPT: privacy preserving data analysis made easy. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20--24, 2012, pages 349--360, 2012.
16. K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In STOC, pages 75--84. ACM, 2007.
17. V. Shenmaier. The problem of a minimal ball enclosing k points. Journal of Applied and Industrial Mathematics, 7(3):444--448, 2013.
18. A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6--8 June 2011, pages 813--822, 2011.
19. A. Thakurta and A. Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In S. Shalev-Shwartz and I. Steinwart, editors, COLT, volume 30 of JMLR Proceedings, pages 819--850. JMLR.org, 2013.
20. S. Vadhan. The Complexity of Differential Privacy. 2016.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Security and privacy

  • Security services

    • Privacy-preserving protocols