Hypothesis Testing Interpretations and Renyi Differential Privacy

Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, Tetsuya Sato

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":

  1. $k$-cuts: A method of projecting complex probability distributions onto a simplified domain with $k$ possible outcomes.
  2. $k$-generatedness: A privacy definition is considered $k$-generated if its guarantees can be fully captured by a decision rule with $k$ possible outcomes.
  3. 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.
Summary of privacy definitions and their respective bounds on privacy loss.

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.
Visualization of privacy regions in the Type I vs. Type II error 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

Abstract

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.
BibTeX
@inproceedings{balle2020hypothesis,
  author = {Borja Balle and Gilles Barthe and Marco Gaboardi and Justin Hsu and Tetsuya Sato},
  title = {{Hypothesis Testing Interpretations and Renyi Differential Privacy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure