4.2 可乘权重算法：在线机制

我们现在将给出一种机制，用于回答在线的、可以交互选择的查询。该算法将 稀疏向量算法 和指数梯度下降算法相结合，用于在线学习线性预测器。

后一种算法也被称为 对冲（Hedge）或更普遍的可乘权重技术。其思想是：当我们将数据库 $D\in \mathbb{N}^{|\mathcal{X}|}$ 看作一个直方图，并且只对线性查询（即该直方图的线性函数）感兴趣时，我们就可以将回答线性查询的问题看作是学习线性函数 $D$ 的问题，该线性函数 $D$ 为给定一个查询 $q\in [0,1]^{|\mathcal{X}|}$，返回答案为 $⟨ D,q ⟩$。如果学习算法仅需要使用隐私保护的查询方式访问数据，那么隐私损失只会随着学习算法需要的查询数量增加而增加，而不是随我们想回答的查询数增加而增加。我们接下来介绍的 “可乘权重” 算法就是这种学习算法的一个经典例子：该算法仅进行少量查询来学习任何线性预测变量。它始终维持一个当前的 “假设预测器”，并且只通过要求查询其 “假设预测器” 与（真实）隐私数据库有很大差异的查询例子来访问数据。这个算法的保证是，只要给出少量这样的例子，它就可以一直学习目标线性函数，直到误差很小。我们怎样才能找到这些例子？

我们在上一节中看到的 稀疏向量算法 允许我们动态地执行此操作，同时只为那些在当前乘法权重假设上有高错误的示例损失隐私预算。当查询进入时，我们询问查询的真实答案是否与当前乘法权重假设的查询答案有实质性的不同。注意，这是一个由稀疏向量技术处理的阈值类查询。

• 如果答案是 “否” ，这意味着当前已知的假设预测器会产生低于阈值，那么我们可以使用公开的假设预测器响应查询，并且不再有隐私损失。

• 如果答案是 “是”，这意味着当前已知的假设预测器会产生高于阈值的错误，那么我们找到了一个合适的例子来更新我们的学习算法。

因为 “高于阈值” 的答案恰好对应于更新我们的学习算法所需的查询，所以总的隐私损失仅取决于算法的学习率，而不取决于我们答复的查询总数。