Calibrating Noise to Variance in Adaptive Data Analysis
By Vitaly Feldman, Thomas Steinke. 2017
57 citations recorded by the source corpus.
Datasets are often used multiple times and each successive analysis may depend on the outcome of previous analyses. Standard techniques for ensuring generalization and statistical validity do not account for this adaptive dependence. A recent line of work studies the challenges that arise from such adaptive data reuse by considering the problem of answering a sequence of "queries" about the data distribution where each query may depend arbitrarily on answers to previous queries. The strongest results obtained for this problem rely on differential privacy -- a strong notion of algorithmic stability with the important property that it "composes" well when data is reused. However the notion is rather strict, as it requires stability under replacement of an arbitrary data element. The simplest algorithm is to add Gaussian (or Laplace) noise to distort the empirical answers. However, analysing this technique using differential privacy yields suboptimal accuracy guarantees when the queries have low variance. Here we propose a relaxed notion of stability that also composes adaptively. We demonstrate that a simple and natural algorithm based on adding noise scaled to the standard deviation of the query provides our notion of stability. This implies an algorithm that can answer statistical queries about the dataset with substantially improved accuracy guarantees for low-variance queries. The only previous approach that provides such accuracy guarantees is based on a more involved differentially private median-of-means algorithm and its analysis exploits stronger "group" stability of the algorithm.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Thomas Steinke
- Mark Bun
- Gintare Karolina Dziugaite
- Daniel M. Roy
- Jeffrey Negrea
- Mahdi Haghifam
- Jonathan Ullman
- Ashish J. Khisti
Citations in the corpus
- Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, methodology): “Our results can be viewed as providing a unified approach that simultaneously matches the results of Karwa and Vadhan [24] for Gaussians and Feldman and Steinke [16] for general distributions (and everything in between).”
- Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, background): “, in terms of average leave-one-out KL stability [12].”