  We propose Zeno++, a new robust asynchronous Stochastic Gradient
Descent~(SGD) procedure which tolerates Byzantine failures of the workers. In
contrast to previous work, Zeno++ removes some unrealistic restrictions on
worker-server communications, allowing for fully asynchronous updates from
anonymous workers, arbitrarily stale worker updates, and the possibility of an
unbounded number of Byzantine workers. The key idea is to estimate the descent
of the loss value after the candidate gradient is applied, where large descent
values indicate that the update results in optimization progress. We prove the
convergence of Zeno++ for non-convex problems under Byzantine failures.
Experimental results show that Zeno++ outperforms existing approaches.
