Private and Online Learnability Are Equivalent
Noga Alon, Mark Bun, Roi Livni, M. Malliaris, Shay Moran · Journal of the ACM · 2022
Let H be a binary-labeled concept class. We prove that H can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.