An \Tilde{O}Ptimal Differentially Private 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 $\tildeO\varepsilon,δ,α,δ\log^ d$, nearly matching the lower bound of $Ω\log^ d$ proved by Alon et al...