← 研踪 PaperTrailarXiv:2602.07732 · v2
Efficient Adaptive Data Analysis over Dense Distributions
首次提交 2026-02-08 07:44
版本更新 2026-11-09 13:12
雷达观测 2026-11-10 13:18
摘要
Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For $T$ rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal $O(\sqrt{T})$ sample complexity, whereas for arbitrary distributions, algorithms with $O(\log T)$ sample complexity are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and logarithmic sample complexity in $T$ are achievable. We propose a computationally efficient ADA mechanism that attains $O(\log T)$ sample complexity, optimal in its dependence on $T$, when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature-label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., $O(\log T)$ samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security (Cohen and Nissim 2020) whenever the number of its possible update transcripts is polynomial in the sample size. Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.
作者备注：20 pages, NeurIPS 2026 Camera-ready
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-09 13:12 · 最新观测版本
Efficient Adaptive Data Analysis over Dense Distributions
Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For $T$ rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal $O(\sqrt{T})$ sample complexity, whereas for arbitrary distributions, algorithms with $O(\log T)$ sample complexity are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and logarithmic sample complexity in $T$ are achievable. We propose a computationally efficient ADA mechanism that attains $O(\log T)$ sample complexity, optimal in its dependence on $T$, when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature-label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., $O(\log T)$ samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security (Cohen and Nissim 2020) whenever the number of its possible update transcripts is polynomial in the sample size. Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.
查看此版本解读 →查看此版本原文 ↗