  In large-scale distributed learning, security issues have become increasingly
important. Particularly in a decentralized environment, some computing units
may behave abnormally, or even exhibit Byzantine failures -- arbitrary and
potentially adversarial behavior. In this paper, we develop distributed
learning algorithms that are provably robust against such failures, with a
focus on achieving optimal statistical performance. A main result of this work
is a sharp analysis of two robust distributed gradient descent algorithms based
on median and trimmed mean operations, respectively. We prove statistical error
rates for three kinds of population loss functions: strongly convex,
non-strongly convex, and smooth non-convex. In particular, these algorithms are
shown to achieve order-optimal statistical error rates for strongly convex
losses. To achieve better communication efficiency, we further propose a
median-based distributed algorithm that is provably robust, and uses only one
communication round. For strongly convex quadratic loss, we show that this
algorithm achieves the same optimal error rate as the robust distributed
gradient descent algorithms.
