Differentially Private Stochastic Linear Bandits: (Almost) for Free

• URL: http://arxiv.org/abs/2207.03445v1
• Date: Thu, 7 Jul 2022 17:20:57 GMT
• Title: Differentially Private Stochastic Linear Bandits: (Almost) for Free
• Authors: Osama A. Hanna, Antonious M. Girgis, Christina Fragouli, Suhas Diggavi
• Abstract summary: In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In the shuffled model, we also achieve regret of $tildeO(sqrtT+frac1epsilon)$ %for small $epsilon$ as in the central case, while the best previously known algorithm suffers a regret of $tildeO(frac1epsilonT3/5)$.
• Score: 17.711701190680742
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of $\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ matching the known lower bound for private linear bandits, while the best previously known algorithm achieves $\tilde{O}(\frac{1}{\epsilon}\sqrt{T})$. In the local case, we achieve a regret of $\tilde{O}(\frac{1}{\epsilon}{\sqrt{T}})$ which matches the non-private regret for constant $\epsilon$, but suffers a regret penalty when $\epsilon$ is small. In the shuffled model, we also achieve regret of $\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ %for small $\epsilon$ as in the central case, while the best previously known algorithm suffers a regret of $\tilde{O}(\frac{1}{\epsilon}{T^{3/5}})$. Our numerical evaluation validates our theoretical results.

Related papers

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  We introduce a simple, unified UCB-based algorithm that achieves novel $p$-mean regret bounds. Our framework encompasses both average cumulative regret and Nash regret as special cases.
  arXiv  Detail & Related papers  (2024-12-14T08:38:26Z)
• Private Zeroth-Order Nonsmooth Nonconvex Optimization [41.05664717242051]
  We introduce a new zeroth-order algorithm for private optimization on non and nonsmooth objectives. Given a dataset size $M$, our algorithm finds a privacy differential. Although the objective is not smooth, we have privacy. for free whenever $tdepsilon$.
  arXiv  Detail & Related papers  (2024-06-27T23:57:01Z)
• DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
  We give the first differentially private dueling bandit algorithm for active learning with user preferences. Our algorithms are computationally efficient with near-optimal performance. We extend our results to any general decision space in $d$-dimensions with potentially infinite arms.
  arXiv  Detail & Related papers  (2024-03-22T09:02:12Z)
• Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
  We consider online learning problems in the realizable setting, where there is a zero-loss solution. We propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds.
  arXiv  Detail & Related papers  (2023-02-27T21:19:24Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries.
  arXiv  Detail & Related papers  (2022-10-24T18:40:19Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  We give an $(varepsilon,delta)$-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.
  arXiv  Detail & Related papers  (2021-06-05T14:11:01Z)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  We study differentially private online learning problems in a environment under both bandit and full information feedback. For differentially private bandits, we propose both UCB and Thompson Sampling-based algorithms that are anytime and achieve the optimal $O left(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right right)$ minimax lower bound. For the same differentially private full information setting, we also present an $epsilon$-differentially
  arXiv  Detail & Related papers  (2021-02-16T02:48:16Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)

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.