# Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2014.

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

- [Prototypical Graph Contrastive Learning](https://mlsanity.com/paper/2106.09645/) (2021)
- [Optimizing Chain-of-Thought Reasoners via Gradient Variance Minimization in Rejection Sampling and RL](https://mlsanity.com/paper/2505.02391/) (2025)
- [Reweighting Augmented Samples by Minimizing the Maximal Expected Loss](https://mlsanity.com/paper/2103.08933/) (2021)
- [Parallel Successive Learning for Dynamic Distributed Model Training over Heterogeneous Wireless Networks](https://mlsanity.com/paper/2202.02947/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling](https://mlsanity.com/paper/2206.02275/) (2022)
- [Uniform Sampling over Episode Difficulty](https://mlsanity.com/paper/2108.01662/) (2021)
- [A Survey of Dataset Refinement for Problems in Computer Vision Datasets](https://mlsanity.com/paper/2210.11717/) (2022)
- [DPP-based Client Selection for Federated Learning with Non-IID Data](https://mlsanity.com/paper/2303.17358/) (2023)
- [Variance Matters: Improving Domain Adaptation via Stratified Sampling](https://mlsanity.com/paper/2512.05226/) (2025)
- [Order Matters: Improving Domain Adaptation by Reordering Data](https://mlsanity.com/paper/2605.05084/) (2026)
- [Drill the Cork of Information Bottleneck by Inputting the Most Important Data](https://mlsanity.com/paper/2105.07181/) (2021)
- [Efficient multi-view training for 3D Gaussian Splatting](https://mlsanity.com/paper/2506.12727/) (2025)
- [Approximate Inference via Clustering](https://mlsanity.com/paper/2111.14219/) (2021)
- [Preferential Subsampling for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2210.16189/) (2022)
- [Rainfall regression from C-band Synthetic Aperture Radar using Multi-Task Generative Adversarial Networks](https://mlsanity.com/paper/2411.03480/) (2024)
- [Disentangling Sampling from Training Budget in Class-Imbalanced CT Body Composition Segmentation](https://mlsanity.com/paper/2605.20405/) (2026)
- [Variance-reduced Domain Adaptation using Paired Sampling](https://mlsanity.com/paper/2607.20367/) (2026)
- [Online Variance Reduction for Domain Adaptation on Streaming Data](https://mlsanity.com/paper/2607.20374/) (2026)
- [Metadata-Aware Adaptation of a Generative Foundation Model for Conditional CMR Synthesis](https://mlsanity.com/paper/2608.24342/) (2026)
- [Kinematics-Induced Multimodal 3D Human Pose Estimation with Subject-Level Privacy](https://mlsanity.com/paper/2610.02943/) (2026)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is a popular optimization method which has been applied to many important machine learning tasks such as Support Vector Machines and Deep Neural Networks. In order to parallelize SGD, minibatch training is often employed. The standard approach is to uniformly sample a minibatch at each step, which often leads to high variance. In this paper we propose a stratified sampling strategy, which divides the whole dataset into clusters with low within-cluster variance; we then take examples from these clusters using a stratified sampling technique. It is shown that the convergence rate can be significantly improved by the algorithm. Encouraging experimental results confirm the effectiveness of the proposed method.