TY - CONF AB - This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity. AU - Alistarh, Dan-Adrian AU - Allen-Zhu, Zeyuan AU - Li, Jerry ID - 6558 T2 - Advances in Neural Information Processing Systems TI - Byzantine stochastic gradient descent VL - 2018 ER -