NeurIPS 2021poster7 citations
Multiclass versus Binary Differentially Private PAC Learning
Satchit Sivakumar, Mark Bun, Marco Gaboardi
Abstract
We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. We apply this transformation to a recently proposed binary private PAC learner to obtain a private multiclass learner with sample complexity that has a polynomial dependence on the multiclass Littlestone dimension and a poly-logarithmic dependence on the number of classes. This yields a doubly exponential improvement in the dependence on both parameters over learners from previous work. Our proof extends the notion of $\Psi$-dimension defined in work of Ben-David et al. [JCSS, 1995] to the online setting and explores its general properties.
Differential PrivacyPAC LearningOnline LearningMulticlass Learning
BibTeX
@inproceedings{
sivakumar2021multiclass,
title={Multiclass versus Binary Differentially Private {PAC} Learning},
author={Satchit Sivakumar and Mark Bun and Marco Gaboardi},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=MBxJ0ydw6b}
}