  Collaborative learning algorithms, such as distributed SGD (or D-SGD), are
prone to faulty machines that may deviate from their prescribed algorithm
because of software or hardware bugs, poisoned data or malicious behaviors.
While many solutions have been proposed to enhance the robustness of D-SGD to
such machines, previous works either resort to strong assumptions (trusted
server, homogeneous data, specific noise model) or impose a gradient
computational cost that is several orders of magnitude higher than that of
D-SGD. We present MoNNA, a new algorithm that (a) is provably robust under
standard assumptions and (b) has a gradient computation overhead that is linear
in the fraction of faulty machines, which is conjectured to be tight.
Essentially, MoNNA uses Polyak's momentum of local gradients for local updates
and nearest-neighbor averaging (NNA) for global mixing, respectively. While
MoNNA is rather simple to implement, its analysis has been more challenging and
relies on two key elements that may be of independent interest. Specifically,
we introduce the mixing criterion of $(\alpha, \lambda)$-reduction to analyze
the non-linear mixing of non-faulty machines, and present a way to control the
tension between the momentum and the model drifts. We validate our theory by
experiments on image classification and make our code available at
https://github.com/LPD-EPFL/robust-collaborative-learning.
