Moritz Hardt
ABSTRACT
We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:Rn -> R non-adaptively. Here, the database is represented by a vector in R and proximity between databases is measured in the l1-metric. We show that the noise complexity is determined by two geometric parameters associated with the set of queries. We use this connection to give tight upper and lower bounds on the noise complexity for any d ≤ n. We show that for d random linear queries of sensitivity 1, it is necessary and sufficient to add l2-error Θ(min d√d/ε,d√(log (n/d))/ε) to achieve ε-differential privacy. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds.
Our bound translates to error $O(min d/ε,√(d log(n/d)/ε)) per answer. The best previous upper bound (Laplacian mechanism) gives a bound of O(min (d/ε,√n/ε)) per answer, while the best known lower bound was Ω(√d/ε).
In contrast, our lower bound is strong enough to separate the concept of differential privacy from the notion of approximate differential privacy where an upper bound of O(√{d}/ε) can be achieved.
- B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In Proc. $26$th PODS, pages 273--282. ACM, 2007. Google Scholar
Digital Library
- I. Barany and Z. Furedi. Approximation of the sphere by polytopes having few vertices. Proceedings of the American Mathematical Society, 102(3):651--659, 1988.Google ScholarCross Ref
- A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the sulq framework. In PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128--138, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In STOC '08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 609--618, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), pages 289--296, 2008.Google Scholar
- I. Dinur and K. Nissim. Revealing information while preserving privacy. In Proc. $22$nd PODS, pages 202--210. ACM, 2003. Google ScholarDigital Library
- C. Dwork. Differential privacy: A survey of results. In Proc. 5th TAMC, pages 1--19. Springer, 2008. Google ScholarDigital Library
- C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Proc. 25th EUROCRYPT, pages 486--503. Springer, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proc. $3$rd TCC, pages 265--284. Springer, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of LP decoding. In Proc. 39th STOC, pages 85--94. ACM, 2007. Google ScholarDigital Library
- C. Dwork and S. Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In Proc. 28th CRYPTO, pages 469--480. Springer, 2008. Google ScholarDigital Library
- M. E. Dyer, A. M. Frieze, and R. Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1--17, 1991. Google ScholarDigital Library
- D. Feldman, A. Fiat, H. Kaplan, and K. Nissim. Private coresets. In Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, pages 361--370. ACM New York, NY, USA, 2009. Google ScholarDigital Library
- A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In STOC, pages 351--360, 2009. Google ScholarDigital Library
- A. Giannopoulos. Notes on isotropic convex bodies. Preprint, 2003.Google Scholar
- A. Gupta, K. Ligett, F. McSherry, A. Roth, and K. Talwar. Differentially private approximation algorithms. In Proceedings of the Twenty First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010. To appear.Google Scholar
- R. Kannan, L. Lovász, and M. Simonovits. Random walks and an o*(n5) volume algorithm for convex bodies. Random Struct. Algorithms, 11(1):1--50, 1997. Google ScholarDigital Library
- S. Kasiviswanathan, M. Rudelson, and A. Smith. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. Manuscript, 2009.Google Scholar
- S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 531--540, Washington, DC, USA, 2008. IEEE Computer Society. Google ScholarDigital Library
- B. Klartag. On convex perturbations with a bounded isotropic constant. Geometric and Functional Analysis (GAFA), 16(6):1274--1290, December 2006.Google Scholar
- B. Klartag and G. Kozma. On the hyperplane conjecture for random convex sets. Israel Journal of Mathematics, 170(1):253--268, 2009.Google ScholarCross Ref
- A. E. Litvak, A. Pajor, M. Rudelson, and T.-J. N. Smallest singular value of random matrices and geometry of random polytopes. Adv. Math., 195(2):491--523, 2005.Google ScholarCross Ref
- F. McSherry and I. Mironov. Differentially private recommender systems: building privacy into the net. In Proc. 15th KDD, pages 627--636. ACM, 2009. Google ScholarDigital Library
- F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proc. 48th FOCS, pages 94--103. IEEE, 2007. Google ScholarDigital Library
- V. Milman and A. Pajor. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space. Geometric Aspects of Functional Analysis, 1376:64--104, 1989.Google ScholarCross Ref
- K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75--84, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- V. Rastogi, D. Suciu, and S. Hong. The boundary between privacy and utility in data publishing. In VLDB '07: Proceedings of the 33rd international conference on Very large data bases, pages 531--542. VLDB Endowment, 2007. Google ScholarDigital Library
- S. Vempala. Geometric random walks: a survey. MSRI Volume on Combinatorial and Computational Geometry, 52:577--616, 2005.Google Scholar
Index Terms
- On the geometry of differential privacy
Recommendations
The geometry of differential privacy: the sparse and approximate cases
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingWe study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been the focus of a long line of work. For a given set of d ...
Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms
AbstractDifferential privacy can achieve the tradeoff between privacy and utility by using privacy metric and utility metric. However, since privacy metric and utility metric may not be bounded, differential privacy can not provide the bounded ...
The Geometry of Differential Privacy: The Small Database and Approximate Cases
In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been a focus of a long line of work. For a given set ...
Comments