PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Gaussian Mechanism for Differential Privacy

Fang Liu

arXiv:1602.06028v6math.ST

TL;DR

The paper addresses how to construct differentially private releases with broad query sensitivities while preserving privacy and utility. It generalizes Laplace and Gaussian noise into a generalized Gaussian framework, analyzes its privacy conditions and related mechanisms, and reports theoretical and empirical comparisons across several datasets. The resulting framework distinguishes when pure or probabilistic privacy is attainable and supplies a Gaussian scale bound under probabilistic DP.

  • Problem

    Differentially private data release requires mechanisms that provide privacy at a specified budget while addressing different query sensitivities and preserving useful information.

  • Method

    The paper develops a generalized Gaussian mechanism based on l_p global sensitivity, analyzes truncated variants and Exponential-mechanism connections, and studies Gaussian and Laplace utility through theory and experiments.

  • Results

    The paper shows that pure ε-DP is unattainable for unbounded outputs when p ≠ 1, while bounded-data truncation and (ε, δ)-probabilistic DP provide alternatives, and derives a Gaussian scale lower bound.

  • Takeaways & Limitations

    The GG framework unifies Laplace and Gaussian mechanisms while clarifying the privacy conditions, alternatives, and utility trade-offs associated with different orders and data domains.

  • Takeaways & Limitations

    The framework uses global sensitivity, which can inject large noise, and developing a GG mechanism based on local sensitivity remains future work.

Abstract

from arXiv · show

Assessment of disclosure risk is of paramount importance in the research and applications of data privacy techniques. The concept of differential privacy (DP) formalizes privacy in probabilistic terms and provides a robust concept for privacy protection without making assumptions about the background knowledge of adversaries. Practical applications of DP involve development of DP mechanisms to release results at a pre-specified privacy budget. In this paper, we generalize the widely used Laplace mechanism to the family of generalized Gaussian (GG) mechanism based on the $l_p$ global sensitivity of statistical queries. We explore the theoretical requirement for the GG mechanism to reach DP at prespecified privacy parameters, and investigate the connections and differences between the GG mechanism and the Exponential mechanism based on the GG distribution We also present a lower bound on the scale parameter of the Gaussian mechanism of $(ε,δ)$-probabilistic DP as a special case of the GG mechanism, and compare the statistical utility of the sanitized results in the tail probability and dispersion in the Gaussian and Laplace mechanisms. Lastly, we apply the GG mechanism in 3 experiments (the mildew, Czech, adult data), and compare the accuracy of sanitized results via the $l_1$ distance and Kullback-Leibler divergence and examine how sanitization affects the prediction power of a classifier constructed with the sanitized data in the adult experiment.

1 Introduction

The paper develops the generalized Gaussian mechanism as a broader framework for differentially private data release, extending beyond the Laplace mechanism through l_p global sensitivity. It analyzes when this mechanism satisfies different privacy guarantees and connects it to the Exponential mechanism and Gaussian privacy mechanisms.

  • The generalized Gaussian mechanism unifies the Laplace and Gaussian mechanisms using the l_p global sensitivity of statistical queries.The paper frames both mechanisms within a common family based on a generalized Gaussian distribution.
  • For p ≠ 1 and unbounded outputs, no scale parameter yields pure ε-DP, motivating (ε, δ)-probabilistic DP as an alternative.For bounded data, truncated and boundary-inflated truncated GG mechanisms are introduced to satisfy pure ε-DP.
  • The paper examines connections between the GG mechanism and the Exponential mechanism when utility is based on Minkowski distance.It relates the Exponential mechanism’s utility sensitivity to the l_p global sensitivity of queries.
  • It derives a lower bound for the Gaussian mechanism’s scale parameter under (ε, δ)-probabilistic DP and compares Gaussian and Laplace noise using tail probability and dispersion.The Gaussian mechanism is treated as the order-2 GG mechanism, with comparisons to approximate DP and Laplace noise.

2 Generalized Gaussian Mechanism

The paper develops generalized Gaussian mechanisms using l_p global sensitivity, clarifying when pure or probabilistic differential privacy is achievable and how these mechanisms relate to Laplace, Gaussian, and Exponential mechanisms.

  • 2.1 differential privacy (DP): Differential privacy bounds how similarly perturbed query outputs behave on neighboring data sets, with ε controlling the allowed probability difference.Relaxed variants add δ to permit probabilistic or approximate privacy guarantees.
  • 2.1 differential privacy (DP): The l_p global sensitivity Δ_p is the maximum Minkowski-distance change in query results between neighboring data sets and determines disclosure risk.For histograms, changing one record alters only one bin, so sensitivity need not scale with the total number of bins.
  • 2.3 generalized Gaussian distribution: The GG family includes Laplace noise at p = 1 and Gaussian noise at p = 2, while equal-variance distributions differ substantially in concentration near the mean.With equal variance, Laplace noise is most likely to generate values close to the mean, followed by Gaussian noise.
  • 2.4 GG mechanism of ε-DP: For unbounded outputs, no scale parameter yields pure ε-DP for GG mechanisms when p ≠ 1; at p = 1, the Laplace lower bound is b = Δ_1/ε.The paper addresses this by using bounded truncation for pure ε-DP or probabilistic (ε, δ)-DP for unbounded settings.
  • 2.6 GG mechanism of (ε, δ)-pDP: For p ≥ 2, Corollary 7 provides a scale condition for (ε, δ)-pDP, but closed-form solutions are generally unavailable when p > 2.Numerical results show that the required b increases as ε or δ decreases and, in the examined cases, as p increases.
  • 2.7 Connection between GG mechanism and Exponential Mechanism: The GG-distribution-based Exponential mechanism can generate the same GG form, but its scale depends on utility sensitivity Δ_u rather than query sensitivity Δ_p.When utility is negative Minkowski distance, both approaches reduce to the truncated Laplace mechanism for u = −||s*−s||_1.

3 Gaussian Mechanism

The Gaussian mechanism is analyzed as a special case of the GG mechanism, including a pDP scale bound and comparisons with aDP and Laplace mechanisms. The analysis finds tighter pDP bounds than aDP and examines tail probability, privacy cost, and dispersion trade-offs.

  • Gaussian mechanism: The Gaussian mechanism is obtained from the GG mechanism by setting p = 2, with Gaussian variance σ^2 = b^2/2.For bounded query results, the paper also describes a truncated Gaussian mechanism satisfying pure ϵ-DP.
  • Scale bound: An analytical lower bound is provided for the scale parameter b of the Gaussian mechanism under (ϵ, δ)-pDP.The bound is stated in Lemma 10 as b ≥ 2^-1/2 ϵ^-1 ∆2.
  • Scale bound: The pDP lower bound is tighter than the aDP bound for the same (ϵ, δ), while it does not require the aDP restriction ϵ < 1.Across the examined settings, the aDP-to-pDP bound ratio is below 1; smaller ϵ or larger δ increases the difference.
  • Utility comparisons: Tail-probability comparisons evaluate Laplace noise against Gaussian noise across ϵ values and δ settings, excluding cases where both tail probabilities are below 10^-4.The ratio p1:p2 can decrease and later rebound, with the rebound depending on the privacy specification.
  • Utility comparisons: For equal tail probabilities, the relative privacy cost ϵ2:ϵ1 indicates when Gaussian noise achieves the same tail probability with less privacy cost than Laplace noise.The comparison varies with |t| and the relaxation parameter δ.
  • Utility comparisons: When δ < 0.157, Gaussian noise has greater variance than Laplace noise under the compared privacy specifications, implying greater dispersion and mean squared error.The condition is sufficient but not necessary; the paper notes that Laplace is therefore superior in the examined precision comparison.

4 Experiments

The experiments sanitize histograms from mildew, Czech, and adult data using Laplace and Gaussian mechanisms, then compare count fidelity, divergence, and adult-data prediction accuracy. Laplace most closely preserves original counts across the three datasets, while adult-data SVM accuracy is barely affected by sanitization.

  • Experimental setup: Experiments use mildew, Czech, and Census Income (adult) datasets, sanitizing histogram counts with Laplace and two Gaussian mechanisms.The Gaussian mechanisms are (ϵ, δ)-pDP and (ϵ, δ)-aDP variants.
  • Experimental setup: For the mildew and Czech experiments, all histogram bins were sanitized; adult data used 17,985 nonempty training cells and postprocessing clipped counts to [0,n].Sanitized counts were normalized to the original sample size n, assuming n is public.
  • Count fidelity: Laplace was the obvious winner in all three datasets, producing counts closest to the originals with the smallest l1 error and KL divergence.The Gaussian (ϵ, δ)-pDP mechanism followed, while GGM3 and the Gaussian (ϵ, δ)-aDP mechanism performed worse in the stated mildew ordering.
  • Prediction accuracy: In adult data, SVM prediction accuracy from sanitized data was barely affected, with decreases largely ignorable at 0.25% to 1%.This held regardless of the mechanism, even after accounting for variation.

5 Discussion

The discussion positions the GG mechanism as a unified framework for Laplace and Gaussian mechanisms, with bounded-data variants and probabilistic DP alternatives. It also identifies global sensitivity as a source of potentially large noise and points to local sensitivity as future work.

  • Contributions: The paper unifies Laplace and Gaussian mechanisms through generalized Gaussian mechanisms based on l_p global sensitivity.For bounded data, truncated and boundary-inflated truncated GG mechanisms achieve ϵ-DP.
  • Contributions: For order p ≥ 2, (ϵ, δ)-probabilistic DP is proposed as an alternative to pure ϵ-DP for the GG mechanism.The paper also connects GG mechanisms with the Exponential mechanism under a Minkowski-distance utility.
  • Gaussian mechanism analysis: The Gaussian (ϵ, δ)-pDP scale lower bound is tighter than the corresponding lower bound for Gaussian (ϵ, δ)-aDP.The paper also compares tail probability and dispersion between Gaussian and Laplace noise.
  • Limitations and future work: Global sensitivity strengthens privacy protection but can inject large amounts of noise into query results.The discussion identifies data-dependent local sensitivity as a route toward improving sanitized-result accuracy.

B Proof of Claim 4

The proof shows that for unbounded results and p ≠ 1, the GG DP condition depends on random noise terms, preventing a noise-independent scale solution. When p = 1, the mechanism reduces to Laplace ϵ-DP.

  • Sensitivity bounds: The proof bounds the privacy condition using the l1 global sensitivities Δ1,k of component queries and the l_p sensitivity Δp of the full query.A less tight bound can be obtained by applying Lemma 2.
  • Unbounded results: The lower-bound inequalities depend on the random GG noise terms e_k, whose support is the full space (−∞,∞)^r.Therefore, no random-noise-free solution for the scale parameter b exists in the p ≠ 1 case.
  • Special case p = 1: When p = 1, the error terms disappear from the inequality and the GG mechanism reduces to the familiar Laplace mechanism of ϵ-DP.This special case yields Claim 4.

C Proof of ϵ-DP of the truncated GG mechanism in Definition 5

The proof establishes pure ϵ-DP for the truncated GG mechanism by bounding the relevant privacy term under bounded support. The condition is expressed through the scale lower bound involving b_p(ϵ/2).

  • Privacy bound: If the term in Eqn. (C.6) satisfies ϵ/2-DP, then Eqn. (C.7) also satisfies ϵ/2-DP.This composition step is used in the proof of the truncated mechanism.
  • Scale condition: Appendix B establishes Eqn. (C.7) under the condition b_p(ϵ/2) ≥ Δ_p.The resulting bound is combined with the bounded-support argument for the truncated mechanism.
  • Bounded support: Because s* is bounded within [c_k0,c_k1], the truncated GG mechanism satisfies pure ϵ-DP.The bounded range supplies the condition used to establish the result.

D Conservativeness of Exponential mechanism

The Exponential mechanism’s nominal privacy budget is conservative: its actual privacy cost is always below ε and can reach ε/2 under an x-independent normalization factor.

  • The actual privacy cost of the Exponential mechanism is always less than the nominal budget ε.
  • When A(x) is independent of x, the actual privacy cost is ε/2.
  • An x-independent normalization factor makes utility-score changes cancel after integration or summation over possible outputs.
  • The exact upper bound ε cannot be attained because the required equality conditions cannot hold simultaneously unless Δu = 0.

E Proof of Lemma 9

The proof establishes the relevant sensitivity relationship under bounded query-result coordinates, using coordinatewise inequalities involving first- and second-order sensitivity terms.

  • For p = 1, the utility-score sensitivity is bounded by the query’s l1 global sensitivity.
  • The proof assumes each coordinate s_k, and therefore s*_k, is bounded within specified interval endpoints.
  • The coordinatewise inequalities combine first-order sensitivity, interval width, and second-order sensitivity terms to establish nonnegativity.

F Proof of Lemma 10

The proof derives a scale requirement for the generalized Gaussian mechanism to satisfy (ε,δ)-probabilistic differential privacy, covering scalar and multidimensional query results.

  • When r = 1, the sensitivity Δ_p is identical to Δ for every p ≥ 1.
  • For r > 1, the proof uses a multidimensional Gaussian-mechanism argument to derive the corresponding privacy condition.
  • The resulting lower bound on the scale parameter b applies across the scalar and multidimensional cases.

G Proof of Lemma 11

The proof compares Gaussian and Laplace noise through their variance ratio when the Gaussian scale is set at its derived lower bound, while relating the ratio to ε and δ.

  • At the lower bound in Eqn (18), the proof evaluates the variance ratio between Gaussian noise for (ε,δ)-pDP and Laplace noise for ε-DP.
  • Because δ/2 lies in [0, 0.5], Φ^-1(δ/2) is negative, and the proof derives a lower bound involving (Φ^-1(δ/2))^2/2.
Loading 1602.06028v6…