Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training 阅读笔记
Problem Statement
Decentralized System Model
所有训练数据样本存储在分布式节点里。
In this work, we are motivated by the edge IoT setting,
where users want to collaboratively train an ML model, in the
absence of a centralized parameter server.
...
In this setup, each node can send its
model update to any set of users in the network.
在无集中式参数服务器的前提下，建立一种逻辑环的顺序（即对于当前环进行一个重标号），同时该分布式系统的图结构为一个完全图结构。
Model Training
\(\mathbf {x}^{*} = \arg \min _{\mathbf {x}\in \mathbb {R}^{d} } \left [{ f(\mathbf {x}):= \frac {1}{r} \sum _{i=1}^{r} f_{i}(\mathbf {x})}\right ]\)
找到一个最小的 $\mathbf {x} $ 使得后面的式子最小。（其中 \(\mathbf {x}\) 为模型优化向量，\(f_i\) 为节点 \(i\) 的预期损失函数 \(f_i(x)=E_{ζ_i∼P_i}[l_i(x,ζ_i)]\)）
第k轮训练：
\(\mathbf {x}^{(i)}_{k}= \bar {\mathbf {x}}^{(i)}_{k}-\eta _{k}^{(i)} g_{i}(\bar {\mathbf {x}}^{(i)}_{k})\)
The Proposed Basil Algorithm
Now, we describe Basil, our proposed approach for mitigating both malicious updates and faulty updates in the IID setting, where the local dataset Z_i at node i consists of IID data samples from a distribution P_i, where P_i = P for i \in N , and characterize the complexity of Basil. Note that, in Section IV, we extend Basil to the non-IID setting by
integrating it to our proposed Anonymous Cyclic Data Sharing scheme.
Basil algorithm
目的：减轻拜占庭节点的恶意更新和错误更新。
算法流程：
step1:
首先所有用户共享 id，默认按照升序排列。
通过一个公共的随机数种子，随出一个环的顺序（这里默认按照 \(1-N\) 升序连接），即形成一个逻辑环。
注1：由于是伪随机数，所以每个人的标号都是默认的。
注2：由于随机的性质，所以可以默认拜占庭节点是在环上随机分布的。
注3：实际上，这个操作仅仅是用于随机打乱一下初始排列情况，防止拜占庭节点连续分布。
step2:
当前节点进行本地模型更新后，将模型顺时针发送到接下来 \(S= b + 1\) 个节点。通过抽屉原理的操作可以使得每个良性节点至少会接收到一个良性节点的模型。
\(A_{basil}\) 模型聚合规则
\(\bar {\mathbf {x}}_{k}^{(i)} = \mathcal {A}_{\texttt {Basil} } ( \mathcal {N}^{i}_{k}) = \arg \min _{ \mathbf {y} \in \mathcal {N}^{i}_{k} } \mathbb {E} \left [{{l}_{i}({\mathbf {y}}, \zeta _{i})}\right ]\)
其中 \(\mathcal {N}^{i}_{k} = \{\mathbf{y_1},…,\mathbf{y_S}\}\)
通过该规则，在 接收到的 \(S\) 个模型中选取最好的一个。
拓展 \(S = b + 1\)
当将 \(S\) 放宽到 \(S < b + 1\) 时，Basil 失败的概率为：
\(\mathbb {P}( {Failure}) \leq \frac {b! (N-S)! }{(b-S)! (N-1)!}\)
Theoretical Guarantees
IID 数据集
有界方差
平滑度
损失函数是两次可微的
When the learning rate \(η^{(i)}_k\) for node \(i∈R\) in round k satisfies \(η^{(i)}_k\le \frac{1}{L}\) , the expected loss function \(E[l_i(⋅)]\) of node \(i\) evaluated on the set of models in \(\mathcal{N}^i_k\) can be arranged as follows:
\(\mathbb {E} \left [{ l_{i} (\mathbf {y}_{1}) }\right ] \leq \mathbb {E} \left [{ l_{i} (\mathbf {y}_{2}) }\right ] \leq {\dots } \leq \mathbb {E} \left [{ l_{i} (\mathbf {y}_{r^{i}}) }\right ] < \mathbb {E} \left [{ l_{i} (\mathbf {x}) }\right ], \forall \mathbf {x} \in \mathcal {B}_{k}^{i}\)
注：其中 \(\mathcal{G^{i}_{k}}=\left{\mathbf {y}_{1},…,\mathbf {y}_{r^{i}}\right}\) 为按照距离由近到远的良性节点发送模型
where \(\mathcal{G^i_k}=\{\mathbf{y}_1,…,\mathbf{y_{r_i}}\}\) is the set of benign models stored at node i . Hence, the Basil aggregation rule in Definition 1 is reduced to \(\bar{\mathbf{x}}^{(i)}_k=\mathcal{A_{Basil}(N^i_k)}=\mathbf{y_1}\) . Hence, the model update step in (2) can be simplified as follows:
\(\mathbf {x}_{k}^{(i)} = \mathbf {y}_{1} - \eta _{k}^{(i)} g_{i}(\mathbf {y}_{1})\)
注：此处可大致理解为更近的节点一定可以学习到了更多的模型，所以更近的节点学习效果一定更好。
证明了在 \(S = 1\) 是仍可线性收敛
Generalizing Basil To Non-IID Setting VIA Anonymous Cyclic Data Sharing
ACDS algorithm
ACDS保证共享数据所有者的身份在节点之间不勾结的情况下对所有其他节点保持隐藏。
step1:
分组，并在组内将数据集分成敏感和非敏感，每个点从非敏感数据集中选出 \(\alpha D\) 个数据点，并分为 \(H\) 批。
step2：
每次每个节点仅将自己的上一次共享的数据替换掉。
除自己本身外，剩下节点数据均为新增或更新，为有效匿名。
最坏情况下每个节点通信代价：
\(C_{\ {ACDS}} = \alpha D I \left({\frac {1}{H} +n (G+1)}\right)\)
其中 \(I\) 为每个数据点大小，\(n\) 为每组点数
注：\(1_g\) 为最坏情况节点
完成 ACDS 的总时长：
\(T_{ {ACDS}} = \frac {\alpha D I}{HR} \left [{n^{2} (H+0.5) + n \left ({H (G-1) - 1.5}\right ) }\right ]\)
其中 \(R\) 为上传和下载速度
Basil +: Parallelization of Basil
Basil + algorithm
step1
分组，设定 \(S = min(n-1,b + 1)\)
step2:
组内进行 \(\tau\) 轮
step3:
组间聚合
\(\mathbf {z}_{i}^{g+1}= \frac {1}{g+1} \left ({ \mathbf {x}^{(i,g+1)}_{\tau }+ g \bar {\mathbf {z}}_{i}^{g+1}}\right )\)
\(\mathcal {L}_{g} = \{ \mathbf {z}_{n-1}^{g}, \mathbf {z}_{n-2}^{g}, {\dots }, \mathbf {z}_{n-S+1}^{g} \}\)
\(\bar {\mathbf {z}}_{i}^{g+1} = \mathcal {A}_{\texttt {Basil} } ( \mathcal {L}_{g}) = \arg \min _{ \mathbf {y} \in \mathcal {L}_{g} } \mathbb {E} \left [{{l}^{g+1}_{i}({\mathbf {y}}, \zeta ^{g+1}_{i})}\right ]\)
step4：
将模型传回到 \(S_1\) 然后再按照规则聚合一次。
重复上述 \(K\) 轮
Basil + 可证明仍然是线性的
当 \(S = min(n-1,b+1)\) 时：
\(\mathbb {P}(\text {Failure}) {=}\mathbb {P}( \bigcup _{j=1}^{G}B_{j}) \overset{(a)}{\leq} \sum _{j=1}^{G}\mathbb {P}(B_{j}) {=} \frac {\binom {b}{n} + \binom {b}{n-1} \binom {N-b}{1}}{\binom {N}{n}} G\!\! \\ {}\)
当 \(S < n - 1\) 时：
\(\mathbb {P}(F) \leq G \sum _{i = 0}^{\min { (b,n)}} \left ({ \prod _{s=0 }^{S-1} \frac { \max \left ({i-s, 0 }\right )}{(N-s) } n }\right ) \frac {\binom {b}{i}\binom {N-b}{n-i}}{\binom {N}{n}}\)
实验
占坑，待补。
Conclusion
一个有趣的未来方向是探索一些技术，如数据压缩或数据放置和编码洗牌，以减少使用ACDS产生的通信成本。此外，在研究添加的噪声对整体训练性能的影响的同时，如何通过在ACDS中的共享数据中增加噪声，以进一步提供隐私是很有趣的。
个人感觉
这个保护隐私的做法很有意思。
这个Basil+ 基于Basil的推广感觉很nice。
标签：Training,Decentralized,mathbf,Byzantine,right,Basil,mathcal,节点,left From： https://www.cnblogs.com/wtz2333/p/16834121.html