Multiclass versus Binary Differentially Private PAC Learning
This addresses the challenge of efficient private learning for multiclass classification, with incremental theoretical advancements in sample complexity bounds.
The paper tackles the problem of multiclass differentially private PAC learning by developing a generic reduction to binary private PAC learning, achieving sample complexity with polynomial dependence on multiclass Littlestone dimension and poly-logarithmic dependence on the number of classes, which represents an exponential improvement over prior work.
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 an 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. [JCSS '95] to the online setting and explores its general properties.