Standard optimization algorithms like Stochastic Gradient Descent (SGD) rely on a fundamental assumption: that every data point in a training set should be sampled uniformly at random. While mathematically convenient, uniform sampling introduces a severe computational bottleneck. As a model trains, it quickly masters simple, redundant patterns. Continuing to process these "easy" samples forces the model to execute expensive forward and backward passes for negligible gradient updates, wasting valuable compute. As noted by Fartash Faghri in Training Efficiency and Robustness in Deep Learning, this brute-force approach treats all data points as equally important, leading to severe diminishing returns.
To overcome this inefficiency, a prominent research direction focuses on adaptive importance sampling and informed data selection. Instead of treating a dataset as a static, homogeneous block, these methods dynamically evaluate the utility of each sample. The goal is to shift computational resources away from redundant data and toward the model's "knowledge frontier."
Why Uniform Sampling Fails: Gradient Variance
To understand why non-uniform sampling accelerates convergence, we must look at the variance of stochastic gradients. In uniform SGD, the convergence rate is inherently limited by the worst-case variance across the entire dataset. When a dataset is highly heterogeneous, uniform sampling frequently selects points with low or zero gradient contribution, adding noise rather than signal.
By biasing the sampling distribution toward points with higher gradient variability or loss, we can drastically reduce the variance of the gradient estimator. Deanna Needell et al. demonstrated in Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm that importance sampling can reduce the iteration complexity's dependence on the problem's conditioning from quadratic to linear. Similarly, Samuel Horváth showed in Nonconvex Variance Reduced Optimization with Arbitrary Sampling that leveraging non-uniform "arbitrary sampling" within variance-reduced frameworks yields superlinear speedups over uniform baselines.
Quantifying Sample Informativeness
To sample non-uniformly, we need a proxy for how much a model can learn from a given point. Several distinct metrics have emerged to quantify this utility:
- Gradient Norms and Loss: The most direct proxy for a sample's utility is its loss or gradient norm. Angelos Katharopoulos et al. developed a principled importance sampling scheme in Not All Samples Are Created Equal: Deep Learning with Importance Sampling using a low-cost upper bound of the gradient norm to prioritize high-signal samples. Similarly, Kenji Kawaguchi et al. proposed Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization, which explicitly prioritizes "hard" examples with larger losses to improve generalization.
- Reducible Loss: High loss alone can be misleading; a sample might have high loss simply because it is noisy or an unlearnable outlier. To fix this, Sören Mindermann et al. introduced RHO-LOSS in Prioritized Training on Points that are Learnable, Worth Learning, and not yet Learnt. This technique prioritizes points whose loss is reducible—meaning they are learnable, worth learning, and not yet mastered—preventing the model from wasting compute on irreducible noise.
- Approximate Losses: Computing the exact loss or gradient for every sample to decide whether to train on it can defeat the purpose of saving compute. To solve this, Rudrajit Das et al. introduced a "sifting" strategy in Understanding the Training Speedup from Sampling with Approximate Losses, which uses cheap, approximate loss estimates from early model layers to filter out uninformative samples before performing expensive backpropagation.
Adapting to the Model's Evolving Frontier
A sample's informativeness is not static; what is challenging at the beginning of training becomes trivial later on. Therefore, effective sampling must adapt dynamically over time.
Hwanjun Song proposed tracking "recency bias" in Carpe Diem, Seize the Samples Uncertain "At the Moment" for Adaptive Batch Selection via a sliding window of recent predictions to capture what the model is struggling with at the moment.
This dynamic prioritization has proven crucial for large language models (LLMs) and reinforcement learning pipelines:
- Pretraining and Fine-Tuning: Daouda Sow et al. demonstrated in Dynamic Loss-Based Sample Reweighting for Improved Large Language Model Pretraining that dynamically down-weighting low-loss tokens during LLM pretraining prevents the model from wasting cycles on repetitive web-scraped text.
- Self-Training and Alignment: In self-training, Xiaoxuan Wang et al. developed an entropy-based weighting scheme in Entropy-Based Adaptive Weighting for Self-Training to prioritize challenging, uncertain examples. For reasoning models, Zexu Sun showed in CurES: From Gradient Analysis to Efficient Curriculum Learning for Reasoning LLMs that curriculum-based sampling can target a "sweet spot" of moderate difficulty, avoiding both trivial prompts and overly complex problems that provide no useful gradient signal.
- Reinforcement Learning: Similarly, Ziyu Ye et al. introduced asymmetric self-play in Reward-Guided Prompt Evolving in Reinforcement Learning for LLMs to allow models to adaptively generate and prioritize their own training prompts, bypassing the inefficiencies of static, pre-curated datasets.
By replacing uniform random selection with mechanisms that respect the varying information density of data, these approaches ensure that every forward and backward pass directly contributes to expanding the model's capabilities.