In many areas of machine learning, we are forced to estimate complex values—like the importance of a feature or the performance of a policy—using a limited number of samples. Simple random sampling is the default, but it is often inefficient because it treats all samples as equally informative. A growing body of research suggests that by partitioning our search space into "strata" and sampling deliberately from each, we can drastically reduce estimation error without increasing computational cost.
The Intuition: Eliminating Between-Group Noise
To understand why stratification works, consider the tutorial by Benyamin Ghojogh and colleagues in Sampling Algorithms, from Survey Sampling to Monte Carlo Methods. They explain that the total variance of an estimator comes from two sources: the variance within groups and the variance between groups.
When we sample purely at random, our estimate fluctuates because we might accidentally pick too many samples from a "high-value" group and too few from a "low-value" group. Stratified sampling eliminates this "between-group" noise by fixing the number of samples taken from each group (stratum). If the strata are chosen such that members within a group are similar to each other but different from other groups, the resulting estimate becomes much more stable.
Stratifying by Cardinality in Shapley Values
The most prominent application of this idea is in approximating the Shapley value, a method for fair credit assignment in Explainable AI (XAI) and data valuation. Calculating exact Shapley values requires evaluating a model on every possible subset of features—an exponential task.
Researchers like Long Tran-Thanh and Talal Rahwan demonstrated in Bounding the Estimation Error of Sampling-based Shapley Value Approximation With/Without Stratifying that the "worth" of a coalition of features is often highly correlated with its cardinality (the number of features in the subset).
By partitioning the space of all possible feature subsets into strata based on their size, we can ensure that we sample coalitions of all sizes proportionally. This prevents the estimator from being biased by an unlucky run of very small or very large subsets. Patrick Kolpaczki, Viktor Bengs, and Eyke Hüllermeier extended this in their SVARM and Stratified SVARM algorithms (Approximating the Shapley Value without Marginal Contributions). They showed that size-based stratification allows a single model evaluation to update the importance scores of all features simultaneously, leading to state-of-the-art accuracy.
Stabilizing Off-Policy Evaluation
The benefits of stratification extend beyond feature importance to Off-Policy Evaluation (OPE)—estimating how well a new decision-making policy will perform using historical data.
Often, this historical data comes from multiple different "logging policies" (e.g., different versions of a recommendation engine). In Optimal Off-Policy Evaluation from Multiple Logging Policies, Nathan Kallus, Yuta Saito, and Masatoshi Uehara argue that we should treat these data sources as fixed strata.
In standard sampling, the relative size of each data source is treated as a random variable, which adds uncertainty. By treating the dataset sizes as fixed, the researchers derived a "Stratified Doubly Robust" estimator that achieves the theoretical lower bound for variance. This approach is particularly effective when the underlying models are misspecified, as the stratification structure provides a "safety net" that stabilizes the value estimate.
Robustness in Data Marketplaces
Stratification also solves the problem of reproducibility in Data Valuation. If a marketplace wants to pay users for their data based on its contribution to a model's accuracy, the valuation must be stable.
Mengmeng Wu and Ruoxi Jia introduced Variance Reduced Data Shapley (VRDS) in Robust Data Valuation via Variance Reduced Data Shapley. By replacing random permutations with cardinality-based stratified sampling, they ensured that the estimated value of a data point doesn't swing wildly between different runs of the algorithm. This makes the valuation "trustworthy"—a critical requirement for real-world data exchanges.
Summary of the Mechanism
The shared insight across these papers is that randomness is a source of error that can be engineered away. Whether we are:
- Grouping feature subsets by size (SVARM-IQ),
- Fixing the number of samples from different logging policies (Kallus et al.), or
- Clustering data points with similar gradients (Deborshee Sen et al. in Efficient posterior sampling for high-dimensional imbalanced logistic regression),
the goal is the same: use domain knowledge to partition the population into groups that are more homogeneous than the whole. By sampling systematically across these groups, we ensure that our estimator "sees" a representative slice of the problem space every time.