On the Optimal Batch Size for Byzantine-Robust Distributed Learning
Yi-Rui Yang Chang-Wei Shi Wu-Jun Li
Byzantine-robust distributed learning (BRDL), in which computing devices are
likely to behave abnormally due to accidental failures or malicious attacks,
has recently become a hot research topic. However, even in the independent and
identically distributed (i.i.d.) case, existing BRDL methods will suffer from a
significant drop on model accuracy due to the large variance of stochastic
gradients. Increasing batch sizes is a simple yet effective way to reduce the
variance. However, when the total number of gradient computation is fixed, a
too-large batch size will lead to a too-small iteration number (update number),
which may also degrade the model accuracy. In view of this challenge, we mainly
study the optimal batch size when the total number of gradient computation is
fixed in this work. In particular, we theoretically and empirically show that
when the total number of gradient computation is fixed, the optimal batch size
in BRDL increases with the fraction of Byzantine workers. Therefore, compared
to the case without attacks, the batch size should be set larger when under
Byzantine attacks. However, for existing BRDL methods, large batch sizes will
lead to a drop on model accuracy, even if there is no Byzantine attack. To deal
with this problem, we propose a novel BRDL method, called Byzantine-robust
stochastic gradient descent with normalized momentum (ByzSGDnm), which can
alleviate the drop on model accuracy in large-batch cases. Moreover, we
theoretically prove the convergence of ByzSGDnm for general non-convex cases
under Byzantine attacks. Empirical results show that ByzSGDnm has a comparable
performance to existing BRDL methods under bit-flipping failure, but can
outperform existing BRDL methods under deliberately crafted attacks.