Page 496 - 《软件学报》2025年第7期

张朋飞 等: 基于自适应剪枝的满足本地差分隐私的真值发现算法 3417

8) 根据定理 5 进行剪枝;
9) end for
10) for (n=1 to N) do
11) 根据定理 6 进行剪枝;
12) end for

通过对算法流程的分析, 可以发现算法主要包括初始化、为任务挑选值和对工人和任务进行剪枝. 对工人和
任务分别进行初始化消耗 O(M) 和 O(N); 为每个任务挑选值并更新 X 消耗 O(N); 对每个工人和任务剪枝最多消耗
2 2 2 2
O(M ) 和 O(N ). 那么总的复杂度为 O(M + N + M + N).

4 算法分析与讨论

4.1 算法分析

在本节中, 首先进行算法分析, 包含隐私、效用和复杂度, 接着进行算法讨论.

4.1.1 隐私分析
定理 7. NATURE 算法严格满足 ε-LDP.
证明: 在 NATURE 中, 共包含 4 个阶段, 只在算法的阶段 1 接触原始数据, 假设每个工人 s 做的任务数用 |M s |
表示, 那么该工人对于每个任务 t 的隐私预算为 ε t = ε/|M s |, 根据定理 1, 该部分严格满足 ε-LDP.
在 NATURE 的后续阶段, 由于不接触原始数据, 因此不消耗隐私预算. 根据定理 3, 该部分也严格满足 ε -LDP.
根据定理 2, NATURE 对所有工人的数据严格满足 ε -LDP.

4.1.2 效用分析
首先在引理 1 中说明剪枝的必要性, 接着分析剪枝后的效果为什么更好.
引理 1. 剪枝的必要性.
证明: 只要证明剪枝后总误差更小, 便可证明剪枝的必要性.
根据文献 [6], LDP 下假设第 i 个工人的误差为 σ , 那么使用该工人数据引入的总误差为 w σ . 假设用 L 1 和
2
2
2
i
i
i
L 2 分别表示有某个工人和没有某个工人的总误差, 那么我们只需要证明 L 1 > L 2 即可.

M−1
∑
M ∑
2
2
2
L 1 − L 2 = w σ − w σ 2 (34)
ai i bi i
i=1 i=1
其中, w ai 和 w bi 分别表示第 i 个工人在有第 M 个工人数据和没有第 M 个工人数据时候的质量. 第 M 个工人的质
量很小.
M−1
∑
−1
−1 L = 2 2 L 1 ⩾ L 2 . 构造如下优化问题:
显然, 如果 L ⩾ L 2 , 其中 w σ , 那么
1 1 ai i

i=1 
M−1
 ∑

 2 2 2
 min σ (w −w )

 i ai bi

 w ai ,w bi

 i=1


 
 M

  ∑
 
 
  w ai = 1
 
 
 (35)
 i=1
 
 
 
 
 
 M−1
 ∑
s.t. 
 
 
  w bi = 1
 
 
 
 
  i=1
 
 
 
 
 w M → 0
构造拉格朗日乘数可得:

   
M−1 M M−1
∑ ∑  ∑ 

2
2
2
L = σ (w −w )+λ      w ai −1  +µ      w bi −1      (36)

ai
bi
i


i=1 i=1 i=1