Reproduce “Better Gaussian Mechanism using Correlated Noise” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Christian Janos Lebeda
A new variant of the Gaussian mechanism reduces noise for `d`-counting queries by approximately half the standard deviation, achieving this by adding correlated noise and simultaneously providing a private estimate of the dataset size. The mechanism, developed by Christian Janos Lebeda, offers a substantial utility improvement over the standard Gaussian mechanism for this common query type.
Key insights
- Exploiting the specific geometric structure of the sensitivity space, rather than just its worst-case L2 norm, allows for a more efficient Gaussian mechanism by adding correlated noise.
- Complex correlated noise mechanisms can be rigorously proven private by embedding the original problem into a higher-dimensional space where the standard Gaussian mechanism applies, followed by post-processing.
- A tunable parameter allows for a flexible trade-off between the accuracy of counting queries and the accuracy of the estimated dataset size, providing versatility for different application needs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.