Data Banzhaf: A Data Valuation Framework with Maximal Robustness to
  Learning Stochasticity
  This paper studies the robustness of data valuation to noisy model
performance scores. Particularly, we find that the inherent randomness of the
widely used stochastic gradient descent can cause existing data value notions
(e.g., the Shapley value and the Leave-one-out error) to produce inconsistent
data value rankings across different runs. To address this challenge, we first
pose a formal framework within which one can measure the robustness of a data
value notion. We show that the Banzhaf value, a value notion originated from
cooperative game theory literature, achieves the maximal robustness among all
semivalues -- a class of value notions that satisfy crucial properties entailed
by ML applications. We propose an algorithm to efficiently estimate the Banzhaf
value based on the Maximum Sample Reuse (MSR) principle. We derive the lower
bound sample complexity for Banzhaf value approximation, and we show that our
MSR algorithm's sample complexity nearly matches the lower bound. Our
evaluation demonstrates that the Banzhaf value outperforms the existing
semivalue-based data value notions on several downstream ML tasks such as
learning with weighted samples and noisy label detection. Overall, our study
suggests that when the underlying ML algorithm is stochastic, the Banzhaf value
is a promising alternative to the semivalue-based data value schemes given its
computational advantage and ability to robustly differentiate data quality.
