论文标题
动态的全球敏感性对差异私人上下文匪徒
Dynamic Global Sensitivity for Differentially Private Contextual Bandits
论文作者
论文摘要
强盗算法已成为交互式建议的参考解决方案。但是，由于这种算法直接与用户进行改进的建议，因此对其实际使用提出了严重的隐私问题。在这项工作中，我们通过基于树的机制提出了一种差异性的线性上下文匪徒算法，以将拉普拉斯或高斯噪声添加到模型参数中。我们的关键见解是，随着模型在在线更新期间收敛时，其参数的全局灵敏度随着时间的推移而缩小（因此命名为动态全局灵敏度）。与现有解决方案相比，我们的动态全球灵敏度分析使我们能够减少噪声，从而获得$（ε，δ）$差异私密性，并在$ \ tilde o（\ log {t} \ sqrt {t}/ε）$中引起的噪声注入引起的额外遗憾。我们通过动态全局灵敏度和我们提出的算法的相应上层遗憾界定了对噪声的量进行严格的理论分析。合成数据集和现实世界数据集的实验结果证实了该算法对现有解决方案的优势。
Bandit algorithms have become a reference solution for interactive recommendation. However, as such algorithms directly interact with users for improved recommendations, serious privacy concerns have been raised regarding its practical use. In this work, we propose a differentially private linear contextual bandit algorithm, via a tree-based mechanism to add Laplace or Gaussian noise to model parameters. Our key insight is that as the model converges during online update, the global sensitivity of its parameters shrinks over time (thus named dynamic global sensitivity). Compared with existing solutions, our dynamic global sensitivity analysis allows us to inject less noise to obtain $(ε, δ)$-differential privacy with added regret caused by noise injection in $\tilde O(\log{T}\sqrt{T}/ε)$. We provide a rigorous theoretical analysis over the amount of noise added via dynamic global sensitivity and the corresponding upper regret bound of our proposed algorithm. Experimental results on both synthetic and real-world datasets confirmed the algorithm's advantage against existing solutions.
