  We study robust distributed learning that involves minimizing a non-convex
loss function with saddle points. We consider the Byzantine setting where some
worker machines have abnormal or even arbitrary and adversarial behavior. In
this setting, the Byzantine machines may create fake local minima near a saddle
point that is far away from any true local minimum, even when robust gradient
estimators are used. We develop ByzantinePGD, a robust first-order algorithm
that can provably escape saddle points and fake local minima, and converge to
an approximate true local minimizer with low iteration complexity. As a
by-product, we give a simpler algorithm and analysis for escaping saddle points
in the usual non-Byzantine setting. We further discuss three robust gradient
estimators that can be used in ByzantinePGD, including median, trimmed mean,
and iterative filtering. We characterize their performance in concrete
statistical settings, and argue for their near-optimality in low and high
dimensional regimes.
