An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

Abstract

We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension $d$. Our algorithm achieves the sample complexity of ${\tilde{O}}_{\epsilon ,\hat{I}´,\hat{I}\pm ,\hat{I}´}({\log }^{\ast }d)$, nearly matching the lower bound of $\hat{I}\text{c◯}({\log }^{\ast }d)$ proved by Alon et al. [STOC19]. Prior to our work, the best known upper bound is $\tilde{O}(VC\cdot d^5)$ for general VC classes, as shown by Ghazi et al. [STOC21].

Add proper learner