arXiv:2510.17348stat.MLcs.LG2025-10NeurIPS被引 2

在差分隐私约束下,首次将最优选最优臂的样本复杂度差距缩小至常数倍。

Optimal Best Arm Identification under Differential Privacy

  • 设计基于运输成本的私有采样策略,融合KL散度与总变差距离。
  • 提出新停止规则与顶部两臂采样法,理论样本复杂度逼近下界。
  • 适用于医疗试验等高敏感数据场景,适合关注隐私保障的研究者。

最优臂识别(BAI)算法被用于临床试验、用户研究等敏感数据场景。针对伯努利分布下的固定置信度BAI问题,本文研究全局差分隐私(DP)条件下的最优性。尽管非私有场景已有众多渐近最优算法,但在全局DP设定下,上下界之间的差距仍较大。本文将该差距缩小至一个较小的乘法常数(对任意隐私预算ε均成立)。首先,我们给出了任意δ-正确且ε-全局DP策略的期望样本复杂度的更紧下界,用一种新的信息论量替代了非私有情形中的KL散度,该量在KL散度与缩放后的总变差距离间实现最优权衡。其次,我们引入基于这些运输成本的停止规则,并结合基于臂相关几何分批的私有均值估计器。在证明停止规则正确性的过程中,我们还推导了拉普拉斯分布及伯努利+拉普拉斯和的浓度不等式,具有独立兴趣。第三,我们提出一种基于运输成本的“顶部两臂”采样规则。对于任意ε,其期望样本复杂度的渐近上界与我们的下界仅相差小于8的乘法常数。实验表明,该算法在不同ε值下均优于现有δ-正确且ε-全局DP BAI算法。

原文摘要 · Abstract (English)

Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies. Driven by the privacy concerns of these applications, we study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions. While numerous asymptotically optimal BAI algorithms exist in the non-private setting, a significant gap remains between the best lower and upper bounds in the global DP setting. This work reduces this gap to a small multiplicative constant, for any privacy budget $ε$. First, we provide a tighter lower bound on the expected sample complexity of any $δ$-correct and $ε$-global DP strategy. Our lower bound replaces the Kullback-Leibler (KL) divergence in the transportation cost used by the non-private characteristic time with a new information-theoretic quantity that optimally trades off between the KL divergence and the Total Variation distance scaled by $ε$. Second, we introduce a stopping rule based on these transportation costs and a private estimator of the means computed using an arm-dependent geometric batching. En route to proving the correctness of our stopping rule, we derive concentration results of independent interest for the Laplace distribution and for the sum of Bernoulli and Laplace distributions. Third, we propose a Top Two sampling rule based on these transportation costs. For any budget $ε$, we show an asymptotic upper bound on its expected sample complexity that matches our lower bound to a multiplicative constant smaller than $8$. Our algorithm outperforms existing $δ$-correct and $ε$-global DP BAI algorithms for different values of $ε$.

差分隐私最优臂识别统计学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。