Timezone: »

 
Poster
Byzantine Stochastic Gradient Descent
Dan Alistarh · Zeyuan Allen-Zhu · Jerry Li

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #164
in Thu Poster Session A »
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 $\alpha$-fraction are Byzantine, and may behave 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{\alpha^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 sample complexity and time complexity.
Keywords: Learning Theory · Online Learning
[ Paper] 

Author Information

Dan Alistarh (IST Austria)
Zeyuan Allen-Zhu (Microsoft Research)
Jerry Li (Berkeley)

More from the Same Authors