# Variance Reduction in SGD by Distributed Importance Sampling

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2015.

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

- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [Efficient training of physics-informed neural networks via importance sampling](https://mlsanity.com/paper/2104.12325/) (2021)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [FedBalancer: Data and Pace Control for Efficient Federated Learning on Heterogeneous Clients](https://mlsanity.com/paper/2201.01601/) (2022)
- [Identifying Spurious Biases Early in Training through the Lens of Simplicity Bias](https://mlsanity.com/paper/2305.18761/) (2023)
- [Towards Sustainable Learning: Coresets for Data-efficient Deep Learning](https://mlsanity.com/paper/2306.01244/) (2023)
- [EfficientTrain: Exploring Generalized Curriculum Learning for Training Visual Backbones](https://mlsanity.com/paper/2211.09703/) (2022)
- [Neural Approaches to Conversational Information Retrieval](https://mlsanity.com/paper/2201.05176/) (2022)
- [No Train No Gain: Revisiting Efficient Training Algorithms For Transformer-based Language Models](https://mlsanity.com/paper/2307.06440/) (2023)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [DELTA: Diverse Client Sampling for Fasting Federated Learning](https://mlsanity.com/paper/2205.13925/) (2022)
- [Mitigating Dataset Bias by Using Per-sample Gradient](https://mlsanity.com/paper/2205.15704/) (2022)
- [NLU on Data Diets: Dynamic Data Subset Selection for NLP Classification Tasks](https://mlsanity.com/paper/2306.03208/) (2023)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [EfficientTrain++: Generalized Curriculum Learning for Efficient Visual Backbone Training](https://mlsanity.com/paper/2405.08768/) (2024)
- [Can Language Models Act as Knowledge Bases at Scale?](https://mlsanity.com/paper/2402.14273/) (2024)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [Upweighting Easy Samples in Fine-Tuning Mitigates Forgetting](https://mlsanity.com/paper/2502.02797/) (2025)
- [Federated Few-Shot Learning for Mobile NLP](https://mlsanity.com/paper/2212.05974/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [Large Batch Experience Replay](https://mlsanity.com/paper/2110.01528/) (2021)
- [Diversified Batch Selection for Training Acceleration](https://mlsanity.com/paper/2406.04872/) (2024)
- [Unsupervised Concept Discovery Mitigates Spurious Correlations](https://mlsanity.com/paper/2402.13368/) (2024)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2404.13804/) (2024)
- [Meta Learning on a Sequence of Imbalanced Domains with Difficulty Awareness](https://mlsanity.com/paper/2109.14120/) (2021)
- [A Comprehensive Survey of Federated Transfer Learning: Challenges, Methods and Applications](https://mlsanity.com/paper/2403.01387/) (2024)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [GaitMPL: Gait Recognition with Memory-Augmented Progressive Learning](https://mlsanity.com/paper/2306.04650/) (2023)

## Abstract (arXiv)

Humans are able to accelerate their learning by selecting training materials that are the most informative and at the appropriate level of difficulty. We propose a framework for distributing deep learning in which one set of workers search for the most informative examples in parallel while a single worker updates the model on examples selected by importance sampling. This leads the model to update using an unbiased estimate of the gradient which also has minimum variance when the sampling proposal is proportional to the L2-norm of the gradient. We show experimentally that this method reduces gradient variance even in a context where the cost of synchronization across machines cannot be ignored, and where the factors for importance sampling are not updated instantly across the training set.