Sivakumar, SatchitBun, MarkGaboardi, Marco2022-07-262022-07-262021-12-06S. Sivakumar, M. Bun, M. Gaboardi. "Multiclass versus Binary Differentially Private PAC Learning." Conference on Neural Information Processing Systemshttps://hdl.handle.net/2144/44936We 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.en-USConference materials734946