Differentially Private Shapley Values for Data Evaluation
This work addresses privacy and efficiency issues in data valuation for machine learning applications, offering a practical solution for scenarios like empirical risk minimization, though it is incremental as it builds on existing Shapley value methods.
The paper tackled the problem of computing Shapley values for data valuation, which is computationally expensive and risks privacy, by proposing the Layered Shapley Algorithm that uses small random samples and coalitions to achieve probabilistic accuracy and incorporate differential privacy. Experimental results showed the algorithm identifies high-value data points that improve validation accuracy and preserves approximate ranking under privacy constraints.
The Shapley value has been proposed as a solution to many applications in machine learning, including for equitable valuation of data. Shapley values are computationally expensive and involve the entire dataset. The query for a point's Shapley value can also compromise the statistical privacy of other data points. We observe that in machine learning problems such as empirical risk minimization, and in many learning algorithms (such as those with uniform stability), a diminishing returns property holds, where marginal benefit per data point decreases rapidly with data sample size. Based on this property, we propose a new stratified approximation method called the Layered Shapley Algorithm. We prove that this method operates on small (O(\polylog(n))) random samples of data and small sized ($O(\log n)$) coalitions to achieve the results with guaranteed probabilistic accuracy, and can be modified to incorporate differential privacy. Experimental results show that the algorithm correctly identifies high-value data points that improve validation accuracy, and that the differentially private evaluations preserve approximate ranking of data.