Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces "mixture mechanisms," a novel approach to achieve (ε, δ)-differential privacy for scalar queries, particularly effective in moderate and low-privacy regimes. These mechanisms combine multiple Gaussians with shared variance but varying means, effectively creating a convex combination of a zero-mean Gaussian and sensitivity-dependent Gaussians. The authors derive tight conditions for (ε, δ)-DP and demonstrate that mixture mechanisms significantly reduce expected noise amplitudes and variances compared to the analytic Gaussian mechanism, approaching optimality in low-privacy settings.
Mixture mechanisms close the optimality gap of the analytic Gaussian mechanism in low-privacy differential privacy regimes, offering substantially lower noise.
We design a class of additive noise mechanisms that satisfy \((\varepsilon, δ)\)-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 \textit{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, δ)\)-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.