Timezone: »
Multiclass versus Binary Differentially Private PAC Learning
Satchit Sivakumar · Mark Bun · Marco Gaboradi
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. \cite{Ben} to the online setting and explores its general properties.
Author Information
Satchit Sivakumar (Boston University)
Mark Bun (Boston University)
Marco Gaboradi (Boston University)
More from the Same Authors
-
2021 : When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? »
Gavin Brown · Mark Bun · Vitaly Feldman · Adam Smith · Kunal Talwar -
2021 : Differentially Private Sampling from Distributions »
Satchit Sivakumar · Marika Swanberg · Sofya Raskhodnikova · Adam Smith -
2021 : Covariance-Aware Private Mean Estimation Without Private Covariance Estimation »
Gavin Brown · Marco Gaboradi · Adam Smith · Jonathan Ullman · Lydia Zakynthinou -
2021 Poster: Differentially Private Correlation Clustering »
Mark Bun · Marek Elias · Janardhan Kulkarni -
2021 Spotlight: Differentially Private Correlation Clustering »
Mark Bun · Marek Elias · Janardhan Kulkarni