Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

摘要

We compare the sample complexity of private learning and sanitization tasks under pure ε-differential privacy [Dwork, McSherry, Nissim, and Smith TCC 2006] and approximate (ε, δ)-differential privacy [Dwork, Kenthapadi, McSherry, Mironov, and Naor EUROCRYPT 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy.