Mind the gap: mixtures of Gaussians in approximate differential privacy
File(s)
Accepted version
Author(s)
Liu, Huikang
Selvi, Aras
Wiesemann, Wolfram
Type
Conference Paper
Abstract
We design a class of additive noise mechanisms that satisfy (ε, δ)-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, Balle & Wang 2018) and additional Gaussians whose means depend on the sensitivity of the query function. We derive tight conditions on the variances required for (ε, δ)-DP and provide efficient algorithms to compute them. Compared to the analytic Gaussian mechanism, our mechanisms yield substantially lower expected noise amplitudes (l1-loss) and variances (l2-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.
Date Acceptance
2026-04-30
Citation
Proceedings of Machine Learning Research
ISSN
2640-3498
Publisher
MLResearchPress
Journal / Book Title
Proceedings of Machine Learning Research
Copyright Statement
Subject to copyright. This paper is embargoed until publication.
Source
Forty-Third International Conference on Machine Learning (ICML)
Publication Status
Accepted
Start Date
2026-07-06
Finish Date
2026-07-11
Coverage Spatial
Seoul, South Korea