An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1
By: Chao Yan
Potential Business Impact:
Makes learning private and super fast.
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,\delta}(\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].
Similar Papers
Private Learning of Littlestone Classes, Revisited
Machine Learning (Stat)
Makes learning private and faster for computers.
Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Cryptography and Security
Makes private computer learning much faster.
Optimal Differentially Private Sampling of Unbounded Gaussians
Data Structures and Algorithms
Lets computers make private data from random numbers.