Source-linked AI summary
Preserving Statistical Validity in Adaptive Data Analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth
TL;DR
The paper addresses the gap between fixed-procedure statistical theory and adaptive data analysis, where data reuse guides new hypotheses and analyses. It uses differential-privacy techniques to perturb and coordinate estimates, showing that nearly exponentially many adaptively chosen queries can be answered accurately rather than only linearly many with standard empirical estimators.
Problem
The paper asks how to preserve statistical validity when data are adaptively reused, since conventional inference assumes procedures were selected before data collection.
Method
The paper uses differential privacy, including private oracles and perturbed query answers, to connect adaptive analyses with generalization from empirical averages to true expectations.
Results
Nearly exponentially many adaptively chosen statistical queries can be answered accurately, improving over standard empirical estimators limited to a linear number of estimates.
Takeaways & Limitations
Privacy-preserving analysis can provide a principled way to maintain statistical validity under adaptive data reuse.
Takeaways & Limitations
The mechanism described is not computationally efficient because its running time is linear in the data-universe size, which may be exponential in data dimension.
Abstract
from arXiv · showhide
A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of $m$ adaptively chosen functions on an unknown distribution given $n$ random samples. We show that, surprisingly, there is a way to estimate an exponential in $n$ number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question.
1 Introduction
Adaptive data analysis can invalidate standard statistical inference because hypotheses and analyses are selected using the same data. The paper develops privacy-based methods that preserve validity while answering nearly exponentially many adaptive statistical queries.
- Motivation: Statistical inference theory assumes procedures are fixed before data collection, whereas scientific analysis adaptively reuses data to generate hypotheses, analyses, and reported tests.This mismatch creates an implicit multiple-comparisons problem that standard significance levels do not capture.
- Motivation: Fresh samples or conservative data splitting avoid adaptive overfitting but can reduce the data available per procedure by about a factor of m.The paper notes that testing data are often reused in practice, including for parameter tuning.
- Problem Definition: The paper studies how many adaptively chosen statistical queries—expectations of functions ψ: X → [0,1]—can be answered accurately from n i.i.d. samples.The target is additive tolerance τ with high probability.
- Results: Nearly exponentially many adaptive queries can be answered, reducing sample complexity from linear in m to polylogarithmic dependence and nearly matching the non-adaptive requirement.The result concerns answers accurate up to tolerance τ with high probability.
- Results: A computationally efficient algorithm matches a quadratic lower bound using independent noise, while another handles exponentially many queries generated in o(n) adaptive rounds.The round-adaptive method pays for rounds only when adaptivity causes overfitting, according to the paper.
- Techniques: Differential privacy provides the central technique: analyses that access data through a private algorithm retain generalization from empirical averages to true expectations.Post-processing allows the adaptive analyst and private oracle to be treated as one differentially private algorithm.
2 Preliminaries
This section defines statistical queries and differential privacy, then explains how privacy-induced stability supports generalization from empirical to true expectations. It also contrasts the paper’s high-probability bounds with earlier expectation-based guarantees.
- A statistical query asks for the expectation P[ψ] of a function ψ: X → [0,1] within tolerance τ.
- For a fixed data-independent query, Hoeffding’s bound gives error probability at most 2 · exp(−2τ^2n), allowing exponentially many such queries.
- Differential privacy requires similar output distributions on datasets differing in one element, with parameters ε and δ controlling the allowed change.
- Differential privacy implies replace-one stability, which yields on-average generalization for functions output by private algorithms.
- The paper strengthens this connection from expectation bounds to high-probability bounds with logarithmic dependence on 1/β.
3 Differential Privacy and Preservation of Moments
This section proves that differentially private algorithms produce data-dependent functions whose empirical averages remain close to their population expectations. The proof uses moment comparisons and extends from pure to approximate privacy.
- The analysis resolves the dependence between a private output function φ=A(S) and the dataset S by comparing empirical averages on S with averages on an independent dataset T.
- Moment inequalities transfer concentration from an independent sample to the adaptively generated function, providing the core proof technique.
- Theorem 9 guarantees |P[φ]−ES[φ]|≤τ except with probability β when n≥12 ln(4/β)/τ^2 and ε≤τ/2 under pure differential privacy.
- The approximate-privacy extension handles small nonzero δ by conditioning on intervals of possible population expectations rather than exact function equality.
- Theorem 10 gives the analogous guarantee for (ε,δ)-differential privacy when n≥48 ln(4/β)/τ^2, ε≤τ/4, and δ=exp(−4 · ln(8/β)/τ).
4 Beyond statistical queries
This section generalizes the privacy-to-generalization argument beyond statistical queries to arbitrary output spaces and associated bad-dataset sets. The resulting transfer theorem preserves small error probabilities for private outputs.
- For each output ψ, define R(ψ) as the datasets where its empirical average differs from P[ψ] by more than τ.
- The general transfer theorem applies to any private algorithm with output space Z when every output y has a sufficiently small probability of its associated bad set R(y).
- The proof uses differential privacy to control how output probabilities change across neighboring datasets, then applies concentration and related inequalities.
- Corollary 12 gives an ε-privacy condition under which the probability of statistical-query error exceeding τ is bounded by 3√… .
5 Applications
The applications instantiate the privacy-based framework with several query-answering mechanisms. These methods trade computational efficiency, dependence on the number of queries, tolerance, failure probability, and adaptivity structure.
- General framework: Differential privacy connects adaptive query answering to statistical validity because arbitrary analysts remain private when accessing data only through a private mechanism.Postprocessing preserves privacy, so adaptive query generation inherits the mechanism’s privacy guarantee.
- Laplacian Noise Addition: The Laplace algorithm efficiently answers m adaptively chosen [0,1]-valued functions with empirical-query error at most τ and per-query failure probability β under stated sample-complexity bounds.Its guarantees are given separately for pure and approximate differential privacy.
- Laplacian Noise Addition: The resulting efficient population estimates require n ≥ CnL(τ, β, m), while the corresponding approximate-privacy corollary improves the dependence on m quadratically at some cost in τ and 1/β.The comparison is explicitly made between the approximate-privacy result and the pure-privacy corollary.
- Multiplicative Weights Technique: Private Multiplicative Weights achieves an exponential improvement in m over the Laplacian mechanism, but its worst-case runtime is linear in |X| and is not generally computationally efficient.The method provides population-query guarantees through the differential-privacy generalization bound.
- Sparse Vector Technique: The sparse-vector mechanism answers queries with guesses by either returning an accurate answer or certifying that the guess is close within a threshold.Its guarantee distinguishes ⊥ outputs from numerical answers and provides separate error bounds for each case.
- Sparse Vector Technique: EffectiveRounds uses estimation samples plus a private round-detection sample and discards an estimation set when guesses indicate overfitting.Its cost depends on incorrect guesses, which may be smaller than the number of adaptivity rounds in practice.
A Adaptivity in fitting a linear model
The paper constructs an adaptive linear-fitting strategy that can overfit even a standard Gaussian distribution. It aggregates sample-specific correlations into a model that appears predictive on the sample despite lacking population linear structure.
- Adaptivity in fitting a linear model: The analyst seeks a unit vector or linear model maximizing average correlation with an unknown distribution, but instead optimizes the corresponding finite-sample objective.The sample contains n observations with d real-valued attributes.
- Adaptivity in fitting a linear model: The adaptive strategy determines the sign of each attribute’s empirical correlation and aggregates all signs into one linear model.The procedure repeatedly queries empirical averages before forming the final model.
- Adaptivity in fitting a linear model: Even when the underlying distribution is normally distributed and has no linear structure, the strategy falsely discovers a linear model with a large objective value.The result demonstrates poor generalization when the dimension is large.
- Adaptivity in fitting a linear model: For a standard Gaussian distribution, every unit vector has population objective f(u)=0, while the empirically selected model has a nonzero expected sample objective.The lemma supplies the distributional basis for the overfitting example.
- Adaptivity in fitting a linear model: The example can be converted to [0,1]-valued queries by truncating and rescaling Gaussian functions, changing the analysis only by a logarithmic factor.The relevant functions are coordinate projections and the final inner product.
B Background on Differential Privacy
Differential privacy protects individual data elements while allowing analysts to learn about the dataset and distribution. Its composition properties support sequences of adaptively chosen analyses, although privacy and utility degrade as answers accumulate.
- Theorem 25 composes k differential privacy mechanisms by summing their ε_i and δ_i parameters.The theorem applies to algorithms A_i whose joint output is the tuple of individual outputs.
- Theorem 26 gives a stronger composition guarantee for k arbitrary (ε, δ)-differentially private mechanisms, yielding (ε′, kδ + δ′)-differential privacy even under adaptive choice.
- Privacy composition can answer many queries, but overly accurate answers to too many questions eventually consume the available utility and destroy privacy.
C.1 Concentration inequalities
The section introduces concentration tools used to control deviations of random quantities from their expectations. It states a multiplicative Chernoff bound for Bernoulli sums and McDiarmid’s inequality for functions of independent variables.
- Lemma 27 states a multiplicative Chernoff bound for i.i.d. Bernoulli random variables with expectation p > 0.The bound applies for every γ > 0.
- Lemma 28 states McDiarmid’s inequality for a function of independent random variables when changing one input changes the function by at most c.It bounds deviations from the function’s expectation.
C.2 Moment Bounds
The section develops moment bounds for sums of bounded independent variables and uses them to control upper-tail probabilities. The derivation combines Bernoulli moment bounds, Chernoff estimates, Markov’s inequality, and explicit parameter conditions.
- Chernoff’s bound is substituted into the moment calculation to obtain an exponential upper-tail expression for the Bernoulli sum.The derivation introduces γ and optimizes an exponent involving k and np.
- Lemma 30 bounds the k-th moment of sums of independent [0,1]-valued variables by the corresponding Bernoulli case.The Bernoulli variables have expectation p, and the bound holds for n ≥ k ≥ 1.
- The Bernoulli moment estimate is derived by expanding over k-tuples of indices and grouping repeated indices by their multiplicities.
- The exponent is maximized at γ0 satisfying (1 + γ0) ln(1 + γ0) = k.
- Lemma 31 converts a k-th moment bound on a non-negative random variable into a tail bound using Markov’s inequality.The result assumes E[V^k] ≤ e^εk M_k[B(n, p)] + δ and controls P[V ≥ p + τ].
- The tail-bound derivation requires conditions including ε ≤ τ/2, τ ≤ 1/3, n ≥ 3k/τ, and k ≥ max{4 ln(2/β)/τ, 2 log log n}.