NeFut Logo NeFut
EN 管理员登录

[算法理论] 隐私过滤器的残差捕获:自由自然过滤器的特征与自适应成本

发布于:2026-11-09 22:00 最后更新:2026-11-12 00:51
#algorithm #optimization #DP

我们研究了隐私过滤器——一种在自适应选择隐私特性的差分隐私(DP)机制中进行隐私会计的工具。我们证明,与任意隐私过滤器交互的最坏情况隐私损失可以用一个 Bellman 方程来刻画。

基于该理论,我们提出了残差过滤器,它统一了已有的各种隐私过滤器。我们进一步构造了高斯 DP(GDP)残差过滤器,其性能严格优于传统的朴素 GDP 过滤器。平均情况下,该新过滤器在非自适应情形下能够容纳的纯 DP 查询数量与理论上限相同,并且比朴素 GDP 过滤器多出约 $\pi/2$ 倍的纯 DP 查询。

残差过滤器还能捕获自然过滤器的行为——后者通过精确的隐私会计技术利用完整的隐私配置文件,从而提供更高的效用。早期的隐私过滤器仅考虑 R\'enyi‑DP 或 GDP 等单一参数,而自然过滤器考虑每个查询的完整隐私曲线,因而在给定隐私预算下使用更高效。

我们进一步证明,自然隐私过滤器并非在所有情况下都是“免费”的。我们给出了一个判别条件:只有当一族隐私机制在组合时形成全序(即任意两个机制可比较)时,才存在对任意隐私预算都免费的自然过滤器。

最后,尽管在自适应对手存在时,自然的近似 DP 过滤器可能失效,但其失效程度有限:输出仍保持近似 DP,且其参数至多比原设定差一个多项式对数因子。

点评:本文通过 Bellman 方程将隐私过滤的最坏情况分析形式化,提出的残差过滤器在理论上显著提升了查询容量,尤其在高斯 DP 场景下实现了 $\pi/2$ 的提升。对自然过滤器的免费性条件给出了清晰的结构性限制,为后续设计自适应安全的隐私会计方案提供了重要指引。

原文链接: https://arxiv.org/abs/2602.15815

[h] 返回首页