Generalization for Adaptively-chosen Estimators via Stable Median

By Vitaly Feldman, Thomas Steinke. 2017

48 citations recorded by the source corpus.

Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not account for these dependencies and little is known about how to provably avoid overfitting and false discovery in the adaptive setting. We consider a natural formalization of this problem in which the goal is to design an algorithm that, given a limited number of i.i.d.~samples from an unknown distribution, can answer adaptively-chosen queries about that distribution. We present an algorithm that estimates the expectations of $k$ arbitrary adaptively-chosen real-valued estimators using a number of samples that scales as $\sqrt{k}$. The answers given by our algorithm are essentially as accurate as if fresh samples were used to evaluate each estimator. In contrast, prior work yields error guarantees that scale with the worst-case sensitivity of each estimator. We also give a version of our algorithm that can be used to verify answers to such queries where the sample complexity depends logarithmically on the number of queries $k$ (as in the reusable holdout technique). Our algorithm is based on a simple approximate median algorithm that satisfies the strong stability guarantees of differential privacy. Our techniques provide a new approach for analyzing the generalization guarantees of differentially private algorithms.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, neutral): “Theorem 2.11 ([24, 7, 52, 29]) .”
Privacy-preserving Prediction (2018, background): “Recent work in the context of adaptive data analysis has substantially strengthened this connection, proving that differential privacy ensures generalization with high probability (Dwork et al., 2014; Bassily et al., 2016; Feldman and Steinke, 2017).”
Unlocking High-Accuracy Differentially Private Image Classification through Scale (2022, background): “However these bounds degrade rapidly with increasing 𝜀 , and even the best bounds we are aware of are vacuous in our setting (Feldman and Steinke, 2017; Jung et al., 2020).”
Calibrating Noise to Variance in Adaptive Data Analysis (2017, background): “Recently, Feldman and Steinke [FS17] gave a diﬀerent algorithm that achieves such a guarantee.”