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 \ge 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 synthetic and small-scale neural network experiments.
Introduction
Standard Stochastic Gradient Descent (SGD) is the workhorse of modern machine learning. However, it implicitly assumes that all training data points are equally valid. In real-world scenarios, datasets often contain outliers or mislabeled examples. Because outliers typically produce large errors, their gradients can disproportionately influence the model, pulling parameters away from the true optimum. While robust optimization methods exist, they are often computationally prohibitive or require full-batch access. This work introduces Min-$k$ Loss SGD (MKL-SGD), a computationally efficient, drop-in replacement for SGD that inherently resists the influence of corrupt data.
The Min-$k$ Loss SGD Algorithm
The MKL-SGD algorithm modifies the standard stochastic update with a simple selection step:
- Randomly select a set of $k$ samples from the dataset.
- Evaluate the current loss for each of these $k$ samples.
- Select the sample with the smallest current loss.
- Update the model parameters using the gradient of only this selected sample.
When $k=1$, the algorithm reduces to vanilla SGD. For $k \ge 2$, the algorithm performs dynamic weighted sampling, favoring "clean" samples that the model already fits well. This approach flips the logic of hard-example mining; instead of focusing on high-loss samples (which are likely outliers in corrupted data), it prioritizes low-loss samples to ensure robustness.
Theoretical Analysis
The authors demonstrate that MKL-SGD effectively minimizes a non-convex surrogate loss function. Despite this non-convexity, they prove that in a "clean" setting (no outliers), the true optimum $w^*$ remains the unique stationary point.
In the presence of corruption, MKL-SGD is provably more robust than SGD. The theoretical analysis establishes that the residual error term caused by outliers is significantly smaller for MKL-SGD. The algorithm maintains a linear convergence rate for strongly convex functions up to a neighborhood of the optimum. A key insight is the "Goldilocks $k$": while increasing $k$ improves outlier filtering, an excessively large $k$ can make the algorithm too greedy, potentially leading to entrapment in spurious local minima.
Experimental Evaluation
Synthetic Linear Regression
The algorithm was first tested on synthetic linear regression tasks with varying outlier fractions ($\epsilon$) and condition numbers ($\kappa$).
As shown in the figure above, MKL-SGD consistently achieves lower parameter error ($||w - w^*||^2$) than SGD as the fraction of outliers increases. This advantage holds across different condition numbers, highlighting the algorithm's stability.
Deep Learning Benchmarks
The effectiveness of MKL-SGD was further evaluated on MNIST and CIFAR-10 datasets corrupted with directed label noise.
- MNIST: Under 40% corruption, standard SGD accuracy dropped to 71.95%, whereas MKL-SGD maintained 94.20% accuracy.
- CIFAR-10: With 20% corruption, MKL-SGD reached 77.77% accuracy, significantly outperforming SGD's 72.29%.
The training curves for CIFAR-10 illustrate that even a small $k$ (e.g., $k=2$) provides a substantial boost in final test accuracy and convergence stability under systematic noise.
Conclusion
Min-$k$ Loss SGD offers a simple yet powerful modification to standard SGD for robust learning. By prioritizing samples with lower current loss, the algorithm naturally filters out outliers and label noise. While the current theoretical framework focuses on convex losses, empirical results on neural networks suggest broad applicability. Future work may involve adaptive selection of $k$ and extending the theoretical guarantees to non-convex landscapes.
Summary updated