PaperlayerView exact revision on arXiv

Source-linked AI summary

Preventing False Discovery in Interactive Data Analysis is Hard

Moritz Hardt, Jonathan Ullman

arXiv:1408.1655v1cs.LGcs.CCcs.DS

TL;DR

The paper asks whether valid answers to many adaptively chosen statistical queries can be computed efficiently from finite samples, a question motivated by false discovery in modern adaptive analysis. Using statistical-query lower bounds based on fingerprinting codes and encryption, it proves that, assuming one-way functions exist, no efficient oracle can accurately answer n^{3+o(1)} adaptive queries. This establishes a computational barrier to preventing false discovery and highlights dimensionality as an essential scope condition.

  • Problem

    Modern empirical analysis is highly adaptive, so preventing false discovery requires answers that generalize from finite samples to the underlying distribution.

    Source: §1 · p. 3

  • Method

    The paper analyzes adaptive statistical queries through a reconstruction attack combining fingerprinting codes with encryption.

    Source: §1.1 · p. 5, §4.1 · p. 15, §4.2 · p. 16

  • Results

    Assuming one-way functions exist, no computationally efficient oracle given n samples can accurately answer n^{3+o(1)} adaptively chosen statistical queries.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The result identifies an inherent computational obstruction to preventing false discovery in collaborative science under adaptive data analysis.

    Source: §1 · p. 4

    The hardness result requires dimensionality growing more than logarithmically with n, and relies on standard cryptographic hardness assumptions for efficient-oracle impossibility.

    Source: §1 · p. 4, §4.1 · p. 15

Abstract

from arXiv · show

We 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 $n^{3+o(1)}$ adaptively chosen statistical queries. A statistical query asks for the expectation of a predicate over the underlying distribution, and an answer to a statistical query is valid if it is "close" to the correct expectation over the distribution. Our result stands in stark contrast to the well known fact that exponentially many statistical queries can be answered validly and efficiently if the queries are chosen non-adaptively (no query may depend on the answers to previous queries). Moreover, a recent work by Dwork et al. shows how to accurately answer exponentially many adaptively chosen statistical queries via a computationally inefficient algorithm; and how to answer a quadratic number of adaptive queries via a computationally efficient algorithm. The latter result implies that our result is tight up to a linear factor in $n.$ Conceptually, our result demonstrates that achieving statistical validity alone can be a source of computational intractability in adaptive settings. For example, in the modern large collaborative research environment, data analysts typically choose a particular approach based on previous findings. False discovery occurs if a research finding is supported by the data but not by the underlying distribution. While the study of preventing false discovery in Statistics is decades old, to the best of our knowledge our result is the first to demonstrate a computational barrier. In particular, our result suggests that the perceived difficulty of preventing false discovery in today's collaborative research environment may be inherent.

1 Introduction

Modern data analysis is inherently adaptive, making false-discovery control difficult to formalize and computationally hard. The paper proves that efficient statistical-query oracles cannot generally maintain validity for more than n^{3+o(1)} adaptive queries, while outlining a reconstruction-based proof and connections to privacy.

1 Introduction

  • Adaptive data analysis lets algorithmic choices depend on prior data interactions, making a precise a priori description of the experimental setup nearly impossible.The paper motivates this setting through large collaborative projects and data-science competitions.Source: §1 · p. 3

1.2 Connection to privacy and reconstruction attacks

  • Earlier work established exponential-query inefficient and quadratic-query efficient upper bounds, while related results use differential privacy, traitor-tracing schemes, and linear-sketch lower bounds.The paper’s hardness result applies to arbitrary efficient statistical-query oracles and is described as largely orthogonal to the linear-sketch result of Hardt and Woodruff.Source: §1 · p. 3, §1.2 · pp. 6–7, §1.3 · p. 7

1 Introduction

  • Assuming one-way functions exist, no computationally efficient oracle given n samples can accurately answer n^{3+o(1)} adaptively chosen statistical queries.The result concerns accuracy with respect to the underlying distribution, not merely the observed sample.Source: §1 · pp. 3–4
  • The hardness requires dimensionality growing beyond logarithmically with n; when n is much larger than 2^d, empirical distributions can approximate the underlying distribution and every query is answerable accurately.A second theorem states that polynomially large dimension can defeat even computationally unbounded accuracy for adaptive queries.Source: §1 · p. 4
  • The paper concludes that adaptivity is essential to modern data-analysis models and creates an intrinsic computational obstacle to preventing false discovery.This conclusion frames the barrier as relevant to collaborative science rather than only to the statistical-query formalism.Source: §1 · p. 4

1.1 Proof overview

  • The attack adaptively reconstructs all but O(1) oracle samples in roughly n rounds of n^2 queries, then finds queries with blatantly inaccurate answers.Fingerprinting codes recover individual samples, while encryption hides query information outside the sample from computationally bounded oracles.Source: §1.1 · p. 5
  • Random challenge predicates and robust fingerprinting codes keep the oracle’s sample sufficiently aligned with the underlying distribution while reconstruction proceeds.This concentration property prevents tracing from failing merely because sample and distribution answers differ.Source: §1.1 · pp. 5–6

1.2 Connection to privacy and reconstruction attacks

  • The result is an efficient reconstruction attack: any efficient oracle accurate on n^{3+o(1)} adaptive queries must be blatantly non-private, linking false-discovery hardness to privacy.The distinction is that false-discovery accuracy is measured against the underlying distribution, whereas privacy analyses often use the oracle’s sample.Source: §1.2 · p. 6

2 Preliminaries

The paper formalizes adaptive statistical-query answering through an oracle that estimates expectations from samples, then introduces error-robust fingerprinting codes used in its lower-bound construction.

2 Preliminaries

  • A statistical query is the expectation of a Boolean predicate under an unknown distribution, which an oracle must estimate from iid samples.The oracle is evaluated on adaptively chosen query sequences and is computationally efficient when each query is processed in polynomial time.Source: §2 · p. 8
  • An accurate oracle must keep every answer close to the population expectation throughout an adaptively chosen sequence, with accuracy quantified by α and failure probability β.The shorthand α-accuracy uses a failure probability that tends to zero with n.Source: §2 · p. 8

2.1 Fingerprinting codes

  • Error-robust fingerprinting codes trace a combined codeword to a colluding user even when consistency holds on only 99% of columns.Their consistency condition requires each output bit to remain within 1/3 of the corresponding colluders’ column mean, while the relaxed condition applies to most columns.Source: §2.1 · p. 9
  • The construction of Bun, Ullman, and Vadhan, building on Tardos, provides error-robust fingerprinting codes of length ℓFPC(p) = ˜Θ(p2).The paper uses this nearly optimal length in its later query-complexity bound.Source: §2.1 · p. 9
  • For sufficiently large user sets, most fingerprinting-code columns have nearly matching means over all users and the selected subset.The supplied lemma establishes this concentration property using Hoeffding bounds and independence across columns.Source: §2.1 · pp. 9–10

3 Lower bound for natural oracles

The paper proves a lower bound for natural oracles by recovering most sample values with fingerprinting-code queries and then forcing an adaptive query that the oracle cannot answer accurately. This yields an n^{3+o(1)}-query impossibility result for natural oracles.

3.1 Analysis of the recovery phase

  • Naturality makes oracle answers independent of query behavior outside the sample, allowing fingerprinting-code tracing to recover users from the oracle’s answers.This property bridges the fingerprinting-code security condition, which applies only to information about sampled users, with the adaptive queries issued by the adversary.Source: §3 · p. 10, §3.1 · pp. 12–13

3 Lower bound for natural oracles

  • The adversary samples a distribution, identifies most oracle-held samples during recovery, and uses that knowledge to construct a query distinguishing the sample from the population.The three phases are distribution selection, sample recovery, and an attack query that defeats accuracy.Source: §3 · p. 11, §3.1 · p. 11

3.1 Analysis of the recovery phase

  • If a natural oracle is (1/12)-accurate for n·ℓFPC(2000n)+1 adaptive queries, the recovery phase leaves more than 500 unrecovered sampled values.The recovery argument applies fingerprinting-code consistency across rounds and uses concentration over most columns.Source: §3.1 · p. 13

3.2 Analysis of the Attack Phase

  • After recovery, the attack query has a population answer close to φ, but the oracle cannot distinguish φ = 0 from φ = 1/500 when it sees only zero values on the unrecovered sample portion.This ambiguity occurs with constant probability, so the oracle’s answer is far from the population value with constant probability.Source: §3.2 · pp. 13–14

3.3 Putting it together

  • The recovery and attack phases contradict the definition of an accurate oracle, completing the lower bound for natural oracles.The contradiction follows because accuracy requires each adaptive query to be answered correctly with probability 1 − o(1), whereas the final query fails with probability bounded away from zero.Source: §3.2 · p. 14, §3.3 · p. 15
  • No natural oracle is (1/2000)-accurate for n3+o(1) adaptively chosen queries given n samples.The attack uses k = n3+o(1) queries, combining a recovery phase with one final attack query.Source: §3.3 · p. 15

4 Lower bound for all computationally bounded oracles

This section constructs an adaptive attack showing that efficient statistical-query oracles cannot remain accurate for n^{3+o(1)} queries, and extends the argument to an information-theoretic lower bound when d=n^{3+o(1)}.

4 Lower bound for all computationally bounded oracles

  • The lower bound assumes one-way functions and rules out efficient oracles accurate on n^{3+o(1)} adaptively chosen queries.The attack uses computationally secure encryption, whose existence follows from one-way functions.Source: §4.1 · p. 16

4.2 Description of the attack

  • The attack chooses a distribution, recovers most samples held by the oracle, then uses that knowledge to construct a query the oracle cannot answer accurately.The recovery and attack phases are implemented using fingerprinting codes and encrypted information.Source: §4.2 · p. 16, §4.3 · p. 16

4.3 Analysis of the recovery phase

  • For polynomial n = n(d) and sufficiently large d, the cited claims concern computationally efficient O that is (1/12)-accurate for n·ℓFPC(2000n)+1 adaptively chosen queries, with |S \ T R| > 500.Source: §4.3 · p. 19
  • Encryption hides fingerprinting-code rows outside the sampled users, making the real and ideal attacks computationally indistinguishable to an efficient oracle.This comparison supplies the computational step needed to apply fingerprinting-code security despite adaptive queries.Source: §4.3 · p. 18

4.4 Analysis of the attack phase

  • After recovery, the attack-phase query has population value close to φ, while the oracle cannot distinguish the cases φ=0 and φ=1/500 with sufficient accuracy.The argument uses |q*(D)−φ|≤1/2000 and shows constant-probability inaccuracy for q* in the ideal attack before transferring the conclusion back.Source: §4.4 · pp. 21–22

4.5 Putting it together

  • There is no computationally efficient oracle that is (1/2000)-accurate for n^{3+o(1)} adaptively chosen queries given n samples; the entire attack uses k=n^{3+o(1)} queries.Source: §4.5 · p. 23

4.6 An information-theoretic lower bound

  • Replacing encryption with a one-time pad extends the construction to an information-theoretic lower bound when d=n^{3+o(1)}.Because the attack encrypts only ˜O(n^3) single-bit messages, a key of matching length suffices for the information-theoretic construction.Source: §4.6 · pp. 23–24

5 Lower bounds for avoiding blatant non-privacy

This section shows that efficiently answering n^{3+o(1)} adaptive statistical queries necessarily leads to blatant non-privacy, under computational assumptions and even for unbounded oracles in the stated dimension. It formalizes sample-accuracy and proves these lower bounds through reconstruction-based attacks and idealized hybrids.

5.1 Blatant non-privacy

  • The section defines blatant non-privacy by changing accuracy from the underlying distribution to the sample and modeling an adversary interaction game.Source: §5.1 · p. 24

5.2 Lower bounds

  • n^{3+o(1)} accurate answers to adaptively chosen queries are blatantly non-private for computationally efficient oracles.Source: §5.2 · p. 25
  • The lower-bound proof uses a reconstruction adversary that recovers a set close to the sample when the oracle is sample-accurate.Source: §5.2 · p. 25
  • The efficient-oracle lower bound relies on computational indistinguishability between the privacy attack and an ideal attack.Source: §5.2 · p. 27
  • The same query scale is blatantly non-private even for computationally unbounded oracles when n samples have dimension d = n^{3+o(1)}.Source: §5.2 · p. 28

A Security reductions from Section 4

This appendix reduces differences between real and ideal attack events to breaking encryption security. Efficient simulators make any non-negligible difference computationally exploitable.

A Security reductions from Section 4

Related papers

Loading 1408.1655v1…