Research map / Learning theory and algorithms / Prediction and decision losses
One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a one-sample-fits-all (OFA) framework that reuses sampled subsets to approximate every probabilistic value simultaneously, with an average-optimal sampling vector (OFA-A) and per-value optimized variant (OFA-S), and links it to datamodels regression.
Problem
Approximating probabilistic values (Shapley, Beta Shapley, weighted Banzhaf) is exponentially expensive, and since the best value choice is downstream-dependent, practitioners need to approximate many candidates; no existing estimator approximates all of them simultaneously and efficiently.
Approach
A sampling-based framework that keeps the principle of maximum sample reuse and avoids amplifying scalars, with convergence governed by a formula D(m,q) whose minimization over a sampling vector q yields an average-optimal (OFA-A) and per-value-optimal (OFA-S) estimator.
Key results
- OFA-A achieves O(n log n) convergence simultaneously for all probabilistic values on average and outperforms baselines on all 18 tested probabilistic values in experiments.
- OFA-A attains the fastest convergence for Beta Shapley values with alpha, beta >= 1, including the Shapley value, theoretically and empirically.
- OFA-S is consistently fastest on the Shapley value and is the best on most tested probabilistic values except on the SOU games.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OFA-A instead of the group testing estimator | Shapley value estimation · Shapley value | convergence rate: O(n(\log n)^{2}) -> O(n\log n) | Helped |
| Use OFA-A instead of the previous best estimator | Beta Shapley value estimation with α = 1, β > 1 or α > 1, β = 1 · Beta Shapley values | utility evaluations: O(n(\log n)^{3}) -> O(n\log n) | Helped |
| Use OFA-A instead of the previous best weighted Banzhaf estimator | Weighted Banzhaf value estimation · Weighted Banzhaf values | convergence rate: O(n\log n) -> O(n^{\frac{3}{2}}\log n) | Hurt |
| Tune the sampling vector for each specific probabilistic value (OFA-S) rather than using the average-optimal vector (OFA-A) | OFA estimation · Weighted Banzhaf values | convergence rate: O(n^{\frac{3}{2}}\log n) -> O(n\log n) | Helped |
| Tune the sampling vector for each specific probabilistic value (OFA-S) rather than using the average-optimal vector (OFA-A) | OFA estimation · Shapley value | convergence rate | No clear effect |
| Use OFA-S rather than OFA-A | OFA estimation · Six utility functions and evaluated probabilistic values | AUCC | Helped |
| Use OFA-S rather than the considered baselines | Probabilistic value estimation · Evaluated settings except SOU games requiring only n² utility evaluations for exact values | AUCC | Helped |
| Use OFA-A rather than the selected baselines | One-for-all estimation · 18 probabilistic values | AUCC | Helped |
Surprising findings
- Amplifying scalars in previous unbiased/weighted estimators (e.g., WSL-Banzhaf amplifier up to 2^24/24 at n=24) can cause large empirical error spikes.
Limitations
- OFA-A is slower than the best weighted Banzhaf estimator by a factor of sqrt(n) for weighted Banzhaf values.
- Convergence results rely on (epsilon, delta)-approximation with bounded utility and fixed constants; the second assumption of Theorem 1 is needed unless pre-allocation is used.
- Experiments use synthetic SOU games and small LeNet utilities on CPUs, with n up to 256.
Experimental setup
Datasets: FMNIST MNIST iris
Benchmarks: LeNet cross-entropy utility on FMNIST, MNIST, iris (n=24) sum of unanimity games utility (n=64,128,256)
Metrics: area under convergence curve (AUCC) of relative L2 error
Baselines: WSL-Shapley SHAP-IQ weightedSHAP permutation-Shapley kernelSHAP unbiased kernelSHAP group testing complement estimator MSR-Banzhaf GELS ARM AME
Builds on: Beta Shapley weighted Banzhaf values datamodels KernelSHAP
Closest papers by meaning
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.87)
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.87)
- KAIROS: Scalable Model-Agnostic Data Valuation (NeurIPS 2025 · similarity 0.86)
- A Provably Accurate Randomized Sampling Algorithm for Logistic Regression (AAAI 2024 · similarity 0.85)
- Optimal Hypothesis Selection in (Almost) Linear Time (NeurIPS 2024 · similarity 0.85)
- A Black-Box Debiasing Framework for Conditional Sampling (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.