# Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond

arXiv: https://arxiv.org/abs/2604.08438 · HTML: https://mlsanity.com/paper/2604.08438/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 9 Apr 2026.

## Builds on (most cited first, 25 of 25)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [ContextCite: Attributing Model Generation to Context](https://mlsanity.com/paper/2409.00729/) (2024)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [WeightedSHAP: analyzing and improving Shapley based feature attributions](https://mlsanity.com/paper/2209.13429/) (2022)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [SHED: Shapley-Based Automated Dataset Refinement for Instruction Fine-Tuning](https://mlsanity.com/paper/2405.00705/) (2024)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [Variance reduced Shapley value estimation for trustworthy data valuation](https://mlsanity.com/paper/2210.16835/) (2022)
- [Linear TreeShap](https://mlsanity.com/paper/2209.08192/) (2022)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values](https://mlsanity.com/paper/2506.05216/) (2025)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)

## Built on by (most cited first, 1 of 1)

- [Is Data Shapley Not Better than Random in Data Selection? Ask NASH](https://mlsanity.com/paper/2605.10684/) (2026)

## Abstract (arXiv)

The Shapley value, and its broader family of semi-values, has received much attention in various attribution problems. A fundamental and long-standing challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players n. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a Theta(n) space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires O(fracnε2logfrac1δ) utility queries to ensure P(|hatboldsymbolφ-boldsymbolφ|2≥ε)≤ δ for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean squared error mathbbE[|hatboldsymbolφ-boldsymbolφ|22] for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean squared error. All of our theoretical findings are experimentally validated. Our code is available at https://github.com/watml/adalina.