Differential Privacy and the Fat-Shattering Dimension of Linear Queries | SpringerLink
Skip to main content
Springer Nature Link
Log in

Differential Privacy and the Fat-Shattering Dimension of Linear Queries

  • Conference paper
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM 2010, APPROX 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6302))

Abstract

In this paper, we consider the task of answering linear queries under the constraint of differential privacy. This is a general and well-studied class of queries that captures other commonly studied classes, including predicate queries and histogram queries. We show that the accuracy to which a set of linear queries can be answered is closely related to its fat-shattering dimension, a property that characterizes the learnability of real-valued functions in the agnostic-learning setting.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alon, N., Ben David, S., Cesa Bianchi, N., Haussler, D.: Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM) 44(4), 615–631 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Beimel, A., Kasiviswanathan, S., Nissim, K.: Bounds on the sample complexity for private learning and private data release. In: Micciancio, D. (ed.) Theory of Cryptography. LNCS, vol. 5978, pp. 437–454. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  3. Bartlett, P.L., Long, P.M.: More theorems about scale-sensitive dimensions and learning. In: Proceedings of the eighth annual conference on Computational learning theory, pp. 392–401. ACM, New York (1995)

    Chapter  Google Scholar 

  4. Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 609–618. ACM, New York (2008)

    Google Scholar 

  5. Bartlett, P.L., Long, P.M., Williamson, R.C.: Fat-shattering and the learnability of real-valued functions. In: Proceedings of the seventh annual conference on Computational learning theory, pp. 299–310. ACM, New York (1994)

    Chapter  Google Scholar 

  6. Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  7. Dwork, C., McSherry, F., Talwar, K.: The price of privacy and the limits of LP decoding. In: Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing, p. 94. ACM, New York (2007)

    Google Scholar 

  8. Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 202–210 (2003)

    Google Scholar 

  9. Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, pp. 381–390. ACM, New York (2009)

    Chapter  Google Scholar 

  10. Dwork, C., Yekhanin, S.: New efficient attacks on statistical disclosure control mechanisms. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 469–480. Springer, Heidelberg (2008)

    Google Scholar 

  11. Hardt, M., Talwar, K.: On the Geometry of Differential Privacy. In: The 42nd ACM Symposium on the Theory of Computing, STOC 2010 (2010)

    Google Scholar 

  12. Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What Can We Learn Privately? In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 531–540 (2008)

    Google Scholar 

  13. Kasiviswanathan, S., Rudelson, M., Smith, A., Ullman, J.: The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows. In: The 42nd ACM Symposium on the Theory of Computing, STOC 2010 (2010)

    Google Scholar 

  14. Kearns, M.J., Schapire, R.E.: Efficient distribution-free learning of probabilistic concepts*. Journal of Computer and System Sciences 48(3), 464–497 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  15. McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: Proceedings of the 48th Annual Symposium on Foundations of Computer Science (2007)

    Google Scholar 

  16. Nissim, K., Raskhodnikova, S., Smith, A.: Smooth sensitivity and sampling in private data analysis. In: Annual ACM Symposium on Theory of Computing: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. Association for Computing Machinery, Inc., New York (2007)

    Google Scholar 

  17. Roth, A., Roughgarden, T.: Interactive Privacy via the Median Mechanism. In: The 42nd ACM Symposium on the Theory of Computing, STOC 2010 (2010)

    Google Scholar 

  18. Ullman, J., Vadhan, S.: PCPs and the Hardness of Generating Synthetic Data (manuscript) (2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Carnegie Mellon University and Microsoft Research, New England

    Aaron Roth

Authors
  1. Aaron Roth
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universitat Politecnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, Campus Nord - Ed Omega, Desp. 235, Jordi Girona, 1-3, 08034, Barcelona, Spain

    Maria Serna

  2. Department of Computer Science, University of Haifa, Mount Carmel, 31905, Haifa, Israel

    Ronen Shaltiel

  3. Department of Computer Science, University of Kiel, Olshausenstrasse 40, 24098, Kiel, Germany

    Klaus Jansen

  4. University of Geneva, Centre Universitaire d’Informatique, Battelle Bat. A, 7 rte de Drize, 1227, Carouge, Switzerland

    José Rolim

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Roth, A. (2010). Differential Privacy and the Fat-Shattering Dimension of Linear Queries. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_51

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-15369-3_51

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-15368-6

  • Online ISBN: 978-3-642-15369-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation