Adaptive Importance Sampling for Efficient Deep Learning

200 concepts166 papers2 proposals

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:

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:

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.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 179 papers
  2. Version 1 · 2026-10-04 · 289 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_uniform_sampling_inefficiency_uniform_sa_a0f71809,
  title = {uniform sampling inefficiency (uniform sampling variance)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-sampling-inefficiency-uniform-sampling-variance/rdr_a0f71809c3114e5c8897813d3d5f3669},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_uniform_sampling_inefficiency_uniform_sa_a0f71809_v2,
  title = {uniform sampling inefficiency (uniform sampling variance)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-sampling-inefficiency-uniform-sampling-variance/rdr_a0f71809c3114e5c8897813d3d5f3669/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake