On the Low Rank Theory for the Data Shapley: Kernel Perspective

As the quality of training data strongly affects model performance, Data Shapley has emerged as a principled method to assess the value of data by its Shapley value. However, its computational cost is prohibitively high for large models. Kernel-based Data Shapley, notably FreeShap, replaces model retraining with kernel regression, but its computational complexity remains a bottleneck for practical deployment. We analyze the relations among kernel approximation, prediction, and Data Shapley errors: we prove that the kernel approximation error upper-bounds the Data Shapley error, whereas a low prediction error does not guarantee a low Data Shapley error. Based on this analysis, we compare eigen and Nystr\"om decompositions and find that eigendecomposition is more suitable, since the Nystr\"om method is unstable for Data Shapley although it is stable for kernel approximation. On three downstream tasks, our method, LRFShap, achieves performance comparable to FreeShap while speeding up Data Shapley computation by up to 55$\times$.