Subsampled Renyi Differential Privacy and Analytical Moments Accountant

Yu-Xiang Wang, Borja Balle, Shiva Prasad Kasiviswanathan

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 Renyi 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.

Introduction

In differentially private machine learning, such as NoisySGD, algorithms typically operate on small "mini-batches" (subsamples) rather than the entire dataset. Intuitively, if an individual's data is only included in a mini-batch with a small probability, the privacy risk to that individual is reduced. This phenomenon, known as privacy amplification by subsampling, is critical for achieving high utility in private models while maintaining rigorous privacy guarantees.

While the existence of this amplification has been known, calculating exact, tight bounds for Rényi Differential Privacy (RDP) under subsampling has remained a challenge. Previous methods were either loose or restricted to specific noise distributions like the Gaussian mechanism. This paper provides the first tight, general bounds for RDP under subsampling, enabling precise privacy accounting for a wide range of algorithms beyond standard Gaussian noise.

Methodology

The authors introduce two primary contributions to the field of privacy accounting:

  1. Theorem 9 (The Tight Bound): A new, non-asymptotic upper bound for the RDP parameters of any subsampled mechanism. By combining binomial expansion with a "ternary version" of the Pearson-Vajda divergence, the authors prove a bound that is nearly optimal.
  2. The Analytical Moments Accountant: Unlike previous "moments accountants" that required pre-defining a fixed list of moments (orders of $\alpha$), this tool stores the Cumulant Generating Function (CGF) in symbolic form. This allows for infinite precision, support for any RDP-compliant mechanism (e.g., Laplace, Randomized Response), and efficient conversion back to standard $(\epsilon, \delta)$ units via a bisection method.

Key Insights: The Phase Transition

A central discovery of this work is that RDP behavior under subsampling undergoes a "phase transition." For low values of the RDP order $\alpha$, the privacy parameter $\epsilon$ scales quadratically with the sampling rate ($\gamma^2$). For high values of $\alpha$, it scales linearly ($\gamma$). This behavior explains why subsampling is exceptionally powerful for the "moments" typically used in deep learning, as it allows for significantly better privacy guarantees than previously thought.

RDP behavior showing the phase transition between quadratic and linear scaling as a function of the order alpha.

Experimental Evaluation

To evaluate the tightness of these mathematical bounds, the authors conducted synthetic simulations of the Gaussian mechanism (noise scale $\sigma = 5$, subsampling ratio $\gamma = 0.001$).

The results demonstrate an order of magnitude improvement in privacy accounting. When composing a subsampled Gaussian mechanism over 600,000 iterations, the RDP-based approach yields an $\epsilon$ significantly smaller (better) than standard "strong composition" methods. Furthermore, the analytical approach avoids numerical integration issues that plagued earlier versions, providing a more robust and faster accounting framework.

Comparison of privacy loss (epsilon) over multiple rounds of composition, showing the superiority of the RDP-based accountant over naive and strong composition.

Conclusion

This work provides the necessary mathematical foundation for practitioners to use differential privacy with explicit, tight constants. By generalizing the moments accountant to any subsampled RDP mechanism, it opens the door for more complex noise distributions and more efficient private machine learning. While the current proof relies on integer values for $\alpha$, future work aims to provide a direct proof for all real-valued $\alpha > 1$ and explore "per-instance" RDP for even tighter bounds.

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 Renyi 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 Renyi Differential Privacy and Analytical Moments Accountant}},
  journal = {J. Priv. Confidentiality},
  year = {2020},
  doi = {10.29012/jpc.723},
}
Figure