GAAvernor

Related Works

GAR

从分布式服务器接收到各自的梯度 $V_i^t$ 之后，将不同的梯度更新方向整合到一个方向。 通常来说，参数的更新方式为： ${\theta }_{t+1}={\theta }_t-\lambda \mathcal{F}(V_1^t,\cdots ,V_n^t)$ 其中 $\lambda$ 为学习率。

Clasical GAR

$$\mathcal{F}(V_1,\cdots ,V_n)=\frac{1}{n}\sum _{i=1}^n{V}_i$$

Linear GAR

$$\mathcal{F}(V_1,\cdots ,V_n)=\sum _{i=1}^n{\alpha }^i{V}_i$$

Workers

Benign Worker

如果一个 worker 在时刻 t 的梯度 $V^t$ 是无偏的，即 $E{V}^t=g_t$ ，则称此 worker 是 Benign Worker 。

Byzantine Worker

如果一个 worker 在时刻 t 的梯度 $V^t$ 是有偏的，即 $E{V}^t-g_t\ne 0$ ，则称此 worker 是 Byzantine Worker 。

Role Function

用来决定当前 worker 是 Benign 还是 Byzantine 。 如果是 Byzantine Worker，在传送梯度到 server 时会对梯度进行篡改。

Previous Defenses

Brute-Force

找一个最优集 $C^{\text{*}}$ ，它是 $Q$ 的子集，大小为 $n-m$ ，

$$C^{\text{*}}=\arg \underset{C\in R}{\min }\underset{(V_i,V_j)\in C\times C}{\max }||V_i-V_j||$$

GAR 函数为：

$$\mathcal{F}(V_1,\cdots ,V_n)=\frac{1}{n-m}\sum _{V\in C^{\text{*}}}V$$

需要满足 Byzantine ratio： $n\ge 2m+1$

GeoMed

找与其他 worker 距离之和最小的一个 worker 的梯度作为最终梯度。

GAR 函数为：

$$\mathcal{F}(V_1,\cdots ,V_n):=\arg \underset{V_i}{\min }\sum _{j\ne i}||V_i-V_j||$$

需要满足 Byzantine ratio： $n\ge 2m+1$

Krum

首先利用 Brute-Force GAR 的方法找一个大小为 $n-m-2$ 的最优集， 然后对每个最优集中的 worker，计算： $s(V_i)={\sum }_{i\to j}||V_i-V_j|{|}^2$

GAR 函数为：

$$\mathcal{F}(V_1,\cdots ,V_n)=\arg \underset{V_i\in Q}{\min }s(V_i)$$

需要满足 Byzantine ratio： $n\ge 2m+3$

Bulyan

首先，它运行 Krum 方法得到 $n-2m$ 的梯度的选择集， 然后，它在每个方向上计算 $\mathcal{F}$ ： $\mathcal{F}$ 的第 i 个坐标等于选择集中第 i 个坐标的中值旁边 $n-4m$ 个值的平均值。

需要满足 Byzantine ratio： $n\ge 4m+3$

Security Assumptions

Server 是安全可信的。

至少有一个 worker 不被敌人控制。

各个 worker 的数据集是独立同分布的。

GAA 有权限接触到验证集。

Goals

确保分布式学习可以得到正确的梯度，将损失降到可接受的范围。

Distributed Learning as a Markov Decision Process

States $s_t:=(Q_t,{\theta }_t,{\hat{f}}_B({\theta }_t))$

${\theta }_t$ 是 Server 的参数， $Q_t$ 是接收到的梯度， ${\hat{f}}_B({\theta }_t)$ 是 Server 在验证集 $B$ 上的损失。

Actions 各个 worker 的权重

Rewards \hat{f}_{B}(\theta_t)-\hat^{f}_{B}(\theta_{t+1})

Views

Methods

Experiments

Conclusion