Source-linked AI summary
Hypothesis Testing Interpretations and Renyi Differential Privacy
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, Tetsuya Sato
TL;DR
The paper asks when privacy definitions based on statistical divergences admit the hypothesis-testing interpretation familiar from differential privacy. It introduces k-cuts and k-generatedness, showing that 2-generatedness is the relevant criterion, that Rényi divergence is instead ∞-generated, and that its 2-cut restores the interpretation while improving conversion rules to differential privacy.
Problem
The paper investigates whether variants of differential privacy based on Rényi divergence can receive hypothesis-testing interpretations similar to differential privacy.
Method
The paper introduces k-cuts and k-generatedness to analyze how many decisions are needed for a divergence to be fully characterized in a hypothesis test.
Results
A privacy definition has a hypothesis-testing interpretation exactly when its divergence is 2-generated; Rényi divergence is ∞-generated, but its 2-cut provides the interpretation and better conversion rules to (ε, δ)-differential privacy.
Takeaways & Limitations
The framework distinguishes the direct hypothesis-testing semantics of differential privacy from Rényi-based relaxations and supplies a 2-cut-based route for analyzing the latter.
Takeaways & Limitations
The input model assumes datasets are related by a symmetric adjacency relation, informally differing in one individual’s data, and one technical claim holds only for sufficiently well-behaved distributions.
Abstract
from arXiv · showhide
Differential privacy is a de facto standard in data privacy, with applications in the public and private sectors. A way to explain differential privacy, which is particularly appealing to statistician and social scientists is by means of its statistical hypothesis testing interpretation. Informally, one cannot effectively test whether a specific individual has contributed her data by observing the output of a private mechanism---any test cannot have both high significance and high power. In this paper, we identify some conditions under which a privacy definition given in terms of a statistical divergence satisfies a similar interpretation. These conditions are useful to analyze the distinguishability power of divergences and we use them to study the hypothesis testing interpretation of some relaxations of differential privacy based on Renyi divergence. This analysis also results in an improved conversion rule between these definitions and differential privacy.
1 Introduction
The paper develops a hypothesis-testing interpretation for privacy definitions based on statistical divergences, focusing on when finitely many test decisions characterize them. It applies this framework to differential privacy and Rényi-based relaxations, while deriving conversion rules and characterization conditions.
- Analytical framework: The paper introduces k-cuts and k-generatedness to measure how many decisions are needed to characterize a divergence in a hypothesis test.A k-cut restricts input distributions to a domain of cardinality k, while k-generatedness means the divergence equals its k-cut.
- Analytical framework: A divergence-based privacy definition has a hypothesis-testing interpretation if and only if the divergence is 2-generated.The 2-generatedness criterion connects divergence characterization to tests with two possible outcomes.
- Applications: The 2-cut of Rényi divergence yields better conversion rules from Rényi differential privacy to (ε, δ)-differential privacy.The paper also uses this tool to study relations with Gaussian Differential Privacy.
- Characterization: For quasi-convex divergences, being defined as a supremum over probabilities of k-partitions is sufficient and necessary for k-generatedness.This characterization provides a way to construct divergences supporting the hypothesis-testing interpretation.
- Differential privacy: The differential-privacy divergence is 2-generated, supporting the usual hypothesis-testing interpretation of differential privacy.The paper also relates this property to privacy regions introduced in prior work.
- Rényi differential privacy: Rényi divergence is ∞-generated, so Rényi-based privacy notions do not directly admit the same hypothesis-testing interpretation.The paper obtains such an interpretation by using the 2-cut of Rényi divergence instead.
2 Background: hypothesis testing, privacy, and Rényi divergences
The paper frames differential privacy as limiting the ability to distinguish adjacent datasets through hypothesis tests, then introduces Rényi-based privacy variants and their privacy-loss interpretations.
- Hypothesis testing interpretation: A hypothesis test observes a mechanism output and decides whether it came from M(x0) or M(x1) using a rejection region.The null is that the output came from M(x0), while the alternative is that it came from M(x1).
- Hypothesis testing interpretation: Differential privacy guarantees that no rejection rule can achieve low Type I and Type II errors simultaneously on adjacent inputs.The error-rate inequalities characterize (ε, δ)-differential privacy and make adjacent output distributions statistically hard to distinguish.
- Privacy regions: Privacy regions describe the attainable pairs of false-alarm and missed-detection probabilities for tests between adjacent inputs.For DP, the region is characterized by (1 − x) ≤ e^εy + δ, together with its symmetric counterpart in the full formulation.
- Research question: The paper asks whether Rényi-based and other differential-privacy variants admit hypothesis-testing interpretations analogous to DP.This question motivates the subsequent analysis of divergences and their distinguishability power.
- Rényi-based variants: Rényi-based privacy definitions bound moments of privacy loss, whereas DP bounds its maximum value and related concentrated definitions bound different ranges of moments.RDP fixes an order α, zCDP quantifies over all α > 1, and tCDP quantifies over α below a threshold.
3 k-generated divergences
This section defines k-cuts and k-generatedness to measure how many decision outcomes are needed to characterize a divergence, then establishes key structural properties and contrasts DP with Rényi divergence.
- k-cuts: A k-cut restricts a divergence to distributions obtained through decision rules with an output domain of cardinality k.For divergences satisfying data processing, the k-cut is independent of the particular k-element output set.
- k-generatedness: A divergence is k-generated when its value is fully captured by its k-cut, making k-generatedness a measure of the number of decisions needed to characterize it.Every k-cut is k-generated, and a divergence satisfying data processing has its k-cut as the greatest k-generated divergence below it.
- Differential privacy: The DP divergence ∆ε is 2-generated, so its privacy guarantee is completely characterized by binary hypothesis tests.Its 2-cut reproduces the original divergence because ∆ε is quasi-convex and satisfies data processing.
- Rényi divergence: The Rényi divergence is not k-generated for any finite k and is instead exactly ∞-generated.Its 2-cut is strictly weaker than the full divergence, although the quantitative difference in the counterexample is small and positive.
4 Hypothesis Testing Interpretation of Divergences
The paper connects divergence-based privacy to hypothesis testing through privacy regions, showing that 2-generated divergences admit complete binary-test characterizations while arbitrary divergences yield potentially incomplete 2-cut interpretations.
- Binary-test characterization: The 2-cut of an arbitrary divergence admits a hypothesis-testing characterization based on binary decision rules.Privacy regions encode the attainable pairs of acceptance and rejection errors for these rules.
- Privacy regions: The DP privacy region is expressed by inequalities constraining the two error coordinates under ε and δ.The region includes pairs satisfying 1 − x ≤ e^εy + δ, with the symmetric relation obtained from the two test directions.
- Complete interpretations: A privacy definition based on a 2-generated divergence is characterized completely by its hypothesis-testing interpretation.This follows because the divergence equals its 2-cut, which captures the relevant binary decision rules.
- Incomplete interpretations: For an arbitrary divergence, the 2-cut provides a hypothesis-testing interpretation but need not provide a complete characterization of the original divergence.This distinction applies to Rényi-based relaxations because Rényi divergence is not 2-generated.
5 Applications
The paper applies privacy regions and divergence cuts to improve RDP-to-DP conversion, relate GDP to a 2-generated divergence, and analyze how cuts affect distinguishability.
- Conversion laws: Privacy-region inclusion reduces the search for a conversion law to comparing the regions of the source and target divergences.The desired parameters are the smallest ε(ρ) and δ(ρ) making the source region a subset of the corresponding DP region.
- Better conversion from RDP to DP: The refined RDP-to-DP conversion states that (α, ρ)-RDP implies (ρ + log((α −1)/α) −(log δ + log α)/(α −1), δ)-DP.This improves the original conversion law for any 0 < δ < 1.
- Better conversion from RDP to DP: The paper conjectures that tangent lines to the boundary of the RDP privacy region yield an optimal RDP-to-DP conversion law.The conjecture is based on calculating tangents to the boundary of R_Dα(ρ).
- Gaussian differential privacy: GDP can be characterized by a divergence satisfying data processing, and this divergence is 2-generated.Its privacy region therefore supports the same binary-test framework developed for 2-generated divergences.
- Distinguishability: Higher-order cuts can distinguish distribution pairs that lower-order cuts cannot, so increasing k increases distinguishability information.For the paper’s Rényi counterexample, a threshold exists where the 3-cut distinguishes the pair but the 2-cut does not.
6 A characterization of k-generated divergences
This section characterizes k-generated quasi-convex divergences and shows that suprema of quasi-convex functions over size-k partitions provide a construction criterion. The result also enables constructing new divergences with hypothesis-testing interpretations.
- Suprema of quasi-convex functions over size-k partitions determine k-generated divergences.Theorem 23 states that the divergence defined from a quasi-convex F on [0,1]2k is both k-generated and quasi-convex.
- The proof takes the k-cut over a k-element domain and uses a convex decomposition of probabilistic functions.The construction relies on the weak Birkhoff-von Neumann theorem for countable domains.
- The characterization provides a method for constructing new divergences with hypothesis-testing interpretations by varying F.
7 Conclusion
The paper develops analytical tools for studying hypothesis-testing interpretations of privacy definitions based on statistical divergences. It applies k-cut and k-generatedness to Rényi-based relaxations and identifies a possible connection to formal-verification complexity for future study.
- The paper introduces k-cut and k-generatedness to analyze divergence-based privacy definitions.These notions quantify how many decisions are needed in an experiment analogous to hypothesis testing to characterize a divergence.
- The tools are used to study hypothesis-testing interpretations of Rényi-divergence relaxations of differential privacy.
- The notions may measure the complexity of tools for formal verification, which the paper leaves for future work.
A Weak version of Birkhoff-von Neumann Theorem
This appendix proves a weak Birkhoff-von Neumann theorem by decomposing probabilistic maps into convex combinations of deterministic maps. The construction terminates after finitely many steps for finite domains and extends to countable domains.
- A probabilistic map from a k-element domain to distributions over an l-element domain can be represented by a stochastic matrix.The proof considers matrices whose columns encode probability distributions.
- The finite-domain cardinality can be extended to the countable infinite cardinal ω, yielding countably infinite families of maps and coefficients.
- Deterministic maps correspond to matrices with exactly one 1 in each relevant column and zeros elsewhere.The family G consists of matrix representations of these deterministic maps.
- The construction terminates within k · l steps and yields a convex decomposition with coefficients summing to 1.
B Omitted Proofs
The omitted proofs establish structural properties of k-generated divergences using probabilistic-process composition and data processing. They show monotonicity in k, characterize boundary cases, and connect k-cuts with k-generatedness.
- Probabilistic-process composition is associative and has identity maps, supporting the proof manipulations.The composition operator is extended to deterministic and probabilistic maps through the unit law.
- A divergence satisfying the data-processing inequality inherits corresponding inequalities for its k-cuts.The proof uses composition and inclusion relations between families of probabilistic maps.
- If a divergence is k-generated, its k-cut is independent of the chosen k-element reference set.Bijections between reference sets transfer the relevant distributions and preserve the characterization.
- Every 1-generated divergence is constant, while every k-generated divergence is also k + 1-generated.
- Every divergence satisfying data processing is at least ∞-generated, and every k-cut is k-generated.The same conclusions extend to general measurable settings under continuity assumptions.
- For continuous divergences satisfying data processing, countable approximations support the extension to ∞-generatedness.
B.6 Proof of Lemma 15
The proof extends the k-cut characterization under data processing and establishes the 2-generatedness of ε-divergence by reducing probabilistic decision rules to deterministic ones.
- B.6 Proof of Lemma 15: Lemma 33 extends the k-cut characterization to divergences satisfying the data-processing inequality and k-generated divergences.The extension is presented as suitable for differential-privacy conversion laws.
- B.6 Proof of Lemma 15: The proof uses quasi-convexity, data processing, and the weak Birkhoff–von Neumann theorem to decompose probabilistic binary rules into deterministic rules.This reduction allows the argument to compare randomized decision rules with indicator functions of measurable subsets.
- B.6 Proof of Lemma 15: The argument first assumes a countable sample space and then extends to general measurable spaces using continuity of ε-divergence.Measurability is imposed on the relevant functions in the general setting.
- B.6 Proof of Lemma 15: ε-divergence is 2-generated: its 2-cut equals ε-divergence itself.The converse follows by choosing the acceptance event and the corresponding indicator rule.
B.9 Proof of ∞-generatedness of Rényi-divergence
The proof shows that Rényi divergence cannot be reduced to any finite k-cut: strict convexity of its associated f-divergence creates a strict gap for every finite k, while general measurable settings follow by continuity.
- B.9 Proof of ∞-generatedness of Rényi-divergence: Strictly convex weight functions yield f-divergences that are not k-generated for any finite k.Rényi divergence inherits this obstruction because its representation uses the strictly convex weight function t 7→ t^α and a strictly monotone logarithmic transformation.
- B.9 Proof of ∞-generatedness of Rényi-divergence: The finite-k proof constructs distributions with distinct likelihood ratios and uses the pigeonhole principle to force two inputs into one output class.Strict convexity then makes Jensen’s inequality strict, preventing equality with the k-cut.
- B.9 Proof of ∞-generatedness of Rényi-divergence: For every α > 1, α-Rényi divergence is not k-generated for any finite k.The paper therefore characterizes Rényi divergence as requiring infinitely many generated outcomes.
- B.9 Proof of ∞-generatedness of Rényi-divergence: The k-generatedness characterization extends from finite discrete spaces to general measurable spaces when the defining quasi-convex function is continuous.The extension approximates measurable probabilistic rules through finite measurable partitions.
- B.9 Proof of ∞-generatedness of Rényi-divergence: Total variation provides a contrasting 2-generated divergence because it can be represented through the quasi-convex function F(x, x′, y, y′) = |x − y|.The paper derives this using the general k-generatedness results.
C.2 An optimal conversion law from Hellinger to DP
The paper derives an optimal conversion law from Hellinger distance to differential privacy by comparing their privacy-region boundaries and using a tangent construction.
- C.2 An optimal conversion law from Hellinger to DP: The Hellinger privacy-region boundary is obtained by solving a quadratic equation for y at each x.The equation’s degree is two, so the boundary can be solved explicitly.
- C.2 An optimal conversion law from Hellinger to DP: The conversion law is constructed from tangents to the Hellinger privacy-region boundary.The tangent slope is matched to e^ε, and the resulting intercept determines δ.
- C.2 An optimal conversion law from Hellinger to DP: The resulting conversion from Hellinger distance to differential privacy is optimal.The paper states this conclusion after deriving the boundary and tangent relationship.
- C.2 An optimal conversion law from Hellinger to DP: Figure 3 compares the differential-privacy privacy region with the privacy region induced by the 2-cut of Hellinger distance.The comparison is made at the level of attainable privacy regions.