mlsanityData to 7 Oct 2026

Robust Training in High Dimensions via Block Coordinate Geometric Median Descent

arXiv 2106.08882 ↗First posted 16 Jun 2021cs.LG cs.DC math.OCcited by 20

Not on the map. Why?

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.

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

Builds on

51 of 121 references.

References · 51

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  4. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  5. 2019Benchmarking Neural Network Robustness to Common Corruptions and Perturbationscited by 2,857
  6. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  7. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  8. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  9. 2017Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoningcited by 1,012
  10. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  11. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  12. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
38 more
  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  2. 2018Spectral Signatures in Backdoor Attackscited by 457
  3. 2018Sparsified SGD with Memorycited by 373
  4. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
  5. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 324
  6. 2019Robust Aggregation for Federated Learningcited by 314
  7. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  8. 2020Data Poisoning Attacks Against Federated Learning Systemscited by 266
  9. 2018The Convergence of Sparsified Gradient Methodscited by 228
  10. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  11. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  12. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  13. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  14. 2018Backdoor Embedding in Convolutional Neural Network Models via Invisible Perturbationcited by 131
  15. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  16. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  17. 2018Byzantine Stochastic Gradient Descentcited by 81
  18. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  19. 2019Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attackscited by 79
  20. 2018DRACO: Byzantine-resilient Distributed Training via Redundant Gradientscited by 74
  21. 2017Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descentcited by 59
  22. 2019Understanding Top-k Sparsification in Distributed Deep Learningcited by 56
  23. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  24. 2019BRIDGE: Byzantine-resilient Decentralized Gradient Descentcited by 45
  25. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  26. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  27. 2016Geometric Median in Nearly Linear Timecited by 38
  28. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  29. 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
  30. 2019Implicit Regularization and Convergence for Weight Normalizationcited by 20
  31. 2020Byzantine-Resilient SGD in High Dimensions on Heterogeneous Datacited by 17
  32. 2014Distributed Robust Learningcited by 13
  33. 2019Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approachcited by 13
  34. 2013Accelerated Mini-Batch Stochastic Dual Coordinate Ascentcited by 11
  35. 2018Efficient Greedy Coordinate Descent for Composite Problemscited by 8
  36. 2015Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Datacited by 6
  37. 2020Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)cited by 4
  38. 2016New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditionscited by 3

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 5; 2024: 8; 2025: 3; 2026: 1.

20 papers.

Sort:

By area:

  1. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  2. 2023Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneitycited by 25
  3. 2022An Equivalence Between Data Poisoning and Byzantine Gradient Attackscited by 16
  4. 2023Byzantine-Robust Learning on Heterogeneous Data via Gradient Splittingcited by 13
  5. 2024Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updatescited by 13
  6. 2022Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learningcited by 4
  7. 2022Robust supervised learning with coordinate gradient descentcited by 3
  8. 2024Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Trainingcited by 3
  9. 2024Private Geometric Mediancited by 3
  10. 2024The poison of dimensionalitycited by 3
  11. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  12. 2025Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous MLcited by 2
8 more
  1. 2026RoPoLL: Robust Panel of LLM Judgescited by 2
  2. 2024Geometric Median (GM) Matching for Robust Data Pruningcited by 1
  3. 2024Submodular Maximization Approaches for Equitable Client Selection in Federated Learningcited by 1
  4. 2024Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filteringcited by 1
  5. 2025Geometric Median Matching for Robust k-Subset Selection from Noisy Datacited by 1
  6. 2023Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applicationscited by 0
  7. 2023Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensingcited by 0
  8. 2024Tracking the Median of Gradients with a Stochastic Proximal Point Methodcited by 0