# Preserving Statistical Validity in Adaptive Data Analysis

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

## Key facts

- Cited by 103 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2014.

## Built on by (most cited first, 30 of 103)

- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Antipodes of Label Differential Privacy: PATE and ALIBI](https://mlsanity.com/paper/2106.03408/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Enhancing Adversarial Training with Second-Order Statistics of Weights](https://mlsanity.com/paper/2203.06020/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Leave-one-out Unfairness](https://mlsanity.com/paper/2107.10171/) (2021)
- [Inherent Trade-Offs between Diversity and Stability in Multi-Task Benchmarks](https://mlsanity.com/paper/2405.01719/) (2024)
- [Differentially Private Label Protection in Split Learning](https://mlsanity.com/paper/2203.02073/) (2022)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Do Question Answering Modeling Improvements Hold Across Benchmarks?](https://mlsanity.com/paper/2102.01065/) (2021)
- [RATT: Leveraging Unlabeled Data to Guarantee Generalization](https://mlsanity.com/paper/2105.00303/) (2021)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [On the Privacy Properties of GAN-generated Samples](https://mlsanity.com/paper/2206.01349/) (2022)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [A Theory of Dynamic Benchmarks](https://mlsanity.com/paper/2210.03165/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Patterns, predictions, and actions: A story about machine learning](https://mlsanity.com/paper/2102.05242/) (2021)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization](https://mlsanity.com/paper/2210.01318/) (2022)
- [Online multiple testing with e-values](https://mlsanity.com/paper/2311.06412/) (2023)
- [Does Label Differential Privacy Prevent Label Inference Attacks?](https://mlsanity.com/paper/2202.12968/) (2022)
- [What You See is What You Get: Principled Deep Learning via Distributional Generalization](https://mlsanity.com/paper/2204.03230/) (2022)

## Abstract (arXiv)

A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of m adaptively chosen functions on an unknown distribution given n random samples. We show that, surprisingly, there is a way to estimate an exponential in n number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question.