Abstract
Differential Privacy (DP) is often interpreted through the lens of statistical hypothesis testing, providing an intuitive understanding of privacy guarantees in terms of Type I and Type II error trade-offs. However, Rényi Differential Privacy (RDP), while mathematically advantageous for composition, lacks a straightforward hypothesis testing interpretation. This paper introduces the framework of $k$-generatedness to analyze the "distinguishing power" of privacy definitions. We demonstrate that while standard $(\epsilon, \delta)$-DP is 2-generated, RDP is $\infty$-generated, requiring an infinite number of outcomes for a complete hypothesis testing description. We further provide a "2-cut" approximation to interpret RDP and derive tighter conversion rules between RDP and standard $(\epsilon, \delta)$-DP.
Introduction
Differential Privacy (DP) provides a rigorous framework for protecting individual privacy in data analysis. Its primary appeal lies in its interpretation via statistical hypothesis testing: a privacy guarantee ensures that an adversary cannot reliably distinguish between two neighboring datasets (differing by one individual). This is typically quantified by the trade-off between the probability of a false alarm (Type I error) and a missed detection (Type II error).
In practice, researchers frequently employ Rényi Differential Privacy (RDP) due to its elegant composition properties, particularly in private deep learning. However, RDP's mathematical convenience comes at the cost of interpretability; it does not naturally map to the binary hypothesis testing framework used to explain privacy to non-experts and regulators. This work seeks to bridge this gap by establishing a formal hypothesis testing meaning for RDP.
Methodology
The authors propose a theoretical framework to measure the complexity of privacy definitions based on their "distinguishing power":
- $k$-cuts: A method of projecting complex probability distributions onto a simplified domain with $k$ possible outcomes.
- $k$-generatedness: A privacy definition is considered $k$-generated if its guarantees can be fully captured by a decision rule with $k$ possible outcomes.
- Privacy Regions: Geometric representations in the Type I vs. Type II error space that visualize the set of all possible error rates allowed under a specific privacy definition.
The study evaluates several privacy variants, including $(\epsilon, \delta)$-DP, $(\alpha, \rho)$-RDP, and Gaussian Differential Privacy (GDP), using these tools.
Key Insights and Theoretical Complexity
A central finding of the paper is the disparity in complexity between standard DP and RDP:
- Simplicity of DP: The authors prove that standard $(\epsilon, \delta)$-DP is 2-generated. This confirms that a simple binary hypothesis test ("Is the individual present?") is sufficient to describe the privacy guarantee.
- Complexity of RDP: Conversely, RDP is shown to be $\infty$-generated. A complete hypothesis testing interpretation of RDP would theoretically require a test with an infinite number of possible outcomes.
- The 2-cut Approximation: To provide an interpretable view of RDP, the authors suggest looking at its "2-cut"—the optimal binary test achievable. While this doesn't capture the full RDP guarantee, it provides a useful lower bound in the familiar hypothesis testing space.
Results and Practical Implications
The theoretical framework leads to several key results:
- Theorem 16: Formally proves that the divergence underlying standard DP is 2-generated, validating the traditional binary testing approach.
- Improved Conversion Rules: By analyzing the overlap of privacy regions, the authors derive a refined formula (Theorem 20) for converting $(\alpha, \rho)$-RDP parameters into $(\epsilon, \delta)$-DP. This provides tighter bounds than the widely used Mironov (2017) rule, which is crucial for practitioners reporting privacy budgets in deep learning.
- Validation of GDP: The paper shows that Gaussian Differential Privacy (GDP) is also 2-generated, explaining its growing popularity as a hypothesis-testing-centric alternative to RDP.
Conclusion
This work clarifies the relationship between RDP and hypothesis testing, revealing that RDP's mathematical elegance stems from a higher level of complexity than standard DP. While the paper is purely analytical and does not empirically test model utility, the improved conversion formulas offer immediate benefits for privacy accounting. Future research may leverage the $k$-cut framework for formal verification of privacy-preserving algorithms, as reducing complex distributions to finite outcomes facilitates automated checking.
Summary updated