Byzantine robustness is an essential feature of algorithms for certain
distributed optimization problems, typically encountered in
collaborative/federated learning. These problems are usually huge-scale,
implying that communication compression is also imperative for their
resolution. These factors have spurred recent algorithmic and theoretical
developments in the literature of Byzantine-robust learning with compression.
In this paper, we contribute to this research area in two main directions.
First, we propose a new Byzantine-robust method with compression --
Byz-DASHA-PAGE -- and prove that the new method has better convergence rate
(for non-convex and Polyak-Lojasiewicz smooth optimization problems), smaller
neighborhood size in the heterogeneous case, and tolerates more Byzantine
workers under over-parametrization than the previous method with SOTA
theoretical convergence guarantees (Byz-VR-MARINA). Secondly, we develop the
first Byzantine-robust method with communication compression and error feedback
-- Byz-EF21 -- along with its bidirectional compression version -- Byz-EF21-BC
-- and derive the convergence rates for these methods for non-convex and
Polyak-Lojasiewicz smooth case. We test the proposed methods and illustrate our
theoretical findings in the numerical experiments.

通过压缩和收敛速率，提出了两种新的拜占庭容错化方法，并证明了它们在非凸和 Polyak-Lojasiewicz 平滑优化问题中具有更好的收敛速率、异构情况下更小的邻域大小以及在过参数化时更能容忍拜占庭节点；同时还开发了带有压缩和误差反馈的第一种拜占庭容错化方法，并推导了这些方法在非凸和 Polyak-Lojasiewicz 平滑情况下的收敛速率，并通过数值实验证明了理论发现。