3.6.3 数值稀疏算法
最后,我们给出了 Sparse 算法的一个版本,它实际上输出了高于阈值查询的数值,我们只需要在精度上损失一个常数因子就可以做到这一点。我们称这种算法为 NumericSparse ,它是一种简单的使用 Laplace 机制组成的 Sparse 算法。它不是输出向量 a ∈ { ⊤ , ⊥ } ∗ a \in \{\top,\bot\}^* a ∈ { ⊤ , ⊥ } ∗ ,而是输出向量 a ∈ ( R ∪ { ⊥ } ) ∗ a \in (\mathbb{R} \cup \{\bot\})^* a ∈ ( R ∪ { ⊥ } ) ∗ 。
我们发现 NumericSparse 算法是具有隐私性的:
定理 3.27 NumericSparse 算法是( ε , δ ) (\varepsilon,\delta) ( ε , δ ) - 差分隐私的。
【证明】 我们发现,如果δ = 0 \delta=0 δ = 0 ,则NumericSparse 算法 ( D , { f i } , T , c , ε , 0 ) (D,\{f_i\},T,c,\varepsilon,0) ( D , { f i } , T , c , ε , 0 ) 就是 Sparse 算法 ( D , { f i } , T , c , 8 9 ε , 0 ) (D,\{f_i\},T,c,\frac{8}{9}\varepsilon,0) ( D , { f i } , T , c , 9 8 ε , 0 ) 的自适应组合,其中输出具体数值使用了具有隐私参数 ( ε ′ , δ ) = ( 1 9 ε , 0 ) (\varepsilon',\delta)=(\frac{1}{9}\varepsilon,0) ( ε ′ , δ ) = ( 9 1 ε , 0 ) 的 Lapalace 机制。如果 δ > 0 \delta>0 δ > 0 ,则 NumericSparse 算法 ( D , { f i } , T , c , ε , δ ) (D,\{f_i\},T,c,\varepsilon,\delta) ( D , { f i } , T , c , ε , δ ) 是 Sparse 算法 ( D , { f i } , T , c , 5 1 2 5 1 2 + 1 ε , δ / 2 ) (D,\{f_i\},T,c,\frac{\sqrt{512}}{\sqrt{512}+1}\varepsilon,\delta/2) ( D , { f i } , T , c , 5 1 2 + 1 5 1 2 ε , δ / 2 ) 的自适应组合, 其中输出具体数值使用了具有隐私参数 ( ε ′ , δ ) = ( 1 5 1 2 ε , δ / 2 ) (\varepsilon',\delta)=(\frac{1}{\sqrt{512}}\varepsilon,\delta/2) ( ε ′ , δ ) = ( 5 1 2 1 ε , δ / 2 ) 的 Lapalace 机制。
因此,NumericSparse 算法的隐私来自简单的组合。
【定理 3.27 证毕】
要讨论准确性,我们必须定义一种机制的准确性,这是指响应一系列数值查询而输出流 a ∈ ( R ∪ { ⊥ } ) ∗ a \in (\mathbb{R} \cup \{\bot\})^* a ∈ ( R ∪ { ⊥ } ) ∗ 的含义:
定义3.10(数值精度) 一个响应 k k k 个查询流 f 1 , . . . , f k f_1,...,f_k f 1 , . . . , f k 并输出应答流 a 1 , . . . , ∈ ( R ∪ { ⊥ } ) ∗ a_1,...,\in(\mathbb{R} \cup \{\bot\})^* a 1 , . . . , ∈ ( R ∪ { ⊥ } ) ∗ 的算法,如果除概率最大为 β \beta β 之外,算法不会在 f k f_k f k 之前停止,并且对于所有 a i ∈ R a_i \in \mathbb{R} a i ∈ R 有:
∣ f i ( D ) − a i ∣ ≤ α
|f_i(D)-a_i|\leq \alpha
∣ f i ( D ) − a i ∣ ≤ α
对于所有 a i = ⊥ a_i =\bot a i = ⊥ ,有:
f i ( D ) ≤ T + α
f_i(D) \leq T + \alpha
f i ( D ) ≤ T + α
则这个算法是相对于阈值 T T T 的 ( α , β ) (\alpha,\beta) ( α , β ) 准确。
定理 3.28 。 对于 k k k 个查询的任何序列 f 1 , . . . f k f_1,...f_k f 1 , . . . f k 使得 L ( T ) ≡ ∣ { i : f i ( D ) ≥ T − α } ∣ ≤ c L(T)\equiv|\{i:f_i(D)\geq T-\alpha\}|\leq c L ( T ) ≡ ∣ { i : f i ( D ) ≥ T − α } ∣ ≤ c ,如果 δ > 0 \delta>0 δ > 0 ,当:
α = ( ln k + ln 4 c β ) c ln 2 δ ( 5 1 2 + 1 ) ε
\alpha = \frac{(\ln k+\ln \frac{4c}{\beta})\sqrt{c\ln \frac{2}{\delta}}(\sqrt{512}+1)}{\varepsilon}
α = ε ( ln k + ln β 4 c ) c ln δ 2 ( 5 1 2 + 1 )
NumericSparse 算法是相对于阈值 T T T 的 ( α , β ) (\alpha,\beta) ( α , β ) 准确的。
如果 δ = 0 \delta=0 δ = 0 ,当:
α = 9 c ( ln k + ln ( 4 c / β ) ) ε
\alpha = \frac{9c(\ln k + \ln(4c/\beta))}{\varepsilon}
α = ε 9 c ( ln k + ln ( 4 c / β ) )
NumericSparse 算法是相对于阈值 T T T 的 ( α , β ) (\alpha,\beta) ( α , β ) 准确的。
【证明】 精度需要两个条件:首先,对于所有 a i = ⊥ : f i ( D ) ≤ T a_i =\bot:f_i(D)\leq T a i = ⊥ : f i ( D ) ≤ T : Sparse 准确定理以 1 − β / 2 1-\beta/2 1 − β / 2 概率成立。另外,对于所有 a i ∈ R a_i\in \mathbb{R} a i ∈ R ,它要求 ∣ f i ( D ) − a i ∣ ≤ α |f_i(D)-a_i|\leq \alpha ∣ f i ( D ) − a i ∣ ≤ α 。 这通过 Laplace 机制的精度以 1 − β / 2 1-\beta/2 1 − β / 2 概率成立。
【定理 3.28证毕】
我们到底显示了什么?如果给我们一系列查询,并保证只有最多 c c c 个答案的答案高于 T + α T+\alpha T + α ,我们就可以回答高于给定阈值 T T T 的那些查询,直至误差 α \alpha α 。如果我们事先知道进行这些高于阈值查询的身份,并使用拉普拉斯机制进行回答,那么在给定相同的隐私保证的情况下,此精度等于(等于常数和log k \log k log k )。也就是说,稀疏向量技术允许我们几乎“免费”地辨别这些大型查询的身份,只为这些不相关的查询进行对数精度的响应。这种算法与另一种形式(通过指数机制找到造成隐私损失大的查询,然后通过拉普拉斯机制响应这些查询)提供相同的保证。然而,这个稀疏向量算法运行起来很简单,而且最关键的是,它允许我们自适应地选择查询。