Sample-efficient proper PAC learning with approximate differential privacy

In this paper we prove that the sample complexity of properly learning a\nclass of Littlestone dimension $d$ with approximate differential privacy is\n$\\tilde O(d^6)$, ignoring privacy and accuracy parameters. This result answers\na question of Bun et al. (FOCS 2020) by improving upon their upper bound of\n$2^{O(d)}$ on the sample complexity. Prior to our work, finiteness of the\nsample complexity for privately learning a class of finite Littlestone\ndimension was only known for improper private learners, and the fact that our\nlearner is proper answers another question of Bun et al., which was also asked\nby Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et\nal., we then show that the sample complexity of sanitizing a binary hypothesis\nclass is at most polynomial in its Littlestone dimension and dual Littlestone\ndimension. This implies that a class is sanitizable if and only if it has\nfinite Littlestone dimension. An important ingredient of our proofs is a new\nproperty of binary hypothesis classes that we call irreducibility, which may be\nof independent interest.\n