Multiclass versus binary differentially private PAC learning
Files
Date
2021-12-06
DOI
Authors
Sivakumar, Satchit
Bun, Mark
Gaboardi, Marco
Version
OA Version
Citation
S. Sivakumar, M. Bun, M. Gaboardi. "Multiclass versus Binary Differentially Private PAC Learning." Conference on Neural Information Processing Systems
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.