我们还可以看到如果数据集中

ditihekhatun15

只有一个点则不可能提供隐私保护解决方案因为它必须返回该点。因此我们可以问以下基本问题我们可以解决私有区间点问题的最小输入大小是多少已知必须随着域大小||的增加而增加并且这种依赖性至少是迭代日志函数||。​另一方面最好的现有算法要求输入大小至少为||。为了弥补这一差距我们设计了一种算法该算法仅需要||的阶数。点。迭代对数函数增长极其缓慢它是在达到等于或小于的值之前需要对某个值取对数的次数。这个函数是如何在分析中自然而然出来的呢算法的每一步都会将域重新映射为其先前大小的对数。因此有||总共步骤。更严格的分析消除了所需输入大小中步数的平方根。尽管区间点任务看起来非常基础但它抓住了常见聚合任务的私有解决方案的困难本质。接下来我们描述其中两个任务并用表示这些任务所需的输入大小。私人近似中位数这些常见聚合任务之一是近似中值输入是来自有序域的个点的数据集。目标是返回的⅓和⅔分位数之间的点。即中的至少三分之一的点小于或等于且至少三分之一的点大于或等于。

请注意使用差分隐私不可能返回精确的中值因为它公开了数据点的存在。因此我们考虑近似中位数的宽松要求如下所示。我们可以通过找到间隔点来计算近似中  沙特阿拉伯手机号码列表 值我们切出个最小点和个最大点然后计算剩余点的间隔点。后者必须是近似中位数。当数据集大小至少为时此方法有效。域上的数据区间点集和近似中位数集的示例。私学轴对齐矩形对于下一个任务输入是一组个标记数据点其中每个点是域上的维向量。如下所示目标是学习定义维矩形的轴的值因此对于每个示例如果被正向标记如下图红色加号所示则它位于矩形内即对于所有轴位于区间中并且如果被标记为负数如下图蓝色减号所示那么它位于矩形之外也就是说对于至少一个轴位于区间之外。





一组二维标记点和相应的矩形。该问题的任何解决方案都必须是近似的因为必须允许学习的矩形错误标记一些数据点其中一些正标记点位于矩形外部或负标记点位于矩形内部。这是因为精确的解决方案可能对特定数据点的存在非常敏感并且不会是私有的。我们的目标是一种解决方案使错误标记点的必要数量保持在较小的范围内。我们首先考虑一维情况。我们正在寻找一个区间它覆盖所有正点且不覆盖任何负点。我们证明我们可以用最多个错误标记点来做到这一点。我们专注于积极标记的点。在第一个步骤中我们切出个最小的点并将私有区间点计算为。然后我们切出个最大的点并计算一个私有区间点。解决方案正确标记了所有负标记点最多错误标记了个正标记点。因此总共最多~个点被错误标记。