  Data valuation, especially quantifying data value in algorithmic prediction
and decision-making, is a fundamental problem in data trading scenarios. The
most widely used method is to define the data Shapley and approximate it by
means of the permutation sampling algorithm. To make up for the large
estimation variance of the permutation sampling that hinders the development of
the data marketplace, we propose a more robust data valuation method using
stratified sampling, named variance reduced data Shapley (VRDS for short). We
theoretically show how to stratify, how many samples are taken at each stratum,
and the sample complexity analysis of VRDS. Finally, the effectiveness of VRDS
is illustrated in different types of datasets and data removal applications.
