Document Open Access Logo

Differentially Private Approximations of a Convex Hull in Low Dimensions

Authors Yue Gao, Or Sheffet

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITC.2021.18.pdf
  • Filesize: 1.05 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory of database privacy and security
Keywords
  • Differential Privacy
  • Computational Geometry
  • Tukey Depth

Metrics

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

Abstract

We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball, etc. Our work relies heavily on the notion of Tukey-depth. Instead of (non-privately) approximating the convex-hull of the given set of points P, our algorithms approximate the geometric features of D_{P}(κ) - the κ-Tukey region induced by P (all points of Tukey-depth κ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature μ our (α,Δ)-approximation is a value "sandwiched" between (1-α)μ(D_P(κ)) and (1+α)μ(D_P(κ-Δ)).
Our work is aimed at producing a (α,Δ)-kernel of D_P(κ), namely a set 𝒮 such that (after a shift) it holds that (1-α)D_P(κ) ⊂ CH(𝒮) ⊂ (1+α)D_P(κ-Δ). We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by [Pankaj K. Agarwal et al., 2004], fails to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find (α,Δ)-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn D_P(κ) into a "fat" region but only if its volume is proportional to the volume of D_P(κ-Δ). Lastly, we give a novel private algorithm that finds a depth parameter κ for which the volume of D_P(κ) is comparable to the volume of D_P(κ-Δ). We hope our work leads to the further study of the intersection of differential privacy and computational geometry.

Cite As Get BibTex

Yue Gao and Or Sheffet. Differentially Private Approximations of a Convex Hull in Low Dimensions. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.18

Author Details

Yue Gao
  • Department of Computing Science, University of Alberta, Edmonton, Canada
Or Sheffet
  • Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel

Funding

Much of this work was done when the first author was adviced by the second author, and was supported by grant #2017–06701 of the Natural Sciences and Engineering Research Council of Canada (NSERC). In addition, this work was partially done when O.S. was a participant of the Simons' Institute for the Theory of Computing program of Data-Privacy. O.S. is supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office, and by ISF grant no. 2559/20.

Acknowledgements

Both authors thank the anonymous reviewers for many helpful suggestions in improving this paper.

References

  1. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606-635, 2004. Google Scholar
  2. Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Daniel Wichs and Yishay Mansour, editors, Symposium on Theory of Computing, STOC, pages 1046-1059. ACM, 2016. Google Scholar
  3. Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. In COLT, pages 269-282, 2019. Google Scholar
  4. Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 363-378. Springer, 2013. Google Scholar
  5. Victor-Emmanuel Brunel. Concentration of the empirical level sets of tukey’s halfspace depth. Probability Theory and Related Fields, 173(3-4):1165-1196, 2019. Google Scholar
  6. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634-649, 2015. Google Scholar
  7. Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Symposium on Discrete Algorithms, SODA, pages 1306-1325. SIAM, 2017. Google Scholar
  8. Michael A. Burr and Robert J. Fabrizio. Uniform convergence rates for halfspace depth. Statistics & Probability Letters, 124(C):33-40, 2017. Google Scholar
  9. Timothy M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl., 12(1-2):67-85, 2002. Google Scholar
  10. C. Dwork, F. Mcsherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006. Google Scholar
  11. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science (New York, N.Y.), 349(6248):636-638, August 2015. URL: http://www.sciencemag.org/content/349/6248/636.
  12. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006. Google Scholar
  13. Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51-60. IEEE Computer Society, 2010. Google Scholar
  14. Herbert Edelsbrunner. Algorithms in combinatorial geometry. Monographs in Theoretical Computer Science (10). Springer-Verlag, 1 edition, 1987. Google Scholar
  15. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, NeurIPS, 2020. Google Scholar
  16. Sariel Har-peled. Geometric Approximation Algorithms. American Mathematical Society, USA, 2011. Google Scholar
  17. Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Conference on Learning Theory, COLT, volume 100 of Proceedings of Machine Learning Research. PMLR, 2020. Google Scholar
  18. Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Differentially private learning of geometric concepts. In International Conference on Machine Learning, ICML, volume 97 of Proceedings of Machine Learning Research, pages 3233-3241. PMLR, 2019. Google Scholar
  19. Haim Kaplan, Micha Sharir, and Uri Stemmer. How to find a point in the convex hull privately. In International Symposium on Computational Geometry (SoCG), volume 164 of LIPIcs, pages 52:1-52:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  20. Xiaohui Liu, Karl Mosler, and Pavlo Mozharovskyi. Fast computation of tukey trimmed regions and median in dimension p > 2. Journal of Computational and Graphical Statistics, 28(3):682-697, 2019. Google Scholar
  21. K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In STOC, pages 75-84. ACM, 2007. Full version in: URL: http://www.cse.psu.edu/~asmith/pubs/NRS07.
  22. Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. In ALT, pages 619-653, 2018. Google Scholar
  23. Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Locating a small cluster privately. In PODS, pages 413-427, 2016. Google Scholar
  24. Peter J Rousseeuw and Ida Ruts. Constructing the bivariate tukey median. Statistica Sinica, 8(3):827-839, 1998. Google Scholar
  25. Haruyuki Sanuki, Rui Fukui, Tsukasa Inajima, and Shin'ichi Warisawa. Cuff-less calibration-free blood pressure estimation under ambulatory environment using pulse wave velocity and photoplethysmogram signals. In BIOSIGNALS, 2017. Google Scholar
  26. J. W. Tukey. Mathematics and the picturing of data. Proceedings of the International Congress of Mathematicians, 2:523-531, 1975. Google Scholar
  27. Gary M. Weiss, Kenichi Yoneda, and Thaier Hayajneh. Smartphone and smartwatch-based biometrics using activities of daily living. IEEE Access, 7:133190-133202, 2019. Google Scholar
  28. Yijun Zuo and Robert Serfling. Structural properties and convergence results for contours of sample statistical depth functions. Ann. Statist., 28(2):483-499, April 2000. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact