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

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2019.

## Built on by (most cited first, 30 of 51)

- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [Chaos as an interpretable benchmark for forecasting and data-driven modelling](https://mlsanity.com/paper/2110.05266/) (2021)
- [Prompt Curriculum Learning for Efficient LLM Post-Training](https://mlsanity.com/paper/2510.01135/) (2025)
- [No Train No Gain: Revisiting Efficient Training Algorithms For Transformer-based Language Models](https://mlsanity.com/paper/2307.06440/) (2023)
- [Self-Influence Guided Data Reweighting for Language Model Pre-training](https://mlsanity.com/paper/2311.00913/) (2023)
- [ACPL: Anti-curriculum Pseudo-labelling for Semi-supervised Medical Image Classification](https://mlsanity.com/paper/2111.12918/) (2021)
- [Calibrated Selective Classification](https://mlsanity.com/paper/2208.12084/) (2022)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [On Efficient Training of Large-Scale Deep Learning Models: A Literature Review](https://mlsanity.com/paper/2304.03589/) (2023)
- [Sum of Ranked Range Loss for Supervised Learning](https://mlsanity.com/paper/2106.03300/) (2021)
- [Learning to Reason at the Frontier of Learnability](https://mlsanity.com/paper/2502.12272/) (2025)
- [On Continual Model Refinement in Out-of-Distribution Data Streams](https://mlsanity.com/paper/2205.02014/) (2022)
- [Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Play](https://mlsanity.com/paper/2411.00062/) (2024)
- [A Tale Of Two Long Tails](https://mlsanity.com/paper/2107.13098/) (2021)
- [Upweighting Easy Samples in Fine-Tuning Mitigates Forgetting](https://mlsanity.com/paper/2502.02797/) (2025)
- [Tokens for Learning, Tokens for Unlearning: Mitigating Membership Inference Attacks in Large Language Models via Dual-Purpose Training](https://mlsanity.com/paper/2502.19726/) (2025)
- [GRASP: A Rehearsal Policy for Efficient Online Continual Learning](https://mlsanity.com/paper/2308.13646/) (2023)
- [Diversified Batch Selection for Training Acceleration](https://mlsanity.com/paper/2406.04872/) (2024)
- [Towards Accelerated Model Training via Bayesian Data Selection](https://mlsanity.com/paper/2308.10544/) (2023)
- [K-SAM: Sharpness-Aware Minimization at the Speed of SGD](https://mlsanity.com/paper/2210.12864/) (2022)
- [A Recipe for Global Convergence Guarantee in Deep Neural Networks](https://mlsanity.com/paper/2104.05785/) (2021)
- [Mini-Batch Optimization of Contrastive Loss](https://mlsanity.com/paper/2307.05906/) (2023)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Prioritized training on points that are learnable, worth learning, and not yet learned (workshop version)](https://mlsanity.com/paper/2107.02565/) (2021)
- [Stochastic Optimization for Spectral Risk Measures](https://mlsanity.com/paper/2212.05149/) (2022)
- [DRoP: Distributionally Robust Data Pruning](https://mlsanity.com/paper/2404.05579/) (2024)
- [How Important is Importance Sampling for Deep Budgeted Training?](https://mlsanity.com/paper/2110.14283/) (2021)
- [A Survey of Dataset Refinement for Problems in Computer Vision Datasets](https://mlsanity.com/paper/2210.11717/) (2022)
- [Neural Active Learning on Heteroskedastic Distributions](https://mlsanity.com/paper/2211.00928/) (2022)

## Abstract (arXiv)

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), utilize an unbiased gradient estimator of the empirical average loss. In contrast, we develop a computationally efficient method to construct a gradient estimator that is purposely biased toward those observations with higher current losses. On the theory side, we show that the proposed method minimizes a new ordered modification of the empirical average loss, and is guaranteed to converge at a sublinear rate to a global optimum for convex loss and to a critical point for weakly convex (non-convex) loss. Furthermore, we prove a new generalization bound for the proposed algorithm. On the empirical side, the numerical experiments show that our proposed method consistently improves the test errors compared with the standard mini-batch SGD in various models including SVM, logistic regression, and deep learning problems.