TY - JOUR

T1 - Closure Properties for Private Classification and Online Prediction

AU - Alon, Noga

AU - Beimel, Amos

AU - Moran, Shay

AU - Stemmer, Uri

N1 - Funding Information:
∗Department of Mathematics, Princeton University, Princeton, New Jersey, USA and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, Israel. Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267, and the Simons Foundation. †Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel. This work was done while visiting Georgetown University, supported by NSF grant no. 1565387, TWC: Large: Collaborative: Computing Over Dis-tributed Sensitive Data and also supported by ISF grant 152/17, by ERC grant 742754 (project NTSC), and by a grant from the Cyber Security Research Center at Ben-Gurion University of the Negev. ‡ Google AI, Princeton. § Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel, and Google Research. Partially sup-ported by ISF grant 1871/19.
Publisher Copyright:
© 2020 N. Alon, A. Beimel, S. Moran & U. Stemmer.

PY - 2020

Y1 - 2020

N2 - Let H be a class of boolean functions and consider a composed class H0 that is derived from H using some arbitrary aggregation rule (for example, H0 may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H0 in terms of that of H. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class H to a private learner for the composed class H0. Using the same ideas we show that any (proper or improper) private algorithm that learns a class of functions H in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class H in the agnostic case.

AB - Let H be a class of boolean functions and consider a composed class H0 that is derived from H using some arbitrary aggregation rule (for example, H0 may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H0 in terms of that of H. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class H to a private learner for the composed class H0. Using the same ideas we show that any (proper or improper) private algorithm that learns a class of functions H in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class H in the agnostic case.

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

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

M3 - Conference article

AN - SCOPUS:85161309953

SN - 2640-3498

VL - 125

SP - 119

EP - 152

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 33rd Conference on Learning Theory, COLT 2020

Y2 - 9 July 2020 through 12 July 2020

ER -