TY - GEN

T1 - Private PAC learning implies finite littlestone dimension

AU - Alon, Noga

AU - Livni, Roi

AU - Malliaris, Maryanthe

AU - Moran, Shay

N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.

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 -