Source-linked AI summary
The Limits of Post-Selection Generalization
Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman
TL;DR
Adaptive choices based on prior interactions with a dataset complicate generalization, motivating algorithms that provide post hoc guarantees. This paper establishes limits for such guarantees on adaptive statistical queries and shows that they may fail under composition.
Problem
Adaptivity makes the choice of analysis depend on previous interactions with the same dataset, raising the question of how conclusions can be made to generalize to its population.
Source: §1 · p. 1Method
The paper proves lower bounds for post hoc generalizing algorithms answering adaptive statistical queries and constructs examples where individually generalizing algorithms fail under composition.
Source: §1 · p. 3Results
The authors establish almost tight accuracy limits for adaptive statistical queries and show that composition can lose all non-trivial post hoc generalization, even for a collection of O(log n) algorithms.
Source: §1 · p. 3, §1.1.2 · pp. 4–5Takeaways & Limitations
The results identify barriers to progress with post hoc generalization and motivate studying subclasses of such algorithms that do compose.
Source: §1.1.2 · p. 5The lower-bound conclusion requires domain dimension at least k; it is false when d ≪ k.
Source: §1.1.1 · p. 4
Abstract
from arXiv · showhide
While statistics and machine learning offer numerous methods for ensuring generalization, these methods often fail in the presence of adaptivity---the common practice in which the choice of analysis depends on previous interactions with the same dataset. A recent line of work has introduced powerful, general purpose algorithms that ensure post hoc generalization (also called robust or post-selection generalization), which says that, given the output of the algorithm, it is hard to find any statistic for which the data differs significantly from the population it came from. In this work we show several limitations on the power of algorithms satisfying post hoc generalization. First, we show a tight lower bound on the error of any algorithm that satisfies post hoc generalization and answers adaptively chosen statistical queries, showing a strong barrier to progress in post selection data analysis. Second, we show that post hoc generalization is not closed under composition, despite many examples of such algorithms exhibiting strong composition properties.
1 Introduction
Adaptivity—choosing analyses based on prior interactions with the same dataset—undermines generalization methods that assume data-independent selection. The paper identifies limits on post hoc generalization for adaptive statistical queries and on composing algorithms with that guarantee.
1 Introduction
- Adaptive analysis can undermine statistical validity because analysts choose methods using prior interactions with the same data.The paper frames this as a concern for exploratory analysis, feature selection followed by regression, and dataset reuse.Source: §1 · pp. 1–2
- Earlier post-selection inference methods generally tailor conditional inference or uniform-convergence arguments to a particular analysis sequence, rather than prescribe how to design one.The authors study post hoc generalization, a guarantee that the algorithm's output does not make it possible to identify a statistical query whose dataset and population values differ significantly.Source: §1 · p. 2
1.1.1 Sample Complexity Bounds for Statistical Queries
- The paper gives new, almost tight limits on the accuracy of post hoc generalizing algorithms answering adaptively chosen statistical queries.The authors describe the lower bound as a barrier to improving state-of-the-art algorithms within this analysis framework; their result has optimal dependence on ε.Source: §1 · p. 3, §1.1.1 · pp. 3–4
1.1.2 Negative Results for Composition
- A collection of O(log n) algorithms can each have almost optimal post hoc generalization while their composition has no non-trivial post hoc generalization.The paper also shows that computational post hoc generalization can fail under composition for just two algorithms, assuming pseudorandom generators exist.Source: §1.1.2 · pp. 4–5
1.2 Related Work
- Related selective-inference approaches include uniform validity for particular analysis classes and conditioning on prior answers, but may require large samples, a prior, or computationally infeasible methods.The authors describe conditional-inference work as more descriptive than prescriptive, and identify its connection to their approach as an open problem.Source: §1 · p. 2, §1.2 · p. 5
2 Lower Bounds for Statistical Queries
This section formalizes post hoc generalization for adaptive statistical queries and develops a score-based lower-bound argument for natural algorithms. The proof establishes a high-probability dichotomy between a tracing query violating post hoc generalization and the algorithm accumulating a large in-sample score.
2.1 Post Hoc Generalization for Adaptive Statistical Queries
- The section frames adaptive statistical queries as an interaction in which an adversary may choose each query based on earlier queries and answers, and defines post hoc generalization and accuracy for this setting.Source: §2.1 · p. 6
2.2 A Lower Bound for Natural Algorithms
- With k = Θ(ε^4n^2 log(1/ε)), a natural algorithm has probability at least 2/3 of inaccurate answers, a tracing-query generalization violation, or a final query whose empirical and population answers differ by more than ε.The bound applies for sufficiently small ε and sufficiently large n with ε^2n ≥ C log n.Source: §2.2 · pp. 7, 9
2.2.1 Proof of Claim 2.7
- The proof of Claim 2.7 uses fingerprinting to establish large expected in-sample scores, then truncates answers around the empirical query average to obtain a high-probability bound while linking that truncation to the algorithm’s bias-based truncation.This link relies on the empirical average tracking the bias when few sample points have been accused; too many accusations imply a post hoc generalization violation.Source: §2.2.1 · pp. 10, 12
- The proof keeps truncation inactive while fewer than 6εn sample items are accused, then establishes conditional drift and applies Azuma’s inequality to the stopped scores.The subclaims show the untruncated scores coincide with the algorithm’s scores in those rounds and the stopped sum is large with high probability.Source: §2.2.1 · p. 14
- When the stopping time T ≥ k−20, the accumulated in-sample scores are at least k/18, establishing Claim 2.7’s second outcome.The proof bounds the stopped sum below by T/13−k/48, then accounts for at most 20 remaining rounds.Source: §2.2.1 · pp. 15–16
- With probability at least 49/50, every natural mechanism satisfies one of Claim 2.7’s two outcomes: a tracing-query violation or the score outcome.The bound holds for sufficiently large n with ε^2n ≥ C log n.Source: §2.2.1 · p. 16
3 Lower Bounds for General Algorithms
The section lifts lower bounds against natural algorithms to arbitrary algorithms using random masks, then uses pseudorandom masks to obtain analogous computational lower bounds with lower-dimensional data. The computational reduction relies on a pseudorandom generator and is stated for computationally bounded algorithms.
3 Lower Bounds for General Algorithms
- The section lifts lower bounds against natural algorithms to arbitrary algorithms by constructing adversaries that preserve the algorithm’s view.The information-theoretic source adversary chooses the uniform distribution on [N].Source: §3 · p. 17, §3.1 · p. 17
3.1 Information-Theoretic Lower Bounds via Random Masks
- Random masks hide query evaluations outside the dataset, effectively forcing an arbitrary algorithm to behave like a natural algorithm.The reduction transfers the source adversary’s lower bound to an adversary for arbitrary algorithms.Source: §3.1 · p. 17
3.2 Computational Lower Bounds via Pseudorandom Masks
- Pseudorandom masks use a short seed to generate bits that appear random to computationally efficient algorithms, reducing the data dimension needed for masking.The random-mask procedure requires data dimension at least the number of queries because the mask is given to the algorithm.Source: §3.2 · pp. 19–20
- The stated pseudorandom-generator assumption gives seed length kc and error k^-C for sufficiently large k, for arbitrarily small c > 0 and large C > 0.The assumption also sets the running-time bound to k^C.Source: §3.2 · p. 19
- Under a pseudorandom-generator assumption, the computational reduction transfers the natural-algorithm lower bound to computationally bounded algorithms.Replacing pseudorandom masks with uniform masks changes the relevant failure probability by at most O(Nγ) for an efficient algorithm.Source: §3.2 · pp. 20–21
4 Post Hoc Generalization Does Not Compose
The paper shows that post hoc generalization can fail under composition in both information-theoretic and computational settings. In the information-theoretic construction, individually generalizing mechanisms can collectively reveal the sample; the computational result gives a two-mechanism construction under a pseudorandom-generator assumption.
4.1 Information-Theoretic Composition
- The information-theoretic construction composes mechanisms that individually satisfy post hoc generalization, yet their combined output reveals the sample.The recovered sample permits defining a predicate that is 1 on every sample element.Source: §4.1 · pp. 21, 23
- Encrypermute makes its output independent of the dataset, while repeated compositions can progressively reveal the full sample.The proof describes the composed mechanisms as revealing all of X, from which a sample-membership predicate can be defined.Source: §4.1 · pp. 21, 23
4.2 Computational Post Hoc Generalization
- Assuming a pseudorandom generator with the stated parameters, two mechanisms can each satisfy computational post hoc generalization while their composition does not.The construction composes PRG-Encrypermute with a mechanism that outputs the first k elements.Source: §4.2 · pp. 23, 24, 26
- The computational construction replaces uniform masks with pseudorandom masks, using a generator to stretch a short seed into a longer key for encryption.The proof contrasts this with the information-theoretic construction, which needs multiple rounds because its key can encrypt only as many bits as its length.Source: §4.2 · pp. 24, 26