跳到主要内容
返回时间线
arXiv来源发表:

在线分配也要隐私:PPOA把预算与对偶变量加噪,竞争比仍可逼近无隐私上限

核心概要

在线分配中,共享预算会把一个请求的决策变成其他用户上下文的侧信道,而标准差分隐私又几乎不允许算法随上下文调整动作。PPOA把剩余预算与拉格朗日对偶变量作为需要加噪的协调量,给出在联合差分隐私或本地差分隐私下同时满足预算约束并达到渐近近优性能的充分条件。两个实例中,PPOA-FTRL在仅需联合差分隐私时竞争比达0.834,PPOA-DMD在同时满足两种隐私时达0.665。

AI-generated editorial illustration: Online Allocation with Differential Privacy

深度剖析

在线分配的资源预算把不同请求的决策耦合在一起,因此一个用户看到的分配结果会透露此前用户的上下文;PPOA把这种耦合中的协调量作为隐私保护对象,而不是把动作输出本身当作唯一需要隐藏的东西。 此前的联合差分隐私资源分配工作要么处理离线凸目标,要么在随机到达模型下实现在线算法,都没有覆盖需要对所有上下文序列一致成立的最坏情况竞争保证。 在RouterBench的电池供电边缘AI模型路由任务上,同时满足联合与本地差分隐私的PPOA-DMD取得0.665的竞争比和0.801的平均归一化奖励,而同样满足两种隐私的NDMD为0.635和0.778。

算法每一轮先用干净上下文、加噪后的对偶变量和加噪后的剩余预算预选动作,再把动作投影到由加噪预算减去预留余量得到的保守预算之内,从而在噪声存在时仍以高概率不超支。 直接套用带噪对偶镜像下降会让无界噪声随时间累积,破坏最坏情况保证;PPOA-DMD改为带范数上界的投影对偶镜像下降,PPOA-FTRL则用树聚合机制释放累计预算消耗。 仅需联合差分隐私时,采用树聚合的PPOA-FTRL在RouterBench上取得0.834的竞争比和0.879的平均归一化奖励,高于NFTRL的0.597和0.726,也高于PPOA-DMD的0.665和0.801。

启示与展望

讨论范围限于带预算约束的在线分配问题,实验落在RouterBench的电池供电边缘AI模型路由任务与iPinYou在线广告竞价任务上,隐私参数默认取较小的松弛量与1到10之间的隐私预算。理论保证是渐近的:竞争比在概率意义下成立,遗憾在独立同分布到达下为次线性。

作者指出,所建立的性能界在隐私水平上的缩放未必最优,仍有向几乎必然渐近或非渐近形式改进的空间。在非平稳上下文中,概率意义下的渐近竞争比仍成立,但次线性期望遗憾需要额外假设。实验还显示,当隐私预算继续收紧时,所有方法的分配性能都变得很弱。