Subsampled Rényi Differential Privacy and Analytical Moments Accountant

Yu-Xiang Wang, Borja Balle, Shiva Prasad Kasiviswanathan

TL;DR

This paper introduces a novel way to analyze and bound privacy loss in differentially private algorithms that use subsampling. They provide a general theorem for Rényi Differential Privacy (RDP) that tightens existing bounds and enables more accurate privacy accounting, especially for complex machine learning models.

What Problem Does This Paper Address?

Differential privacy (DP) is a crucial concept for protecting sensitive data, especially in machine learning. Many modern DP algorithms rely on subsampling data (e.g., using mini-batches in training) before applying a privacy mechanism. While this subsampling can amplify privacy, precisely quantifying this amplification, especially using the more refined Rényi Differential Privacy (RDP) framework, has been a significant challenge. Existing methods often provide loose bounds or are limited to specific mechanisms like the Gaussian mechanism. This paper tackles the problem of providing tight, general RDP bounds for subsampled mechanisms, which is essential for designing practical and provably private algorithms.

Methods

The core of this paper is the development of a new amplification theorem for Rényi Differential Privacy (RDP) under subsampling without replacement. This theorem provides a tight upper bound on the RDP parameters of a subsampled mechanism in terms of the original mechanism's RDP parameters and the subsampling ratio.

Key techniques include:

  • Rényi Differential Privacy (RDP): The paper leverages RDP, a generalization of DP that uses α-Rényi divergences, as it offers a more nuanced view of privacy and is amenable to composition techniques.
  • Moments Accountant: Building on the work of Abadi et al. (2016), the authors develop an "analytical moments accountant." This is a data structure that symbolically tracks the Cumulant Generating Function (CGF) of the privacy loss random variable. This allows for efficient and precise tracking of privacy over multiple mechanism compositions, including subsampling.
  • Ternary-|x|<sup>α</sup>-divergence: A novel privacy definition is introduced to naturally handle subsampling. This definition is then related back to RDP, providing a bridge for the analysis.
  • Analytical Bounds and Conversions: The paper derives analytical formulas for the RDP parameters of subsampled mechanisms and provides efficient methods for converting these RDP bounds to standard (ε, δ)-DP guarantees.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, with experiments conducted on synthetic or standard privacy mechanisms rather than specific datasets.

Key Insights and Ideas

  • Tight Bounds for Subsampling: The paper provides the first general, tight upper bound on RDP amplification due to subsampling. This is a significant improvement over previous, often asymptotic or mechanism-specific, results.
  • Phase Transition in Privacy: A surprising finding is the existence of a "phase transition" in the privacy amplification. As the order of RDP (α) increases, the privacy guarantee behaves differently, either converging quickly or tapering off, depending on the underlying mechanism. This highlights the importance of considering the full RDP spectrum.
  • Analytical Moments Accountant: The development of an analytical moments accountant that handles subsampling symbolically is a major practical contribution. It allows for more efficient and flexible privacy accounting compared to prior methods that required pre-defined lists of privacy orders.
  • Constants Matter: The authors emphasize that in differential privacy, concrete, tight constants are crucial for practical utility-privacy trade-offs, and their work aims to provide these.

Key Results

  • Theorem 9: A tight upper bound on the RDP parameter for subsampled mechanisms is derived. This bound is general and applies to any RDP mechanism.
  • Proposition 11: A matching lower bound is established, demonstrating the tightness of the derived upper bound.
  • Analytical Moments Accountant: A data structure is proposed that efficiently tracks privacy loss over compositions, supporting subsampling and providing (ε, δ)-DP queries with improved time and space complexity.
  • Experimental Validation: Numerical experiments on Gaussian, Laplace, and Randomized Response mechanisms confirm the tightness of the bounds and demonstrate the practical benefits of the analytical moments accountant, showing significant improvements in privacy parameters for composed mechanisms.

Limitations and Future Work

  • Computational Complexity: While the analytical moments accountant is efficient, evaluating the RDP bound itself can still be computationally intensive for large orders of α. The paper discusses approximations to mitigate this.
  • Numerical Stability: Computing the exact bounds can involve very large or small numbers, leading to potential floating-point overflow/underflow issues. The authors mention efforts to address this but note that accurate computation for large j remains an open problem.
  • Future Work: The authors suggest applying their technique to more advanced mechanisms like those used in neural networks, addressing data-dependent per-instance RDP for subsampled mechanisms, and connecting their work to statistical resampling methods like bootstrap and jackknife.

Summary updated

Abstract

We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the R\'enyi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter. Our results generalize the moments accounting technique, developed by Abadi et al. (2016) for the Gaussian mechanism, to any subsampled RDP mechanism.
BibTeX
@article{wang2020subsampled,
  author = {Yu-Xiang Wang and Borja Balle and Shiva Prasad Kasiviswanathan},
  title = {{Subsampled Rényi Differential Privacy and Analytical Moments Accountant}},
  journal = {J. Priv. Confidentiality},
  year = {2020},
  doi = {10.29012/jpc.723},
}
Figure