Multiclass versus Binary Differentially Private PAC Learning
  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 $\Psi$-dimension defined in work of Ben-David et al. [JCSS '95] to the
online setting and explores its general properties.
