Sample-efficient proper PAC learning with approximate differential privacy
This work addresses fundamental questions in private PAC learning by establishing tighter sample complexity bounds and proper learning for classes with finite Littlestone dimension, which is important for researchers in theoretical machine learning and privacy.
This paper demonstrates that the sample complexity for properly learning a class with Littlestone dimension d using approximate differential privacy is O(d^6), significantly improving upon the previous upper bound of 2^O(d). It also shows that a binary hypothesis class is sanitizable if and only if it has finite Littlestone dimension.
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $\tilde O(d^6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2^{O(d)}$ on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.