Is Randomness Necessary for Adaptive Data Analysis?

• URL: http://arxiv.org/abs/2607.07085v1
• Date: Wed, 08 Jul 2026 07:17:35 GMT
• Title: Is Randomness Necessary for Adaptive Data Analysis?
• Abstract summary: We show that randomness is strictly necessary to answer a non-trivial number of adaptive queries.<n>Despite a decade of work on ADA, this question remains open.
• Score: 54.49386214602422
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction [0.0]
  We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities.<n>We construct a matching family with constant adaptive query complexity and $_varepsilon(N2)$ non-adaptive query complexity.
  arXiv  Detail & Related papers  (2026-08-06T16:54:10Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Statistical and computational challenges in ranking [53.03724383992195]
  We consider the problem of ranking $n$ experts according to their abilities, based on the correctness of their answers to $d$ questions.<n>We investigate here the existence of statistically optimal and computationally efficient procedures for this problem.
  arXiv  Detail & Related papers  (2025-12-24T11:18:06Z)
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  We describe an algorithm that satisfies local differential privacy, performs $tildeO(k3/2)$ non-adaptive queries to individuals.<n>We also introduce a new object we dub the Scheff'e graph, which captures structure of the differences between distributions in $Q$.
  arXiv  Detail & Related papers  (2025-09-19T17:41:15Z)
• Let's Think Var-by-Var: Large Language Models Enable Ad Hoc Probabilistic Reasoning [15.568698101627088]
  We propose to extract common sense from large language models (LLMs)<n>We focus our investigation on $textitguesstimation$ questions such as "How much are Airbnb listings in Newark, NJ?"<n>Our framework answers such a question by an $textitad hoc$ probabilistic model.
  arXiv  Detail & Related papers  (2024-12-03T01:53:06Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks.<n>We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube.<n>We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Adaptive Data Analysis in a Balanced Adversarial Model [26.58630744414181]
  In adaptive data analysis, a mechanism gets $n$ i.i.d. samples from an unknown distribution $D$, and is required to provide accurate estimations. We consider more restricted adversaries, called emphbalanced, where each such adversary consists of two separated algorithms. We show that these stronger hardness assumptions are unavoidable in the sense that any computationally bounded emphbalanced adversary implies the existence of public-key cryptography.
  arXiv  Detail & Related papers  (2023-05-24T15:08:05Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
  We present an algorithm for solving binary classification problems when the dataset is not fully representative of the problem being solved.<n>Our algorithm works by reconstructing up to homology the manifold on which lies the support of the underlying distribution.
  arXiv  Detail & Related papers  (2020-10-15T19:17:51Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  We consider sparse regression from the view of correlation, and propose the formula of conditional uncorrelation. By the proposed method, the computational complexity is reduced from $O(frac16k3+mk2+mkd)$ to $O(frac16k3+frac12mk2)$ for each candidate subset in sparse regression.
  arXiv  Detail & Related papers  (2020-09-08T20:32:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.