An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1
This provides a nearly optimal solution for private learning in a specific theoretical setting, addressing a gap in prior work.
The paper tackles the problem of designing a differentially private PAC learner for concept classes with VC dimension 1, achieving a sample complexity of ̃O(ε,δ,α,δ)(log* d), which nearly matches the lower bound of Ω(log* d).
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,δ,α,δ}(\log^* d)$, nearly matching the lower bound of $Ω(\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].