“平滑灵敏度也研究统计量对数据变化的响应,但它使用有限数据库上的相邻修改,而非分布污染方向的无穷小导数。它在邻接距离上对局部灵敏度取指数衰减的上包络,使数据依赖噪声尺度本身缓慢变化。一个估计量…”
形式陈述
设
显然
所以它既罩住当前位置的查询改变量,又限制噪声尺度跨相邻输入的倍率变化。任何满足这两项性质的可计算上界
直觉
全局灵敏度为所有数据库采用同一个最坏尺度。局部灵敏度只看眼前数据库,可能很小,却可能在相邻输入处突然变大。观察输出的波动大小,就可能推断数据库位于突变的哪一侧。
平滑灵敏度向外查看:距离为
一个可直接验证的纯 DP 机制
为展示尺度如何参与证明,
这是重尾 Cauchy 噪声。令
对固定均值,
例子与边界
阈值查询的完整平滑包络
数据库由五个 bit 组成,记
距离最近的不稳定位置分别为
例如
适用代价
Cauchy 分布没有有限均值和方差,所以不能用均方误差描述上述机制的准确性。它的中位数为零,且
一般查询计算
推论与应用
这种方法适合“绝大多数数据稳定,极少数配置很敏感”的统计量。正确顺序是先证明尺度的上界与平滑性质,再选择噪声族与参数;不能先观察一个小局部灵敏度就直接套全局灵敏度机制。
参考资料
- Nissim、Raskhodnikova 与 Smith,“Smooth Sensitivity and Sampling in Private Data Analysis”,STOC 2007,§2 的平滑上界与可接受噪声,§3 的计算方法。本文的 Cauchy 常数通过上面的密度导数单独验证。