null
(Ed.)

We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al. (STOC
2019) who proved the converse statement (this question was also asked by Neel et al. (FOCS
2019)). Together these two results yield an equivalence between online learnability and private
PAC learnability.
We introduce a new notion of algorithmic stability called “global stability” which is essential
to our proof and may be of independent interest. We also discuss an application of our results
to boosting the privacy and accuracy parameters of differentially-private learners.

more »
« less