Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization

Kenji Kawaguchi, Haihao Lu

Abstract: We propose a new stochastic optimization framework for empirical risk minimization problems such as those that arise in machine learning. The traditional approaches, such as (mini-batch) stochastic gradient descent (SGD), treat all samples equally. However, in many applications, some samples are more informative than others. We introduce Ordered SGD, which prioritizes samples with higher losses during training to improve generalization and efficiency.

Introduction

Standard mini-batch Stochastic Gradient Descent (SGD) is the fundamental optimization algorithm for modern machine learning. It operates by selecting a random subset of data and updating model parameters based on the average gradient of that subset. This approach implicitly assumes that every data point contributes equally to the learning process. However, as training progresses, many samples become "easy"—the model classifies them correctly with high confidence, and their gradients provide diminishing information. Conversely, samples near the decision boundary, or "hard" examples, remain crucial for refining the model's accuracy.

Presented at AISTATS 2020, Ordered SGD addresses this inefficiency by prioritizing these hard examples, leading to improved model generalization and training speed.

The Ordered SGD Framework

Ordered SGD introduces a simple yet theoretically grounded modification to the standard mini-batch update. The algorithm follows four primary steps:

  1. Sample: Draw a random mini-batch $S$ of size $s$.
  2. Sort: Calculate the loss for every sample in the mini-batch.
  3. Select: Identify the top $q$ samples ($q \le s$) with the highest current losses.
  4. Update: Compute the gradient and update model parameters using only these $q$ "hard" samples.

While "hard example mining" has been used as a heuristic in the past, this work provides the first rigorous mathematical framework for it, proving that the algorithm minimizes a novel objective function termed the ordered empirical loss. To optimize performance, the authors suggest an adaptive $q$ schedule: starting with $q=s$ (standard SGD) to establish a baseline model, then gradually decreasing $q$ to focus the model on difficult boundary cases.

Handling Imbalance and Complex Boundaries

A key advantage of Ordered SGD is its ability to handle imbalanced data distributions. In standard SGD, small sub-clusters of data may be ignored because they do not significantly shift the average loss. Because Ordered SGD focuses on individual high-loss samples, it can "see" these informative clusters, allowing the model to capture finer details in the data distribution.

Decision boundaries on synthetic data showing how Ordered SGD (bottom row) captures finer details in data distributions compared to standard approaches (top row).

Key Results and Efficiency

The authors evaluated Ordered SGD across 18 experimental configurations, including digit recognition (MNIST, Fashion-MNIST) and natural images (CIFAR-10, CIFAR-100) using architectures like LeNet and PreActResNet18.

Consistent Accuracy Gains

Ordered SGD outperformed standard mini-batch SGD in every test case. For instance, on the Semeion dataset with a LeNet model, it reduced test error from 8.06% to 6.09%—a relative improvement of over 24%. The method proved robust even when using hyperparameters specifically tuned to favor standard SGD.

Computational Speedup

Contrary to intuition, sorting losses does not necessarily increase training time. In deep learning, the "backward pass" (gradient calculation) is significantly more computationally expensive than the "forward pass" (loss calculation). By performing the backward pass for only $q$ samples instead of the full mini-batch $s$, Ordered SGD can reduce wall-clock time per epoch while achieving superior accuracy.

Comparison of test error and training loss between standard mini-batch SGD and Ordered SGD (OSGD) with various q values, demonstrating faster convergence and lower error.

Conclusion

Ordered SGD demonstrates that purposely biasing gradients toward high-loss samples acts as a powerful form of implicit regularization. By ignoring redundant "easy" data, the framework improves both the quality of the final model and the efficiency of the training process. Future work remains in optimizing $q$ schedules for diverse architectures and extending theoretical convergence proofs to a wider array of non-convex neural network configurations.

Summary updated

Abstract

We propose a new stochastic optimization framework for empirical risk minimization problems such as those that arise in machine learning. The traditional approaches, such as (mini-batch) stochastic...
BibTeX
@inproceedings{kawaguchi2020ordered,
  author = {Kenji Kawaguchi and Haihao Lu},
  title = {{Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=BdKUscegf5c},
}
Figure