Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

By Amos Beimel, Kobbi Nissim, Uri Stemmer. 2013

205 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Privacy & Security

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Speciﬁcally, we use lower bounds for ε -di ﬀ erential private learning of the threshold functions in the cura-tor model [11, 30]; these lower bounds do not hold for ( ε,δ )-di ﬀ erential private learning of the threshold functions [12, 17].”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “There have also been attempts to explicitly and precisely determine the sample complexity of even simpler query families than k-way conjunctions, such as point functions and interval functions [2, 3, 4].”
The Price of Selection in Differential Privacy (2017, background): “(2014) and the choosing mechanism Beimel et al. (2013). An interesting future direction is to characterize which distributional assumptions are sufficient to bypass our lower bound. Tracing Attacks. Our lower bounds for differential privacy follow from a tracing attack Homer et al. (2008); Sankarara”
Simultaneous Private Learning of Multiple Concepts (2015, background): “In terms of sample complexity, it is known that private learning (for the case k = 1) is an easier task than data sanitization, and several reductions from private learning to data sanitization were given in [19, 5, 6].”
Private selection from private candidates (2018, methodology): “Margin-based Mechanism Adist [3, 34] Suppose that each qi has sensitivity at most s .”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “Nonetheless, we acknowledge that Theorem 7 in Dwork et al. (2015b) provides an interesting alternative proof for “differentially private learners have small generalization error”, when choosing the statistical query as evaluating a loss function at a privately learned hypothesis.”
Private Hypothesis Selection (2019, background): “This was observed by Beimel, Nissim, and Stemmer [BNS16], who showed that if a good approximation to P is known, e.g., from public unlabeled examples or from diﬀerentially private processing of unlabeled examples, then the number of labeled examples needed for private PAC learning is only O ( V C (…”
Clustering Algorithms for the Centralized and Local Models (2017, methodology): “Using privacy preserving recursion on binary search [3], Nissim et al.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “There have also been attempts to explicitly and precisely determine the sample complexity of even simpler query families than k-way conjunctions, such as point functions and threshold functions [5, 6, 7, 13].”
Private Query Release Assisted by Public Data (2020, methodology): “Now, given these minor details and since any PAP algorithm can obviously be viewed as a differentially private algorithm operating on the private data set (by “hardwiring” the public data set into the algorithm), Lemma 17 follows by invoking the reduction in (Beimel et al., 2013).”
The Large Margin Mechanism for Differentially Private Maximization (2014, methodology): “In the context of private PAC learning, the work of [3] gives the first separation between pure and approximate differential privacy.”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “We also note that there is an extensive literature on alternative private selection mechanisms, e.g., see Beimel et al. (2013); Chaudhuri et al. (2014); Lantz et al. (2015); Minami et al. (2016); Raskhodnikova & Smith (2016); Liu & Talwar (2019); Awan et al. (2019); McKenna & Sheldon (2020).”
Technical Privacy Metrics (2015, background): “, by allowing a wider range of query types [19] or by reducing the sample complexity of private learning [15].”