Introduction
In differentially private machine learning, researchers frequently rely on "privacy amplification by subsampling." The core concept is intuitive: if an algorithm only processes a small, random fraction of the data (such as a minibatch), the privacy risk to any single individual in the broader dataset is naturally diluted.
To track the total privacy "leakage" over thousands of training steps, practitioners use the Moments Accountant within the Rényi Differential Privacy (RDP) framework. However, calculating the exact RDP for a subsampled mechanism is mathematically grueling. While previous work addressed "sampling without replacement," the "Poisson subsampling" scheme—where each data point is selected independently with a fixed probability—lacked a general, tight analytical formula. Because this specific scheme is widely used (including in landmark papers like Abadi et al., 2016), practitioners have often had to rely on loose bounds or expensive numerical integrations. This can lead to overestimating privacy loss and unnecessarily degrading model utility by adding too much noise.
This paper provides the first tight, analytical characterization of RDP for Poisson subsampling, enabling more efficient and accurate privacy accounting for popular algorithms like NoisySGD.
Methodology
The authors tackle the challenge by analyzing the RDP of a mechanism $\mathcal{M}$ composed with a Poisson sampling step. Their approach introduces several key theoretical advancements:
- New Analytical Bounds: They derive a general upper bound for any mechanism $\mathcal{M}$ that is optimal up to a small additive constant.
- The "Tightness" Condition: They identify a specific mathematical condition involving Pearson-Vajda $\chi^\alpha$-divergences. If a mechanism's privacy loss distribution is "skewed to the right" (which they prove holds true for Gaussian and Laplace mechanisms), the lower bound becomes the exact upper bound.
- $\tau$-term Approximation: Calculating the RDP for an order $\alpha$ normally requires $\alpha$ calls to the underlying privacy function. The authors propose an efficient approximation requiring only a small, fixed number of calls ($\tau$), significantly accelerating computation without sacrificing much accuracy.
- Functional View: Instead of treating each privacy parameter ($\epsilon$) in isolation, they treat it as a function of the RDP order $\alpha$, allowing for a more holistic Moments Accountant approach.
Evaluated Mechanisms
As a theoretical work focused on privacy accounting, the paper evaluates its bounds on prototypical privacy mechanisms rather than standard image or text datasets:
- Gaussian Mechanism: The standard for deep learning (e.g., NoisySGD).
- Laplace Mechanism: Common in traditional statistical Differential Privacy.
- Randomized Response: A classic mechanism for categorical data.
Key Findings
By simulating various noise regimes, the authors demonstrate how their bounds behave across different $\epsilon$ values, yielding several critical insights:
- Exact Tightness: For Gaussian and Laplace mechanisms, the authors' bound is exact, successfully closing the constant-factor gap left by previous general bounds.
- The Phase Transition: For the Gaussian mechanism, there is a distinct "phase transition" in the RDP curve. At low orders of $\alpha$, subsampling provides massive privacy gains. At very high orders, this benefit vanishes, and the RDP converges to that of the non-subsampled mechanism.
- Superior Composition: Compared to standard "Strong Composition" methods for adding up privacy budgets, this RDP-based accountant provides significantly tighter privacy guarantees. For instance, after 1,000 iterations of NoisySGD, the method shows a much lower total $\epsilon$.
Furthermore, the authors highlight that in Poisson sampling, the divergence of distribution $P$ from $Q$ is different from $Q$ from $P$. Managing this asymmetry was a key technical hurdle in proving these tight bounds. By providing an analytical formula and a numerically stable implementation (using the log-sum-exp trick), they eliminate the need for bottleneck-inducing numerical integration.
Limitations and Future Work
While the tight bound works perfectly for Gaussian and Laplace mechanisms, it is not universally applicable. Some distributions (like certain Poisson distributions) can have negative odd-order Pearson-Vajda divergences, meaning the tight bound condition fails.
Future work may involve extending these results to more complex, heterogeneous privacy-preserving systems where different components use different mechanisms. The authors also suggest developing an automated tool to check if new, custom mechanisms satisfy the conditions required for the tightest possible bound.
(Note: The authors have released their implementation as part of the autodp library on GitHub, making these tighter bounds immediately accessible to the research community.)
Summary updated