@conference {1637693, title = {Multiclass versus Binary Differentially Private PAC Learning}, booktitle = {Advances in Neural Information Processing Systems 34 (NeurIPS 2021)}, year = {2021}, 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 Ψ-dimension defined in work of Ben-David et al. [5] to the online setting and explores its general properties.}, url = {https://proceedings.neurips.cc/paper/2021/file/c1d53b7a97707b5cd1815c8d228d8ef1-Paper.pdf}, author = {Mark Bun and Marco Gaboardi and Satchit Sivakumar} }