Is Randomness Necessary for Adaptive Data Analysis?

Edith Cohen; Haim Kaplan; Yishay Mansour; Shay Sapir; Uri Stemmer

cs.CRJul 8, 2026

Is Randomness Necessary for Adaptive Data Analysis?

Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer

Abstract

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 $\mathcal{P}$ over a domain $\mathcal{X}$ , and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $\mathcal{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 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 Random Oracle model. 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.

Explore similar work

Aug 6, 2026cs.LG

Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction

Model evaluations may fix all tests before observing any responses or select later tests using earlier responses. We study this choice in a conditional-query model on a finite outcome space

\mathcal{X}

with

|\mathcal{X}|=N

. We first ask which pairs of distribution classes can be reliably distinguished. We then ask how many additional queries are required to match an adaptive tester when all queried events must be fixed in advance. We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities. When this separation is zero, the optimal worst-case error is exactly

1/2

at every finite query budget. For any

T

-query adaptive policy and any

ρ\in (0,1)

, we construct a randomized non-adaptive procedure using

O(N^2(T + \log(1/ρ)))

pair queries chosen before any response is observed. Its simulated transcript is within

ρ

in total variation of the adaptive transcript, uniformly over all distributions in the model. We also construct a matching family with constant adaptive query complexity and

Ω_\varepsilon(N^2)

non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is

Θ_\varepsilon(N^2)

. Thus interaction can reduce the required number of tests by a quadratic factor, but the apparent exponential branching of an interactive evaluation does not yield an exponential query advantage.

Zonghuan Xu

Two-Sample Testing Sample Complexity Value

Ask PDF

Sep 17, 2024cs.DS

Clustering with Non-adaptive Subset Queries

Recovering the underlying

k

-clustering of a set

U

n

points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query

S \subset U

|S|=2

, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be

Θ(nk)

, while non-adaptive algorithms are extremely limited: even for

k=3

, such algorithms require

Ω(n^2)

queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for

|S|>2

, where the oracle returns the number of clusters intersecting

S

. Previous work obtained an

O(n)

query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making

O(n \log k \cdot (\log k + \log\log n)^2)

queries, improving to

O(n \log \log n)

when

k

is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound,

s

, on the query size. We show

Ω(\max(n^2/s^2,n))

queries are necessary and obtain algorithms making

\smash{\widetilde{O}(n^2k/s^2)}

queries for any

s \leq \sqrt{n}

and

\smash{\widetilde{O}(n^2/s)}

queries for any

s \leq n

. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.

Hadley Black, Euiwoong Lee, Arya Mazumdar +1

Clustering Sample Complexity

Ask PDF

Jul 3, 2026cs.IT

Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

Ivan Lau, Jonathan Scarlett

Optimal Sample Complexity Estimators Low-Bit Quantization Exponential Family Interaction Patterns

Ask PDF