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

• Near-Optimal Private Learning in Linear Contextual Bandits [61.39697409886124]
  We analyze the problem of private learning in generalized linear contextual bandits. Our results imply that joint privacy is almost "for free" in all the settings we consider.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms. We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
  High dimensional sparse linear bandits serve as an efficient model for sequential decision-making problems. Motivated by data privacy concerns, we study the joint differentially private high dimensional sparse linear bandits. We show that FLIPHAT achieves optimal regret in terms of privacy parameters.
  arXiv  Detail & Related papers  (2024-05-22T22:19:12Z)
• 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)
• 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 [17.04261371990489]
  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)
• 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)
• 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.