Between Pure and Approximate Differential Privacy
This work addresses a foundational problem in privacy-preserving data analysis for researchers and practitioners in differential privacy, offering both theoretical lower bounds and algorithmic improvements.
The paper tackles the problem of determining the sample complexity for differentially private algorithms that answer statistical queries, showing a new lower bound that optimally depends on the privacy parameter δ and smoothly interpolates between pure and approximate differential privacy, with the result being optimal up to constant factors. It also provides new algorithms that improve sample complexity by a logarithmic factor compared to standard mechanisms.
We show a new lower bound on the sample complexity of $(\varepsilon, δ)$-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 \in \{\pm1\}^{n \times d}$ and its \emph{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 $\pm α$ (on average) while satisfying $(\varepsilon, δ)$-differential privacy, it is necessary that $$ n \geq Ω\left( \frac{\sqrt{d \log(1/δ)}}{α\varepsilon} \right), $$ which is optimal up to constant factors. To prove our lower bound, we build on the connection between \emph{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.