Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy

• URL: http://arxiv.org/abs/2605.28078v1
• Date: Wed, 27 May 2026 07:32:26 GMT
• Title: Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy
• Abstract summary: We design a class of additive noise mechanisms that satisfy (varepsilon, ))-differential privacy.<n>The mechanisms are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights.<n>We derive tight conditions on the variances required for (varepsilon, ))-DP and provide efficient algorithms to compute them.
• Score: 8.387716946569647
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy [51.25798439950639]
  We show that no additive-noise mechanism can improve on the Gaussian mechanism's privacy--utility tradeoff for the strong privacy settings typically used.<n>We develop a new family of emphSpherical Generalized Gamma DP mechanisms, which contains both the Gaussian mechanism and the recently studied $ell$ mechanism.
  arXiv  Detail & Related papers  (2026-06-07T15:33:30Z)
• Private Adaptive Covariance Estimation via Gaussian Graphical Models [17.445722519053046]
  PACE-GGM concentrates its privacy budget on the most informative entries of the empirical covariance matrix.<n>Experiments on diverse real-world datasets demonstrate consistent improvements in estimation error.
  arXiv  Detail & Related papers  (2026-05-22T23:49:45Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Approximation properties relative to continuous scale space for hybrid discretizations of Gaussian derivative operators [0.5439020425819]
  This paper presents an analysis of properties of two hybrid discretization methods for Gaussian derivatives.<n>The motivation for studying these discretization methods is that in situations when multiple spatial derivatives of different order are needed at the same scale level, they can be computed significantly more efficiently.
  arXiv  Detail & Related papers  (2024-05-08T14:44:34Z)
• Convex Parameter Estimation of Perturbed Multivariate Generalized Gaussian Distributions [18.95928707619676]
  We propose a convex formulation with well-established properties for MGGD parameters. The proposed framework is flexible as it combines a variety of regularizations for the precision matrix, the mean and perturbations. Experiments show a more accurate precision and covariance matrix estimation with similar performance for the mean vector parameter.
  arXiv  Detail & Related papers  (2023-12-12T18:08:04Z)
• Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
  Differential privacy via output perturbation has been a de facto standard for releasing query or computation results on sensitive data. We identify that all existing Gaussian mechanisms suffer from the curse of full-rank covariance matrices.
  arXiv  Detail & Related papers  (2023-06-04T04:14:38Z)
• Differential Privacy with Higher Utility by Exploiting Coordinate-wise Disparity: Laplace Mechanism Can Beat Gaussian in High Dimensions [9.20186865054847]
  In a differentially private additive noise mechanism, independent and identically distributed (i.i.d.) noise samples are added to each coordinate of the response.<n>We study the i.n.i.d. Gaussian and Laplace mechanisms and obtain the conditions under which these mechanisms guarantee privacy.
  arXiv  Detail & Related papers  (2023-02-07T14:54:20Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index [61.675604648670095]
  We argue that the three prevailing interpretations of the GM, namely $(varepsilon, delta)$-DP, f-DP and R'enyi DP can be expressed by using a single parameter $psi$, which we term the sensitivity index. $psi$ uniquely characterises the GM and its properties by encapsulating its two fundamental quantities: the sensitivity of the query and the magnitude of the noise perturbation.
  arXiv  Detail & Related papers  (2021-09-22T06:20:01Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.