In machine learning, we routinely rely on uniform random sampling to approximate intractable expectations—whether we are computing stochastic gradients over millions of images, evaluating policy performance from historical logs, or calculating feature importance across exponential combinations. While uniform sampling is unbiased, it is often remarkably inefficient. It treats every data point or subset with equal probability, ignoring underlying structures, clusters, or natural groupings. This blind spot introduces substantial statistical noise, slowing down convergence and destabilizing algorithms.
A powerful paradigm across optimization, data valuation, and evaluation replaces uniform random selection with stratified subsampling. The core intuition is simple: instead of drawing completely at random from the entire population, we partition the population into distinct, meaningful subgroups (strata) and enforce a fixed, deterministic allocation of samples from each stratum. By ensuring that every subpopulation is perfectly represented in every step, stratified designs dramatically reduce variance.
Eliminating Allocation Noise: The Power of Fixed-Size Strata
To understand why stratified sampling outperforms independent and identically distributed (i.i.d.) uniform sampling, consider estimating an expectation over data originating from multiple distinct sources. Under standard i.i.d. sampling, the number of samples drawn from any given source is itself a random variable. This introduces an extra layer of uncertainty known as "allocation noise."
In survey statistics, Patrice Bertail in Bernstein-type exponential inequalities in survey sampling: Conditional Poisson sampling schemes established sharp, non-asymptotic tail bounds showing that fixed-size sampling designs achieve higher precision precisely because they eliminate the variance associated with random fluctuations in sample size.
This foundational insight directly translates to modern machine learning challenges like Off-Policy Evaluation (OPE). When evaluating a new policy using historical data generated by multiple different logging policies, standard approaches treat the combined dataset as an i.i.d. pool. However, in Optimal Off-Policy Evaluation from Multiple Logging Policies, Nathan Kallus et al. demonstrate that treating multi-source data as a stratified sample with fixed dataset sizes yields significantly higher precision. By fixing the number of samples per logging policy, the estimator completely bypasses the variance that would otherwise stem from random fluctuations in the relative proportions of data coming from different sources.
Exploiting Homogeneity: Size-Based Stratification in Shapley Estimation
Stratification is equally transformative when the "population" consists of combinatorial subsets rather than data points. A prime example is estimating the Shapley value for feature importance or data valuation, which requires averaging the marginal contributions of an item across an exponential number of possible coalitions (subsets). Uniformly sampling permutations or coalitions exhibits massive variance because a data point's or feature's contribution varies systematically depending on the size of the coalition it joins.
This is where size-based stratification shines. In Variance reduced Shapley value estimation for trustworthy data valuation, Mengmeng Wu et al. group coalitions into layers based on their size and sample independently within each layer. Because coalitions of similar sizes tend to exhibit similar value distributions, the variance within each stratum is small.
Similarly, Patrick Kolpaczki et al. leverage this mechanism in Approximating the Shapley Value without Marginal Contributions to decouple Shapley values from explicit marginal calculations. By partitioning feature subsets by cardinality, their algorithm ensures that the contribution of different coalition sizes is represented with exact proportions rather than left to the whims of random permutation sampling. The authors extend this principle to higher-order feature interactions in SVARM-IQ: Efficient Approximation of Any-order Shapley Interactions through Stratification, proving that grouping feature subsets into size-based strata consistently minimizes statistical noise and accelerates convergence because subsets of identical cardinality share comparable baseline properties.
Stabilizing Gradients and Geometry: Clustering and Group-Wise Optimization
Beyond eliminating allocation noise and exploiting subset homogeneity, stratified sampling can be actively engineered by imposing geometric or semantic structures on a dataset.
In stochastic optimization, uniform minibatch selection often leads to highly noisy gradient updates, especially when dealing with heterogeneous data. To combat this in Stochastic Gradient MCMC, Tianfan Fu et al. propose a preprocessing step in CPSG-MCMC: Clustering-Based Preprocessing method for Stochastic Gradient MCMC. They partition the dataset into geometric clusters using $k$-means and construct minibatches via stratified sampling across these clusters. The variance reduction achieved here is explicitly tied to the geometric compactness (the within-cluster sum of squares) of the clusters; ensuring that every minibatch contains a representative from every geometric neighborhood guarantees that the diversity of the entire dataset is preserved in every single gradient step.
This stabilization is crucial for complex optimization landscapes. For instance, in large-scale forecasting models where diverse time series create highly volatile updates, Yucheng Lu et al. introduce a stratified control variate method in Variance Reduced Training with Stratified Sampling for Forecasting Models, drawing samples from pre-defined strata to ensure stable, low-variance updates.
The mathematical benefit becomes even more pronounced in minimax problems like Group Distributionally Robust Optimization (GDRO). In Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond, Dingzhi Yu et al. analyze an approach that samples exactly one data point from every defined sub-population simultaneously in each iteration. This group-wise stratified sampling reduces the variance and, crucially, scales down the Lipschitz constant of the stochastic gradient by a factor proportional to the number of groups. By smoothing the gradient landscape and stabilizing the adversarial component, it allows optimizers to take larger step sizes and converge significantly faster.
Finally, this structural representation is highly effective in active learning and few-shot scenarios. Lincy Pattanaik et al. demonstrate in Clustering-based Sampling for Few-Shot Cross-Domain Keyphrase Extraction that replacing random selection with stratified clustering when picking samples for human labeling yields massive performance gains. It avoids the high variance and poor reproducibility of random sampling by forcing the selected few-shot examples to span the entire target domain space evenly.
Whether applied to data points in a geometric cluster, logging policies in an evaluation pool, or feature coalitions of a specific size, the core mechanism remains identical. Stratified subsampling replaces the randomness of where samples are allocated with a deterministic guarantee of structural diversity. By eliminating allocation noise and minimizing intra-stratum variance, it provides a foundational toolkit for making machine learning algorithms faster, more stable, and statistically optimal.
Key Foundational Work
CPSG-MCMC: Clustering-Based Preprocessing method for Stochastic Gradient MCMC (2017) — contributed 2 concept elements to this direction.
Bernstein-type exponential inequalities in survey sampling: Conditional Poisson sampling schemes (2019) — contributed 1 concept elements to this direction.