Optimizing Noise for $f$-Differential Privacy via Anti-Concentration and Stochastic Dominance

• URL: http://arxiv.org/abs/2308.08343v3
• Date: Mon, 11 Nov 2024 08:23:46 GMT
• Title: Optimizing Noise for $f$-Differential Privacy via Anti-Concentration and Stochastic Dominance
• Authors: Jordan Awan, Aishwarya Ramasethu,
• Abstract summary: We show that canonical noise distributions (CNDs) match the anti-concentration bounds at half-integer values. We propose a new notion of discrete CND and prove that a discrete CND always exists. Our theoretical results shed light on the different types of privacy guarantees possible in the $f$DP framework and can be incorporated in more complex mechanisms to optimize performance.
• Score: 7.581259361859479
• License:
• Abstract: In this paper, we establish anti-concentration inequalities for additive noise mechanisms which achieve $f$-differential privacy ($f$-DP), a notion of privacy phrased in terms of a tradeoff function $f$ which limits the ability of an adversary to determine which individuals were in the database. We show that canonical noise distributions (CNDs), proposed by Awan and Vadhan (2023), match the anti-concentration bounds at half-integer values, indicating that their tail behavior is near-optimal. We also show that all CNDs are sub-exponential, regardless of the $f$-DP guarantee. In the case of log-concave CNDs, we show that they are the stochastically smallest noise compared to any other noise distributions with the same privacy guarantee. In terms of integer-valued noise, we propose a new notion of discrete CND and prove that a discrete CND always exists, can be constructed by rounding a continuous CND, and that the discrete CND is unique when designed for a statistic with sensitivity 1. We further show that the discrete CND at sensitivity 1 is stochastically smallest compared to other integer-valued noises. Our theoretical results shed light on the different types of privacy guarantees possible in the $f$-DP framework and can be incorporated in more complex mechanisms to optimize performance.

Related papers

• Stable Neighbor Denoising for Source-free Domain Adaptive Segmentation [91.83820250747935]
  Pseudo-label noise is mainly contained in unstable samples in which predictions of most pixels undergo significant variations during self-training. We introduce the Stable Neighbor Denoising (SND) approach, which effectively discovers highly correlated stable and unstable samples. SND consistently outperforms state-of-the-art methods in various SFUDA semantic segmentation settings.
  arXiv  Detail & Related papers  (2024-06-10T21:44:52Z)
• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• Guarantees of confidentiality via Hammersley-Chapman-Robbins bounds [61.50022257278769]
  Noise is added to the activations in the last layers prior to the final classifiers or other task-specific layers. Lower bounding the variance of every possible unbiased estimator of the inputs quantifies the confidentiality arising from such added noise. Numerical experiments indicate that the HCR bounds are on the precipice of being effectual for small neural nets.
  arXiv  Detail & Related papers  (2024-04-03T16:58:03Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  We show how to shuffle $(epsilon_i,delta_i)$-PLDP setting with personalized privacy parameters. We prove that shuffled $(epsilon_i,delta_i)$-PLDP process approximately preserves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  arXiv  Detail & Related papers  (2023-12-22T02:31:46Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Differential privacy for symmetric log-concave mechanisms [0.0]
  Adding random noise to database query results is an important tool for achieving privacy. We provide a sufficient and necessary condition for $(epsilon, delta)$-differential privacy for all symmetric and log-concave noise densities.
  arXiv  Detail & Related papers  (2022-02-23T10:20:29Z)
• 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)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)

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.