Closure Properties for Private Classification and Online Prediction

Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:119-152, 2020.

Abstract

Let H be a class of boolean functions and consider a composed class H’ that is derived from H using some arbitrary aggregation rule (for example, H’ may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H’ 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 H’. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-alon20a, title = {Closure Properties for Private Classification and Online Prediction}, author = {Alon, Noga and Beimel, Amos and Moran, Shay and Stemmer, Uri}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {119--152}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/alon20a/alon20a.pdf}, url = {https://proceedings.mlr.press/v125/alon20a.html}, abstract = { Let H be a class of boolean functions and consider a composed class H’ that is derived from H using some arbitrary aggregation rule (for example, H’ may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H’ 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 H’. 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.} }
Endnote
%0 Conference Paper %T Closure Properties for Private Classification and Online Prediction %A Noga Alon %A Amos Beimel %A Shay Moran %A Uri Stemmer %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-alon20a %I PMLR %P 119--152 %U https://proceedings.mlr.press/v125/alon20a.html %V 125 %X Let H be a class of boolean functions and consider a composed class H’ that is derived from H using some arbitrary aggregation rule (for example, H’ may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H’ 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 H’. 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.
APA
Alon, N., Beimel, A., Moran, S. & Stemmer, U.. (2020). Closure Properties for Private Classification and Online Prediction. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:119-152 Available from https://proceedings.mlr.press/v125/alon20a.html.

Related Material