Private PAC learning implies finite littlestone dimension

Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension d requires Ωlog(d) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open questions due to [Bun et al. 2015] and [Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages852-860
Number of pages9
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period6/23/196/26/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Differential Privacy
  • Littlestone dimension
  • PAC learning

Fingerprint Dive into the research topics of 'Private PAC learning implies finite littlestone dimension'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Livni, R., Malliaris, M., & Moran, S. (2019). Private PAC learning implies finite littlestone dimension. In M. Charikar, & E. Cohen (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 852-860). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316312