Recently, there is a growing interest in the study of median-based algorithms
for distributed non-convex optimization. Two prominent such algorithms include
signSGD with majority vote, an effective approach for communication reduction
via 1-bit compression on the local gradients, and medianSGD, an algorithm
recently proposed to ensure robustness against Byzantine workers. The
convergence analyses for these algorithms critically rely on the assumption
that all the distributed data are drawn iid from the same distribution.
However, in applications such as Federated Learning, the data across different
nodes or machines can be inherently heterogeneous, which violates such an iid
assumption. This work analyzes signSGD and medianSGD in distributed settings
with heterogeneous data. We show that these algorithms are non-convergent
whenever there is some disparity between the expected median and mean over the
local gradients. To overcome this gap, we provide a novel gradient correction
mechanism that perturbs the local gradients with noise, together with a series
results that provable close the gap between mean and median of the gradients.
The proposed methods largely preserve nice properties of these methods, such as
the low per-iteration communication complexity of signSGD, and further enjoy
global convergence to stationary solutions. Our perturbation technique can be
of independent interest when one wishes to estimate mean through a median
estimator.

本文研究介绍了两种分布式非凸优化算法：signSGD 和 medianSGD，并发现它们在数据异构的情况下是不收敛的。作者提出了一种梯度校正机制来消除梯度的平均值和中位数之间的差异，该方法保留了这些方法的良好性质，并实现了全局收敛。此外，该文中所提的梯度校正技术在其他估计平均值的场合也有独立的应用价值。

异构数据的分布式训练：连接中位数和基于平均值的算法

Distributed Training with Heterogeneous Data: Bridging Median- and  Mean-Based Algorithms

In this paper, we propose a class of robust stochastic subgradient methods
for distributed learning from heterogeneous datasets at presence of an unknown
number of Byzantine workers. The Byzantine workers, during the learning
process, may send arbitrary incorrect messages to the master due to data
corruptions, communication failures or malicious attacks, and consequently bias
the learned model. The key to the proposed methods is a regularization term
incorporated with the objective function so as to robustify the learning task
and mitigate the negative effects of Byzantine attacks. The resultant
subgradient-based algorithms are termed Byzantine-Robust Stochastic Aggregation
methods, justifying our acronym RSA used henceforth. In contrast to most of the
existing algorithms, RSA does not rely on the assumption that the data are
independent and identically distributed (i.i.d.) on the workers, and hence fits
for a wider class of applications. Theoretically, we show that: i) RSA
converges to a near-optimal solution with the learning error dependent on the
number of Byzantine workers; ii) the convergence rate of RSA under Byzantine
attacks is the same as that of the stochastic gradient descent method, which is
free of Byzantine attacks. Numerically, experiments on real dataset corroborate
the competitive performance of RSA and a complexity reduction compared to the
state-of-the-art alternatives.

本文提出了一种适用于异构数据集的分布式学习的鲁棒性随机次梯度方法 ——Byzantine-Robust Stochastic Aggregation (RSA) 方法，用来应对 Byzantine 工人的攻击。RSA 方法不依赖于数据是独立同分布的假设，具有更广泛的适用性。理论上，RSA 收敛到一个接近最优解的解决方案，学习错误取决于 Byzantine 工作人员数目，收敛速率与没有 Byzantine 工人的随机梯度下降方法相同。数值实验表明，RSA 具有竞争性的性能和与现有算法相比较的复杂度降低。

RSA: 分布式异构数据学习的拜占庭容错随机聚合方法

RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed  Learning from Heterogeneous Datasets

Asynchronous distributed machine learning solutions have proven very
effective so far, but always assuming perfectly functioning workers. In
practice, some of the workers can however exhibit Byzantine behavior, caused by
hardware failures, software bugs, corrupt data, or even malicious attacks. We
introduce \emph{Kardam}, the first distributed asynchronous stochastic gradient
descent (SGD) algorithm that copes with Byzantine workers. Kardam consists of
two complementary components: a filtering and a dampening component. The first
is scalar-based and ensures resilience against $\frac{1}{3}$ Byzantine workers.
Essentially, this filter leverages the Lipschitzness of cost functions and acts
as a self-stabilizer against Byzantine workers that would attempt to corrupt
the progress of SGD. The dampening component bounds the convergence rate by
adjusting to stale information through a generic gradient weighting scheme. We
prove that Kardam guarantees almost sure convergence in the presence of
asynchrony and Byzantine behavior, and we derive its convergence rate. We
evaluate Kardam on the CIFAR-100 and EMNIST datasets and measure its overhead
with respect to non Byzantine-resilient solutions. We empirically show that
Kardam does not introduce additional noise to the learning procedure but does
induce a slowdown (the cost of Byzantine resilience) that we both theoretically
and empirically show to be less than $f/n$, where $f$ is the number of
Byzantine failures tolerated and $n$ the total number of workers.
Interestingly, we also empirically observe that the dampening component is
interesting in its own right for it enables to build an SGD algorithm that
outperforms alternative staleness-aware asynchronous competitors in
environments with honest workers.

本文介绍了一种分布式异步随机梯度下降算法，名为 Kardam，可以应对存在拜占庭工人的情况，并且具有自我稳定的过滤组件和调整梯度组件。实证结果表明，Kardam 具备对抗拜占庭行为的鲁棒性和收敛到全局最优解的能力，同时在处理干净工人的情况下也表现得更优秀。