Source-linked AI summary
Rényi Differential Privacy of the Sampled Gaussian Mechanism
Ilya Mironov, Kunal Talwar, Li Zhang
TL;DR
The paper addresses the open problem of characterizing privacy for mechanisms whose output randomness comes from both sampling and injected noise. It reformulates and extends SGM analysis through Rényi differential privacy, providing precise computation and a closed-form bound. The paper concludes that SGM does not satisfy zCDP but does satisfy RDP for a suitable range of α.
Problem
Characterizing differential privacy guarantees that account for both intrinsic sampling randomness and explicitly injected noise remains an open problem.
Method
The paper revisits the moments accountant using Rényi differential privacy, relaxes assumptions, strengthens upper bounds, and develops precise and closed-form SGM analyses.
Results
The paper provides a numerically stable procedure for precise computation of SGM’s RDP and proves a closed-form bound under stated conditions.
Takeaways & Limitations
SGM does not satisfy zCDP but satisfies RDP for a suitable range of α.
Takeaways & Limitations
The analysis uses add-one adjacency and assumes the function has ℓ2-sensitivity at most 1 for adjacent datasets.
Abstract
from arXiv · showhide
The Sampled Gaussian Mechanism (SGM)---a composition of subsampling and the additive Gaussian noise---has been successfully used in a number of machine learning applications. The mechanism's unexpected power is derived from privacy amplification by sampling where the privacy cost of a single evaluation diminishes quadratically, rather than linearly, with the sampling rate. Characterizing the precise privacy properties of SGM motivated development of several relaxations of the notion of differential privacy. This work unifies and fills in gaps in published results on SGM. We describe a numerically stable procedure for precise computation of SGM's Rényi Differential Privacy and prove a nearly tight (within a small constant factor) closed-form bound.
1 Introduction and Definitions
The paper studies privacy for the Sampled Gaussian Mechanism, which combines random sampling with additive Gaussian noise, and reformulates its analysis using Rényi differential privacy. It revisits prior approaches, relaxes assumptions, strengthens bounds, and provides a numerically stable RDP accountant.
- Mechanism: The Sampled Gaussian Mechanism draws a random subset, applies a function, and adds d-dimensional spherical Gaussian noise.Each dataset element is sampled independently with probability q, and the noise has per-coordinate variance σ2.
- Related privacy notions: Several differential-privacy relaxations were motivated by the Gaussian mechanism and the Sampled Gaussian Mechanism.These include approximate differential privacy, concentrated differential privacy, zero-CDP, moments accounting, and truncated CDP.
- Contributions: The paper revisits Abadi et al.’s moments accountant using Rényi differential privacy, relaxes assumptions, and strengthens upper bounds.An open-source implementation of the RDP accountant for SGM is also provided.
- Definitions: Rényi differential privacy is defined by bounding Rényi divergence between mechanism outputs on adjacent inputs.The paper uses adjacency where one dataset is obtained from the other by adding one individual’s contribution.
- Prior approaches: Privacy analysis for the mechanism has used asymptotic, numerically accurate, and closed-form approaches.These approaches target small sampling rates, precise estimates, or the correct dependency on the Rényi order α.
2 Reducing to a simpler case
The paper reduces RDP analysis of the Sampled Gaussian Mechanism to Rényi divergences between mixtures of one-dimensional Gaussians. This reduction uses mixture representations, quasi-convexity, rotational symmetry, product-distribution additivity, and data processing.
- Reduction: The RDP bound for SGM is reduced to a special case involving mixtures of single-dimensional Gaussians.The subsequent analysis bounds the resulting one-dimensional Rényi divergences.
- Reduction: Theorem 4 gives an RDP condition for SGM under an ℓ2-sensitivity bound of 1 for adjacent datasets.The proof bounds Rényi divergences in both directions between outputs on adjacent datasets.
- Mixture representation: Conditioned on a sampled subset T, SGM outputs a Gaussian with mean f(T), so its marginal output distribution is a mixture of Gaussians.The mixture weights are determined by the sampling probabilities of subsets.
- One-dimensional reduction: Rotational symmetry aligns the differing means with one coordinate, while product-distribution additivity reduces the divergence to that coordinate.The distributions are identical in all remaining coordinates.
- One-dimensional reduction: Data processing compares the relevant Gaussian mixtures after adding noise, supporting the reduction to the unit-sensitivity case.The argument uses the fact that larger Gaussian noise can be obtained by adding independent noise.
3 RDP Analysis of Single-Dimensional SGM
The analysis reduces SGM's RDP guarantee to bounding two mixture divergences, Aα and Bα, then shows Aα dominates Bα. It provides both a closed-form bound and a numerically stable procedure for computing Aα, yielding an RDP bound under explicit conditions.
- RDP reduction: SGM's RDP analysis is equivalent to upper bounding the mixture-divergence quantities Aα and Bα.For ℓ2-sensitivity 1, the guarantee is ε ≤ 1/(α−1) log max(Aα, Bα).
- Comparing divergences: Aα ≥ Bα for every α ≥ 1, so bounding Aα suffices for the Gaussian-mixture analysis.The result follows from a more general theorem for centrally symmetric distributions.
- Bounding Aα: The paper upper-bounds Aα using complementary approaches: a closed-form bound and exact computation to any desired precision.Aα can be decomposed into a finite sum or convergent series, enabling analytical integration after exchanging integration and summation.
- Comparing divergences: The symmetry theorem applies to distributions related by an involutive mapping, with Pq and Qq formed by swapping mixture weights.For the Gaussian case, the relevant mapping is ν(x)=1−x, reflecting N(0,σ^2) to N(1,σ^2).
- Closed-form bound: The closed-form analysis splits the integral and uses Gaussian-tail and ratio bounds, with separate conditions on α controlling the tail contribution.The main theorem combines Lemmas 9 and 10 under their stated conditions.
4 Discussion
The discussion relates CDP, zCDP, the moments accountant, and RDP through their treatment of privacy-loss moments, while distinguishing their restrictions and parameters. It highlights that SGM does not satisfy zCDP but does satisfy RDP over a suitable range of α.
- CDP, zCDP, the moments accountant, and RDP are closely related because they control moments of the privacy loss random variable.
- The paper presents equivalent definitions of CDP, zCDP, tCDP, and RDP to clarify their differences.
- The definitions become less restrictive and introduce more parameters when moving down the list from zCDP toward RDP.
- SGM does not satisfy zCDP but satisfies RDP for a suitable range of α.
- The moments accountant tracks the logarithm of Mα directly and converts the resulting bound into an (ε, δ)-DP guarantee.