Christian Lebeda, post-doc at PREMEDICAL, presented his paper “Better Gaussian Mechanism using Correlated Noise” at BARC (Basic Algorithms Research Copenhagen) on April 16 2024.
Abstract:
Privately answering aggregate queries is a common task in differentially private data analysis. The Gaussian Mechanism is the standard technique for this problem, protecting privacy by independently adding Gaussian noise to each query. In this talk I show that, under the add/remove variant of differential privacy, the magnitude of noise can be reduced by almost half by introducing a small amount of correlated noise. The algorithm is extremely simple, requiring only a minor change to the standard approach. The underlying idea can be adapted to other settings to achieve similar improvements.
