Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Leverage SHAP reduces the computational complexity of Shapley value estimation from exponential to O(n log n) model evaluations. By applying leverage score sampling to the Kernel SHAP framework, the method provides non-asymptotic complexity guarantees for feature attribution accuracy. This enables provably accurate explainability for high-dimensional models where exact computation is infeasible.