Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

We compare the sample complexity of private learning and sanitization tasks under pure e-differential privacy [Dwork, McSherry, Nissim, and Smith TCC 2006] and approximate (e,δ)-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.