拜占庭代理存在下的非贝叶斯学习

### 拜占庭代理存在下的非贝叶斯学习 在分布式系统中，非贝叶斯学习是一个重要的研究领域，尤其是在存在拜占庭代理的情况下。本文将探讨如何在这样的环境中实现容错学习，介绍相关算法及其理论基础。 #### 1. 基本概念 - **累积私有信号**：设 $s_{i,1:t}$ 是代理 $i$ 到迭代 $t$ 为止获得的累积私有信号，$s_{1:t} = \{s_{1,1:t}, \cdots, s_{n,1:t}\}$ 是到时间 $t$ 的信号轮廓历史。 - **局部信念**：每个代理 $i$ 维护一个信念向量 $\mu_i \in R^m$，它是集合 $\Theta$ 上的一个分布，其中 $\mu_i(\theta)$ 是代理 $i$ 认为 $\theta$ 是真实环境状态的概率。在算法执行前，由于没有观察到任何信号，信念 $\mu_i$ 通常初始化为在集合 $\Theta$ 上均匀分布，即 $\begin{bmatrix} \mu_{i,0}(\theta_1), \cdots, \mu_{i,0}(\theta_m) \end{bmatrix}^T = \begin{bmatrix} \frac{1}{m}, \cdots, \frac{1}{m} \end{bmatrix}^T$。 - **正确性**：如果对于每个非故障代理 $i \in N$，有 $\lim_{t \to \infty} \mu_{i,t}(\theta^*) = 1$ 几乎必然成立，我们称网络代理协作学习到真实状态 $\theta^*$。 #### 2. 拜占庭共识 拜占庭共识一直是研究热点，过去的工作主要集中在标量输入，近年来更广泛的向量（或多维）输入也得到了研究。与非贝叶斯学习问题更相关的是迭代近似拜占庭共识算法，其中每个代理只能与其邻居交换关于其状态的信息。 ##### 2.1 Byz - Iter 算法 Byz - Iter 算法基于 Tverberg 定理： - **Tverberg 定理**：设 $f$ 是非负整数，$Y$ 是包含来自 $R^m$ 的向量的多重集，且 $|Y| \geq (m + 1)f + 1$。则存在 $Y$ 的一个划分 $Y_1, Y_2, \cdots, Y_{f + 1}$，使得对于 $1 \leq i \leq f + 1$，$Y_i$ 非空，并且 $Y_i$ 的凸包的交集非空，即 $\cap_{i = 1}^{f + 1} Conv(Y_i) \neq \varnothing$。 Byz - Iter 算法使用 One - Iter 作为基本操作，具体步骤如下： ```plaintext 算法 1. One - Iter 算法 输入：代理 i 的 xi 1. Zi ← Ø; 2. 在所有输出链路上传输 xi; 3. 在所有输入链路上接收消息。这些消息值形成大小为 |Ii| 的多重集 Ri; 4. 对于每个满足 |C| = (m + 1)f + 1 的 C ⊆ Ri ∪ {xi} 执行以下操作 5. 将多重集 C 的一个 Tverberg 点添加到 Zi 6. 结束 7. 按如下方式计算 yi： yi ← (1 / (1 + |Zi|)) * (xi + ∑_{z∈Zi} z); 8. 返回 yi; 算法 2. Byz - Iter 算法 代理 i 的第 t 次迭代 1. vi,t ← One - Iter(vi,t - 1); ``` ##### 2.2 Byz - Iter 算法的正确性 通过在 $v_{i,t}$ 的更新中使用 Tverberg 点，有效地去除了可能由故障代理发送的极端消息值。可以通过“简化图”来表征由此获得的有效通信网络。 - **简化图**：图 $G(V, E)$ 的简化图 $H(N, E_F)$ 通过以下方式获得： 1. 移除所有故障节点 $F$ 以及与故障节点 $F$ 相关的所有链路； 2. 对于每个非故障节点（$N$ 中的节点），最多移除 $mf$ 条额外的输入链路。 - **源组件**：任何给定简化图中的源组件是该简化图的一个强连通组件，它没有来自该组件外部的任何输入链路。 假设每个简化图 $G(V, E)$ 都有一个唯一的源组件，在这种情况下，使用 Algorithm 1，所有非故障代理渐近达成共识，即 $\lim_{t \to \infty} |v_{i,t} - v_{j,t}| = 0$，$\forall i, j \in N$。 ##### 2.3 矩阵表示 设 $|F| = \varphi$（因此，$0 \leq \varphi \leq f$），假设代理 1 到 $n - \varphi$ 是非故障的，代理 $n - \varphi + 1$ 到 $n$ 是拜占庭的。在假设每个简化图有唯一源组件的条件下，非故障代理在第 $t$ 次迭代（$t \geq 1$）的状态更新可以表示为 $v_{i,t} = \sum_{j = 1}^{n - \varphi} A_{ij}[t]v_{j,t - 1}$，其中 $A[t] \in R^{(n - \varphi) \times (n - \varphi)}$ 是一个行随机矩阵，存在一个简化图 $H[t]$ 及其邻接矩阵 $H[t]$，使得 $A[t] \geq \beta H[t]$，$0 < \beta \leq 1$ 是仅依赖于 $G(V, E)$ 的常数。 #### 3. 拜占庭容错非贝叶斯学习 我们使用一种修改后的几何平均更新规则来考虑拜占庭故障。在每次迭代中，使用累积观测 $s_{i,1:t}$ 的似然而不是仅当前观测 $s_{i,t}$ 的似然来更新局部信念。 ##### 3.1 算法步骤 对于 $t \geq 1$，代理 $i$ 在第 $t$ 次迭代中要执行的步骤如下： ```plaintext 算法 3. 拜占庭容错非贝叶斯学习：第 t 次迭代（t ≥ 1） 代理 i 1. η_{i,t} ← One - Iter(log μ_{i,t - 1}); 2. 观察 s_{i,t}; 3. 对于每个 θ ∈ Θ 执行以下操作 4. ℓ_i(s_{i,1:t}|θ) ← ℓ_i(s_{i,t}|θ) * ℓ_i(s_{i,1:t - 1}|θ); 5. μ_{i,t}(θ) ← (1 / N_{i,t}) * (ℓ_i(s_{i,1:t}|θ) * exp(η_{i,t}(θ))); 6. 结束 ``` ##### 3.2 可识别性 在没有代理故障的情况下，若图 $G(V, E)$ 是强连通的，且 $\theta^*$ 是全局可识别的，即对于任何 $\theta \neq \theta^*$，存在一个节点 $j \in V$，使得真实边缘 $\ell_j(\cdot|\theta^*)$ 和边缘 $\ell_j(\cdot|\theta)$ 之间的 Kullback - Leibler 散度 $D(\ell_j(\cdot|\theta^*) || \ell_j(\cdot|\theta))$ 不为零，则网络代理可以检测到真实假设 $\theta^*$。 在存在拜占庭代理的情况下，需要更强的全局可识别性。假设每个简化图 $G(V, E)$ 都有一个唯一的源组件，对于任何 $\theta \neq \theta^*$ 和任何简化图 $H$ 及其源组件 $S_H$，有 $\sum_{j