Differentially Private Ranking Release for Kernel SHAP: A Certified Exponential-Mechanism Approach with Empirical Sensitivity Diagnostics

This technical report studies differentially private release of Kernel SHAP explanations under input-level and background-record privacy models.

The main certified contribution is a pure ε-differentially private ranking-release mechanism for Kernel SHAP feature attributions. The mechanism uses the exponential mechanism to release the top-ranked feature, or sequential top-k features, under any valid upper bound Δ∞ on per-coordinate ranking sensitivity. Its utility is governed by the dimensionless ratio Δ∞/g, where g is the top-1/top-2 attribution-magnitude gap. The report gives analytic Δ∞ certificates for linear models, conservative bounds for logistic models, and diagnostic empirical estimates for nonlinear models.

The report also analyzes why full-vector Gaussian release has poor utility in practical regimes and includes a bootstrap-calibrated baseline that is explicitly presented as heuristic rather than a certified worst-case differential privacy mechanism.