Private PAC learning implies finite littlestone dimension

Noga Alon; Roi Livni; Maryanthe Malliaris; Shay Moran

doi:10.1145/3313276.3316312

Private PAC learning implies finite littlestone dimension

Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

64 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 language	English (US)
Title of host publication	STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
Editors	Moses Charikar, Edith Cohen
Publisher	Association for Computing Machinery
Pages	852-860
Number of pages	9
ISBN (Electronic)	9781450367059
DOIs	https://doi.org/10.1145/3313276.3316312
State	Published - Jun 23 2019
Event	51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States Duration: Jun 23 2019 → Jun 26 2019

Publication series

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

Conference

Conference	51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Country/Territory	United States
City	Phoenix
Period	6/23/19 → 6/26/19

All Science Journal Classification (ASJC) codes

Software

Keywords

Differential Privacy
Littlestone dimension
PAC learning

Access to Document

10.1145/3313276.3316312

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

@inproceedings{07c686a00c6846a8bc85090e835e1c47,

title = "Private PAC learning implies finite littlestone dimension",

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.",

keywords = "Differential Privacy, Littlestone dimension, PAC learning",

author = "Noga Alon and Roi Livni and Maryanthe Malliaris and Shay Moran",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

year = "2019",

month = jun,

day = "23",

doi = "10.1145/3313276.3316312",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "852--860",

editor = "Moses Charikar and Edith Cohen",

booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

}

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. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 852-860, 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, United States, 6/23/19. https://doi.org/10.1145/3313276.3316312

Private PAC learning implies finite littlestone dimension. / Alon, Noga; Livni, Roi; Malliaris, Maryanthe et al.
STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ed. / Moses Charikar; Edith Cohen. Association for Computing Machinery, 2019. p. 852-860 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Private PAC learning implies finite littlestone dimension

AU - Alon, Noga

AU - Livni, Roi

AU - Malliaris, Maryanthe

AU - Moran, Shay

PY - 2019/6/23

Y1 - 2019/6/23

N2 - 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.

AB - 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.

KW - Differential Privacy

KW - Littlestone dimension

KW - PAC learning

UR - http://www.scopus.com/inward/record.url?scp=85068736790&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068736790&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316312

DO - 10.1145/3313276.3316312

M3 - Conference contribution

AN - SCOPUS:85068736790

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 852

EP - 860

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

Y2 - 23 June 2019 through 26 June 2019

ER -

Private PAC learning implies finite littlestone dimension

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this