Communication-Efficient and Byzantine-Robust Distributed Learning with Error Feedback
This addresses the challenge of efficient and secure distributed machine learning for systems with unreliable or malicious worker nodes, representing an incremental improvement over existing methods.
The paper tackles the problem of communication-efficient distributed learning robust to Byzantine failures by proposing a gradient-descent algorithm with thresholding and compression, showing it matches the error rate of more complex methods and maintains convergence rates under compression with error feedback, validated experimentally on convex and non-convex tasks.
We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our algorithm matches that of Yin et al.~\cite{dong}, which uses more complicated schemes (coordinate-wise median, trimmed mean). Furthermore, for communication efficiency, we consider a generic class of $δ$-approximate compressors from Karimireddi et al.~\cite{errorfeed} that encompasses sign-based compressors and top-$k$ sparsification. Our algorithm uses compressed gradients and gradient norms for aggregation and Byzantine removal respectively. We establish the statistical error rate for non-convex smooth loss functions. We show that, in certain range of the compression factor $δ$, the (order-wise) rate of convergence is not affected by the compression operation. Moreover, we analyze the compressed gradient descent algorithm with error feedback (proposed in \cite{errorfeed}) in a distributed setting and in the presence of Byzantine worker machines. We show that exploiting error feedback improves the statistical error rate. Finally, we experimentally validate our results and show good performance in convergence for convex (least-square regression) and non-convex (neural network training) problems.