Byzantine-robustness has been gaining a lot of attention due to the growth of the interest in collaborative and federated learning. However, many fruitful directions, such as the usage of variance reduction for achieving robustness and communication compression for reducing communication costs, remain weakly explored in the field. This work addresses this gap and proposes Byz-VR-MARINA - a new Byzantine-tolerant method with variance reduction and compression. A key message of our paper is that variance reduction is key to fighting Byzantine workers more effectively. At the same time, communication compression is a bonus that makes the process more communication efficient. We derive theoretical convergence guarantees for Byz-VR-MARINA outperforming previous state-of-the-art for general non-convex and Polyak-Lojasiewicz loss functions. Unlike the concurrent Byzantine-robust methods with variance reduction and/or compression, our complexity results are tight and do not rely on restrictive assumptions such as boundedness of the gradients or limited compression. Moreover, we provide the first analysis of a Byzantine-tolerant method supporting non-uniform sampling of stochastic gradients. Numerical experiments corroborate our theoretical findings.

本研究提出了一种名为 Byx-VR-MARINA 的新的拜占庭容错方法，其中方差降低是更有效地对抗拜占庭工人的关键，而通信压缩是使过程更具通信效率的奖励。这项工作还对非凸和 Polyak-Lojasiewicz 损失函数的拜占庭容忍方法进行了理论上的收敛保证。

方差降低是拜占庭问题的解药：更好的收敛速率，较弱的假设条件，以及通信压缩作为锦上添花