An Equivalence Between Private Classification and Online Prediction

Understand

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.