A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation, and Blackwell's Theorem

Weijie SuAnnual 2024 · DOI

TL;DR

This paper reframes differential privacy (DP) as a fundamental statistical concept rooted in hypothesis testing, rather than a purely cryptographic one. It introduces "f-differential privacy" as a unified framework that encompasses all existing DP definitions, offering a more principled and powerful way to analyze privacy guarantees in machine learning and data analysis.

What Problem Does This Paper Address?

The paper addresses the challenge of unifying and rigorously understanding the diverse landscape of differential privacy definitions. While DP has gained widespread adoption for its strong privacy guarantees, its origins in cryptography have sometimes obscured its deep statistical underpinnings. This has led to a fragmented understanding and potentially suboptimal privacy analyses. The authors aim to bridge this gap by demonstrating that hypothesis testing is the natural language for DP, leading to a more cohesive framework that can improve privacy analysis across various applications.

Methods

The core of the paper's contribution lies in its statistical reinterpretation of differential privacy. Key methods include:

  • Hypothesis Testing Formulation: The paper formalizes DP as a hypothesis testing problem where an adversary tries to distinguish between the outputs of an algorithm on two neighboring datasets (differing by one individual's record).
  • Blackwell's Informativeness Theorem: This theorem is leveraged to establish a connection between the distinguishability of probability distributions (related to privacy) and the existence of a "randomized algorithm" that can transform one pair of distributions into another.
  • Trade-off Function: A "trade-off function" is introduced, derived from the likelihood ratio between probability distributions. This function captures the essential information for hypothesis testing and, consequently, for privacy.
  • f-Differential Privacy: Based on the trade-off function, "f-differential privacy" is defined. This framework is shown to be a generalization of all existing DP definitions, meaning any DP definition can be represented within this framework.
  • Representation Theorem: A key theorem demonstrates that any DP definition can be represented by a link function applied to the trade-off function, solidifying the statistical foundation.

Datasets

The paper discusses applications to real-world datasets and scenarios, including:

  • U.S. Census Data: The paper highlights the adoption of DP by the U.S. Census Bureau for releasing demographic data and discusses how f-DP can improve privacy analysis in this context.
  • MNIST: An experiment on the MNIST dataset is mentioned in the context of private convex optimization, comparing privacy bounds from different DP definitions.

The paper does not introduce new datasets or benchmarks but rather applies its framework to existing applications and datasets.

Key Insights and Ideas

  • DP is Fundamentally Statistical: The paper makes a strong case that differential privacy is not just a cryptographic tool but a core statistical concept, best understood through the lens of hypothesis testing.
  • Hypothesis Testing as the "Right Language": By framing DP as hypothesis testing, the paper argues that this perspective provides a more rigorous and unified way to reason about privacy, moving beyond ad-hoc defenses.
  • f-DP as a Unifying Framework: The introduction of f-differential privacy offers a powerful generalization that encompasses all prior DP definitions. This means that analyses developed under f-DP can potentially provide tighter bounds and a more comprehensive understanding of privacy.
  • Blackwell's Theorem as a Bridge: The paper elegantly connects the statistical theory of information (via Blackwell's theorem) to the practical problem of privacy, showing how the structure of privacy guarantees is intrinsically linked to the distinguishability of data distributions.
  • Trade-off Function Captures Essential Privacy Information: The trade-off function is identified as the minimal information needed to define privacy, suggesting that DP definitions that rely on more than this are potentially "information-lossy."

Key Results

  • Representation Theorem: Any DP definition can be represented by a link function applied to the trade-off function, establishing f-DP as a general framework.
  • f-DP Generalizes Existing Definitions: The paper shows that f-DP can encompass and generalize standard DP definitions like (ε, δ)-DP and Rényi DP.
  • Improved Privacy Bounds in Applications: The paper demonstrates through examples (private deep learning, convex optimization, shuffled mechanisms, U.S. Census data) that f-DP analysis can lead to tighter privacy bounds compared to existing methods, enabling stronger privacy guarantees or more utility for the same privacy budget. For instance, in the U.S. Census data application, f-DP led to a 10% reduction in mean squared error.

Limitations and Future Work

  • Technical Complexity: While f-DP offers theoretical advantages, the paper acknowledges that evaluating trade-off functions can be technically challenging, requiring specialized tools and techniques.
  • Asymptotic vs. Non-Asymptotic Bounds: f-DP often leads to asymptotic privacy bounds, which are sharper but may be less interpretable or directly applicable in finite-sample scenarios. The paper poses the question of whether this trade-off is fundamental.
  • Developing Practical Tools: The authors suggest the need for more efficient numerical methods for composing privacy bounds and tools to facilitate the use of f-DP in practice.
  • Extending to Non-Euclidean Data: The paper identifies the extension of the f-DP framework to non-Euclidean data as a promising future research direction.
  • Broader Applications: The authors note that while the review covers several applications, areas like federated learning, privacy auditing, and MCMC are not fully explored and represent potential avenues for future research.

Summary updated

Abstract

Differential privacy is widely considered the formal privacy for privacy-preserving data analysis due to its robust and rigorous guarantees, with increasingly broad adoption in public services, academia, and industry. Although differential privacy originated in the cryptographic context, in this review we argue that, fundamentally, it can be considered a pure statistical concept. We leverage Blackwell's informativeness theorem and focus on demonstrating based on prior work that all definitions of differential privacy can be formally motivated from a hypothesis testing perspective, thereby showing that hypothesis testing is not merely convenient but also the right language for reasoning about differential privacy. This insight leads to the definition of f -differential privacy, which extends other differential privacy definitions through a representation theorem. We review techniques that render f -differential privacy a unified framework for analyzing privacy bounds in data analysis and machine learning. Applications of this differential privacy definition to private deep learning, private convex optimization, shuffled mechanisms, and US Census data are discussed to highlight the benefits of analyzing privacy bounds under this framework compared with existing alternatives.
BibTeX
@inproceedings{su2024statistical,
  author = {Weijie Su},
  title = {{A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation, and Blackwell's Theorem}},
  booktitle = {Annual},
  year = {2024},
  doi = {10.1146/annurev-statistics-112723-034158},
}
Figure