Choosing the Sample with Lowest Loss makes SGD Robust

Vatsal Shah, Xiaoxia Wu, Sujay Sanghavi

Abstract

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.

Introduction

Standard Stochastic Gradient Descent (SGD) is notoriously sensitive to outliers. Because vanilla SGD treats every data point with equal importance, even a small fraction of adversarial or noisy samples can pull a model far from the true optimum. While robust optimization methods exist, they are often computationally expensive or limited to specific architectures. This paper introduces Min-k Loss SGD (MKL-SGD), a "drop-in" modification that remains computationally efficient and works across various model architectures, including deep neural networks.

Methodology: Min-k Loss SGD

The MKL-SGD algorithm is elegantly simple. In each iteration, instead of picking one random sample, the algorithm:

  1. Randomly chooses a set $S_t$ of $k$ samples.
  2. Calculates the loss for all $k$ samples.
  3. Selects the single sample $i_t$ with the minimum loss.
  4. Performs a standard SGD update using only the gradient of that "easiest" sample.

The core intuition is that outliers typically exhibit higher loss than "good" samples. By consistently picking the sample with the lowest loss, the algorithm effectively filters out corruption. Mathematically, MKL-SGD is equivalent to performing gradient descent on a non-convex surrogate loss function.

Visualization of the surrogate loss function (dashed blue) compared to clean (green) and corrupted (red) sample losses.

As shown in Figure 2, the surrogate loss (dashed blue line) is constructed from the minimum of multiple sample losses. The authors provide theoretical proofs showing that for convex problems, this surrogate loss still has a unique stationary point near the true optimum $w^*$, even when corrupted samples $w_{\mathcal{B}}$ are present.

Experimental Setup

The authors evaluated MKL-SGD using both synthetic and real-world benchmarks:

  • Synthetic Linear Regression: Testing theoretical convergence across varying dimensions and condition numbers.
  • MNIST & CIFAR-10: Standard image classification benchmarks using ResNet-18.
  • Noise Models: Evaluation against Random Label Noise and Directed Label Noise (where class $A$ errors are systematically assigned to class $B$).

Analysis and Key Insights

A key insight of this work is the "Aha" heuristic: while most "hard example mining" focuses on high-loss samples to improve accuracy, in the presence of outliers, high loss is a signal of corruption, not a signal of a "hard-to-learn" valid sample.

Surface plot of the non-convex surrogate loss function f(x,y) minimized by MKL-SGD.

The surrogate loss landscape, as visualized in Figure 1, is non-convex. Despite this, the algorithm demonstrates robust convergence. There is a fundamental trade-off with the parameter $k$: a larger $k$ increases robustness to higher outlier fractions but slows convergence as the algorithm becomes "pickier." Interestingly, MKL-SGD often results in higher training loss but lower test loss than vanilla SGD, as it avoids overfitting to noisy training labels.

Results

MKL-SGD demonstrates significant robustness to heavy corruption. On MNIST with 40% directed label noise, MKL-SGD achieved 94.20% accuracy, compared to only 71.95% for vanilla SGD. It also consistently outperformed "Median-loss SGD" in stability and effectiveness. Furthermore, the paper proves that MKL-SGD retains linear convergence properties in noiseless settings, ensuring it does not sacrifice excessive speed for robustness.

Conclusion

MKL-SGD offers a simple, effective way to make SGD robust to outliers by leveraging a min-k selection strategy. While it introduces some computational overhead and requires tuning $k$ based on the outlier fraction, its performance on noisy datasets makes it a compelling alternative to standard SGD. Future work includes extending theoretical proofs to deep learning's non-convex landscapes and exploring smarter initialization techniques.

Summary updated

Abstract

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
BibTeX
@inproceedings{shah2020choosing,
  author = {Vatsal Shah and Xiaoxia Wu and Sujay Sanghavi},
  title = {{Choosing the Sample with Lowest Loss makes SGD Robust}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=2xENzyJto3},
}
Figure