# Is Randomness Necessary for Adaptive Data Analysis?

arXiv: https://arxiv.org/abs/2607.07085 · HTML: https://mlsanity.com/paper/2607.07085/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 25 of 25)

- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing](https://mlsanity.com/paper/1604.03924/) (2016)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [The Limits of Post-Selection Generalization](https://mlsanity.com/paper/1806.06100/) (2018)
- [Separating Adaptive Streaming from Oblivious Streaming](https://mlsanity.com/paper/2101.10836/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries](https://mlsanity.com/paper/2303.11843/) (2023)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [A Simple Proof of a New Set Disjointness with Applications to Data Streams](https://mlsanity.com/paper/2105.11338/) (2021)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Streaming algorithms for the missing item finding problem](https://mlsanity.com/paper/2211.05170/) (2022)
- [Finding missing items requires strong forms of randomness](https://mlsanity.com/paper/2310.03634/) (2023)
- [Tight Bounds for Answering Adaptively Chosen Concentrated Queries](https://mlsanity.com/paper/2507.13700/) (2025)
- [Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems](https://mlsanity.com/paper/2510.20341/) (2025)

## Abstract (arXiv)

The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing n i.i.d. samples from an unknown distribution P over a domain X, and our goal is to answer a sequence of k adaptively chosen statistical queries with respect to P. The main question is how many queries we can support (i.e., how large k can be), primarily as a function of the number of samples n. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support k ≈ n2 queries, and no computationally efficient mechanism can answer k gg n2 queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is em not necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic setting. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just k = tildeO(n) queries.