# 基于DP的FL算法

• 接受来自Server的初始参数$\mathbf{w}_s$

• 通过前向传播和反向传播计算出梯度 $\mathbf{g}$

其中计算的过程应该为，首先计算出$\mathcal{D}$中每条数据$\mathcal{D_i}$的梯度$\mathbf{g_i}$，进行梯度裁剪：

$\mathbf{g_i} = \frac{\mathbf{g_i}}{max(1, |\mathbf{g_i}| / C)}$

然后再求平均值，把这个过程写成公式就应该是：$\mathbf{g} = \frac{1}{|\mathcal{D}|} \sum \mathbf{g_i} = \frac{1}{|\mathcal{D}|} \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i}, \mathbf{w_s})$

• 进行梯度下降：$\mathbf{w_c} = \mathbf{w_s} - \eta \mathbf{g}$

• 对参数添加噪音：$\widetilde{\mathbf{w_c}} = \mathbf{w_c} + Lap(\Delta f / \epsilon)$

# 算法详解

## 敏感度$\Delta f$的计算

$\Delta f = max_{\mathcal{D}, \mathcal{D'}} | \mathbf{w_c} - \mathbf{w_c'} | = max_{\mathcal{D}, \mathcal{D'}}| (\mathbf{w_s} - \eta \mathbf{g}) - (\mathbf{w_s} - \eta \mathbf{g'}) | = max_{\mathcal{D}, \mathcal{D'}} \eta | \mathbf{g} - \mathbf{g'} |$

(注意这里是一范数，因为是Laplace机制。)

$| \mathbf{g} - \mathbf{g'} | = \frac{1}{|\mathcal{D}|} | (\sum \mathbf{g_i} - \sum\mathbf{g_i'}) | = \frac{1}{|\mathcal{D}|} | \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i}, \mathbf{w_s}) - \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i'}, \mathbf{w_s}) |$

$| \mathbf{g} - \mathbf{g'} | = \frac{1}{|\mathcal{D}|} | arg \ min_{\mathbf{w_s}} l(\mathcal{D_k}, \mathbf{w_s}) - arg \ min_{\mathbf{w_s}} l(\mathcal{D_k'}, \mathbf{w_s})| = \frac{1}{|\mathcal{D}|} | (\mathbf{g_k} - \mathbf{g_k'}) |$

$| \mathbf{g} - \mathbf{g'} |<= \frac{| \mathbf{g_k} | + | \mathbf{g_k'} | }{|\mathcal{D}|}<= \frac{2C}{|\mathcal{D}|}$

$\Delta f = \eta \frac{2C}{\mathcal{D}}$

# 参考文献

[1]Wei, Kang, et al. “Federated learning with differential privacy: Algorithms and performance analysis.” IEEE Transactions on Information Forensics and Security 15 (2020): 3454-3469.

[2]Wu, Nan, et al. “The value of collaboration in convex machine learning with differential privacy.” 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 2020.

[3]Abadi, Martin, et al. “Deep learning with differential privacy.” Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.

[4]Lee, Jaewoo, and Daniel Kifer. “Concentrated differentially private gradient descent with adaptive per-iteration privacy budget.” Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018.

[6]Truex, Stacey, et al. “LDP-Fed: Federated learning with local differential privacy.” Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking. 2020.