Locally Differentially Private Thresholding Bandits

• URL: http://arxiv.org/abs/2507.23073v1
• Date: Wed, 30 Jul 2025 20:08:30 GMT
• Title: Locally Differentially Private Thresholding Bandits
• Authors: Annalisa Barbara, Joseph Lazzaro, Ciara Pike-Burke,
• Abstract summary: This work investigates the impact of ensuring local differential privacy in the thresholding bandit problem.<n>We propose methods that utilize private responses, obtained through a Bernoulli-based differentially private mechanism, to identify arms with expected rewards exceeding a predefined threshold.
• Score: 3.8916312075738273
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This work investigates the impact of ensuring local differential privacy in the thresholding bandit problem. We consider both the fixed budget and fixed confidence settings. We propose methods that utilize private responses, obtained through a Bernoulli-based differentially private mechanism, to identify arms with expected rewards exceeding a predefined threshold. We show that this procedure provides strong privacy guarantees and derive theoretical performance bounds on the proposed algorithms. Additionally, we present general lower bounds that characterize the additional loss incurred by any differentially private mechanism, and show that the presented algorithms match these lower bounds up to poly-logarithmic factors. Our results provide valuable insights into privacy-preserving decision-making frameworks in bandit problems.

Related papers

• DP-NCB: Privacy Preserving Fair Bandits [7.443474354626665]
  We introduce Differentially Private Nash Confidence Bound (DP-NCB)-a novel and unified algorithmic framework.<n>It simultaneously ensures $epsilon$-differential privacy and achieves order-optimal Nash regret, matching known lower bounds up to logarithmic factors.<n>Our results offer a principled foundation for designing bandit algorithms that are both privacy-preserving and fair, making them suitable for high-stakes, socially impactful applications.
  arXiv  Detail & Related papers  (2025-08-05T18:34:00Z)
• On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models [15.713997170792846]
  We investigate privacy-preserving spectral clustering for community detection within block models (SBMs)<n>Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery.
  arXiv  Detail & Related papers  (2025-05-09T06:34:56Z)
• Improving the Variance of Differentially Private Randomized Experiments through Clustering [16.166525280886578]
  We propose a new differentially private mechanism, "Cluster-DP"<n>We demonstrate that selecting higher-quality clusters, according to a quality metric we introduce, can decrease the variance penalty without compromising privacy guarantees.
  arXiv  Detail & Related papers  (2023-08-02T05:51:57Z)
• Adaptive Privacy Composition for Accuracy-first Mechanisms [55.53725113597539]
  Noise reduction mechanisms produce increasingly accurate answers. Analysts only pay the privacy cost of the least noisy or most accurate answer released. There has yet to be any study on how ex-post private mechanisms compose. We develop privacy filters that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms.
  arXiv  Detail & Related papers  (2023-06-24T00:33:34Z)
• Robust and differentially private stochastic linear bandits [23.96322363134793]
  We study the linear bandit problem under the additional requirements of differential privacy, robustness and batched observations. We present differentially private and robust variants of the arm elimination algorithm using logarithmic batch queries.
  arXiv  Detail & Related papers  (2023-04-23T20:17:03Z)
• 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)
• Private Domain Adaptation from a Public Source [48.83724068578305]
  We design differentially private discrepancy-based algorithms for adaptation from a source domain with public labeled data to a target domain with unlabeled private data. Our solutions are based on private variants of Frank-Wolfe and Mirror-Descent algorithms.
  arXiv  Detail & Related papers  (2022-08-12T06:52:55Z)
• Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints [53.01656650117495]
  There is a disconnect between how researchers and practitioners handle privacy-utility tradeoffs. Brownian mechanism works by first adding Gaussian noise of high variance corresponding to the final point of a simulated Brownian motion. We complement our Brownian mechanism with ReducedAboveThreshold, a generalization of the classical AboveThreshold algorithm.
  arXiv  Detail & Related papers  (2022-06-15T01:43:37Z)
• Privacy Amplification via Shuffled Check-Ins [2.3333090554192615]
  We study a protocol for distributed computation called shuffled check-in. It achieves strong privacy guarantees without requiring any further trust assumptions beyond a trusted shuffler. We show that shuffled check-in achieves tight privacy guarantees through privacy amplification.
  arXiv  Detail & Related papers  (2022-06-07T09:55:15Z)
• Debugging Differential Privacy: A Case Study for Privacy Auditing [60.87570714269048]
  We show that auditing can also be used to find flaws in (purportedly) differentially private schemes. In this case study, we audit a recent open source implementation of a differentially private deep learning algorithm and find, with 99.99999999% confidence, that the implementation does not satisfy the claimed differential privacy guarantee.
  arXiv  Detail & Related papers  (2022-02-24T17:31:08Z)
• 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)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)
• Differential Privacy at Risk: Bridging Randomness and Privacy Budget [5.393465689287103]
  We analyse roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution. We propose privacy at risk that is a probabilistic calibration of privacy-preserving mechanisms. We show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced composition.
  arXiv  Detail & Related papers  (2020-03-02T15:44:14Z)

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.