On the Privacy of Selection Mechanisms with Gaussian Noise

• URL: http://arxiv.org/abs/2402.06137v2
• Date: Thu, 21 Mar 2024 14:03:39 GMT
• Title: On the Privacy of Selection Mechanisms with Gaussian Noise
• Authors: Jonathan Lebensold, Doina Precup, Borja Balle,
• Abstract summary: We revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise. We find that it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold.
• Score: 44.577599546904736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Report Noisy Max and Above Threshold are two classical differentially private (DP) selection mechanisms. Their output is obtained by adding noise to a sequence of low-sensitivity queries and reporting the identity of the query whose (noisy) answer satisfies a certain condition. Pure DP guarantees for these mechanisms are easy to obtain when Laplace noise is added to the queries. On the other hand, when instantiated using Gaussian noise, standard analyses only yield approximate DP guarantees despite the fact that the outputs of these mechanisms lie in a discrete space. In this work, we revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise and show that, under the additional assumption that the underlying queries are bounded, it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold. The resulting bounds are tight and depend on closed-form expressions that can be numerically evaluated using standard methods. Empirically we find these lead to tighter privacy accounting in the high privacy, low data regime. Further, we propose a simple privacy filter for composing pure ex-post DP guarantees, and use it to derive a fully adaptive Gaussian Sparse Vector Technique mechanism. Finally, we provide experiments on mobility and energy consumption datasets demonstrating that our Sparse Vector Technique is practically competitive with previous approaches and requires less hyper-parameter tuning.

Related papers

• Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise [32.79378183735303]
  The Sparse Vector Technique (SVT) is one of the most fundamental tools in differential privacy (DP) Unlike the typical private query releases that directly publicize the noisy query results, SVT is less informative. We provide a new privacy analysis for SVT by considering its less informative nature.
  arXiv  Detail & Related papers  (2024-07-29T14:54:28Z)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Using Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) to ensure Differential Privacy (DP) comes at the cost of model performance degradation. We propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R'enyi DP.
  arXiv  Detail & Related papers  (2023-11-24T17:56:44Z)
• Privacy Amplification for Matrix Mechanisms [18.13715687378337]
  "MMCC" is the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. We show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.
  arXiv  Detail & Related papers  (2023-10-24T05:16:52Z)
• Differential Privacy with Higher Utility by Exploiting Coordinate-wise Disparity: Laplace Mechanism Can Beat Gaussian in High Dimensions [9.20186865054847]
  We study the i.n.i.d. Gaussian and Laplace mechanisms and obtain the conditions under which these mechanisms guarantee privacy. We show how the i.n.i.d. noise can improve the performance in private (a) coordinate descent, (b) principal component analysis, and (c) deep learning with group clipping.
  arXiv  Detail & Related papers  (2023-02-07T14:54:20Z)
• Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions [59.605246463200736]
  We present a novel controller synthesis method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous control system into a finite-state model that captures noise by probabilistic transitions between discrete states. We use state-of-the-art verification techniques to provide guarantees on the interval Markov decision process and compute a controller for which these guarantees carry over to the original control system.
  arXiv  Detail & Related papers  (2023-01-04T10:40:30Z)
• Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints [53.01656650117495]
  There is a disconnect between how researchers and practitioners handle privacy-utility tradeoffs. Brownian mechanism works by first adding Gaussian noise of high variance corresponding to the final point of a simulated Brownian motion. We complement our Brownian mechanism with ReducedAboveThreshold, a generalization of the classical AboveThreshold algorithm.
  arXiv  Detail & Related papers  (2022-06-15T01:43:37Z)
• Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets [3.5379819043314176]
  We introduce a novel framework for designing an optimal noise Mass Probability Function tailored to discrete and finite query sets. Our framework seeks to optimize the noise distribution under an arbitrary $(epsilon, delta)$ constraint, thereby enhancing the accuracy and utility of the response. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-11-23T05:24:34Z)
• Learning Numeric Optimal Differentially Private Truncated Additive Mechanisms [5.079561894598125]
  We introduce a tool to learn truncated noise for additive mechanisms with strong utility bounds. We show that it is sufficient to consider symmetric and thatnew, for from the mean monotonically falling noise. For sensitivity bounded mechanisms, we show that it is sufficient to consider symmetric and thatnew, for from the mean monotonically falling noise.
  arXiv  Detail & Related papers  (2021-07-27T17:22:57Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)

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.