五、差分隐私泛化

在本章中，我们泛化了上一节的查询发布算法。结果，我们得到了任意低灵敏度查询（不仅是线性查询）的界限，还有线性查询的新界限。这些泛化也为查询发布和机器学习之间的联系提供了一些启示。

第 4 章中的 SmallDB 离线查询发布机制是我们称之为 Net 机制的一个特例。我们发现，两种机制都产生了合成数据库，这为在隐私数据库上的任何查询 $\mathcal{Q}$ 的返回值提供了一种方便的逼近方法：只评估合成数据库上的查询，并将结果作为有噪声的答案。更一般地说，一种机制可以产生任意形式的数据结构，与固定的、公共的算法（独立于数据库）一起提供一种近似查询值的方法。

Net 机制是 SmallDB 机制的一个简单泛化：首先，独立于实际数据库，定义一个数据结构的 $\alpha$-Net，其独立于真实数据库，这样使得通过发布的数据结构对 $\mathcal{Q}$ 中的任何查询进行求值，可以很好地（在加性α误差范围内）估计私有数据库上的查询值。下一步，对$\mathcal{Q}$ 中的任何查询应用指数机制对 Net 中的元素进行选择，指数机制中的效用函数将 Net 中元素的最大错误最小化。

我们还对 在线可乘权重算法 进行了泛化，以便我们可以使用任何其他在线学习算法实例化该算法，以通过一组查询来学习数据库。我们注意到，这种机制可以在线运行，也可以离线运行，在这种情况下，这些向 “在线” 机制请求的查询集合是由 “隐私区分器” 来选择的，该隐私区分器识别当前假设与实际数据库大不相同的查询。这些查询将在在线算法中生成更新步骤。事实证明，“隐私区分器”等同于不可知论学习算法，该算法为有效的查询发布机制提供了一个明确的来源。

在下面各节中，我们将讨论查询集 $\mathcal{Q}$ 类型的数据结构。

定义 5.1 一类查询 $\mathcal{Q}$ 有一些数据结构类 $\mathcal{D}$，从这些数据结构类 $\mathcal{D}$ 中提取的数据结构 $D$ 被隐式地赋予了一个分析函数 $\text{Eval:}\mathcal{D}\times\mathcal{Q} \to \mathbb{R}$，我们可以用它来分析 $D$ 上的任何查询。然而，为了避免被符号所困扰，当上下文中的含义清楚时，我们将简单地写 $f(D)$ 来表示 $\text{Eval}(D,f)$。