Is Randomness Necessary for Adaptive Data Analysis?

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 \approx n^2 queries, and no computationally efficient mechanism can answer k \gg n^2 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 = \tilde{O}(n) queries.