# Robust Training in High Dimensions via Block Coordinate Geometric Median Descent

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 121 references that are in the map.
- First posted on arXiv 16 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (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)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Data Poisoning Attacks Against Federated Learning Systems](https://mlsanity.com/paper/2007.08432/) (2020)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Backdoor Embedding in Convolutional Neural Network Models via Invisible Perturbation](https://mlsanity.com/paper/1808.10307/) (2018)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)

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

- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Byzantine-Robust Learning on Heterogeneous Data via Gradient Splitting](https://mlsanity.com/paper/2302.06079/) (2023)
- [Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates](https://mlsanity.com/paper/2402.12780/) (2024)
- [Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning](https://mlsanity.com/paper/2209.07716/) (2022)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training](https://mlsanity.com/paper/2405.14759/) (2024)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML](https://mlsanity.com/paper/2501.09621/) (2025)
- [RoPoLL: Robust Panel of LLM Judges](https://mlsanity.com/paper/2606.30931/) (2026)
- [Geometric Median (GM) Matching for Robust Data Pruning](https://mlsanity.com/paper/2406.17188/) (2024)
- [Submodular Maximization Approaches for Equitable Client Selection in Federated Learning](https://mlsanity.com/paper/2408.13683/) (2024)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [Geometric Median Matching for Robust k-Subset Selection from Noisy Data](https://mlsanity.com/paper/2504.00564/) (2025)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)
- [Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensing](https://mlsanity.com/paper/2309.14512/) (2023)
- [Tracking the Median of Gradients with a Stochastic Proximal Point Method](https://mlsanity.com/paper/2402.12828/) (2024)

## Abstract (arXiv)

Geometric median (textscGm) is a classical method in statistics for achieving a robust estimation of the uncorrupted data; under gross corruption, it achieves the optimal breakdown point of 0.5. However, its computational complexity makes it infeasible for robustifying stochastic gradient descent (SGD) for high-dimensional optimization problems. In this paper, we show that by applying textscGm to only a judiciously chosen block of coordinates at a time and using a memory mechanism, one can retain the breakdown point of 0.5 for smooth non-convex problems, with non-asymptotic convergence rates comparable to the SGD with textscGm.