差分隐私中敏感度如何计算？ 第1页

卸腰。

1. 敏感度的计算就是按定义的那样，对任意一个数据集，你改变数据集中的一项，求这个函数的输出所发生的变化的最大值。一般这个敏感度是可以根据你的函数推出来的，如果推不出来，起码也可以求一个上界。比如你的函数如果是有界的 ，那你的敏感度最多也就是 ，当然你这个上界越紧越好。

2. 我觉得很多人对DP有些误解。DP关心的永远只是隐私，如果我设计一个算法，不管你输入是什么，我总是输出数字0，那这个算法也是满足DP的，因为它的输出跟输入压根没关系，当然不会泄露隐私。大家真正关心的，是如何设计一个好的DP，也就是如何让一个满足DP的算法具有可用性。而且“利用差分来加噪”本身这个说法就是不准确的，应该是反过来“利用噪声去实现差分隐私”。那么什么算法都可以用加噪声来实现DP么？答案是：是的，无论你有什么算法，你总是可以加足够多的噪声（一个极端的例子，让它只输出噪声）让它满足差分隐私，但结果可能是你的算法不再具有可用性，或者可用性非常差。

3. DP作为一个theoretical privacy guarantee，这方面的paper必然会变成一个证明题。这方面的paper思路永远都是：我设计一个加噪声的方法，我证明这个方法能让我的算法变成DP的，我验证这样加噪声后的算法依旧有很好的utility。至于加噪声有没有套路，要说有也算有，无非就是把别人已有的DP算法拿过来改造一下。最经典的比如Laplace Mechanism，很多paper都是在这个算法上设计出来的。为什么这样做？因为证明题并不简单，不是每个人都能无中生有地拿一个算法并证明它满足DP的，所以更多的是用别人证好的东西进行改造。如果想要学套路，唯一的方法就是多看paper。