标题： 通过随机投影在核化上下文老虎机中实现差分隐私 显示英文标题

标题： Differential Privacy in Kernelized Contextual Bandits via Random Projections

摘要： 我们考虑具有随机上下文的上下文核老虎机问题，其中底层奖励函数属于一个已知的再生核希尔伯特空间。 我们在额外的差分隐私约束下研究这个问题，其中代理需要确保查询点序列相对于上下文和奖励序列是差分私有的。 我们提出了一种新算法，在联合和局部差分隐私模型中，分别在时间范围为$T$的情况下实现了累积遗憾度为$\widetilde{\mathcal{O}}(\sqrt{\gamma_TT}+\frac{\gamma_T}{\varepsilon_{\mathrm{DP}}})$和$\widetilde{\mathcal{O}}(\sqrt{\gamma_TT}+\frac{\gamma_T\sqrt{T}}{\varepsilon_{\mathrm{DP}}})$，其中$\gamma_T$是核的有效维度，$\varepsilon_{\mathrm{DP}} > 0$是隐私参数。 所提出算法的关键组成部分是一种新颖的私有核岭回归估计器，该估计器基于私有协方差估计和私有随机投影的结合。 它相比其经典版本具有显著降低的敏感性，同时保持了较高的预测准确性，使我们的算法能够实现最先进的性能保证。 显示英文摘要

摘要： We consider the problem of contextual kernel bandits with stochastic contexts, where the underlying reward function belongs to a known Reproducing Kernel Hilbert Space. We study this problem under an additional constraint of Differential Privacy, where the agent needs to ensure that the sequence of query points is differentially private with respect to both the sequence of contexts and rewards. We propose a novel algorithm that achieves the state-of-the-art cumulative regret of $\widetilde{\mathcal{O}}(\sqrt{\gamma_TT}+\frac{\gamma_T}{\varepsilon_{\mathrm{DP}}})$ and $\widetilde{\mathcal{O}}(\sqrt{\gamma_TT}+\frac{\gamma_T\sqrt{T}}{\varepsilon_{\mathrm{DP}}})$ over a time horizon of $T$ in the joint and local models of differential privacy, respectively, where $\gamma_T$ is the effective dimension of the kernel and $\varepsilon_{\mathrm{DP}} > 0$ is the privacy parameter. The key ingredient of the proposed algorithm is a novel private kernel-ridge regression estimator which is based on a combination of private covariance estimation and private random projections. It offers a significantly reduced sensitivity compared to its classical counterpart while maintaining a high prediction accuracy, allowing our algorithm to achieve the state-of-the-art performance guarantees.