Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT

• URL: http://arxiv.org/abs/2006.07134v3
• Date: Mon, 21 Jun 2021 11:49:45 GMT
• Title: Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT
• Authors: Antti Koskela, Joonas J\"alk\"o, Lukas Prediger and Antti Honkela
• Abstract summary: We propose a numerical accountant for evaluating the tight $(varepsilon,delta)$-privacy loss for algorithms with discrete one dimensional output. We show that our approach allows decreasing noise variance up to 75 percent at equal privacy compared to existing bounds in the literature.
• Score: 6.929834518749884
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a numerical accountant for evaluating the tight $(\varepsilon,\delta)$-privacy loss for algorithms with discrete one dimensional output. The method is based on the privacy loss distribution formalism and it uses the recently introduced fast Fourier transform based accounting technique. We carry out an error analysis of the method in terms of moment bounds of the privacy loss distribution which leads to rigorous lower and upper bounds for the true $(\varepsilon,\delta)$-values. As an application, we present a novel approach to accurate privacy accounting of the subsampled Gaussian mechanism. This completes the previously proposed analysis by giving strict lower and upper bounds for the privacy parameters. We demonstrate the performance of the accountant on the binomial mechanism and show that our approach allows decreasing noise variance up to 75 percent at equal privacy compared to existing bounds in the literature. We also illustrate how to compute tight bounds for the exponential mechanism applied to counting queries.

Related papers

• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants. There is no differentially private distributed method for training, non-feedback problems. We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy [41.51051636162107]
  This paper focuses on improving privacy bounds for shuffling models and one-iteration differentially private gradient descent. We derive a closed-form expression of the trade-off function for shuffling models that outperforms the most up-to-date results. We also study an $f$-DP analog of the advanced joint convexity of the hockey-stick divergence related to $(epsilon,delta)$-DP.
  arXiv  Detail & Related papers  (2023-10-30T19:37:51Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Individual Privacy Accounting with Gaussian Differential Privacy [8.81666701090743]
  Individual privacy accounting enables bounding differential privacy (DP) loss individually for each participant involved in the analysis. In order to account for the individual privacy losses in a principled manner, we need a privacy accountant for adaptive compositions of randomised mechanisms.
  arXiv  Detail & Related papers  (2022-09-30T17:19:40Z)
• Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions [49.726408540784334]
  Key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We show that our pessimistic estimate is the best possible among all pessimistic estimates.
  arXiv  Detail & Related papers  (2022-07-10T04:25:02Z)
• The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
  We introduce a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-07-09T05:46:28Z)
• Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms [93.44378960676897]
  Given a trained model and a data sample, membership-inference (MI) attacks predict whether the sample was in the model's training set. A common countermeasure against MI attacks is to utilize differential privacy (DP) during model training to mask the presence of individual examples. In this paper, we derive bounds for the textitadvantage of an adversary mounting a MI attack, and demonstrate tightness for the widely-used Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-04-12T22:36:56Z)
• Oneshot Differentially Private Top-k Selection [23.88111547236874]
  We introduce a fast, low-distortion, and differentially private primitive for the top-$k$ problem. Compared with existing approaches in the literature, our algorithm adds Laplace noise to the counts and releases the top-$k$ noisy counts and their estimates in a oneshot fashion.
  arXiv  Detail & Related papers  (2021-05-18T02:18:01Z)
• Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT [5.837881923712393]
  We show how to evaluate tight privacy guarantees using the Plancherel theorem at the cost of increased pre-computation and memory usage. We also show how to speed up the evaluation of tight privacy guarantees using the Plancherel theorem at the cost of increased pre-computation and memory usage.
  arXiv  Detail & Related papers  (2021-02-24T17:05:38Z)
• 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.