# Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 45 references that are in the map.
- First posted on arXiv 4 Mar 2021.

## Builds on (most cited first, 17 of 17)

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/1806.05358/) (2018)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [Quantile Regression Under Memory Constraint](https://mlsanity.com/paper/1810.08264/) (2018)
- [First-order Newton-type Estimator for Distributed Estimation and Inference](https://mlsanity.com/paper/1811.11368/) (2018)
- [On the Optimality of Averaging in Distributed Statistical Learning](https://mlsanity.com/paper/1407.2724/) (2014)
- [Distributed Statistical Estimation and Rates of Convergence in Normal Approximation](https://mlsanity.com/paper/1704.02658/) (2017)
- [Distributed Robust Learning](https://mlsanity.com/paper/1409.5937/) (2014)
- [Distributed Inference for Linear Support Vector Machine](https://mlsanity.com/paper/1811.11922/) (2018)
- [Distributed High-dimensional Regression Under a Quantile Loss Function](https://mlsanity.com/paper/1906.05741/) (2019)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)

## Built on by (most cited first, 11 of 11)

- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Resilient Consensus-based Multi-agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2111.06776/) (2021)
- [Byzantine-tolerant distributed learning of finite mixture models](https://mlsanity.com/paper/2407.13980/) (2024)
- [Byzantine Machine Learning: MultiKrum and an optimal notion of robustness](https://mlsanity.com/paper/2602.03899/) (2026)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Distributed Estimation and Inference for Semi-parametric Binary Response Models](https://mlsanity.com/paper/2210.08393/) (2022)
- [Distributed quasi-Newton robust estimation under differential privacy](https://mlsanity.com/paper/2408.12353/) (2024)
- [Adaptive Decentralized Federated Learning for Robust Optimization](https://mlsanity.com/paper/2512.02852/) (2025)
- [Byzantine-Robust Distributed Sparse Learning Revisited](https://mlsanity.com/paper/2605.13283/) (2026)
- [Dual-Channel Robust Group-Relative Policy Optimization via Advantage and Sequence-Weight Estimation](https://mlsanity.com/paper/2609.36944/) (2026)

## Abstract (arXiv)

This paper develops an efficient distributed inference algorithm, which is robust against a moderate fraction of Byzantine nodes, namely arbitrary and possibly adversarial machines in a distributed learning system. In robust statistics, the median-of-means (MOM) has been a popular approach to hedge against Byzantine failures due to its ease of implementation and computational efficiency. However, the MOM estimator has the shortcoming in terms of statistical efficiency. The first main contribution of the paper is to propose a variance reduced median-of-means (VRMOM) estimator, which improves the statistical efficiency over the vanilla MOM estimator and is computationally as efficient as the MOM. Based on the proposed VRMOM estimator, we develop a general distributed inference algorithm that is robust against Byzantine failures. Theoretically, our distributed algorithm achieves a fast convergence rate with only a constant number of rounds of communications. We also provide the asymptotic normality result for the purpose of statistical inference. To the best of our knowledge, this is the first normality result in the setting of Byzantine-robust distributed learning. The simulation results are also presented to illustrate the effectiveness of our method.