Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising

By Borja Balle, Yu-Xiang Wang. 2018

521 citations recorded by the source corpus.

The Gaussian mechanism is an essential building block used in multitude of differentially private data analysis algorithms. In this paper we revisit the Gaussian mechanism and show that the original analysis has several important limitations. Our analysis reveals that the variance formula for the original mechanism is far from tight in the high privacy regime ($\varepsilon \to 0$) and it cannot be extended to the low privacy regime ($\varepsilon \to \infty$). We address these limitations by developing an optimal Gaussian mechanism whose variance is calibrated directly using the Gaussian cumulative density function instead of a tail bound approximation. We also propose to equip the Gaussian mechanism with a post-processing step based on adaptive estimation techniques by leveraging that the distribution of the perturbation is known. Our experiments show that analytical calibration removes at least a third of the variance of the noise compared to the classical Gaussian mechanism, and that denoising dramatically improves the accuracy of the Gaussian mechanism in the high-dimensional regime.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

The Privacy Blanket of the Shuffle Model (2019, methodology): “However, this sufficient condition is not tight for small values of ε [2], so here we prefer to work with the divergence-based characterization.”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “For the case of ( (cid:15), δ ) -DP, Balle et al. (2018) provide a uniﬁed account of privacy ampliﬁcation techniques for diﬀerent types of subsampling and dataset neighboring relations.”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, methodology): “An alternative approach is to extend the recent results for Rényi DP ampliﬁcation by subsampling without replacement given in [Wang et al., 2018] to more general notions of subsampling and neighbouring relations.”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, methodology): “To implement the privacy oracle we compute the global sensitivity according to [49, Algorithm 2] and find the ε for a fixed δ = 10−6 using the exact analysis of the Gaussian mechanism provided in [7].”
Locally Differentially Private Data Collection and Analysis (2019, background): “Theorem 1 (Optimal Gaussian mechanism (Opt-GM) for (ǫ, δ)-differential privacy [3]).”
Differentially Private Federated Learning: An Information-Theoretic Perspective (2021, methodology): “To compute the contraction coefﬁcient of such kernels, we need the following lemma, whose proof is essentially the same as [27, Lemma 6]. where and ∫ ∞ t e − u 2 / 2 d u .”
Differential Privacy Techniques for Cyber Physical Systems: A Survey (2018, methodology): “They are named as Laplace mechanism (LM) [85], Gaussian mechanism [86], and Exponential mechanism (EM) [44].”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “Bassily et al. (2014) refined the analysis for privacy budget by taking into account the randomness of the batch sampling (a.k.a. privacy amplification by sampling Kasiviswanathan et al. (2011), which allowed them to run the algorithm for more steps without a significant cost to privacy.”
Differentially Private Set Union (2020, methodology): “Given any function f : D → R k , the Laplace Mechanism is deﬁned as: where ∆ 1 is the (cid:96) 1 -sensitivity and Y i are i.i.d. random variables drawn from Lap (0 , ∆ 1 /ε ) .”
A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences (2020, unknown): “It is shown in [27], [28] that M is (ε, δ)-DP⇐⇒ sup d∼d′ Eeε(Md‖Md′) ≤ δ.”
Optimal Noise-Adding Mechanism in Additive Differential Privacy (2018, methodology): “Compared with the improved Gaussian mechanisms for (0 , δ ) -differential privacy (Balle and Wang, 2018), our result demonstrates a two-fold and three-fold improvement in the high privacy regime in the context of minimizing the noise magnitude and noise power, respectively.”
Bounding Training Data Reconstruction in Private (Deep) Learning (2022, methodology): “The weaker notion of ( (cid:15), δ ) -DP uses the so-called “hockey-stick” divergence (Polyanskiy et al., 2010), which allows the max divergence bound to fail with probability at most δ > 0 (Balle & Wang, 2018).”
Obfuscation via Information Density Estimation (2019, background): “In fact, the information density appears in DP under the name of privacy loss variable [15–19], thereby connecting DP and information-theoretic quantities, e.”