论文标题
差异化随机线性匪徒：（几乎）免费
Differentially Private Stochastic Linear Bandits: (Almost) for Free
论文作者
论文摘要
在本文中，我们提出了私人算法，以解决中央，局部和洗牌模型中随机线性匪徒的问题。在中心模型中，我们获得了与最佳非私人算法的遗憾，这意味着我们可以免费获得隐私。特别是，我们感到遗憾的是$ \ tilde {o}（\ sqrt {t}+\ frac {1}ε）$匹配已知的私有线性匪徒，而最佳以前已知的algorithm Achieves $ \ tilde {o} {o}（\ frac {\ frac {1} {1} {1} {在当地情况下，我们对$ \ tilde {o}（\ frac {1}ε{\ sqrt {t}}）$感到遗憾，该$符合常数$ε$的非私人遗憾，但是当$ε$很小时，会受到遗憾的惩罚。在改组的模型中，我们还为小$ $ε$的$ \ tilde {o}（\ sqrt {t}+\ frac {1}ε）$％$％$ $ε$作为中心案例所示，而最佳以前已知的算法则遭受了$ \\ tilde {o}（\ frac}的遗憾。我们的数值评估验证了我们的理论结果。
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}ε)$ matching the known lower bound for private linear bandits, while the best previously known algorithm achieves $\tilde{O}(\frac{1}ε\sqrt{T})$. In the local case, we achieve a regret of $\tilde{O}(\frac{1}ε{\sqrt{T}})$ which matches the non-private regret for constant $ε$, but suffers a regret penalty when $ε$ is small. In the shuffled model, we also achieve regret of $\tilde{O}(\sqrt{T}+\frac{1}ε)$ %for small $ε$ as in the central case, while the best previously known algorithm suffers a regret of $\tilde{O}(\frac{1}ε{T^{3/5}})$. Our numerical evaluation validates our theoretical results.
