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