Choosing the Sample with Lowest Loss makes SGD Robust

By Vatsal Shah, Xiaoxia Wu, Sujay Sanghavi. 2020

51 citations recorded by the source corpus.

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

Subfields: Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Optimization & Training

Citations in the corpus

On The Impact of Machine Learning Randomness on Group Fairness (2023, background): “Data order during training governs gradient updates and thus its impact on fairness is unsurprising [32, 37, 42, 47, 48, 50].”
Towards Understanding Biased Client Selection in Federated Learning (2022, background): “In contrast, Shah et al. (2020) proposes biased selection of lower loss samples to improve robustness to outliers.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “[25] suggests selecting a sample with the smallest loss from a set of data points sampled with replacement to make the training more robust.”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “In contrast, [30] proposes biased selection of lower loss samples to improve robustness to outliers.”