Source-linked AI summary
Algorithmic Stability for Adaptive Data Analysis
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman
TL;DR
Adaptive data analysis raises the question of how many independent samples are needed to answer adversarially chosen queries accurately. This work gives optimal and simpler stability-based analyses, yielding improved bounds for statistical queries and first bounds for broader query families.
Problem
The paper studies how to answer adaptively and adversarially chosen queries about an unknown distribution using independent samples while preserving statistical validity.
Method
The authors analyze max-KL stable algorithms and generalize the connection between stability and statistical validity to broader statistics using simpler proofs and a monitoring construction.
Results
n ≳ k/α^2 samples suffice for k adaptive statistical queries, with optimal dependence on α; the work also gives first sample-complexity bounds for low-sensitivity and optimization queries.
Takeaways & Limitations
Stability-based mechanisms provide the best known sample-complexity bounds for adaptive statistical queries and extend validity guarantees to broader query families.
Takeaways & Limitations
Using weaker total-variation stability yields a weaker bound, while max-KL stability requires decreasing δ with the number of queries rather than ε.
Abstract
from arXiv · showhide
Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated the formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. Specifically, suppose there is an unknown distribution $\mathbf{P}$ and a set of $n$ independent samples $\mathbf{x}$ is drawn from $\mathbf{P}$. We seek an algorithm that, given $\mathbf{x}$ as input, accurately answers a sequence of adaptively chosen queries about the unknown distribution $\mathbf{P}$. How many samples $n$ must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? In this work we make two new contributions: (i) We give upper bounds on the number of samples $n$ that are needed to answer statistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015, NIPS, 2015). (ii) We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and an important class of optimization queries. As in Dwork et al., our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that stability implies low generalization error. We also study weaker stability guarantees such as bounded KL divergence and total variation distance.
1 Introduction
The paper studies how to preserve statistical validity when analyses adapt to prior data interactions, extending stability-based guarantees to broader query families and sharper bounds. It develops optimal analyses for max-KL stability, new bounds for low-sensitivity and optimization queries, and weaker-stability results.
- Motivation: Adaptive data analysis can produce false discoveries because later analyses depend on earlier interactions with the same data.This adaptivity occurs in sequential research, preprocessing pipelines, competitions, and test-data reuse.
- Problem formulation: The paper models a mechanism answering adaptively chosen queries using a finite sample while requiring answers to generalize to the underlying distribution.A response is α-accurate when it differs from the population query value by at most α with high probability.
- Existing baseline: For statistical queries, empirical answers require n ≳ log(k)/α^2 samples nonadaptively but can require n ≳ k/α^2 under adaptive querying.An adaptive procedure can find an α-error query after observing answers to O(α^2n) random queries.
- Contributions: The paper gives a simpler, quantitatively optimal stability-to-generalization analysis yielding improved adaptive statistical-query bounds, including n ≳ k/α^2 samples.The dependence on α is optimal because 1/α^2 samples are necessary even for one nonadaptive query.
- Contributions: The guarantees extend beyond statistical queries to arbitrary low-sensitivity queries and optimization queries, while requiring a weaker stability condition than prior work.Low-sensitivity examples include distance queries and maxima of statistical queries.
- Techniques: A monitor amplifies rare generalization failures by running stable mechanisms on independent samples and selecting the query with the largest error.This reduction avoids parameter loss from a union bound over queries and supports broader stability notions.
- Scope and limits: The connection between max-KL stability and generalization is optimal, whereas KL- and TV-stability yield polynomially rather than exponentially decreasing error tails.The paper states that improving its bounds requires weaker stability or a different approach.
2 Preliminaries
The preliminaries define query families, adaptive accuracy, and stability for interactive mechanisms. They also introduce accuracy games and composition properties used to analyze mechanisms answering adaptively chosen queries.
- Queries: Statistical queries evaluate the expected value of a function q: X → [0,1] under the population distribution.
- Queries: Low-sensitivity queries generalize statistical queries by changing by at most 1/n when one sample changes, including distance and optimization-related examples.They are defined through an arbitrary function on datasets and its expectation over samples from the population.
- Queries: Minimization queries select a parameter minimizing a loss function, with finite-set and convex variants; low-sensitivity queries reduce to minimization using L(x;θ)=|θ−q(x)|.
- Adaptive accuracy: The mechanism must answer up to k queries accurately for every adversary, even when each query depends arbitrarily on earlier queries and answers.Accuracy is defined relative to either the population or the supplied sample.
- Stability: Interactive stability is defined by treating the mechanism–analyst transcript as a noninteractive algorithm and requiring max-KL stability for every adversary.Max-KL stability is also called differential privacy and is preserved under post-processing.
- Stability: A mechanism stable for one query remains approximately (kε,kδ)-stable after k adaptive queries through composition.
3 From Max-KL Stability to Accuracy for Low-Sensitivity Queries
The section proves that max-KL stability transfers sample accuracy to population accuracy for adaptive low-sensitivity queries. A monitoring algorithm and de-correlated expectation lemmas provide the key bridge, with max-KL yielding stronger bounds than total variation stability.
- Monitoring argument: The proof uses multiple independent samples and a monitor that outputs the least accurate query across simulated interactions.The monitor preserves stability while amplifying any nontrivial probability of population-level inaccuracy.
- De-correlated expectation: The main technical lemma bounds the expected difference between a query’s population value and its value on the selected subsample for max-KL stable mechanisms.It applies to Δ-sensitive queries and multiple samples, using intermediate datasets and post-processing stability.
- Comparison of stability notions: Using total variation stability instead gives the weaker bound 2T(e^ε −1 + δ)Δn, whereas max-KL stability requires decreasing δ with T but not ε.The distinction matters because stable mechanisms have linear dependence on 1/ε and only polylogarithmic dependence on 1/δ.
- Proof construction: The proof interpolates between independent sample collections through neighboring intermediate datasets, enabling repeated applications of max-KL stability.The intermediate samples preserve identical marginal distributions while differing by controlled replacements.
- Main transfer theorem: A max-KL stable mechanism that is accurate on its sample is also accurate on the population for adaptively chosen low-sensitivity queries.This is the section’s main transfer result.
4 Other Notions of Stability and Accuracy on Average
This section compares stability notions beyond max-KL stability and shows that total variation stability supports weaker, expectation-based accuracy guarantees. Post-processing preserves these notions, and a monitoring argument transfers sample accuracy on average to population accuracy on average.
- Relationships: KL stability implies TV stability by Pinsker’s inequality, while max-KL stability has more nuanced relationships with both notions.For ε ≤1, (ε,0)-max-KL stability implies ε-KL and ε-TV stability; with δ > 0 it implies (2ε + δ)-TV stability.
- Composition: TV stability composes linearly across queries, while KL and max-KL stability offer stronger composition behavior.A mechanism that is ε-TV stable for one query becomes εk-stable for k queries.
- TV stability and average accuracy: Total variation stable algorithms guarantee accuracy on average for adaptively chosen queries, rather than the high-probability accuracy considered earlier.Average accuracy is defined through expected error over the mechanism’s and analyst’s randomness.
- Proof strategy: The TV-stability proof uses intermediate samples differing in one entry to compare the monitor’s output distributions.Post-processing preserves TV stability, and the intermediate samples have matching marginals despite dependence.
- Transfer result: If a mechanism is (α/2)-accurate on average for its sample and sufficiently TV-stable, it is α-accurate on average for the population.The result applies to k adaptively chosen queries from a low-sensitivity query family.
5 From Low-Sensitivity Queries to Optimization Queries
The section extends the transfer framework from low-sensitivity queries to minimization queries. Its monitor outputs a low-sensitivity error function associated with the most inaccurate loss-function answer, enabling the same contradiction argument.
- Monitoring algorithm: The monitoring algorithm simulates the mechanism and analyst on multiple independent samples and selects the interaction with the largest error.It then outputs the associated error function rather than the minimization query itself.
- Transfer theorem: A max-KL stable mechanism that is accurate on its sample is also accurate on the population for adaptively chosen minimization queries.The transfer theorem uses explicit stability and sample-accuracy parameters involving α, β, Δ, and n.
- Proof relationship: The formal proof is nearly identical to the low-sensitivity transfer proof, with the monitoring algorithm modified to represent loss and answer error.The modification addresses the fact that the general technical lemma applies directly only to low-sensitivity outputs.
- Reduction to low sensitivity: The selected error function is 2Δ-sensitive, allowing the low-sensitivity de-correlated expectation lemma to apply.This converts a population-versus-sample discrepancy for a minimization query into a discrepancy for a low-sensitivity query.
6 Applications
The section instantiates the transfer theorems with existing differentially private mechanisms. These corollaries provide population-accuracy guarantees for adaptive low-sensitivity, statistical, and optimization queries under specified query and loss-function classes.
- Low-sensitivity queries: Existing stable mechanisms yield high-probability population-accuracy guarantees for adaptive low-sensitivity queries with Δ = O(1/n).Two corollaries instantiate the theorem using known mechanisms, with different computational costs.
- Statistical queries: A separate instantiation provides average population accuracy for adaptive statistical queries using a known differentially private mechanism.The mechanism is reported to run in time poly(n,|X|) per query.
- Finite-domain optimization: Existing private empirical-risk minimization algorithms yield mechanisms for adaptive minimization queries over finite parameter sets.For sensitivity-1/n losses bounded between 0 and C, the running time is dominated by O((k + log(1/β)) · D) loss evaluations.
- Convex optimization: The framework applies to convex 1-Lipschitz losses over bounded convex domains, with mechanisms based on gradient evaluations.The cited corollaries cover both convex and strongly convex loss-function classes.
- Strongly convex optimization: For 1-strongly convex, 1-Lipschitz, 1/n-sensitive losses, the framework also gives adaptive population-accuracy mechanisms over bounded convex domains.The implementation uses polynomial-time computation together with k · n^2 gradient evaluations.
7 An Alternative Form of Generalization and Tightness of Our Results
This section reformulates the generalization guarantee as stability preventing sample–population distinction, then establishes that the guarantee is tight through a matching construction.
- 7 An Alternative Form of Generalization and Tightness of Our Results: A technical entropy lemma analyzes exponential-mechanism sampling by relating its normalizing constant and Shannon entropy to the maximum value of the scored function.The entropy is measured in nats, and uniformity provides the entropy upper bound used in the argument.
- 7 An Alternative Form of Generalization and Tightness of Our Results: Theorem 7.2 states that a stable mechanism outputting a low-sensitivity query cannot produce a query that distinguishes its sample from the population.This formulation is more general than requiring the procedure to output a query that fits its sample.
- 7 An Alternative Form of Generalization and Tightness of Our Results: The result gives a learning-theory perspective: when a stable mechanism outputs a query that fits its data, the query also fits the population.
- 7 An Alternative Form of Generalization and Tightness of Our Results: The proof introduces a monitor that accesses its input through the stable mechanism and an exponential mechanism, then uses composition and postprocessing to establish stability.The monitor is shown to be (2ε,δ)-max-KL stable before applying the generalization lemmas.
- 7 An Alternative Form of Generalization and Tightness of Our Results: The proof proceeds by assuming a stable mechanism often outputs a query with large sample–population discrepancy and deriving a contradiction from the monitor’s output.The discrepancy is represented as q(x_t) − q(P), with the monitor selecting among signed query-instance pairs.
- 7.1 Optimality: The max-KL stability–generalization connection is optimal: a (0,δ)-max-KL stable algorithm can output a ∆-sensitive query whose sample and population answers differ by at least α∆n.The construction uses a randomized database-release procedure and a query built from released sample points.
- 7.1 Optimality: The lower-bound construction remains (0,δ)-max-KL stable because its component procedures operate on disjoint databases.
- 7.1 Optimality: The construction’s discrepancy follows because the population query value is zero while the sample query counts released sample points, with failure probability bounded by the stated construction.