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\neq 0$ ，则称此 worker 是 Byzantine Worker 。
Role Function
用来决定当前 worker 是 Benign 还是 Byzantine 。 如果是 Byzantine Worker，在传送梯度到 server 时会对梯度进行篡改。
Previous Defenses
Brute-Force
找一个最优集 $C^{*}$ ，它是 $Q$ 的子集，大小为 $n-m$ ， $$ C^{*}=\arg\min_{C\in R}\max_{(V_i,V_j)\in C\times C}||V_i-V_j|| $$
GAR 函数为： $$ \mathcal{F}(V_1,\cdots,V_n)=\frac{1}{n-m}\sum_{V\in C^{*}}V $$
需要满足 Byzantine ratio： $n\geq{2m+1}$
GeoMed
找与其他 worker 距离之和最小的一个 worker 的梯度作为最终梯度。
GAR 函数为： $$ \mathcal{F}(V_1,\cdots,V_n):=\arg\min_{V_i}\sum_{j\neq i}||V_i-V_j|| $$
需要满足 Byzantine ratio： $n\geq{2m+1}$
Krum
首先利用 Brute-Force GAR 的方法找一个大小为 $n-m-2$ 的最优集， 然后对每个最优集中的 worker，计算： $s(V_i)=\sum_{i\rightarrow j}||V_i-V_j||^2$
GAR 函数为： $$ \mathcal{F}(V_1,\cdots,V_n)=\arg\min_{V_i\in Q}s(V_i) $$
需要满足 Byzantine ratio： $n\geq{2m+3}$
Bulyan
首先，它运行 Krum 方法得到 $n-2m$ 的梯度的选择集， 然后，它在每个方向上计算 $\mathcal{F}$ ： $\mathcal{F}$ 的第 i 个坐标等于选择集中第 i 个坐标的中值旁边 $n-4m$ 个值的平均值。
需要满足 Byzantine ratio： $n\geq{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$ 上的损失。