Closure Properties for Private Classification and Online Prediction

Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)119-152
Number of pages34
JournalProceedings of Machine Learning Research
StatePublished - 2020
Event33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria
Duration: Jul 9 2020Jul 12 2020

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Closure Properties for Private Classification and Online Prediction'. Together they form a unique fingerprint.

Cite this