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

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 \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.

Differential privacy allows data curator to publish useful statistics or train machine-learning models while limiting what can be learned about individual records. A common way to do this is to add random noise to the numerical result; the Gaussian noise is widely used, but it has not been clear when it is truly the best choice. This paper shows that when the query result is in high dimenions, as in modern machine-learning models, no additive-noise mechanism can asymptotically improve on the Gaussian mechanism's privacy--utility tradeoff for the strong privacy settings typically used. The paper also studies cases where the query result is in low dimenions. There, it introduces a flexible new family of noise choices and finds settings where some choices give the same privacy with up to 15% less error than both Gaussian noise and a recent alternative. Finally, the paper gives a way to accurately track privacy when these methods are used many times.