3.6 稀疏向量技术
拉普拉斯机制可用于回答自适应选择的低敏感度查询,并且从我们的合成定理中我们知道,隐私参数与所回答的查询数量(或其平方根)成比例地降低。不幸的是,经常会发生我们有大量问题要回答的问题,即使使用 3.5节 中的高级合成定理,也有太多问题无法使用独立的扰动技术来提供合理的隐私保证。但是,在某些情况下,我们只会关心知道高于某个阈值的查询的标识。在这种情况下,我们希望通过放弃对明显低于阈值的查询的数字答案,而仅报告这些查询确实低于阈值,从而获得本质的分析。(如果我们这样选择的话,我们也将能够获得阈值以上查询的数字值,而只需花费额外的费用)。这类似于我们在3.3节中的“Report Noisy Max”机制中所做的事情,实际上,对于非交互式或脱机情况,可以选择迭代该算法或指数机制。
在本节中,我们显示如何在在线设置中分析此方法。该技术很简单:添加噪音并仅报告噪声值是否超过阈值。本节中,我们的重点是分析隐私只会随着实际高于阈值的查询数量而降低,而不会随着查询总数的增加而降低。如果我们知道位于阈值以上的查询集比查询总数小得多(也就是说,如果答案向量稀疏的话),那么将可以大量节省(隐私参数)。
更详细地讲,我们将考虑一系列事件(每个查询一个),如果在数据库上评估的查询超过给定(已知的、公共的)阈值,则会发生这些事件。我们的目标是释放一个位向量,以指示每个事件是否已发生。在提出每个查询时,该机制将计算一个噪声响应,并将其与(众所周知的)阈值进行比较,如果超过了该阈值,则将揭示此事实。由于隐私证明(定理3.24)中的技术原因,该算法适用于阈值 的噪声版本 。虽然 是公开的,但噪声版本 不是。
并非对每个可能的查询都造成隐私损失,后文的分析将仅针对接近或高于阈值的查询值导致隐私损失。
设置 设 表示灵敏度为 1 的查询总数,可以自适应地选择。在不丧失通用性的情况下,有一个预先固定的阈值 (或者每个查询可以有自己的阈值,但结果不变)。我们将在查询值中添加噪声,并将结果与 进行比较。正向的结果意味着噪声查询值超过了阈值。我们期望 (少量)个噪声值超过阈值,并且我们只释放高于阈值的噪声值。算法将 用作其停止条件。
我们将首先分析在超过阈值查询的 之后算法停止的情况,并表明无论查询的总序列有多长,该算法都是 -差分隐私的。然后利用我们的合成定理分析 的情形,并推导出 和-差分隐私的界。