An Õptimal Differentially Private PAC Learner for Concept Classes with VC Dimension 1

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}_{\varepsilon,\delta,\alpha,\beta}(\log^*d)$, nearly matching the lower bound of $\Omega(\log^*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]. The main idea is to combine the tree structure of VC-dimension-$1$ classes with the private median primitive for interior-point selection. We first privately locate a good depth in the tree, then privately identify a good node on that layer. For proper learning, we show how to descend from the improper output to a proper leaf while controlling the additional false positives.