# Importance Sampling for Minibatches

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2016.

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

- [InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning](https://mlsanity.com/paper/2303.04947/) (2023)
- [Online Continual Learning on Class Incremental Blurry Task Configuration with Anytime Inference](https://mlsanity.com/paper/2110.10031/) (2021)
- [Stop Wasting My Time! Saving Days of ImageNet and BERT Training with Latest Weight Averaging](https://mlsanity.com/paper/2209.14981/) (2022)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Reweighting Augmented Samples by Minimizing the Maximal Expected Loss](https://mlsanity.com/paper/2103.08933/) (2021)
- [Amortized Variational Inference: A Systematic Review](https://mlsanity.com/paper/2209.10888/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling](https://mlsanity.com/paper/2210.09634/) (2022)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [A General Theory for Client Sampling in Federated Learning](https://mlsanity.com/paper/2107.12211/) (2021)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [Uniform Sampling over Episode Difficulty](https://mlsanity.com/paper/2108.01662/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [Deep Neural Networks Inspired by Differential Equations](https://mlsanity.com/paper/2510.09685/) (2025)
- [Training Memory in Deep Neural Networks: Mechanisms, Evidence, and Measurement Gaps](https://mlsanity.com/paper/2601.21624/) (2026)
- [Modelling calibration uncertainty in networks of environmental sensors](https://mlsanity.com/paper/2205.01988/) (2022)
- [Tricks and Plugins to GBM on Images and Sequences](https://mlsanity.com/paper/2203.00761/) (2022)
- [A Negative Result on Gradient Matching for Selective Backprop](https://mlsanity.com/paper/2312.05021/) (2023)
- [Unsupervised Federated Optimization at the Edge: D2D-Enabled Learning without Labels](https://mlsanity.com/paper/2404.09861/) (2024)
- [Grad Queue : A probabilistic framework to reinforce sparse gradients](https://mlsanity.com/paper/2404.16917/) (2024)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Efficient Training of Deep Networks using Guided Spectral Data Selection: A Step Toward Learning What You Need](https://mlsanity.com/paper/2507.04269/) (2025)
- [Tricks and Plug-ins for Gradient Boosting in Image Classification](https://mlsanity.com/paper/2507.22842/) (2025)
- [Tricks and Plug-ins for Gradient Boosting with Transformers](https://mlsanity.com/paper/2508.02924/) (2025)

## Abstract (arXiv)

Minibatching is a very well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling -- a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is no existing work combining the power of importance sampling with the strength of minibatching. In this paper we propose the first em importance sampling for minibatches and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular datasets, and show that the improvement can reach an order of magnitude.