Randomized Response with Gradual Release of Privacy Budget
- URL: http://arxiv.org/abs/2401.13952v1
- Date: Thu, 25 Jan 2024 05:18:47 GMT
- Title: Randomized Response with Gradual Release of Privacy Budget
- Authors: Mingen Pan,
- Abstract summary: An algorithm is developed to gradually relax the Differential Privacy (DP) guarantee of a randomized response.
The output from each relaxation maintains the same probability distribution as a standard randomized response.
The entire relaxation process is proven to have the same DP guarantee as the most recent relaxed guarantee.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: An algorithm is developed to gradually relax the Differential Privacy (DP) guarantee of a randomized response. The output from each relaxation maintains the same probability distribution as a standard randomized response with the equivalent DP guarantee, ensuring identical utility as the standard approach. The entire relaxation process is proven to have the same DP guarantee as the most recent relaxed guarantee. The DP relaxation algorithm is adaptable to any Local Differential Privacy (LDP) mechanisms relying on randomized response. It has been seamlessly integrated into RAPPOR, an LDP crowdsourcing string-collecting tool, to optimize the utility of estimating the frequency of collected data. Additionally, it facilitates the relaxation of the DP guarantee for mean estimation based on randomized response. Finally, numerical experiments have been conducted to validate the utility and DP guarantee of the algorithm.
Related papers
- Adaptive Online Bayesian Estimation of Frequency Distributions with Local Differential Privacy [0.4604003661048266]
We propose a novel approach for the adaptive and online estimation of the frequency distribution of a finite number of categories under the local differential privacy (LDP) framework.
The proposed algorithm performs Bayesian parameter estimation via posterior sampling and adapts the randomization mechanism for LDP based on the obtained posterior samples.
We provide a theoretical analysis showing that (i) the posterior distribution targeted by the algorithm converges to the true parameter even for approximate posterior sampling, and (ii) the algorithm selects the optimal subset with high probability if posterior sampling is performed exactly.
arXiv Detail & Related papers (2024-05-11T13:59: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) - Mitigating LLM Hallucinations via Conformal Abstention [70.83870602967625]
We develop a principled procedure for determining when a large language model should abstain from responding in a general domain.
We leverage conformal prediction techniques to develop an abstention procedure that benefits from rigorous theoretical guarantees on the hallucination rate (error rate)
Experimentally, our resulting conformal abstention method reliably bounds the hallucination rate on various closed-book, open-domain generative question answering datasets.
arXiv Detail & Related papers (2024-04-04T11:32:03Z) - Regression with Label Differential Privacy [64.21020761920322]
We derive a label DP randomization mechanism that is optimal under a given regression loss function.
We prove that the optimal mechanism takes the form of a "randomized response on bins"
arXiv Detail & Related papers (2022-12-12T17:41:32Z) - Differentially Private Learning with Margin Guarantees [48.83724068578305]
We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees.
For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviation margin guarantees.
We also present a new efficient DP learning algorithm with margin guarantees for kernel-based hypotheses.
arXiv Detail & Related papers (2022-04-21T19:12:06Z) - Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP)
We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
arXiv Detail & Related papers (2022-02-17T16:04:49Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
arXiv Detail & Related papers (2021-12-07T07:47:37Z) - On the Renyi Differential Privacy of the Shuffle Model [25.052851351062845]
In the shuffle model, each of the $n$ clients randomizes its response using a local differentially private (LDP) mechanism and the untrusted server only receives a random permutation (shuffle) of the client responses without association to each client.
The principal result in this paper is the first non-trivial guarantee for general discrete local randomization mechanisms in the shuffled privacy model.
arXiv Detail & Related papers (2021-05-11T16:34:09Z) - Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
We propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN)
In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent.
This is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model.
arXiv Detail & Related papers (2021-03-17T21:49:53Z) - On the Practicality of Differential Privacy in Federated Learning by
Tuning Iteration Times [51.61278695776151]
Federated Learning (FL) is well known for its privacy protection when training machine learning models among distributed clients collaboratively.
Recent studies have pointed out that the naive FL is susceptible to gradient leakage attacks.
Differential Privacy (DP) emerges as a promising countermeasure to defend against gradient leakage attacks.
arXiv Detail & Related papers (2021-01-11T19:43:12Z)
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.