Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy

• URL: http://arxiv.org/abs/2606.08681v1
• Date: Sun, 07 Jun 2026 15:33:30 GMT
• Title: Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy
• Abstract summary: We show that no additive-noise mechanism can improve on the Gaussian mechanism's privacy--utility tradeoff for the strong privacy settings typically used.<n>We develop a new family of emphSpherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied $ell$ mechanism.
• Score: 51.25798439950639
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The additive noise mechanism is a foundational tool for differential privacy (DP) of $T$-dimensional real-valued vector queries. The Gaussian mechanism, utilizing Gaussian noise, is the mostly widely used such mechanism, due to its simplicity and strong privacy guarantees. In this work, we provide justification for this choice, showing that as the dimension $T\to\infty$, no additive-noise mechanism can asymptotically improve on the Gaussian mechanism's privacy--utility tradeoff for the strong privacy settings typically used.We also develop a new family of \emph{Spherical Generalized Gamma} DP mechanisms, which contains both the Gaussian mechanism and the recently studied $\ell_2$ mechanism (Joseph \emph{et al.}, ICML 2025). We identify members of this family that outperform both the Gaussian and $\ell_2$ mechanisms in certain low-dimensional settings, and show tight composition of all mechanisms in this family, answering an open question of Joseph \emph{et al.}~regarding the $\ell_2$ mechanism.

Related papers

• Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy [8.387716946569647]
  We design a class of additive noise mechanisms that satisfy (varepsilon, ))-differential privacy.<n>The mechanisms are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights.<n>We derive tight conditions on the variances required for (varepsilon, ))-DP and provide efficient algorithms to compute them.
  arXiv  Detail & Related papers  (2026-05-27T07:32:26Z)
• Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy [3.7942266369982955]
  We show that for any dimension, any norm, and any norm-monotone cost function, there exists an $$-DP staircase mechanism that is optimal among all additive mechanisms.<n>This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.
  arXiv  Detail & Related papers  (2026-01-21T02:35:33Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Approximate Differential Privacy of the $\ell_2$ Mechanism [52.61055173572399]
  We study the $ell$ mechanism for computing a $d$-dimensional statistic with bounded $ell$ sensitivity under approximate differential privacy.<n>Across a range of privacy parameters, we find that the $ell$ mechanism obtains lower error than the Laplace and Gaussian mechanisms.
  arXiv  Detail & Related papers  (2025-02-21T20:56:34Z)
• Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
  Differential privacy via output perturbation has been a de facto standard for releasing query or computation results on sensitive data. We identify that all existing Gaussian mechanisms suffer from the curse of full-rank covariance matrices.
  arXiv  Detail & Related papers  (2023-06-04T04:14:38Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index [61.675604648670095]
  We argue that the three prevailing interpretations of the GM, namely $(varepsilon, delta)$-DP, f-DP and R'enyi DP can be expressed by using a single parameter $psi$, which we term the sensitivity index. $psi$ uniquely characterises the GM and its properties by encapsulating its two fundamental quantities: the sensitivity of the query and the magnitude of the noise perturbation.
  arXiv  Detail & Related papers  (2021-09-22T06:20:01Z)
• Improved Matrix Gaussian Mechanism for Differential Privacy [29.865497421453917]
  Differential privacy (DP) mechanisms are conventionally developed for scalar values, not for structural data like matrices. Our work proposes Improved Matrix Gaussian Mechanism (IMGM) for matrix-valued DP, based on the necessary and sufficient condition of $ (varepsilon,delta) $-differential privacy. Among the legitimate noise distributions for matrix-valued DP, we find the optimal one turns out to be i.i.d. Experiments on a variety of models and datasets also verify that IMGM yields much higher utility than the state-of-the-art mechanisms at the same privacy guarantee
  arXiv  Detail & Related papers  (2021-04-30T07:44:53Z)
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness [50.96431444396752]
  We argue that the main difficulty is how to assess the appropriateness of each randomized mechanism. We first conclude that the Gaussian mechanism is indeed an appropriate option to certify $ell$-norm. Surprisingly, we show that the Gaussian mechanism is also an appropriate option for certifying $ell_infty$-norm, instead of the Exponential mechanism.
  arXiv  Detail & Related papers  (2020-05-15T03:54:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.