# Efficient Adaptive Data Analysis over Dense Distributions

arXiv: https://arxiv.org/abs/2602.07732 · HTML: https://mlsanity.com/paper/2602.07732/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 7 Feb 2026.

## Builds on (most cited first, 30 of 30)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing](https://mlsanity.com/paper/1604.03924/) (2016)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Towards Formalizing the GDPR's Notion of Singling Out](https://mlsanity.com/paper/1904.06009/) (2019)
- [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014)
- [The Limits of Post-Selection Generalization](https://mlsanity.com/paper/1806.06100/) (2018)
- [Adaptive Learning with Robust Generalization Guarantees](https://mlsanity.com/paper/1602.07726/) (2016)
- [A bounded-noise mechanism for differential privacy](https://mlsanity.com/paper/2012.03817/) (2020)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis](https://mlsanity.com/paper/1906.09231/) (2019)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Sampling Without Compromising Accuracy in Adaptive Data Analysis](https://mlsanity.com/paper/1709.09778/) (2017)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [Information, Privacy and Stability in Adaptive Data Analysis](https://mlsanity.com/paper/1706.00820/) (2017)
- [A Rademacher Complexity Based Method fo rControlling Power and Confidence Level in Adaptive Statistical Analysis](https://mlsanity.com/paper/1910.03493/) (2019)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)

## Abstract (arXiv)

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(√T) sample complexity, whereas statistically optimal O(log T) algorithms 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 optimal sample complexity are achievable. We propose a computationally efficient ADA mechanism that attains optimal O(log T) sample complexity 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). Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.