Source-linked AI summary
Between Pure and Approximate Differential Privacy
Thomas Steinke, Jonathan Ullman
TL;DR
The paper asks how many samples are needed to answer statistical queries privately and accurately when the approximate-privacy parameter δ varies. It combines fingerprinting-code and group-privacy arguments to derive δ-sensitive lower bounds, while developing improved pure and approximate private mechanisms. The main result gives a lower bound that smoothly connects pure and approximate privacy, alongside logarithmic-factor improvements over standard mechanisms for worst-case accuracy.
Problem
The sample complexity of accurate private statistical analysis is less understood for approximate differential privacy across varying δ, especially between δ>0 and pure privacy.
Method
The paper uses fingerprinting-code attacks with group privacy and row replication for lower bounds, and develops exponential-mechanism and sparse-vector constructions for upper bounds.
Results
The main lower bound is n≥Ω(√(d log(1/δ))/(αε)) for accurate one-way marginals, while new mechanisms improve standard worst-case sample complexity by a logarithmic factor.
Takeaways & Limitations
The results provide a δ-sensitive bridge between pure and approximate privacy and show that independent noise is suboptimal for worst-case accuracy guarantees.
Takeaways & Limitations
The lower bound requires a specified δ range, and the analysis does not optimize constant factors.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies the sample complexity of privately answering one-way marginals, focusing on how privacy parameter δ affects the cost of accurate analysis. It proves lower bounds that interpolate between pure and approximate differential privacy and presents improved worst-case-accuracy algorithms.
- Motivation: Differential privacy protects individuals by limiting how much one record influences released information, with ε controlling influence and δ the probability that this bound fails.The paper frames sample complexity as the records needed to release accurate statistics while satisfying privacy.
- Motivation: Approximate differential privacy remains less understood than pure privacy, motivating bounds that quantify sample complexity as δ approaches zero.Prior work gave strong bounds near δ≈1/n, while this paper targets a broader range of δ values.
- Problem setting: One-way marginals are the means of the d columns of a database D∈{±1}^(n×d), and accuracy can be measured by worst-case or average error.The lower bound uses average-case L1 error, which also implies the corresponding worst-case L∞ guarantee.
- Lower bounds: The main lower bound combines previous pure- and approximate-privacy bounds and introduces a multiplicative log(1/δ) dependence for answering query families.The stated δ range is necessary because the Laplace mechanism achieves pure privacy with n≥O(d/εα).
- Upper bounds: The paper presents pure and approximate private algorithms that improve worst-case one-way-marginal sample complexity over standard mechanisms by roughly a log d factor.The standard baselines are the Laplace mechanism for pure privacy and the Gaussian mechanism for approximate privacy.
- Proof strategy: The lower-bound proof reduces differential-privacy data release to fingerprinting-code attacks using group privacy and row replication.Replicating each row k times yields privacy parameters roughly (kε,e^kεδ) and applies the attack to a database of n/k rows.
- Algorithmic approach: For pure privacy, the upper-bound mechanism instantiates the exponential mechanism with the L∞ norm, while the approximate-private method repairs a small set of large Gaussian errors using sparse vector.These designs avoid relying solely on independent noise and union bounds for worst-case accuracy.
2 Preliminaries
The preliminaries define the database and privacy setting, then reduce accuracy and privacy parameters so lower bounds can focus on a normalized mechanism.
- A database is an n-row matrix of d-bit records, with adjacency defined by changing one row.
- (ε,δ)-differential privacy requires a randomized mechanism to protect outputs on adjacent databases.
- Group privacy extends the guarantee from databases differing in one row to databases differing in at most k rows.
- The paper uses a generic reduction to relate accuracy and privacy parameters to sample complexity through a 1/(αε) dependence.The reduction converts a mechanism on n samples into one on n′ = Θ(αεn) samples with adjusted privacy parameters.
3 Lower Bounds for Approximate Differential Privacy
The lower-bound proof reduces accurate marginal release to fingerprinting-code tracing, using row replication and group privacy to obtain a contradiction for small δ.
- Main theorem: The main theorem derives a lower bound for (1,δ)-private mechanisms that accurately answer one-way marginals.
- Fingerprinting-code reduction: Fingerprinting codes of length d = O(n^2 log(1/δ)) supply the combinatorial parameter regime used by the lower bound.The construction is attributed to adaptations of Tardos codes for average-case error guarantees.
- Fingerprinting-code reduction: Fingerprinting codes provide the tracing attack that connects accurate marginal answers to violations of differential privacy.The construction uses an average-case accuracy guarantee and a trace procedure over d columns.
- Fingerprinting-code reduction: The reduction forms M_k by copying each input row k times before applying the original mechanism, then analyzes privacy through group privacy.The copied database has n rows formed from an input database of n_k = floor(n/k) rows, with remaining entries filled by 1s.
- Contradiction: The fingerprinting code forces tracing with probability at least 9/100, while privacy and soundness imply a contradiction under the selected k.The proof records P[Trace(M_k(D*)) ≠ ∅] ≥ 9/100 > 1/12 and chooses k proportional to log(1/δ).
4 New Mechanisms for L∞Error
The section introduces pure and approximate differentially private mechanisms for worst-case error, using radial noise and sparse vector techniques. These mechanisms provide efficient sampling and combine Gaussian and sparse-vector outputs for approximate privacy.
- Independent noise is suboptimal for worst-case L∞ error, motivating mechanisms tailored beyond average-case L1 accuracy.
- Pure Differential Privacy: Theorem 4.1 provides a continuous noise distribution with privacy, accuracy, and efficient-sampling properties.The distribution is used to obtain the pure-DP mechanism and its worst-case accuracy guarantees.
- Approximate Differential Privacy: The sparse-vector component answers adaptive linear queries and controls its failure probability through a Chernoff-bound analysis.Its failure probability is combined with the Gaussian-related bound, with βSV = exp(−log^4 d).
- Approximate Differential Privacy: The approximate-DP mechanism combines a Gaussian mechanism with sparse vector using composition.Each component receives half of the privacy parameters, yielding an overall (ε,δ)-differentially private mechanism.
- The analysis does not optimize constant factors.
A Alternative Lower Bound for Pure Differential Privacy
An alternative proof establishes the pure differential privacy lower bound for answering one-way marginals. The argument constructs correlated databases and contrasts tail bounds using independence, concentration, and privacy.
- Any ε-differentially private mechanism answering d one-way marginals requires n ≥ Ω(d/ε) samples.
- Theorem A.1 formalizes the lower-bound condition for an ε-differentially private mechanism mapping databases to d-dimensional answers.
- Hoeffding’s inequality supplies a concentration bound for the random inner-product analysis.
- The proof samples independent uniform vectors and forms databases consisting of repeated copies of each vector.It compares Z = ⟨M(D),x⟩ with Z′ = ⟨M(D′),x⟩.
- The proof derives conflicting tail bounds for Z and Z′, then relates them through differential privacy between databases differing in n rows.