Max-Information, Differential Privacy, and Post-selection Hypothesis Testing

By Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar. 2016

91 citations recorded by the source corpus.

In this paper, we initiate a principled study of how the generalization properties of approximate differential privacy can be used to perform adaptive hypothesis testing, while giving statistically valid p-value corrections. We do this by observing that the guarantees of algorithms with bounded approximate max-information are sufficient to correct the p-values of adaptively chosen hypotheses, and then by proving that algorithms that satisfy (∈,δ)-differential privacy have bounded approximate max information when their inputs are drawn from a product distribution. This substantially extends the known connection between differential privacy and max-information, which previously was only known to hold for (pure) (∈,0)-differential privacy. It also extends our understanding of max-information as a partially unifying measure controlling the generalization properties of adaptive data analyses. We also show a lower bound, proving that (despite the strong composition properties of max-information), when data is drawn from a product distribution, (∈,δ)-differentially private algorithms can come first in a composition with other algorithms satisfying max-information bounds, but not necessarily second if the composition is required to itself satisfy a nontrivial max-information bound. This, in particular, implies that the connection between (∈,δ)-differential privacy and max-information holds only for inputs drawn from product distributions, unlike the connection between (∈,0)-differential privacy and max-information.

Subfields: Artificial Intelligence

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

Citations in the corpus

Calibrating Noise to Variance in Adaptive Data Analysis (2017, background): “Another known implication of bounded mutual information is that any event that would happen with sufficiently low probability on fresh data will still happen with low probability (Russo and Zou, 2016; Rogers et al., 2016).”
Generalization for Adaptively-chosen Estimators via Stable Median (2017, methodology): “Generalization guarantees in the adaptive setting can also be derived via other approaches such as bounding the approximate max-information or mutual information between the choice of estimator and the data (Dwork et al., 2015a; Rogers et al., 2016; Russo and Zou, 2016) or using other notions of sta”
Adversarially Learned Representations for Information Obfuscation and Inference (2019, methodology): “This differs from other frameworks such as Differential Privacy (DP) (Dwork, 2008; Dwork et al., 2015; Rogers et al., 2016; Holohan et al., 2015) where guarantees are provided as a worst-case scenario, a strictly stronger notion than the one proposed here.”
A New Class of Private Chi-Square Tests (2016, background): “Specifically, [17] deals with post-selection hypothesis testing where they can ensure a bound on Type I error even for several adaptively chosen tests, as long as each test is differentially private.”
Adaptive Machine Unlearning (2021, methodology): “1 (DP implies bounded max-information [Rogers et al., 2016]).”
The Complexity of Differential Privacy (2017, background): “We remark that for approximate differential privacy, one can bound the mutual information I(X;M(X)) in case the rows of X are independent [77, 91], but these bounds do not hold for general correlated distributions [29].”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “More formally, it is known that differential privacy implies a bound on the mutual information I(X;M) [27, 17, 34, 10].”