Interactive fingerprinting codes and the hardness of preventing false discovery

By Thomas Steinke, Jonathan Ullman. 2014

119 citations recorded by the source corpus.

We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given n samples from an unknown distribution. A statistical query asks for the expectation of a predicate over the underlying distribution, and an answer to a statistical query is accurate if it is “close” to the correct expectation over the distribution. This question was recently studied by Dwork et al. [DFH+ 15], who showed how to answer Ω(n2) queries efficiently, and also by Hardt and Ullman [HU14], who showed that answering Õ(n3) queries is hard. We close the gap between the two bounds and show that, under a standard hardness assumption, there is no computationally efficient algorithm that, given n samples from an unknown distribution, can give valid answers to O(n2) adaptively chosen statistical queries. An implication of our results is that computationally efficient algorithms for answering arbitrary, adaptively chosen statistical queries may as well be differentially private. We obtain our results using a new connection between the problem of answering adaptively chosen statistical queries and a combinatorial object called an interactive fingerprinting code [FT01]. In order to optimize our hardness result, we give a new Fourier-analytic approach to analyzing fingerprinting codes that is simpler, more flexible, and yields better parameters than previous constructions.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Information Theory

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 Computational Theory and Mathematics

In Statistical Learning Theory

In Information Theory

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, methodology): “Techniques Our techniques build on the recent line of work proving lower bounds in differential privacy and related problems via either fingerprinting codes or techniques inspired by fingerprinting codes [16], [24], [25], [17], [18], [26].”
Algorithmic stability for adaptive data analysis (2015, background): “Unfortunately, this running time is known to be optimal, as [HU14, SU15b] (building on hardness results in privacy [Ull13]) showed that, assuming exponentially hard one-way functions exist, any poly( n, 2 o ( d ) ) time mechanism that answers k = ω ( n 2 ) statistical queries is not even 1 /…”
Robust Traceability from Trace Amounts (2015, background): “Description of The Attack Like the attacks in previous tracing work for the genomic setting [1], [2], [28]–[30] and in the fingerprinting setting [17], [20], our attack uses a simple scoring function to make its decision.”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “The work of [26, 42] shows that, under standard cryptographic assumptions, the exponential running time of the algorithm instantiating our main result is unavoidable, and that the sample complexity of our efficient algorithm is nearly optimal, among all computationally efficient mechanisms for answe”
A Minimax Theory for Adaptive Data Analysis (2016, methodology): “Related work Adaptive data analysis has been studied in (but not limited to) Dwork et al. (2015b,a); Bassily et al. (2015); Russo & Zou (2015); Steinke & Ullman (2014); Hardt & Ullman (2014).”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, background): “It turns out this is for fundamental reasons – Hardt and Ullman [11] and Steinke and Ullman [19] prove that, under cryptographic assumptions, no efficient algorithm can answer more than quadratically many statistical queries chosen adaptively by an adversary who knows the true data distribution.”
Calibrating Noise to Variance in Adaptive Data Analysis (2017, background): “This quadratic relationship between n and k was also shown to be optimal in the worst case (Hardt and Ullman, 2014; Steinke and Ullman, 2015).”
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing (2016, methodology): “Computational and information theoretic lower bounds for adaptively estimating means in this framework were proven by Hardt and Ullman [HU14], and Steinke and Ullman [SU15].”
The Complexity of Differential Privacy (2017, background): “Remarkably, both positive and negative results for differential privacy (including both information-theoretic and computational lower bounds as we have seen in this tutorial) have found analogues for the false discovery problem [44, 60, 98, 6], suggesting that it will also be a very fertile area for”
Private Hypothesis Selection (2019, background): “In contrast, for non-product distributions over the hypercube, estimating the mean to the same accuracy under ε -diﬀerential privacy requires n = Ω( d 3 / 2 /ε ) samples [HT10, SU15].”
Privately Learning High-Dimensional Distributions (2018, methodology): “We will use the following key lemma, which is an extension of a similar statement in Steinke and Ullman (2015) for the uniform distribution over [−1, 1].”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “These works [37, 48] effectively reverse a connection established in [19, 3], which used differentially private algorithms to obtain positive results for this problem.”