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

Yu Wei, Alexander Bienstock, Antigoni Polychroniadou
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:133468-133499, 2026.

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 Spherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied $\ell_2$ mechanism (Joseph 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 et al. regarding the $\ell_2$ mechanism.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-wei26a, title = {Asymptotic Optimality of the High-Dimensional {G}aussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy}, author = {Wei, Yu and Bienstock, Alexander and Polychroniadou, Antigoni}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {133468--133499}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/wei26a/wei26a.pdf}, url = {https://proceedings.mlr.press/v306/wei26a.html}, 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 Spherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied $\ell_2$ mechanism (Joseph 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 et al. regarding the $\ell_2$ mechanism.} }
Endnote
%0 Conference Paper %T Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy %A Yu Wei %A Alexander Bienstock %A Antigoni Polychroniadou %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-wei26a %I PMLR %P 133468--133499 %U https://proceedings.mlr.press/v306/wei26a.html %V 306 %X 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 Spherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied $\ell_2$ mechanism (Joseph 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 et al. regarding the $\ell_2$ mechanism.
APA
Wei, Y., Bienstock, A. & Polychroniadou, A.. (2026). Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:133468-133499 Available from https://proceedings.mlr.press/v306/wei26a.html.

Related Material