Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Researchers propose Local Shapley, a new method that dramatically reduces computational complexity in data valuation by focusing only on training data points that actually influence specific predictions. The approach achieves substantial speedups while maintaining accuracy by leveraging model-induced locality properties.

• →Local Shapley reduces #P-hard Shapley value computation by focusing only on influential training data subsets for each prediction.
• →The method exploits model-induced locality through support sets like KNN neighbors, tree leaves, or GNN receptive fields.
• →LSMR algorithm trains each influential subset exactly once, achieving optimal reuse and significant computational savings.
• →The approach maintains high valuation fidelity while delivering substantial retraining reductions across multiple model families.
• →Information-theoretic lower bounds prove the method's optimality in terms of required retraining operations.