Smooth sensitivity and sampling in private data analysis

By Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith. 2007

1,280 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Statistics and Probability, 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 Statistics and Probability

In Privacy & Security

Citations in the corpus

Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, background): “To get around this, we bound the smooth sensitivity (Nissim et al., 2007) of the moments and add noise proportional to it to the moments themselves.”
Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “mechanisms, both using worst-case sensitivity analysis, hence the amount of noise is very conservative. A promising alternative is to build upon a more ﬁne-tuned technique, such as smooth sensitivity [32] which uses data-dependent sensitivity bounds. That may let us add less noise to “easy to defend”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, methodology): “We note that existing work on differentially-private learning of mixtures (e.g., (Nissim et al., 2007)) has mainly focused on asymptotic guarantees, and we are not aware of any exiting algorithms that have been evaluated on high-dimensional datasets such as CIFAR-10.”
Differentially Private Learning with Adaptive Clipping (2019, neutral): “For any C , deﬁne which implies Hence, Therefore, C ∗ is at the γ th quantile of X (Koenker and Bassett Jr, 1978).”
The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
The structure of optimal private tests for simple hypotheses (2018, methodology): “A folklore result based on the sample-and-aggregate paradigm [59] shows that for every P ,Q and every ε > 0, SC ε = O( 1 ε SCP,Q ), meaning privacy comes at a cost of at most O( 1 ε ).”
Scalable Private Learning with PATE (2018, methodology): “To remedy this, we use the smooth sensitivity framework proposed by Nissim et al. (2007).”
Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “PINQ [36] internalizes the use of standard composition in the form of a privacy budget management platform, Airavat [45] uses differential privacy combined with the map-reduce approach, GUPT [40] implements the general idea of sample and aggregate [41].”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “Finally, it is worth mentioning that there exists a relaxed version of ϵ -differential privacy called ( ϵ, δ ) -differential privacy [23].”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, background): “Several frameworks for constructing differentially private functions by means of perturbation are presented in the literature (see [11, 2, 22, 20]).”
On the geometry of differential privacy (2009, background): “Nissim, Raskhodnikova and Smith [NRS07] show that one can add noise proportional to a smoothed version of the local sensitivity of the query, which can be much smaller than the global sensitivity for some non-linear queries.”
A learning theory approach to non-interactive database privacy (2008, neutral): “Categories and Subject Descriptors F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity General Terms Algorithms, Security, Theory Keywords non-interactive database privacy, learning theory”
Universally utility-maximizing privacy mechanisms (2008, background): “The diﬀerential privacy literature [10, 8, 16, 18, 5, 7, 12, 4] has proposed a rigorous and quantiﬁable deﬁnition of privacy, as well as provably privacy-preserving mechanisms for diverse applications including statistical queries, machine learning, and pricing.”
Differentially private combinatorial optimization (2009, background): “, see [11, 8, 27, 6, 23, 15, 12], and see [9] for an excellent survey), that tries to capture the intuition of individual privacy.”