差分隐私条件下时间序列的查询敏感性

Question

我无意中发现了一篇围绕这一论点提出地方民主党的论文：

• 用户u_i在特定的时间戳上生成一个观察序列s_{i}：

s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))

• 通过增加拉普拉斯噪声，将(\varepsilon/n, 0)-DP应用于每一序列。
• 众所周知，Laplacian必须是规模为b = \frac{\Delta f}{ \text{budget}}的

作者提出了\varepsilon / n的预算，这是正确的。但是他们也定义了\Delta f，也就是查询的敏感性，简单地定义了任意时间戳\text{max}(x) - \text{min}(x)的任何值的范围。

我不相信这才是真正的敏感。据我理解，查询输出(忽略时间戳)不是单个值\mathbb{R}，而是输出\mathbb{R}^n的向量，因此根据函数f : \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathbb{R}^k的灵敏度\ell_1-sensitivity的定义：

\Delta f = \max_{x, y \in \mathbb{N}; \| x - y\|_1 = 1} \| f(x) - f(y) \|_1

如果正确地将\ell_1范数计算为\| x - y\|_1 = \sum_{i = 1}^{k} | x_i - y_i |，则灵敏度应为

(\text{max}(x) - \text{min}(x))^n

我的推理是正确的(报纸的DP可能是错的)，还是我遗漏了什么？(我不是故意泄露这篇论文的。)

更新:克拉伊夫时间序列的上下文。

每个用户的健康数据流都表示为序列s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))。 在这里，(t_d, x_d)表示流中的d-th点，其中x_d表示可穿戴健康设备在时间戳t_d上测量的值。我们进一步假设由可穿戴健康设备中的特定传感器测量的x_d在预定义的范围内[x_{min}, x_{max}]。

他们的特殊用例是收集随时间变化的心率(x) (t).

Answer 1

我想你应该解释一下这个时间序列中的x_i是什么。我建议把这份文件联系起来。我认为，如果没有一个强有力的背景，我们可能会回答错误，因为也许你可能理解错了，因为它有时发生在我身上。以下几点：

1. 查询输出可以是\mathbb{R}或\mathbb{R}^n，这取决于您定义和使用的查询类型。
2. 你说得对，我怀疑他们定义了一个全局灵敏度，因为也许计算起来更容易。但是这取决于他们在纸上定义的查询类型，是一个线性查询，一个只有一个查询还是一个非线性查询。