AI & ML
Is Randomness Necessary for Adaptive Data Analysis?
arXiv cs.CR0 views
arXiv:2607.07085v3 Announce Type: replace 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 {\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 {\em 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.
Source:https://arxiv.org/abs/2607.07085PreviousStatic Attribution of Android Residential Proxy Malware Using Graph KernelsNextLanguage Model Security Modules: Turning LLM Interpretability into Runtime Defense
Related posts
paper-orchestra: A Multi-Agent Pipeline That Turns Experiment Logs Into LaTeX Submissions
0dev.to
Kerberos Through the HTTPS Tunnel: Pre-Auth Capture via the KDC Proxy
0dev.to
We checked 100 well-known sites for AI-crawler readiness: llms.txt, robots.txt, schema, sitemaps
0dev.to
We asked ChatGPT, Perplexity and Gemini which software to buy. Here's who they named first
0dev.to
LangSmith to RAGAS — converting an exported dataset without losing fields silently
0dev.to
![Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fawosw4u7jitr9h27f7c5.png)
Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]
0dev.to