First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint
Abstract
Probabilistic values, including Shapley values and semivalues, provide a model-agnostic framework to attribute the behavior of a black-box model to data points or features, with a wide range of applications including explainable artificial intelligence and data valuation. However, their exact computation requires utility evaluations over exponentially many coalitions, making Monte Carlo approximation essential in modern machine learning applications. Existing estimators are often developed through different representation strategies, including weighted averages, self-normalized weighting, regression adjustment, and weighted least squares. Our key observation is that these seemingly distinct constructions share a common first-order expansion, in which the leading term is determined by the sampling law and a working surrogate function. This first-order representation yields an explicit expression for the leading mean squared error (MSE), which characterizes how the sampling law and the surrogate jointly determine statistical efficiency. Guided by this criterion, we propose an Efficiency-Aware Surrogate-adjusted Estimator (EASE) that directly chooses the sampling law and surrogate to minimize the first-order MSE. We demonstrate that EASE consistently outperforms existing estimators for various probabilistic values.
Related
- A Statistical Viewpoint on Adam, Shampoo and Muon
- From priors to performance: enhancing statistical efficiency with Bayesian dynamic borrowing
- A probabilistic score estimation using the Bismut--Elworthy--Li formula
- Approximation Families and the Statistical Efficiency of Denoising Score Matching
- On the Computational and Statistical Efficiency of the Empirical Maximum Entropy on the Mean Method
BibTeX
@misc{liu2026firstorder,
title = {{First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint}},
author = {Ziqi Liu and Kiljae Lee and Yuan Zhang and Weijing Tang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2605.02827},
eprint = {2605.02827},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.02827},
}
RIS
TY - UNPB
TI - First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint
AU - Ziqi Liu
AU - Kiljae Lee
AU - Yuan Zhang
AU - Weijing Tang
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2605.02827
UR - https://arxiv.org/abs/2605.02827
AB - Probabilistic values, including Shapley values and semivalues, provide a model-agnostic framework to attribute the behavior of a black-box model to data points or features, with a wide range of applications including explainable artificial intelligence and data valuation. However, their exact computation requires utility evaluations over exponentially many coalitions, making Monte Carlo approximation essential in modern machine learning applications. Existing estimators are often developed through different representation strategies, including weighted averages, self-normalized weighting, regression adjustment, and weighted least squares. Our key observation is that these seemingly distinct constructions share a common first-order expansion, in which the leading term is determined by the sampling law and a working surrogate function. This first-order representation yields an explicit expression for the leading mean squared error (MSE), which characterizes how the sampling law and the surrogate jointly determine statistical efficiency. Guided by this criterion, we propose an Efficiency-Aware Surrogate-adjusted Estimator (EASE) that directly chooses the sampling law and surrogate to minimize the first-order MSE. We demonstrate that EASE consistently outperforms existing estimators for various probabilistic values.
ER -