Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy

We design a class of additive noise mechanisms that satisfy $(\varepsilon, \delta)$-differential privacy (DP) for scalar, real-valued query functions with known sensitivities, with a particular focus on moderate and low-privacy regimes. These mechanisms, which we call *mixture mechanisms*, are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights. The resulting distributions can be interpreted as convex combinations of a zero-mean Gaussian (as used in the analytic Gaussian mechanism) and additional Gaussians whose means depend on the sensitivity of the query function. We derive tight conditions on the variances required for $(\varepsilon, \delta)$-DP and provide efficient algorithms to compute them. Compared to the analytic Gaussian mechanism, our mechanisms yield substantially lower expected noise amplitudes ($l_1$-loss) and variances ($l_2$-loss for zero-mean distributions). In the low-privacy regime that motivates our design, our mechanisms approach optimality, mitigating nearly all of the optimality gap of the analytic Gaussian mechanism.

Organizations often want to publish statistics from sensitive datasets, such as hospital records or census responses, without revealing whether any one person's data was included. AI systems also rely on large amounts of data, so the same privacy concern arises when such systems are trained on sensitive information. Differential privacy is a mathematical standard for addressing this concern, usually by adding carefully calibrated random noise before a result is released. A common choice is Gaussian noise, the familiar bell-shaped randomness, because it is simple and behaves well when many private computations are combined. This paper studies the privacy-utility tradeoff: stronger privacy requirements usually reduce the utility one can gain from data. In practical settings with moderate rather than extremely strict privacy requirements, a single Gaussian can add more noise than necessary. We design a new shape of noise that combines several Gaussian “bells” instead of relying on just one, so that privacy is preserved with smaller levels of noise. We provide efficient algorithms for designing the exact shape of this noise, and our experiments show that our new approach substantially reduces noise compared to the standard Gaussian baseline while retaining the simplicity of Gaussians.