Provably Adaptive Linear Approximation for the Shapley Value and Beyond

2026-04-09 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

A new theoretical framework addresses the challenge of efficiently approximating Shapley values and other semi-values, which are crucial in various attribution problems but computationally intensive. Exact computation typically demands an exponential number of utility queries relative to the number of players, $n$. This research focuses on efficient approximation under a $Θ(n)$ space constraint, leveraging a vector concentration inequality to derive sharper query complexities for existing unbiased randomized algorithms. The framework systematically develops a linear-space algorithm requiring $O(\frac{n}{\varepsilon^{2}}\log\frac{1}{\delta})$ utility queries to guarantee $P(\|\hat{\boldsymbol{\varphi}}-\boldsymbol{\varphi}|_{2}\geq\varepsilon)\leq \delta$ for common semi-values. This approach unifies methods like OFA, unbiased kernelSHAP, SHAP-IQ, and regression-adjusted techniques, clarifying the benefits of paired sampling. The authors also introduce Adalina, the first adaptive, linear-time, linear-space randomized algorithm, which theoretically minimizes mean square error and is experimentally validated.

Key takeaway

For Research Scientists developing attribution models, this work provides a robust, provably efficient method for approximating Shapley values. You should consider integrating the Adalina algorithm into your large-scale applications to achieve improved mean square error and reduced computational complexity, especially when working with $Θ(n)$ space constraints.

Key insights

A new framework and algorithm significantly improve the efficient approximation of Shapley values and semi-values.

Principles

• Vector concentration improves query complexity.
• Linear space algorithms are feasible for semi-value approximation.
• Adaptive algorithms can minimize mean square error.

Method

The Adalina algorithm uses a vector concentration inequality to achieve $O(\frac{n}{\varepsilon^{2}}\log\frac{1}{\delta})$ utility queries, unifying existing methods and explicitly minimizing mean square error for specific utility functions.

In practice

• Apply Adalina for large-scale attribution problems.
• Utilize paired sampling for specific utility functions.
• Integrate the framework with kernelSHAP or SHAP-IQ.

Topics

• Shapley Value
• Semi-values
• Query Complexity
• Linear-Space Algorithms
• Adalina Algorithm

Best for: AI Engineer, Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• MinShap: A Modified Shapley Value Approach for Feature Selection — MinShap adapts Shapley values for robust feature selection by focusing on minimum marginal contributions across permutations.
• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials — Noisy L-infinity learning of Boolean polynomial surrogates requires significantly higher sample complexity than noiseless or L2-norm settings.
• Revisiting a crazy global NLP problem — Non-convex quadratic optimization problems can be intractable even for small instances.
• Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors — New frequent directions algorithms enhance low-rank matrix and tensor approximations for efficiency and accuracy.
• Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem — This paper introduces a polynomial-time algorithm for the "group selection" problem within the algebraic diversity (AD) framework, which replaces temporal averaging with algebraic group action for sec…
• Quantifying and Understanding Uncertainty in Large Reasoning Models — A new method quantifies LRM uncertainty with statistical guarantees, linking reasoning traces to final answers.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.