Between Pure and Approximate Differential Privacy

By Thomas Steinke, Jonathan Ullman. 2015

176 citations recorded by the source corpus.

We show a new lower bound on the sample complexity of (ε,δ)-differentially private algorithms that accurately answer statistical queries on high-dimensional databases. The novelty of our bound is that it depends optimally on the parameter δ, which loosely corresponds to the probability that the algorithm fails to be private, and is the first to smoothly interpolate between approximate differential privacy (δ >0) and pure differential privacy (δ= 0). Specifically, we consider a database D ∈{±1}n×d and its one-way marginals, which are the d queries of the form “What fraction of individual records have the i-th bit set to +1?” We show that in order to answer all of these queries to within error ±α (on average) while satisfying (ε,δ)-differential privacy for some function δ such that δ≥2−o(n) and δ≤1/n1+Ω(1), it is necessary that \[n≥Ω (\frac{√dlog(1/δ)}{αε}).\] This bound is optimal up to constant factors. This lower bound implies similar new bounds for problems like private empirical risk minimization and private PCA. To prove our lower bound, we build on the connection between fingerprinting codes and lower bounds in differential privacy (Bun, Ullman, and Vadhan, STOC’14). In addition to our lower bound, we give new purely and approximately differentially private algorithms for answering arbitrary statistical queries that improve on the sample complexity of the standard Laplace and Gaussian mechanisms for achieving worst-case accuracy guarantees by a logarithmic factor.

Subfields: Artificial Intelligence, Computer Science Applications, Statistical Learning Theory, 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 Computer Science Applications

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Pure Differentially Private Summation from Anonymous Messages (2020, background): “In the central and local settings, several prior works either obtained pure protocols in regimes where approximate protocols were previously known, or proved separations between pure and approximate protocols (e.g., [HT10, De12, NTZ13, SU15, BNS18]).”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “6The lower bound can be made to include a log(1/δ) factor using a group privacy reduction [17].”
Robust Traceability from Trace Amounts (2015, methodology): “Questions of this type arise in many natural situations in which membership in the dataset is considered sensitive; indeed, this is typically the reason for choosing to publish summary statistics, as opposed to releasing the raw data.”
Interactive fingerprinting codes and the hardness of preventing false discovery (2014, methodology): “Our proof thereof combines and simplifies the analyses of Tardos (2008) and Bun et al.”
Simultaneous Private Learning of Multiple Concepts (2015, background): “The connection between fingerprinting codes and differential privacy lower bounds was established by Bun, Ullman, and Vadhan [11] in the context of private query release, and has since been extended to a number of other differentially private analyses [1, 16, 26, 10].”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “The most closely related works to ours are [BDMN05, BUV14, SU15, DSS + 15, SU17, KV18, KLSU19, CWZ19, BS19, AMB19], which study differentially private estimation of the mean of a distribution.”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, unknown): “Yet developing private algorithms that achieve reasonable utility is challenging, as the strong protections differential privacy provides necessarily degrade statistical utility.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, methodology): “Subsequent to our work, Steinke and Ullman [47] refined our use of fingerprinting codes to prove a lower bound of Ω( √ d log(1/δ)/ε) on the number of samples required to release the mean of each of the d attributes under (ε, δ)-differential privacy when δ 1/n.”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “Upper and lower bounds for learning the mean of a product distribution over the hypercube in `∞-distance include [12, 14, 32, 61].”