# Choosing the Sample with Lowest Loss makes SGD Robust

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2020.

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

- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [On The Impact of Machine Learning Randomness on Group Fairness](https://mlsanity.com/paper/2307.04138/) (2023)
- [Sum of Ranked Range Loss for Supervised Learning](https://mlsanity.com/paper/2106.03300/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [REALM: Robust Entropy Adaptive Loss Minimization for Improved Single-Sample Test-Time Adaptation](https://mlsanity.com/paper/2309.03964/) (2023)
- [One Backward from Ten Forward, Subsampling for Large-Scale Deep Learning](https://mlsanity.com/paper/2104.13114/) (2021)
- [Learning Deep Neural Networks under Agnostic Corrupted Supervision](https://mlsanity.com/paper/2102.06735/) (2021)
- [Adaptively Weighted Data Augmentation Consistency Regularization for Robust Optimization under Concept Shift](https://mlsanity.com/paper/2210.01891/) (2022)
- [AdaSelection: Accelerating Deep Learning Training through Data Subsampling](https://mlsanity.com/paper/2306.10728/) (2023)
- [Efficient Backpropagation with Variance-Controlled Adaptive Sampling](https://mlsanity.com/paper/2402.17227/) (2024)
- [A Two-Stage Data Selection Framework for Data-Efficient Model Training on Edge Devices](https://mlsanity.com/paper/2505.16563/) (2025)
- [OrderDP: A Theoretically Guaranteed Lossless Dynamic Data Pruning Framework](https://mlsanity.com/paper/2606.08574/) (2026)
- [Geometric Median (GM) Matching for Robust Data Pruning](https://mlsanity.com/paper/2406.17188/) (2024)
- [Geometric Median Matching for Robust k-Subset Selection from Noisy Data](https://mlsanity.com/paper/2504.00564/) (2025)
- [OLR-WA: Online Weighted Average Linear Regression in Multivariate Data Streams](https://mlsanity.com/paper/2512.14892/) (2025)
- [Provable Hierarchical Lifelong Learning with a Sketch-based Modular Architecture](https://mlsanity.com/paper/2112.10919/) (2021)
- [A Robust Optimization Method for Label Noisy Datasets Based on Adaptive Threshold: Adaptive-k](https://mlsanity.com/paper/2203.14165/) (2022)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Randomized Dimension Reduction with Statistical Guarantees](https://mlsanity.com/paper/2310.01739/) (2023)
- [FedVSR: Towards Model-Agnostic Federated Learning in Video Super-Resolution](https://mlsanity.com/paper/2503.13745/) (2025)
- [Quantile-Based Randomized Kaczmarz for Corrupted Tensor Linear Systems](https://mlsanity.com/paper/2503.18190/) (2025)
- [Online Data Curation for Object Detection via Marginal Contributions to Dataset-level Average Precision](https://mlsanity.com/paper/2511.14197/) (2025)
- [OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging](https://mlsanity.com/paper/2512.12779/) (2025)
- [Understanding the Gain from Data Filtering in Multimodal Contrastive Learning](https://mlsanity.com/paper/2512.14230/) (2025)
- [Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent](https://mlsanity.com/paper/2609.13040/) (2026)

## Abstract (arXiv)

The presence of outliers can potentially significantly skew the parameters of machine learning models trained via stochastic gradient descent (SGD). In this paper we propose a simple variant of the simple SGD method: in each step, first choose a set of k samples, then from these choose the one with the smallest current loss, and do an SGD-like update with this chosen sample. Vanilla SGD corresponds to k = 1, i.e. no choice; k >= 2 represents a new algorithm that is however effectively minimizing a non-convex surrogate loss. Our main contribution is a theoretical analysis of the robustness properties of this idea for ML problems which are sums of convex losses; these are backed up with linear regression and small-scale neural network experiments