First-Order Efficiency for Probabilistic Value Esti... | AI Research

First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint introduces a unified framework to improve how we estimate the contribution of data points or features in machine learning models. Probabilistic values, such as Shapley values, are essential for explaining black-box model decisions, but they are computationally expensive to calculate exactly because they require evaluating a model across an exponential number of possible data combinations. This paper provides a statistical foundation for Monte Carlo approximations, allowing researchers to design more efficient estimators that require fewer samples while maintaining high accuracy.

A Unified Statistical View

The authors observe that many existing estimation methods—which often appear distinct—actually share a common mathematical structure. Whether an estimator uses weighted averages, self-normalized weighting, or weighted least squares, it can be represented as an "augmented inverse-probability weighted" term. This term relies on a "working surrogate function," which acts as a model to help reduce the variance of the estimate. By identifying this shared structure, the researchers provide a single, consistent way to analyze and compare different estimation strategies.

The Efficiency-Aware Surrogate-adjusted Estimator (EASE)

Guided by this unified view, the authors propose a new method called the Efficiency-Aware Surrogate-adjusted Estimator (EASE). EASE is designed to minimize the leading mean squared error (MSE) of the estimation process. Because the optimal design depends on the unknown utility function of the model, EASE uses a two-stage approach: 1. Initialization: It uses a small set of pilot samples to learn an initial surrogate model and determine an effective sampling strategy. 2. Estimation: It draws further samples based on the learned strategy and applies a cross-fitted estimator, continuously refining the surrogate to minimize the first-order error.

Practical Performance and Design

The paper demonstrates that the first-order MSE approximation becomes highly accurate once the number of samples reaches a polynomial scale relative to the number of players. This makes the theoretical framework a practical tool for real-world applications where computational budgets are limited. Numerical experiments show that EASE consistently outperforms state-of-the-art estimators across various probabilistic value targets. By explicitly choosing both the sampling law and the surrogate function, EASE provides a more systematic and efficient path toward reliable model explanation and data valuation.