Differentially Private High Dimensional Bandits
- URL: http://arxiv.org/abs/2402.03737v1
- Date: Tue, 6 Feb 2024 06:10:46 GMT
- Title: Differentially Private High Dimensional Bandits
- Authors: Apurv Shukla
- Abstract summary: We present PrivateLASSO, a differentially private LASSO bandit algorithm.
PrivateLASSO is based on two sub-routines: (i) a sparse hard-thresholding-based privacy mechanism and (ii) an episodic thresholding rule for identifying the support of the parameter $theta$.
- Score: 1.3597551064547502
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider a high-dimensional stochastic contextual linear bandit problem
when the parameter vector is $s_{0}$-sparse and the decision maker is subject
to privacy constraints under both central and local models of differential
privacy. We present PrivateLASSO, a differentially private LASSO bandit
algorithm. PrivateLASSO is based on two sub-routines: (i) a sparse
hard-thresholding-based privacy mechanism and (ii) an episodic thresholding
rule for identifying the support of the parameter $\theta$. We prove minimax
private lower bounds and establish privacy and utility guarantees for
PrivateLASSO for the central model under standard assumptions.
Related papers
- 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) - Private Fine-tuning of Large Language Models with Zeroth-order
Optimization [54.24600476755372]
We introduce DP-ZO, a new method for fine-tuning large language models that preserves the privacy of training data by privatizing zeroth-order optimization.
We show that DP-ZO exhibits just $1.86%$ performance degradation due to privacy at $ (1,10-5)$-DP when fine-tuning OPT-66B on 1000 training samples from SQuAD.
arXiv Detail & Related papers (2024-01-09T03:53:59Z) - Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
We consider a private discrete distribution estimation problem with one-bit communication constraint.
We characterize the first-orders of the worst-case trade-off under the one-bit communication constraint.
These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint.
arXiv Detail & Related papers (2023-10-17T05:21:19Z) - About the Cost of Central Privacy in Density Estimation [0.0]
We study non-parametric density estimation for densities in Lipschitz and Sobolev spaces.
We consider regimes where the privacy budget is not supposed to be constant.
arXiv Detail & Related papers (2023-06-26T09:19:01Z) - Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis.
In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
arXiv Detail & Related papers (2022-09-08T22:43:50Z) - When Privacy Meets Partial Information: A Refined Analysis of
Differentially Private Bandits [4.964737844687583]
We study the problem of multi-armed bandits with $epsilon$-global Differential Privacy (DP)
We instantiate $epsilon$-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB.
AdaP-KLUCB is the first algorithm that both satisfies $epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.
arXiv Detail & Related papers (2022-09-06T15:26:24Z) - Optimal and Differentially Private Data Acquisition: Central and Local
Mechanisms [9.599356978682108]
We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest.
We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local.
We pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities.
arXiv Detail & Related papers (2022-01-10T00:27:43Z) - Privacy Amplification via Shuffling for Linear Contextual Bandits [51.94904361874446]
We study the contextual linear bandit problem with differential privacy (DP)
We show that it is possible to achieve a privacy/utility trade-off between JDP and LDP by leveraging the shuffle model of privacy.
Our result shows that it is possible to obtain a tradeoff between JDP and LDP by leveraging the shuffle model while preserving local privacy.
arXiv Detail & Related papers (2021-12-11T15:23:28Z) - Adaptive Control of Differentially Private Linear Quadratic Systems [5.414308305392762]
We study the problem of regret in reinforcement learning (RL) under differential privacy constraints.
We develop the first private RL algorithm, PRL, which is able to attain a sub-linear regret while guaranteeing privacy protection.
arXiv Detail & Related papers (2021-08-26T03:06:22Z) - Generalized Linear Bandits with Local Differential Privacy [4.922800530841394]
Many applications such as personalized medicine and online advertising require the utilization of individual-specific information for effective learning.
This motivates the introduction of local differential privacy (LDP), a stringent notion in privacy, to contextual bandits.
In this paper, we design LDP algorithms for generalized linear bandits to achieve the same regret bound as in non-privacy settings.
arXiv Detail & Related papers (2021-06-07T06:42:00Z) - Private Reinforcement Learning with PAC and Regret Guarantees [69.4202374491817]
We design privacy preserving exploration policies for episodic reinforcement learning (RL)
We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP)
We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee.
arXiv Detail & Related papers (2020-09-18T20:18:35Z)
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.