  Byzantine robustness has received significant attention recently given its
importance for distributed and federated learning. In spite of this, we
identify severe flaws in existing algorithms even when the data across the
participants is identically distributed. First, we show realistic examples
where current state of the art robust aggregation rules fail to converge even
in the absence of any Byzantine attackers. Secondly, we prove that even if the
aggregation rules may succeed in limiting the influence of the attackers in a
single round, the attackers can couple their attacks across time eventually
leading to divergence. To address these issues, we present two surprisingly
simple strategies: a new robust iterative clipping procedure, and incorporating
worker momentum to overcome time-coupled attacks. This is the first provably
robust method for the standard stochastic optimization setting. Our code is
open sourced at https://github.com/epfml/byzantine-robust-optimizer.
