# Better Gaussian Mechanism using Correlated Noise

arXiv: https://arxiv.org/abs/2408.06853 · HTML: https://mlsanity.com/paper/2408.06853/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2024.

## Built on by (most cited first, 2 of 2)

- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)

## Abstract (arXiv)

We present a simple variant of the Gaussian mechanism for answering differentially private queries when the sensitivity space has a certain common structure. Our motivating problem is the fundamental task of answering d counting queries under the add/remove neighboring relation. The standard Gaussian mechanism solves this task by adding noise distributed as a Gaussian with variance scaled by d independently to each count. We show that adding a random variable distributed as a Gaussian with variance scaled by (√d + 1)/4 to all counts allows us to reduce the variance of the independent Gaussian noise samples to scale only with (d + √d)/4. The total noise added to each counting query follows a Gaussian distribution with standard deviation scaled by (√d + 1)/2 rather than √d. The central idea of our mechanism is simple and the technique is flexible. We show that applying our technique to another problem gives similar improvements over the standard Gaussian mechanism.