# Online Importance Sampling for Stochastic Gradient Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 24 Nov 2023.

## Builds on (most cited first, 25 of 25)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Implicit Neural Representations with Periodic Activation Functions](https://mlsanity.com/paper/2006.09661/) (2020)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Dataset Pruning: Reducing Training Data by Examining Generalization Influence](https://mlsanity.com/paper/2205.09329/) (2022)
- [Online Batch Selection for Faster Training of Neural Networks](https://mlsanity.com/paper/1511.06343/) (2015)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning](https://mlsanity.com/paper/2303.04947/) (2023)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Biased Importance Sampling for Deep Neural Network Training](https://mlsanity.com/paper/1706.00043/) (2017)
- [A Study of Gradient Variance in Deep Learning](https://mlsanity.com/paper/2007.04532/) (2020)
- [Active Mini-Batch Sampling using Repulsive Point Processes](https://mlsanity.com/paper/1804.02772/) (2018)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Accelerating Deep Neural Network Training with Inconsistent Stochastic Gradient Descent](https://mlsanity.com/paper/1603.05544/) (2016)
- [One Backward from Ten Forward, Subsampling for Large-Scale Deep Learning](https://mlsanity.com/paper/2104.13114/) (2021)
- [AdaSelection: Accelerating Deep Learning Training through Data Subsampling](https://mlsanity.com/paper/2306.10728/) (2023)

## Built on by (most cited first, 1 of 1)

- [From Detrimental to Beneficial: Dynamic Influence-based Valuation and Editing](https://mlsanity.com/paper/2608.22522/) (2026)

## Abstract (arXiv)

Machine learning optimization often depends on stochastic gradient descent, where the precision of gradient estimation is vital for model performance. Gradients are calculated from mini-batches formed by uniformly selecting data samples from the training dataset. However, not all data samples contribute equally to gradient estimation. To address this, various importance sampling strategies have been developed to prioritize more significant samples. Despite these advancements, all current importance sampling methods encounter challenges related to computational efficiency and seamless integration into practical machine learning pipelines. In this work, we propose a practical algorithm that efficiently computes data importance on-the-fly during training, eliminating the need for dataset preprocessing. We also introduce a novel metric based on the derivative of the loss w.r.t. the network output, designed for mini-batch importance sampling. Our metric prioritizes influential data points, thereby enhancing gradient estimation accuracy. We demonstrate the effectiveness of our approach across various applications. We first perform classification and regression tasks to demonstrate improvements in accuracy. Then, we show how our approach can also be used for online data pruning by identifying and discarding data samples that contribute minimally towards the training loss. This significantly reduce training time with negligible loss in the accuracy of the model.