Antithetic Sampling for Efficient Shapley Value Estimation

This direction is merged into another direction: combinatorial explosion in feature attribution. Its last version stays readable and citable here.

Version 1 of 113 papers18 conceptsfrozen 2026-10-04

The Shapley value is the "gold standard" for fair credit assignment in machine learning, whether you are attributing a model's prediction to specific features or a global model's performance to individual data providers. However, calculating it exactly is notoriously difficult: for a model with $n$ features, you must evaluate $2^n$ possible subsets.

To avoid this exponential explosion, researchers rely on sampling. But simple random sampling (Monte Carlo) is often too noisy, requiring thousands of model evaluations to reach a stable estimate. A growing body of research shows that we can drastically reduce this noise by exploiting the mathematical symmetry of the Shapley formula through antithetic sampling.

The Intuition of Paired Sampling

In a standard Monte Carlo approach, you pick a random subset of features, see how the model performs, and repeat. Each sample is independent. Antithetic sampling changes this by picking samples in negatively correlated pairs.

If you sample a subset of features $S$, you immediately also sample its complement $S^c$ (all the features not in $S$). As Christopher P Musco and R. Teal Witter demonstrate in Provably Accurate Shapley Value Estimation via Leverage Score Sampling, this paired strategy ensures that every feature is included in exactly half of the evaluated subsets.

Why does this help? Imagine you are trying to estimate the average height of a population. If you happen to pick a very tall person, your estimate will be too high. But if you were forced to pick a "complementary" short person at the same time, the errors would tend to cancel each other out. In the context of feature attribution, Ramin Okhrati explains in A Multilinear Sampling Algorithm to Estimate Shapley Values that sampling a model at a specific activation probability and its complement simultaneously allows the variance to "halve," leading to more stable results with fewer evaluations.

Exploiting Permutation Symmetry

Another way to view Shapley values is through permutations: the value is the average marginal contribution of a feature across all possible orderings of features.

In kernelshap: Kernel SHAP, Michael Mayer implements an antithetic scheme that evaluates the Shapley formula twice for each feature using a single permutation and its reverse. By using these negatively correlated pairs, the estimator achieves higher precision than standard random permutations. This is a core component of the "Shapley value zoo" described by Ian C. Covert and Scott M. Lundberg in Algorithms to estimate Shapley value feature attributions, where they note that antithetic sampling improves the convergence rate of sampling-based methods across various high-dimensional benchmarks.

Beyond Feature Attribution

The benefits of this variance reduction extend beyond explaining individual model predictions. In Owen Sampling Accelerates Contribution Estimation in Federated Learning, Hossein KhademSohi and colleagues apply these concepts to Federated Learning. Here, the "features" are actually different clients contributing data. By using antithetic pairs of coalitions, they can identify which clients are providing high-quality data and which are redundant, using far fewer communication rounds than traditional methods.

Even in the study of rare events—where standard statistical bounds often fail—the underlying principle of using "ghost samples" or symmetrization to stabilize variance is critical. Stéphane Lhaut, Anne Sabourin, and Johan Segers show in Uniform concentration bounds for frequencies of rare events that combining symmetrization with localized conditioning allows for tighter, more useful bounds in regions of the data space that are usually difficult to model.

Stability and Efficiency

The recurring theme across this research—from Fan Yang's work on SHEAR to Hong Lin's SVBench—is that the bottleneck for Shapley values is not just the number of samples, but the variance of those samples.

By moving from independent random sampling to structured, antithetic sampling, we can:

  1. Reduce Error: Errors in one half of a pair tend to cancel the other.
  2. Ensure Balance: Every feature or participant is represented equally in the sample set.
  3. Accelerate Convergence: Reach a "faithful" explanation or contribution score with a fraction of the computational budget.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_antithetic_sampling_for_efficient_shaple_ca84558f,
  title = {Antithetic Sampling for Efficient Shapley Value Estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/antithetic-sampling-for-efficient-shapley-value-estimation/rdr_ca84558f7e744ad292670baa0e20e61c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_antithetic_sampling_for_efficient_shaple_ca84558f_v1,
  title = {Antithetic Sampling for Efficient Shapley Value Estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/antithetic-sampling-for-efficient-shapley-value-estimation/rdr_ca84558f7e744ad292670baa0e20e61c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}