Multiclass Versus Binary Differentially Private PAC Learning

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.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Sivakumar et al. "Multiclass Versus Binary Differentially Private PAC Learning." Neural Information Processing Systems, 2021.

Markdown

[Sivakumar et al. "Multiclass Versus Binary Differentially Private PAC Learning." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/sivakumar2021neurips-multiclass/)

BibTeX

@inproceedings{sivakumar2021neurips-multiclass,
  title     = {{Multiclass Versus Binary Differentially Private PAC Learning}},
  author    = {Sivakumar, Satchit and Bun, Mark and Gaboardi, Marco},
  booktitle = {Neural Information Processing Systems},
  year      = {2021},
  url       = {https://mlanthology.org/neurips/2021/sivakumar2021neurips-multiclass/}
}