# On the Optimal Batch Size for Byzantine-Robust Distributed Learning

arXiv: https://arxiv.org/abs/2305.13856 · HTML: https://mlsanity.com/paper/2305.13856/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 50 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [Byzantine-Resilient Non-Convex Stochastic Gradient Descent](https://mlsanity.com/paper/2012.14368/) (2020)
- [DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation](https://mlsanity.com/paper/1907.12205/) (2019)
- [Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/1806.05358/) (2018)
- [Communication-Efficient Distributed Dual Coordinate Ascent](https://mlsanity.com/paper/1409.1458/) (2014)
- [Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks](https://mlsanity.com/paper/1910.06093/) (2019)
- [Adding vs. Averaging in Distributed Primal-Dual Optimization](https://mlsanity.com/paper/1502.03508/) (2015)
- [Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters](https://mlsanity.com/paper/1704.03540/) (2017)

## Abstract (arXiv)

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.