Preserving statistical validity in adaptive data analysis (extended abstract)
From MaRDI portal
Abstract: 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 adaptively chosen functions on an unknown distribution given random samples. We show that, surprisingly, there is a way to estimate an exponential in 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.
Recommendations
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(37)- Scalable methods for Bayesian selective inference
- Online rules for control of false discovery rate and false discovery exceedance
- Selective inference with a randomized response
- Separating adaptive streaming from oblivious streaming using the bounded storage model
- Learning privately with labeled and unlabeled examples
- The reusable holdout: preserving validity in adaptive data analysis
- Fingerprinting codes and the price of approximate differential privacy
- On the Power of Learning from k-Wise Queries
- Comment
- Comment
- Rejoinder
- Test Data Reuse for the Evaluation of Continuously Evolving Classification Algorithms Using the Area under the Receiver Operating Characteristic Curve
- Lower bounds for parallel and randomized convex optimization
- Algorithmic stability for adaptive data analysis
- Asynchronous online testing of multiple hypotheses
- Structure and sensitivity in differential privacy: comparing \(K\)-norm mechanisms
- Preserving randomness for adaptive algorithms
- The complexity of differential privacy
- Private sequential learning
- Perturbation of convex risk minimization and its application in differential private learning algorithms
- scientific article; zbMATH DE number 7626742 (Why is no real title available?)
- Inferactive data analysis
- Algorithmic stability for adaptive data analysis
- On differential privacy and adaptive data analysis with bounded space
- Post-selection inference via algorithmic stability
- Stability is stable: connections between replicability, privacy, and adaptive generalization
- Adversarially robust streaming algorithms via differential privacy
- Improved quantum data analysis
- A framework for adversarial streaming via differential privacy and difference estimators
- Subsampling suffices for adaptive data analysis
- Making progress based on false discoveries
- Algorithmic stability implies training-conditional coverage for distribution-free prediction methods
- Simple dynamic spanners with near-optimal recourse against an adaptive adversary
- Valid Inference After Causal Discovery
- Sampling without compromising accuracy in adaptive data analysis
- Average-case information complexity of learning
- PAC verification of statistical algorithms
This page was built for publication: Preserving statistical validity in adaptive data analysis (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941495)
