Byzantine Stochastic Gradient Descent
This addresses the challenge of robust distributed learning for systems vulnerable to adversarial failures, offering a theoretically optimal solution.
The paper tackles the problem of distributed stochastic optimization in the presence of Byzantine adversarial machines, proposing a variant of stochastic gradient descent that finds ε-approximate minimizers in T = Õ(1/(ε²m) + α²/ε²) iterations, with a lower bound showing optimality up to logarithmic factors.
This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the $m$ machines which allegedly compute stochastic gradients every iteration, an $α$-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds $\varepsilon$-approximate minimizers of convex functions in $T = \tilde{O}\big( \frac{1}{\varepsilon^2 m} + \frac{α^2}{\varepsilon^2} \big)$ iterations. In contrast, traditional mini-batch SGD needs $T = O\big( \frac{1}{\varepsilon^2 m} \big)$ 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 sampling complexity and time complexity.