LAVA: Data Valuation without Pre-Specified Learning Algorithms
Authors: Hoang Anh Just
Feiyang Kang
Tianhao Wang
Yi Zeng
Myeongseob Ko
Ming Jin
Ruoxi Jia
Venue: ICLR 2023 notable top 25% (2023)
Keywords: data valuation
optimal transport
model agnostic
data-driven

Abstract: Traditionally, data valuation is posed as a problem of equitably splitting the validation performance of a learning algorithm among the training data. As a result, the calculated data values depend on many design choices of the underlying learning algorithm. However, this dependence is undesirable for many use cases of data valuation, such as setting priorities over different data sources in a data acquisition process and informing pricing mechanisms in a data marketplace. In these scenarios, data needs to be valued before the actual analysis and the choice of the learning algorithm is still undetermined then. Another side-effect of the dependence is that to assess the value of individual points, one needs to re-run the learning algorithm with and without a point, which incurs a large computation burden. 

This work leapfrogs over the current limits of data valuation methods by introducing a new framework that can value training data in a way that is oblivious to the downstream learning algorithm. Our main results are as follows. $\textbf{(1)}$ We develop a proxy for the validation performance associated with a training set based on a non-conventional $\textit{class-wise}$ $\textit{Wasserstein distance}$ between the training and the validation set. We show that the distance characterizes the upper bound of the validation performance for any given model under certain Lipschitz conditions. $\textbf{(2)}$ We develop a novel method to value individual data based on the sensitivity analysis of the $\textit{class-wise}$ Wasserstein distance. Importantly, these values can be directly obtained $\textit{for free}$ from the output of off-the-shelf optimization solvers once the Wasserstein distance is computed. $\textbf{(3) }$We evaluate our new data valuation framework over various use cases related to detecting low-quality data
and show that, surprisingly, the learning-agnostic feature of our framework enables a $\textit{significant improvement}$ over the state-of-the-art performance while being $\textit{orders of magnitude faster.}$ 

Published as a conference paper at ICLR 2023
LAVA: DATA VALUATION WITHOUT PRE-SPECIHEE LEARNING ALGORITHMS
Hoang Anh Just * Feiyang Kang Jiachen T. Wang". Yi Zeng', Myeongseob Ko',
Ming Jin', and Ruoxi Jia
Virginia Tech, Princeton University
(just, Fyk, yizeng, myeongseob, jinming ruoxi (io) taanaaowangerineetooo.co
ABSTRACT
Traditionally, data valuation is posed as problem of equitably splitting the valida- tion performance of a learning algorithm among the training data, As a result, the calculated data values depend on many design choices of the underlying learning algorithm. However, this dependence is undesirable for many use cases of data valuation, such as setting priorities over different data sources process and informing pricing mechanisms in a data marketplace. In these scenar- ios, data needs be valued before the actual analysis and the choice of the learning algorithm is still undetermined then. Another side-effect of the dependence is that to assess the value of individual points, one needs to re-run the learning algorithm with and without point, which incurs a large computation burden.
data acquisition
This work leapfrogs over the current limits of data valuation methods by introducing a new framework that can value training data in way that is oblivious the downstream learning algorithm. Our main results are as follows. (1) We develop a proxy for the validation performance associated with training set based on a non-conventional class-wise Wasserstein distance between the training and the validation set. We show that the distance characterizes the upper bound of the validation performance for any given model under certain Lipschitz conditions. (2) We develop a novel method to value individual data based on the sensitivity analysis of the class-wise Wasserstein distance. Importantly, these values can be directly obtained for free from the output of off-the- sr--the-hhelf optimization solvers when computing the distance. (3) We evaluate
data valuation framework over various use cases related to detecting loa-quality data and show that, surprisingly, the learning-agnostic feature of our framework enables a significant improvement over the state-of thettheartt performance while being orders of magnitude faster.
INTRODUCTION
Advances in machine learning (ML) crucially rely the availability of large. relevant, and high- quality datasets. However, real-world data sources often come in different sizes, relevance levels, and qualities, differing in their value for ML task. Hence, a fundamental question is how quantify the value of individual data sources. Data valuation has a wide range of use cases both within the domain of ML and beyond. It can help practitioners enhance the model performance through prioritizing high-value data sources (Ghorbani & Zou 2019), and it allows one to make strategic and economic decisions data exchange (Scelta al. 2019).
In the past literature (Ghorbani & Zou| 2019 Jia et al. 2019b Kwon & Zou 2021). data valuation is posed as a problem of equitably splitting the validation performance of given learning algorithm among the training data. Formally, given training dataset Dj = { validation dataset D.,, a learning algorithm A, and model performance metric PERF (e.g., classification accuracy). a urility function is first defined over all subsets S C DD, of the training data: USS) := PER)(A(S)). Then, the objective of data valuation is to find score vector & E R that represents the allocation to each datapoint. For instance, one simple way to value point 2; is through leave-one-out (LOO) error (D,) - (D, \ {2))), i.c., the change of model performance when the point is excluded from training. Most of the recent works have leveraged concepts originating from cooperative game theory (CGT), such as the Shapley value (Ghorbani & Zou 2019 Jia et al. 2019b), Banzhaf value (Wang
"qqual contribution. Repository publicly available on Github: http://ghhha...ommmmoxx.jjouuuuu

---

Published as a conference paper at ICLR 2023
2.22), general semivalues (Kwon & Zou 2021). and Least cores (Yan & Procaccia 2021 to value data. Like the LOO, all of these concepts are defined based on the utility function.
& Jia
Since the utility function is defined w.r.t a specific learning algorithm, the data values calculated from the utility function also depend on the learning algorithm. In practice, there are many choice points pertaining to learning algorithm, such the model to be trained, the type of learning algorithm, as well as the hyperparameters. The detailed settings of the learning algorithms are often derived from data analysis. However, in many critical applications of data valuation such as informing data acquisition priorities and designing data pricing mechanism, data needs to be valued before the actual analysis and the choice points of the learning algorithm are still undetermined at that time. This gap presents main hurdle for deploying existing data valuation schemes in the real world.
The reliance on learning algorithms also makes existing data valuation schemes difficult scale to large datasets. The exact evaluation of LOO error and CGT-based data value notions require evaluating utility functions over different subsets and each evaluation entails retraining the model on that subset: the number of retraining times is linear in the number of data points for the former, and exponential for the latter. While existing works have proposed a variety of approximation algorithms, scaling up the calculation of these notions to large datasets remains expensive. Further, approaches rely on the performance scores associated with models trained on different subsets to determine the value of data; thus, they susceptible to noise due to training stochasticity when the learning algorithm is randomized (e.g., SGD) (Wang & Jía 2022).
This work addresses these limitations by introducing framework. LAVA is able to produce efficient and useful estimates of data value in a way that is oblivious downstream learning algorithms. Our technical contributions are listed follows.
soarning-agnostir data valuation (LAVA)
Proxy for validation performance. We propose a proxy for the validation performance associated with training set based on the non-conventional class-wise Wasserstein distance (Alvarez-Melis & Fusi 2020) between the training and the validation set. The hicrarchically-definee Wasserstein distance utilizes a hybrid Euclidean- Wasserstein Enelidean-Wasserseinn cost function compare the feature-label pairs across datasets. We show that this distance characterizes the upper bound of the validation performance of any given models under certain Lipschitz conditions.
Sensitivity analyy--nnaysiss--aaa based data valuation. We develop a method to assess the value of an individual training point by analyzing the sensitivity of the particular Wasserstein distance the perturbations on the corresponding probability mass. The values can be directly obtained for free from the output of off-the-shelf optimization solvers once the Wasserstein distance is computed. As the Wasserstein distance can be solved much more efficiently with entropy regularization (Cuturi) 2013). in our experiments, we utilize the duals of the entropy-regularized program to approximate the sensitivity. Remarkably, we show that the gap between two data values under the original non-regularized Wasserstein distance can be recovered exactly from the solutions to the regularized program.
state-of-the-are performance for differentiating data quality. We evaluate LAVA over wide range of use cases, including detecting mislabeled data, backdoor attacks, poisoning attacks, noisy features, and task-irreeevant data, in which some of these are first conducted in the data valuation setting. Our results show that, surprisingly, the dearning-agnostee feature of our framework enables a significant performance improvement over existing methods, while being orders of magnitude faster.
MEASURING DATASET UTILITY VIA OPTIMAL TRANSPORT
In this section, we consider the problem of quantifying training data utility (DD)) without the knowledge of learning algorithms. Similar to most of the existing data valuation frameworks, assume access to a set of validation points D.. Our idea is inspired by recent work on using the hierarchically-defe
Wasserstein distance characterize the relatedness of two datasets (Alvarez, Melis & Fusi, 2020). Our contribution here is to apply that particular Wasserstein distance to the data valuation problem and provide a theoretical result that connects the distance validation performance of model, which might be of independent interest.
2.1 OPTIMAL TRANSPORT-BASEE DATASET DISTANCE
Background Optimal Transport (OT). OT is celebrated choice for measuring the discrepancy between probability distributions (Villami 2009). Compared to other notable dissimilarity measures
such the Kullback-Leibler Divergence (Kullback & Leibler 1951] Maximum Mean Discrepan-
2

---

Published as a conference paper at ICLR 2023
cies (MMD) (Szekely et al., 2005), the mathematically well-defined OT distance has advantageous analytical properties. For instance, OT is a distance metric, being computationally tractable and computable from finite samples (Genevay et al.
2018 Feydy et al. 2019).
The Kantorovich formulation (Kantorovich) 1942) defines the OT problem as a Lin- Pt, My over the space 2, the OT prob- lem is defined as OT(Pe, (b) = m J2a C(2, ((2,,')d((2222) 2') where [[
Program (LP). Given probability measures
= { E P(2 2) I2 (zzzz))z== = Mt, f2 ((a,z")d=" = No} denotes a collection of couplings be- tween two distributions be and My and C: 2 x 2 + R is some symmetric positive cost func- tion (with C(z, = 0) respectively. If C(2, is the Euclidean distance between z and z' ac- cording to the distance metric d. then (T( (4)) is 2-Wasserstein distance, which we denote as We(pe Pe) = Wa( MM.) == (T pe). In this work, the notation OT and W are used inter- changeably, with slight difference that we use OT to emphasize various of its formulations while W specifies on which distance metric it is computed.
Measuring Dataset Distance. We consider multi-label setting where we denote ft : X {0, fo : X - {0, 13V as the labeling functions for training and validation data, respectively, where V is the number of different labels. Given the training set D. {[I,, (I. of size N, and the of size M, one construct discrete measures [4 y) == N & ((sr.9)) and (, y) := M Ei= ((s,a))) where is Dirae function. Consider that each datapoint consists of a feature-label pair (24,8) E X x V. While the Euclidean distance naturally provides the metric to measure distance between features, the distance between labels generally lacks a definition. Consequently, we define conditional distributions (x
validation set D., {12g fx((()
[f
and (ol()))) == [ (x) Inspired by Alvarez-Melis & Fusi (020)) we measure the distance between two labels in terms of the OT distance between the conditional distributions of the features given each label. Formally, we adopt the following cost function between feature- := d(z;; z.) + (Wa(pe(-lvr) (oo())))), where 2 is weight coefficient. We note that C is a distance metric since Wa is a valid distance metric. With the definition of C, we propose to measure the distance between the training and validation sets using the non-conventional, hierarchically deffnnd Wasserstein distance between the corresponding discrete measures: We (He: po) minrem(pr...)) Zza (2,2²) da (2,2)).
label pairs: C((2t, ye), (Z)) yo))
Despite its usefulness and potentially broad applications, we note that it remains absent for existing research to explore its theoretical properties or establish applications upon this notion. This work aims to fill this gap by extending in both directions-novt analytical results are presented to provide its theoretical justifications while an original computing framework is proposed that extends its applications to a new scenario of datapoint valuation.
Computational Acceleration via Entropic Regularization. Solving the problem above scales cubically with MN,, which is prohibitive for large datasets. Entropy-regularized OT (entropy-OT) becomes a prevailing choice for approximating OT distances as it allows for fastest-known algo- rithms. Using the iterative Sinkhorn algorithm (Cuturi 2013) with almost linear time complexity and memory overhead, entropy-OT OT can be implemented on a large scale with parallel comput- ing (Genevay et al.) 2018 Feydy al. 2019). Given regularization parameter, >> O, entropy-OT can be formulated as OT (1t,,
( (b)) = minxee((m...)) Jzz C(2, x' (dT(2, +')++/ + H( (T|pr @ pw), where
dr. As + O, the dual solutions to the e-entropy- converge to its OT counterparts as long as the latter are unique (Nutz & Wiesel 2021
H (TT ll @ (b) Zz log
dr dpedaa
2.2 LOWER Class-Wise Wasserstein Distance ENTAILS BETTER VALIDATION PERFORMANCE
In this paper, we propose to use We, non-comeentional, class-wise Wasserstein distance w.r.t. the special distance function C defined in [2.] as learning-agnostic surrogate of validation performance to measure the utility of training data. Note that while Wasserstein distances have been frequently used to bound the learning performance change due to distribution drift (Courty et al.) 2017; Damodaran le al. 2018 Shen et al. 2018 Ge et al. 2021), this paper is the first to bound the performance change by the cherarchically-efine
Wasserstein distance with respect to the hybrid cost C.
Figure ! provides empirical justification for using this novel distance metric as proxy, and presents a relation between the class-wise Wasserstein distance and a model's validation performance. Each curve represents a certain dataset trained on a specific model to receive its performance. Since,
3

---

Published as a conference paper at ICLR 2023
each dataset is of different size and structure, their distances will be of different scale. Therefore, normalize the distances to the same scale to present the relation between the Wasserstein distance and model performance, which shows that despite different datasets and models, with increased distance, the validation performance decreases.
The next theorem theoretically justifies using this Wasserstein distance as a proxy for validation performance of a model. With assumptions on Lipschitzness of the downstream model as well as the labeling functions associated with the training and validation sets (as explicated in Appendix (A). we show that the discrepancy between the training and validation performance of a model is bounded by the dierarchically-der defined Wasserstein distance between the training and the validation datasets.
76
ResNetie, CI RoNNtttl EINAN-D0 GoogLeNNet STL-30
70
0.48 0.50 Normelized Wasserstein Distance
Theorem 1.
We denote ft : X + 10,13y, fo X + {0, 13 as the labeling functions for training and validation data, where V is the number of different labels. Let f f: :X - [0, 1]V be the model trained on training data. By definitions, we have that IlI(-))l, llfe(-))l, (-)l & V. Ler pt foy be the training and validation distributions, respectively, and let pee pe(-ly) and p.( be the corresponding conditional distributions given label y. Assume that the model J is e-Lipschitz and the loss function C 10, x [0,1]* 1]V + +t is k-Lipschitz in both imputs. Define cost function (-l--))),, where
Figure I: Normalized Wasserstein distance vs. model performance on different datasets and models.
between (I Yu) and (Ze: ys) C((xe, yt), (Ius vo)) == d( xx) aWalWall e is a constant. Under a certain cross- pross-Lpschitznesss assumption for fr and fo detailed Appendix AA] we have Ex)p)(s) [C(fo()), fx))] I Ez) [f(f((1), fx)) + kcWelPe, pb) + O(KV).
Proofs are deferred Appendix A The bound is interesting to interpret. The first term on the right-hand side corresponds to the training performance. In practice, when model with large enough capacity is used, this term is small. The second one the exact expression of the Wasserstein distance that we propose to use proxy for validation performance. The last error term is due to possible violation of the cross- poooss-ipschhtznesss assumption for ft and fa. This term will be small ft and fu assign the same label to close features with high probability. If the last term is small enough, it is possible to use the proposed Wasserstein distance as proxy for validation loss provided that f. ft and fo verify the cross-Lipschizz assumptions. The bound resonates with the empirical observation in Figure that with lower distance between the training and the validation data, the validation loss of the trained model decreases.
3 EFFICIENT VALUATION OF INDIVIDUAL DATAPOINTS
Note that the class-wise Wasserstein distance defined in the previous section can be used to measure the utility for subsets of DD, Given this utility function, one can potentially use existing CGs-based notions such as the Shapley value to measure the contribution of individual points. However, even approximating these notions requires evaluating the utility function on a large number of subsets, which incurs large extra computation costs. In this section, we introduce new approach to valuating individual points. Remarkably, our values can be directly obtained for free from the output of off the--hhhlf optimization solvers once the proposed Wasserstein distance between the full training and testing datasets is computed.
3.1 DATAPOINT VALUATION VIA PARAMETER SENSITIVITY
OT distance known to be insensitive to small differences while also being not robust large deviations (Villani 2021). This feature is naturally suitable for detecting abnormal datapoints- disregarding normal variations in distances between clean data while being sensitive to abnormal distances of outlying points. We propose to measure individual points' contribution based on the gradient of the OT distance to perturbations on the probability mass associated with each point.
Gradients are local information. However, unlike widely used influence functions that only hold for infinitesimal perturbation (Koh & Liang 2017), gradients for LP hold precisely in a local range and still encode partial information beyond that range, making it capable of reliably predicting the change to the OT distance due to adding or removing datapoints without the need of re-caleulation. Also, the gradients are directed information, revealing both positive and negative contributions for each
4

---

Published as a conference paper at ICLR 2023
datapoint and allowing to perform ranking of datapoints based on the gradient values. Finally, the OT distance always considers the collective effect of all datapoints in the dataset.
Leveraging the duality theorem for LP, rewrite the original OT problem (introduced in 2.1 in the equivalent form: OT(He, (b) == ( (f. (b) + [g. pr), where (2) is the set of all continuous functions, f and 9 are the dual variables. Let n and (f",g") ) be the corresponding optimal solutions to the primal and dual problems. The Strong Duality Theorem indicates that OT(x" (H4 (b)) = Of(f"" .0'f="gg))))" where the right-hand side is the distance parameterized by 14 and My. From the Sensitivity Theorem (Bertsekas) I997), we have that the gradient of the distance w.r.t. the probability mass of datapoints in the two datasets can he expressed as follows: Vp, OT( .g")
(f*)², Vp,. Of g") = (T") Note that the original formulation in 2.1 is always redundant as the constraint > (z,) =
M (=)(=() = 1 is already implied, rendering the dual solution to be non-unin non-unique. To address this issue, we first remove any one of the constraints in [[e He) and -egdegenerate. Then, we assign value of zero to the dual variable
== -
make the primal formulation corresponding to that removed primal constraint.
When measuring the gradients of the OT distance w.r.t. the probability mass of given datapoint in each dataset, we calculate the calibrated gradient as
8 (0 (p((z))
S ΣN'
Σ
fj
DOT(Pt 0po(21)
Σ
9j
(I)
1-
M-
JE(L...NNIV
JE(L...
which represents the rate of change in the OT distance w.r.t the change of the probability mass of a given datapoint along the direction ensuring the probability mass for all datapoints in the dataset always sums up to one (explicitly enforcing the removed constraint). The value of calibrated gradients is independent of the choice of selection during the constraint removal.
Datapoint valuation via calibrated gradients. The calibrated gradients predict how the OT distance changes as more probability mass is shifted to a given datapoint. This can be interpreted as a measure of the contribution of the datapoint to the OT distance. The contribution can be positive or negative, suggesting shifting more probability mass to this datapoint would result in an increase or decrease of the dataset distance, respectively. If we want a training set to match the distribution of the validation dataset, then removing datapoints with large positive gradients while increasing datapoints with large negative gradients can be expected to reduce their OT distance. As we will show later, the calibrated gradients can provide tool to detect abnormal or irrelevant data in various applications.
Radius for accurate predictions. The Linear Programming theories (Bertsimas & Tsitsiklis 1997) give that for each non degennertte optimal solution, we are always able to perturb parameters on the right-hand side of primal constraints (II p.,)) in [2.Ip in small range without affecting the optimal solution to the dual problem. When the perturbation goes beyond a certain range, the dual solution becomes primal infeasible and the optimization problem needs to be solved again. Hence, the calibrated gradients are local information and we would like to know the perturbation radius such that the optimal dual solution remains unchanged-i.e. whether this range is large enough such that the calibrated gradients can accurately predict the actual change to the OT distance. If the perturbation goes beyond this range, the prediction may become inaccurate as the dual solution only encodes partial information about the optimization.
In our evaluation, we find that this range is about 5% to 25% of the probability measure of the datapoint (=)) for perturbations in both directions and the pattern seems independent of the size of the datasets. This range being less than the probability mass of a datapoint suggests that we are only able to predict the change the OT distance for removing/adding a datapoint to the dataset approximately, though, the relative error is well acceptable (depicted in Figure
3.2 PRECISE RECOVERY OF RANKING FOR DATA VALUES OBTAINED FROM ENTROPY-OT
Due to computational advantages of the entropy-OT (defined in Eq. 2.1. one needs to resort to the solutions to entropy-OP -T to calculate data values. We quantify the deviation in the calibrated gradients caused by the entropy regularizer. This analysis provides foundations on the potential impact of the deviation on the applications built on these gradients.
Theorem 2. Let O' (.) and OTg (Je,, pv) be the original formulation and entropy penalized formulation (as defined in 2. for the OT problem between the empirical measures lht and Pe associated with the two datasets Td and DD, respectively, where [TDe] N and [D) M. Then,
5

---

Published as a conference paper at ICLR 2023
Predicted Change
Actual Change
Relative Error Change
Theoretically Accurate Prediction Rangee
Accuraa
0.4
15.0
Stelatiee Livoer (%)
0.3
Debalive Euror (%)
Change in OT
0.2
0.0
Change the
0.1
1.0
0.0
0.0
.0.0
-0.1
5.0
.0.2
...3
-1..0
0.0
50
-100 -30
Lia)
Pertarbatoon Datapoint Libi
Perturtaation Probubillit Maas (%)
(Lix)
Perturbation
1Lbb
Perturbation
Probubiiity Mass (%)
Probsbility Mass (S)
Probabiiity Mass (9)
Figure 2: Predicting the change to the OT distance for increasing/reducing the probability mass of a point. The OT distance is calculated between two subsets of CIFAR-I0. We examine the change to the OT distance predicted by the calibrated gradients against the actual change. The results of two datapoints are visualized for demonstration (I.())(b) and II. (a)(bb) are analyzed on datapoint #1 and #2, respectively). The probability mass of the datapoint is perturbed from -000% (removing the datapoint) 100% (duplicating the datapoint). I.(a) and (a): Predicted change on the OT distance against the actual change. The predicted change demonstrated high consistency to the actual change despite minor deviation for large perturbation. I.(b) and Il.(b): Relative error for the prediction, defined as (predicted __caaneeeee_____ actual Laaeaall_haggeeae -chaagee/acctaal __calggehexx___- 100%. The color bar represents the theoretical range of perturbation where the change in the OT distance can be accurately predicted. The prediction holds approximately well beyond the range.
for any i i k {1, (1,2...., NY and o # #p + E {1, }, the difference between the calibrated gradients for two datapoints 2; and 2ę in dataset D. and the difference for 2/1 and 2/ in De can be calculated as
a OTT(M, po) 00T(p.. (OT,))
N
1
(2)
pp(()) a (p(x)))
① (p)(
- N
(Tz)
(
@OT(Hr, @ (MTG(Me,
(OT,(HI,
(3)
(pp( 0pe(=))
(p)(z))
(pp))z))
M
(Tt)
( po
where nh is the optimal primal solution to the entropy penalized OT problem defined 2.1 datapoint in D; other than or Zk, and z is any datapoint in D. other than z,p or 2/z.
2g is any
The gradient difference on the left-hand side (2 represents the groundtruth value difference between two training points 2; and 25 as the values are calculated based on the original OT formulation. In practice, for the sake of efficiency, one only solves the regularized formulation instead and, therefore, this groundtruth difference cannot be obtained directly. Theorem 2 nevertheless indicates a very interesting fact that one can calculate the groundtruth difference based on the solutions to the regularized problem, because every term in the right-ham side only depends on the solutions the regularized problem. Particularly, the groundtruth value difference is equal to the value difference produced by the regularized solutions plus some calibration terms that scale with e (Nutz. & Wiesel 2021). This result indicates that while it is not possible to obtain individual groundtruth value by solving the regularized problem, one can actually exactly recover the groundtruth value difference based on the regularized solutions. In many applications of data valuation such as data selection, it is the order of data values that matters (Kwon & Zou 2021). For instance, to filter out low- -ualllllty data, would first rank the datapoints based on their values and then throw the points with lowest values. In these applications, solving the intropy-regularized program is an ideal choice- which is both efficient and recovers the exact ranking of datapoiit values. Finally, note that Eq, 3 presents symmetric result for the calibrated gradients for validation data. In our experiments, we set e = 0.1. rendering the corresponding calibration terms to be negligible. As a result, we can directly use the calibrated gradients solved by the regularized program to rank datapoint values.
EXPERIMENTS
In this section, we demonstrate the practical efficacy and efficiency LAVA on various classification datasets. We compare with nine baselines: (1) Influence functions (INF) (Koh & Liang (017). which approximates the LOO error with first-order extrapolation; (2) TracIn-Clest (Pruthi et al. 2020), which accumulates the loss change validation data during training whenever the training point of interest is sampled; (3) TracIn-Self (Pruthi et al. 2020), which is similar to TracIn-Clus Clean but accumulates the training loss changes; (4) KNN-Shapley (KNN-SV) (Tia et al. 2019a). which

---

Published as a conference paper at ICLR 2023
LAVA INF
KNN SV
TracIn Self
Tracin Clean
Random
Backdoor Detection (5%)
Poison Detection (0.1%)
Noisy Features (25%)
Noisy Labels (25%)
Detectin Rate
0.9
Detection Eate
0.9
0.8
0.0
0.6
0L6
0.4
0.
04
04
022
022
02-
02
25000
50000
Ranking
Ranking
Ranking
Ranking
Attack Suerzss Rato (5))
AMtsccc Confiiencee (3)
100
I0
80
Model Accurtcyy
Mode: Accurncy
70-
60
60
20
60
20
80
20
12500
25000
12500
25000
12550
2500n
12500
25000
1/b)
TTrrown Data
11.1b)
Thrown Data
Throwe
[V.bb)
Thrown Deta
Figure 3: Performance comparison between LAVA and baselines various cases. For L(b), depict the Attack Accuracy, where lower value indicates more effective detection. For II.(b), we depict the Attack Confidence, lower confidence indicates better poison removal. For III. and IV.(b), we show the model test accuracy, where higher accuracy means effective data removal.
proxy model; and (5) Random, setting where we select a random subset from the target dataset. We also consider the popular data
approximates the Shapley value using "Nearest-Neightee
valuation approaches: (6) Permutation Sampling-bast based Shapely value (Perm-SV) (Jia et al. 2019b),
(7) Least Cores (LC) (Yan & Procaccial 2021). (8) TMC-Shapley (TMC-SV) and (9) G- G-Shapley (G-SV) (Ghorbani & Zou| 2019). Basclines (6)-(9) are, however, computationally infeasible for the scale of data that we study here. So we exclude them from the evaluation of efficacy in different cases. We also provide detailed runtime comparison of all baselines. For all methods to be compared, a validation set of 10, 000 samples is assumed. For our method, we first use the validation data to train a deep neural network model Net (He al. 2016) from scratch for feature extraction. Then, from its output, we compute the class-wise wise Wasserstein distance and the calibrated gradients for data valuation. Details about datasets, models, hyperparameter settings, and ablation studies of the hyperparameters and validation sizes are provided in Appendix B
We evaluate on five different use cases of data valuation: detecting backdoor attack, poisoning attack, noisy features, mislabeled data, and irrelevant data. The first four are conventional tasks in the literature and the last one is a new case. All of them have a common goal of identifying "low- low-quality" training points. To achieve this goal, we rank datapoints in ascending order of their values and remove some number of points with lowest data values. For each removal budget, we calculate the detection rate, i.c., the percentage of the points that are truly bad within the removed points.
Backdoor Attack Detection. A popular technique of introducing backdoors to models is by injecting maliciously constructed data into training set (Zeng et al.) 2021). At test time, any trained model would misclassify inputs patched with a backdoor trigger as the adversarially-deinee target class. In the main text, consider the Trojan Square attack, a popular attack algorithm (Liu al.. (017). which injects training points that contain a backdoor trigger and are relabeled as a target class. The evaluation of other types of backdoor attacks can be found in Appendix B To simulate this attack, we select the target attack class Airplane and poison 2500 (5%) samples of the total CIFAR- 10 training set (50k) with square trigger. In Figure 3 (.))), we compare the detection rates of different data valuation methods. LAVA and TracIn-Clean outperform the others by a large margin. In particular, for LAVA, the first 20% of the points that it removes contain at least 80% of the poisoned data. We also evaluate whether the model trained after the removal still suffers from the backdoor vulnerability. To perform this evaluation, we calculate the attack accuracy, i.e., the accuracy of the model trained on the remaining points to predict backdoored examples as the target label. A successful data removal would yield a lower attack accuracy. Figure 3 [.(b) shows that our method already takes effect in the early stages, whereas other baselines can start defending from the attack only after removing 13, 000 samples. The efficacy of LAVA is in part attributable to inspection of distances between both features and labels. The backdoored training samples that are poisoned the target class will be
7

---

Published as a conference paper at ICLR 2023
"unnatural" in that class, i.e., they have a large feature distance from the original samples in the target class. While the poisoned examples contain a small feature perturbation compared to the natural examples from some other classes, their label distance to them is large because their labels are altered.
Poisoning Attack Detection. Poisoning attacks are similar to backdoor attacks in the sense that they both inject adversarial points into the training set to manipulate the prediction of certain test examples. However, poisoning attacks are considered unable to control test examples. We consider popular attack termed "feature-collision" attack (Shafahi et al. 2018), where we select target sample from the Cat class test set and blend the selected image with the chosen target class training samples, Frog our case. In this attack, we do not modify labels and blend the Cat image only into 50 (0.1%) samples of Frog, which makes this attack especially hard to detect. During inference time, we expect the attacked model to consistently classify the chosen Cat as Frog. In Figure 3 (a), we observe that LAVA outperforms all baselines and achieves an 80% detection rate by removing only 11k samples, which is around 60% fewer samples than the highest baseline. Figure 3 (l.(b) shows that by removing data according to LAVA ranking, the target model has reduced the confidence of predicting the target Cat sample as a Frog to below 40%. Our technique leverages the fact that the features from a different class are mixed with the features of the poisoned class, which increases the feature distance between the poisoned and non non- non-poisoned Frog examples.
Noisy Feature Detection. While adding small Gaussian noises to training samples may benefit model robustness (Rusak et al., 2020), strong noise, such as due to sensor failure, can significantly affect the model performance. We add strong white noise 25% of all CIFAR-10 dataset without changing any labels. Our method performs extremely well as shown in Figure 3 III. and detects all 12,500 noisy samples by inspecting less than 15,000 samples. This explains the sudden drop of the model's 's accuracy at the removal budget of 15,000 samples in Figure 3 (b): the model starts
throwing away only clean samples from that point. LAVA performs well in this scenario since the strong noise increases the feature distance significantly.
Mislabeled Data Detection. Due to the prevalence of human labeling er- rors (Karimi et al. 2020). it is cru- cial to detect mislabeled samples. We shuffle labels of 25% samples in the CIFAR-10 10 dataset to random classes. Unlike backdoor and poisoning at- tacks, this case especially harder to detect since wrong samples are spread out throughout classes instead of all placed inside a target class, However, as shown in Figure (a), LAVA'S 's detection rate outperforms other base-
Correctly Derected
Wrongly Detected
Deal peisoree into "truc'
08
V3.22%
46
0.
'ruck"
bbuck
po powedd 'dgg clos
46.5%%
Normslzed didance map
Ving
"doog
dogf
Figure 4: Left: Heatmap of inter-class distance of CIFAR-10 10. Right: Examples of irrelevant data. The detection rates of first 500 inspected images are 94% and 46% for -ruckT Cat- respectively.
lines and the model performance maintained even after 20k of removed data (Figure IV.(b)).
Irrelevant Data Detection. Often the collected datasets through web scraping have irrelevant samples in given classes (Northeutt et al. 202T [Tsipras et al. 2020), e.g., in a class of Glasses, we might have both water glass and eyeglasses due to lack of proper inspection or class meaning specification. This case is different from the mislabeled data scenario, in which case the training features are all relevant to the task. Since the irrelevant examples are highly likely to have completely different features than the desired class representation, LAVA expected to detect these examples. We design an experiment where we remove all images of one specific class from the classification output but split them equally to the other remaining classes as irrelevant images. As shown in Figure 4 the detection result over a class varies based the distance between that class and the class from which irrelevant images drawn. For instance, when Deer images are placed into the Truck class, we can detect almost 94% of all Deer images within first 500 removed images. On the other hand, when we place Cat images into dog class, our detection rate drops to 45% within the top 500.
Computational Efficiency. So far, we have focused on the method's performance without considering the actual runtime. We compare the runtime-pent ountine-performnnee performance tradeoff on the CIFAR-10 10 example of 2000 samples with 10% backdoor data, a scale in which every baseline can be executed in a reasonable time. As shown in Figure 3 our method achieves a significant improvement in efficiency while being able to detect bad data more effectively.
8

---

Published as a conference paper at ICLR 2023
Dependence on Validation Data Size. For current experiments, we have assumed the validation set of size 10K. Such a scale of data is not hard to acquire, as one can get high-quality data from crowdsourcing platforms, such as Amazon Mechanical Turk for $12 per each 1K samples (AWS) 2019). While our method achieves remarkable performance when using 10K validation data, we perform ablation study on much smaller sets (Appendix [B.2.T), where LAVA, notably, can still outperform other baselines. As an example on mislabeled data detection, our method with 2K validation data achieves 80% detection rate at data removal budget of 25K (Fig. D. whereas the best performing baseline achieves such a performance with 5 times bigger validation data, 10K (Fig. B (a)). Furthermore, even on a tiny validation set of size 500, LAVA consistently outperforms all the baselines with the same validation size (Fig. [T). This shows that our method remains effective performance for various sizes of validation data.
5 RELATED WORK
Existing data valuation methods include LOO and influence function (Koh & Liang 2017). the Shap-
LAWA
INF Pins-sV
KNK SV TNU-SV
Tracla S4I GSV
Toxlla Clenn 100
ley value (Tia et al. Ghorbani & Zou 2019
1.0
Wang & Jia 2023),
). the Banzhaf value (Wang ang &
Dedecttion Brvar
0.01
Jia 2022).. Least Cores (Yan & Procaccia 2021).
0.4
Beta Shapley (Kwon & Zou 2021), and reinforce-
x
0.2
ment learning-based method (Yoon et al. 2020)
However, they all assume the knowledge of the underlying learning algorithms and suffer large computational complexity. The work of Jia et al.) (2019a) has proposed to use K-Nearest Neighbor Classifier a default proxy model to perform data valuation. While it can be thought of as learning- agnostic data valuation method, it is not effective and efficient as method in distinguishing data quality. Xu et al. (2021) propose to use the volume to measure the utility of a dataset. Volume is agnostic to learning algorithms and easy to caleulate because is defined simply the square root of the trace of feature matrix inner product. However, the sole dependence on features makes it incapable of detecting bad data caused by labeling errors. Moreover, to evaluate the contribution of individual points, the authors propose to resort to the Shapley value, which would still be expensive for large datasets.
10"
101
10"
10'
Clockcc Time Min
Figure 5: Runtime v.s. Detection Error compari- son between LAVA and baselines on inspecting 2000 samples from CIFAR-10 with 10% back- door data.
6 DISCUSSION AND OUTLOOK
This paper describes a learning-agnose data valuation framework. In particular, in contrast to existing methods which typically adopt model validation performance as the utility function, we approximate the utility of dataset based on its class-wise Wasserstein distance to given validation set and provide theoretical justification for this approximation. Furthermore, we propose to use the calibrated gradients of the OT distance to value individual datapoints, which can be obtained for free one uses an off- fff-the-shelf solver to calculate the Wasserstein distance. Importantly, we have tested on various datasets, and our LAVA framework can significantly improve the state-of-the-art performance of using data valuation methods to detect bad data while being substantially more efficient. Due to the stochasticity of ML and the inherent tolerance to noise, it is often challenging to identify low-quality data by inspecting their influence on model performance scores. The take-away from our empirical study is that despite being extensively adopted in the past, low-quality data detection through model performance changes is actually suboptimal; lifting the dependence of data valuation on the actual learning process provides a better pathway to distinguish data quality.
Despite the performance and efficiency improvement, our work still has some limitations. As result, opens up many new investigation venues: (1) How to further lift the dependence on validation data? While validation set representative of the downstream learning task is common assumption in the ML literature, it may or may not be available during data exchange. (2) Our design could be vulnerable to existing poisons that directly indirectly minimize the similarity to clean data (Huang) et al. 2021 Pan et al. 2022). Further investigation into robust data valuation would be intriguing. (3) Our current method does not have enough flexibility for tasks that aim for goals beyond accuracy, e.g., fairness. Folding other learning goals in is an exciting direction. (4) Customizing the framework to natural language data is also of practical interest.
9

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENTS
RJ and the ReDS Lab gratefully acknowledge the support from the Cisco Research Award, the Virginia Tech COE Fellowship, and the NSF CAREER Award. Jiachen T. Wang is supported by Princeton's 's Gordon Y. S. Wu Fellowship. YZ is supported by the Amazon Fellowship.
REFERENCES
David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21428 -22422191,,, 2020.
Amazon Web Services Inc. AWS. Amazon sagemaker data labeling pricing, 2019. Retrieved September 28, 2022, from
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334 334, 1997.
Dimitris Bertsimas and John Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526. 2017.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. Advances in Neural Information Processing Systems, 30, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Proceedings of the European Conference Computer Vision (ECCV), pp. 447-463, 2018
Jean Feydy, Thibault Séjourné, Trançois-Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorm divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2681-2690. PMLR, 2019.
Zheng Ge, Songtao Liu, Zeming Li, Osamu Yoshie, and Jian Sun. Ota: Optimal transport assignment for object detection. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 303-312, 2021.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn di- vergences. In International Conference on Artificial Intelligence and Statistics, pp. 1608-1617.
PMLR, 2018
Amirata Ghorbani and James Zou, Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pp. 2242-2251. PMLR, 2019.
Charles Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchann Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis F. Oliphant. Array programming with NumPy. Nature, 585(7725) September 2020. doi: 10. 10.10388441566-00--6644 020 2649-2
URL
1038
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 635. Springer, 2016.
Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani. James Bailey, and Yisen Wang. Unlearnable examples: Making personal data unexploitable. arXiv preprint 101.:220 2021.
10

---

Published as a conference paper at ICLR 2023
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient sask-specific data valuation for nearest neighbor algorithms. arXiv preprint arXiv:1908.0880 2019a.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019b.
Leonid Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, pp. 199-201, 1942.
Davood Karimi, Haoran Dou, Simon K Warfield, and Ali Gholipour. Deep learning with noisy labels: Exploring techniques and remedies in medical image analysis. Medical Image Analysis, 65:101759, 2020.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1883-1894. PMLR, 2017.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathemati- cal statistics, 22(1):79 86, 1951.
Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation framework for machine learning. arXiv preprint arXiv:2110.14049 2021.
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. 2017.
Curtis G Northeutt, Anish Athalye, and Jonas Mueller. Pervasive label errors in test sets destabilize machine learning benchmarks. arXiv preprint arXiv:2103. 14749, 2021.
Marcel Nutz and Johannes Wiesel. Entropic optimal transport: Convergence of potentials. Probability
Theory and Related Fields, pp. 1-24, 2021.
Minzhou Pan, Yi Zeng, Hoang Anh Just, Lingjuan Lyu, Meikang Qiu, and Ruoxi Jia. Narcissus: A practical clean-label backdoor attack with limited information. arXiv preprint arXiv:2204.0522 055555 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035, Curran Associates, Inc., 2019. URL http:////hhpppppppppec.aaaaaaaa.
pdf
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33: 19920-19930, 2020.
Evgenia Rusak, Lukas Schott, Roland S Zimmermann, Julian Bitterwolf, Oliver Bringmann, Matthias Bethge, and Wieland Brendel. A simple way make neural networks robust against diverse image corruptions. In European Conference on Computer Vision, pp. 53-69. Springer, 2020.
Gabe Scelta, Hamid Rashid, Hoi Wai Jackie Cheng, Marcelo LaFleur, Mariangela Parra-Laccourt, Alex Julca, Nicole Hunt, S. Islam, and Hiroshi Kawamura. Frontier technology quarterly january 2019: Data economy radical transformation or dystopia? 01 2019.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference Learning Representations, 2018

---

Published as a conference paper at ICLR 2023
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. Advances in neural information processing systems, 31, 2018.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Gabor J Szekely, Maria L. Rizzo, al. Hierarchical clustering via joint between-within distances: Extending ward's minimum variance method. Journal of classification, 22(2):151-184, 2005.
Nguyen Thai-Nghe, Andre Busche, and Lars Schmidt- Thieme. Improving academic performance prediction by dealing with class imbalance. In 2009 Ninth international conference on intelligent systems design and applications, pp. 878 883. IEEE, 2009.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Andrew Ilyas, and Aleksander Madry, From imagenet to image classification: Contextualizing progress on benchmarks. In International Conference on Machine Learning, pp. 9625-9635. PMLR, 2020.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Jiachen T Wang and Ruoxi Jia. A note on" towards efficient data valuation based on the shapley value". arXiv preprint arXiv:2302.11431, 2023.
Tianhao Wang and Ruoxi Jia. Data banzhaf: data valuation framework with maximal robustness to learning stochasticity. arXiv preprint arXiv:2205. /5466, 2022.
Xinyi Xu, Zhaoxuan Wu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Validation free and replication robust volume-base bllume-based data valuation. Advances Neural Information Processing Systems, 34, 2021.
Tom Yan and Ariel D Procaccia. If you like shapley then you'll love the core. In Proceedings the AAAI Conference on Artificial Intelligence, volume 35, pp. 5751-5759, 2021.
Jinsung Yoon, Sercan Arik, and Tomas Pfister. Data valuation using reinforcement learning. In International Conference on Machine Learning, pp. 10842-10851. PMLR, 2020.
Yi Zeng, Si Chen, Won Park, Zhuoqing Mao, Ming Jin, and Ruoxi Jia. Adversarial unlearning of backdoors via implicit hypergradient. In International Conference on Learning Representations, 2021.
12

---

Published as a conference paper at ICLR 2023
APPENDIX A RESTATEMENT OF THEOREMS AND FULL PROOFS
In this section, we will restate our main results and give full proofs.
A.1 SUMMARY OF NOTATIONS
Let Ptx py be the training distribution and validation distribution, respectively. denote St X + {0, 1, fe X' {0, 13 the labeling functions for training and validation data, where V is the number of different labels. We can then denote the joint distribution of random data- label pairs (ar, f((x))==p, and (x, (o(x))=~aola as 5 and pbr, respectively, which are the same notations 14, and pa but made with explicit dependence distributions of (F((T))=<pe((t) (fo(z)) (x())))ppp(() (x) are denoted as Pfo respectively. Besides, we fr())
Js and for clarity. The
define conditional distributions (x(())y) = T (x)) (x))) and pr (xll)) == |n(2)] (a) (f Let f X [0, 1 be the model trained on training data and L {0, 1) 10. R be the loss function. We denote E [[(,, (12) as coupling between a pair of distributions μr, P22 and d X X' + as a distance metric function.
The 1- I-Wasserstein distance with respect to distance function d between two distributions fl. M2 [d(x,y), More generally, the I-Wasserstein
defined as Wa(Mi, == inf (lf(e)0()) (a.a)~
distance with respect to cost function C defined as Wc(P1, == inf (nf.ee(()).)))) (x.y)on
E [C(x, v)].
A.2 STATEMENT OF ASSUMPTIONS
To prove Theorem T need the concept of probabilistic cross-Liipschizznsss, which assumes that two labeling functions should produce consistent labels with high probability on two close instances.
Definition 3 (Probabilistic Ctoss-Lipschitzness). Two labeling functions ft : X' {0, 13 and fo X 13, are probbbbibaiiiiitttcccc cross-Lipschitz w.r.t. a joint distribution x over X x X if for all c > 0:
(en=2)>==l((((())) - - (x22) ed(z1, S
Intuitively, given labeling functions fer fo and coupling æ, bound the probability of finding pairs of training and validation instances labelled differently in a (1/e)-ball with respect to x.
Our Assumptions. Assuming that f is an e-Lipschitz function. Given a metric function d(;;),, we define cost function C between (Ia,, Mt) and (I Uv)
C((21. Vo), (Ie, Ue)) == xx)) + cW cWa (Wa(p((-lve) pe (-lu))))
(5)
where c is a constant. Let 2 be the coupling between ult uer such that
arg inf (e(arraa) (C(( ve), (Iv. vo)))]- (u
(6)
We define couplings π and #* between pe(x), (x) as follows:
1 T (Tr, Me)) dyndy..
n (" x.),
(7)
For 7""" we first need to define coupling between Hs. Mse:
Th Uo) = / (i vc), (Iv. Hol) dx,
(8)
13

---

Published as a conference paper at ICLR 2023
and another coupling between pu p!:: 2, (( ye), (Iis vo)) (,,
(9)
Finally, H" is constructed as follows:
Te (2,, x.) = J (ye yo (o (e)) (z yo) dy:
(10)
It is easy to see that all joint distributions defined above are couplings between the corresponding distribution pairs.
We assume that ft, fo are (cte proobabiiiiiiii cross-Lipschit, with respect to मt' in metric d. Additionally, we assume that Ctu/c and the loss function C is k-Lipschitz in both inputs. Besides, from their definitions above, we have that [I(( [[]r()))], fo (z))l S V.
The assumption of probabilistic cross-Lipschitzness would violated only when the underlying coupling assigns large probability to pairs of 1 -bll) but labeled differently. However, 7 is generally not such a coupling. Note that i is the optimal coupling between training and validation distributions that minimizes cost function C pertaining to both feature and label space. Hence, Ty (Vt, yv), the marginal distribution of x over the training and validation label space, tends to assign high probability to those label pairs that agree. On the other hand, म can be thought of as a coupling that first generates training-vale validation labels from my and then generates the features in each dataset conditioning on the corresponding labels. Hence, the marginal distribution T' of criiiingvaaldatioon feature pairs generated by # would assign high likelihood to those features with the same labels. So, conceptually, the probabilistic Lisshiipsshss assumption should be easily satisfied by n².
features that are close enough (within
A.3 DETAILED PROOF
Theorem (restated). Given the above assumptions, we have
E (x) (x) [(() (x) [C(f((z), + keWelud', .nf)) + 26V 8
(11)
Proof.
(
(12)
= Bown. (2(f((z), - (ew (orm ([(())))
(13)
< (x) (((f)t)))) ([f. -E
(14)
We bound (eepntte)
E (z)) as follows:
E Exnas (C(f(()) Ez (C(
(15)
Usee [CCSC(E)), -(](()
(16)
1/e (CCK(())-ffo))----ddooffee------ f(x.) ((f()))) f(x)) du (a+, xc)
(17)
(18)
x2
+
((())))))))
(19)
U2
where the last inequality is due triangle inequality.
14

---

Published as a conference paper at ICLR 2023
Now, we bound U1 and U2 separately. For U1, we have
U1 S k / [lf(ze) f(x))l dn (x))
(20)
I ke / (o) do (1ee
(21)
where both inequalities are due to Lipschitzness of L and f. In order bound U2, we first recall that (36, vo) Sx fx ma Me), (e)) dæ, and Tz.g ((I,, Be): (Z vo)) Ty (yr, (1
Observe that
U2 = Jre. Jyx (((c(E)) - [(fe())), dr ((r,, Ue), (F),
(22)
[ xx
/ [(yo - C(ut, f (x+)) dr (1r,, ( ue), (Zo: vo))
(23)
$ ko 1/2 Jxc 11ve -vll d (Crre yc), (e..yo))
(24)
k 11y. vell (T)
(25)
where the second equality is due to a condition that if * fe(xt) or yo # fo(xx), then Ty (122, ye), (Ze, vo))
Now we can bound U2 as follows:
U2 S yyz 11 Vel d yo)
(26)
I xxa I llye yell ( Me). yo))
(27)
[ ya x2 [1So(1r)) - fe(xz))l di ((r), B1), (N Wo)),
(28)
where the last step holds since if yt # fe(xr) or yo # fo( then मे (x,, vt), (x), = 0. Define the region A = [(x,,,,) (lf((z)) f((x:))l cood x.) x.)}. then
1:
2 xx 115o(1.) fe(x;))l ( (IV:
(29)
Sy f (1fo(x.) fe(xx))l di (are, Me), (o))
(30)
(15((x)) - (e(x))) di ve), (o)s
(31)
[ 2V (0n yt), (Ko,
(32)
XMx
/ / (1 fe(x:e)l di ( vt), yo)).
(33)
Let's define fe(xx) = fe( and Fo(x,) = fo())) (Ke, E A, and Fe(x)) = F. =
otherwise (note that [l.)(a.)) - f((x))) S E(o,, x.) for all (I,, x.) E X2), then we can bound the second term as follows:
15

---

Published as a conference paper at ICLR 2023
y2 J (1((z))) - f((1))) di ((Fe, ve), (Fo)
(34)
[ drg yo) [1f((1))) fe(xa)ll du (e
(35)
k [ dug 9o) S [(o(0 - fi(oo) dee(tslu)dd
(36)
/ ya dr Mo) (eans - (eecm.
k
(37)
< keto [ dry (v. W.) Mo(-
(38)
Inequality 38 is consequence of the duality form of the Gantorovich-Rubinstie theorem Villani (202T). Chapter 1).
Combining two parts, we have
U2 525k3 J / x21A
2V dif d (Zv. vc))
(39)
+ kō ( d yo) Waluee(-lla Mo (-
(40)
$ 2kV 8eu + ket [ dr uo Wa(e((lee))) (o(l)))),
(41)
where the last step is due to the probabilistic cross-Lipschitznsss of fi, fo with respect to "i.y Now, combining the bound for U1 and U2. we have
E Expas (x) (Lf.
(x f(x))
(42)
((1), 2kV 8ew kewo [ drg Uo) (a)) u.
I ke
(43)
x2
( J(xxxy (ed(z,, v.) + ev Wa(ku Mu (-b+0)) do ((x,, vr), (1v, v.)) + 2&V
= k
(44)
Sk
Jucwy (ed( wewaa p (- d (( Bt), (F), v.)) + 2kV 6.v
(45)
-keEn;, [C((1e.))) (Iv, vo))l + 2 keWolug (e!") 2
(46)
(47)
where the last step is due to the definition of Tyy This leads to the final conclusion.
Theorem 5 (restated), Let OT(H, po) and OTg (pr,pe) be the original formulation and entropy penalized formulation (as defined in Subsection 2.1 for the OT problem between the empirical measures and Pa associated with the two data sets D; and D... respectively. Then, for any i * # k (..2,...N) and + # q (1,2,..M the difference between the calibrated gradients for two datapoints 2; and 2 in dataset D, and the difference for zn and zl in D, can be
calculated as
a 00 (z)()))
(0.. 0 a0T(H,; (z()
80Te(pe.po) (p.)
N
1
2 Qp(())
N
(TT))K)
( kj
aOT(pe, a0T(H1; pp.())))
a0T ppe()))
(2()))
(z)
M
(m))
( Dop
where n. is the optimal primal solution to the entropy penalized OT problem, 2j is any datapoint in Dj other than or Zk. zo is any datapoint in D, other than z or z/p [D,] N. and [D,] M.
16

---

Published as a conference paper at ICLR 2023
Proof. Let f.9) and Ce fe. be the Lagrangian functions for original formulation and entropy penalized formulation between the datasets D, and D,, respectively, which can be written as
N
M
f(T, = (T, + fi ( IN - a;) +
Σ
(1's T. - -b));
1=1
==1
(Te)
L (T(Te: (Te, +
log
+
Σ (fe)s [(Te)i 1M -
1Mm((()))) (x(2)))
(r(zz))
Mh (2,)
(ge) [N (me)s m,(2,)) Σ
where e x is the cost matrix consisting of distances between N datapoints in Dr and M datapoints in D., IN = (1,I,...1) E Nx1 and ls = (1, (I.,...11) E RRXM я and (f.g) denote the primal and dual variables, and n. and n, denote the jth row and j column matrix æ, respectively.
The first-order necessary condition for optima in Lagrangian Multiplier Theorem
gives that
ff =0 and ((CE),((T)) (fa)", (9=)")= =0
where x" and (f""g") denote the optimal solutions to the primal and dual problems, respectively. Thus, for any i E (1,2, ......N... and j E {1,2.... ..,)).................. we have
VL=(=" f " )ig ojj SI + 9
1
(F = cy + (xt)
(Se)t (ge) 0.
Subtracting, we have
ff (ff) + [o] (gc) -E
0.
(1)))
Then, for vk Fi (1,2, N). have
1 = 0.
[f (fe)il + [o] (9+) E.
(TT)
Subtracting and reorganizing, we get
[(ft] - (fe) = (ft - ft) - E.
(Tz)
(x²
From the definition of the calibrated gradients in [ we have
a O
00T(pi Ope(zx)
N
(fi f(),
0pr(zz)
a 00T, (M)) (14(2;
2 OOT:(Mr Op((zk)
N
((E)] (f=)il-
N
Finally, subtracting and reorganizing, we have
@OT.(pr. @0Te(pe.H)) aOT(He, OOT(M, Hw) @pe(zz)
8. N
1
@pt(2z) @p)()x)
(p:)
N - [
(
The proof for the second part of the Theorem is similar.
a @OTe(He (0T.(H 0pm()))
(
aOT(Pr
M
0pm(2))
0p.(2z)
O. (2)))
M
( Dop
Then the proof is complete.
17

---

Published as a conference paper at ICLR 2023
APPENDIX B ADDITIONAL EXPERIMENTAL RESULTS
B.I EVALUATING DATA VALUATION USE CASES ON DIVERSE DATASETS
In the main text, we have focused our evaluation on CIFAR-10. Here, we provide experiments show ef- fectiveness of LAVA on diverse datasets for detecting bad data.
LAWA INF
KNN-SV Truclu Selt
Tracin-Clea
Random
Selected Poppes
2.0
P.. Solkted Patone
2.0
0.0
6.0
Backdoor Attack Detection. We evaluate another type of backdoor attack (Section F which is the Hello Kitty blending attack (Blend) (Chen et al.) (017)) that mixes the target class sample with the Hello Kitty image, as illus- trated in Figure (B). We attack the German Traffic Sign dataset (GTSRB) on the target class by poisoning 1764 (5%) samples of the whole dataset. Our method achieves the highest detection rate, as shown in Figure a].. In particular, the 5000 points with lowest data values contain all poisoned data based on the LAVA data values, while the second best method on this task, KNN-SV, can cover all poisoned examples with around 1 1,000 samples. Our algorithm performs especially well for this attack, since the label of poisoned data is changed to the target class and the patching trigger is large. Both the label and feature changes contribute to the increase of the OT distance and thus case the detection.
0.2
0.2
0.0
0.0
(a))
Data Value Racking
(b)
Vilue Ranking
80000
Figure 6: (a) Blend backdoor attack de- tection on GTSRB dataset. Comparison with baselines. (b) Noisy feature detec- tion on the digit MNIST dataset. Com- parison with baselines.
Class
Identified Inrelvvnnt Data Examples
Noisy Feature Detection. Here, we show the usage of LAVA on the MNIST dataset where 25% of the whole dataset is contaminated by feature noise. Our method still outperforms all the baselines by detecting all noisy data within first 14,000 samples, which is 5,000 less than the best baseline would require, which is shown in Figure bb).
Irrelevant Data. We perform another irrelevant data detection experiment and focus on the CIFAR 100 dataset. In Figure 7 we illustrate some of the irrelevant samples detected by LAVA. Intuitively, irrelevant data in the class should be easily detected by LAVA, since the images are far from the representative of the class and increasing the probability mass associated with these images leads to larger distributional distance to the clean validation data.
Figure 7: Visualization of irrelevant data detection within the CIFAR 100 dataset. The left column is one example of the target class and the images on the right columns are selected irrelevant data in the corresponding classes detected by LAVA.
B.2 ABLATION STUDY
We perform an ablation study on validation size and on the hyperparameters in our method, where we provide insights on the impact of setting changes. We use the mislabeled detection use case and the CIFAR-10 dataset as an example setting for the ablation study.
Figure 8: Visualization of each backdoor
attack: A) Trojan-SQ attack. B) Blend attack. C) Trojan-WM attack.
B.2.1 VALIDATION SIZE
For all the experiments in the main text, we use the validation set of size 10,000. Naturally, we want to examine the effect of the size of the validation set on the detection rate mislabeled data. In Figure 9 (c). illustrate the performance
the detection rate with smaller validation data sizes: 200, 500, 2, 000, and 5, 000. We observe that even reducing the validation set by half to 5, 000 can largely maintain the detection rate performance. Small validation sets (200, 500, 2, 000) degrade the detection rate by more than 50%. Despite the performance degradation, our detection performance with these small validation sizes is in fact comparable with the baselines in Figure 3 (V. that
18

---

Published as a conference paper at ICLR 2023
Pet. Selected Polcons
1.0
Seleated Polsocts
1.0
Pet. Sclected Poisons
7.0
0.8
0.8
36
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
(a)
(b)
(c)
Value Ranking
Ranking
Ranking
Figure 9: (a) Comparison between different feature weights on the performance of mislabeled data in CIFAR-10. (b) Comparison between different label weights on the performance of mislabeled data in CIFAR-10 10. (c) Comparison between different validation sizes on inspecting 50k samples from CIFAR-10 10 with 25% mislabeled data.
leverage the full validation size of 10, 000. Additionally, when restricting LAVA and other baselines validation set of 500 samples, our method is better than the best baseline for detecting mislabeled data in the 50k CIFAR- 10 samples with 25% being mislabeled as shown in Figure
B.2.2 FEATURE WEIGHT
Recall the class-wise Wasserstein distance is defined with respect the following distance metric: C(( Wr), (M)) = (x T.) + Mo (-lu))))) Actually, one can change the relative weight between feature distance d(z,, zyy)) and the label distance Wa(pr(-lsx) (4 (-lv))) Here, show the effect of upweighting the feature distance, while keeping the label weight at 1 and the results illustrated in Figure ( uniform weight, the performance on detection rate is decreasing with larger feature weights. With feature weight of 100, performs similarly as the random detector. Indeed, as we increase weight on the features, the weight on the label distance is decreased. As the weight reaches 100, our method performs similarly as the feature embedder without knowing label information and hence, the mislabeled detection performance is comparable to the random baseline.
PreActResNet18
VGG16
ResNet18
Random
1.0
(a). As
moving away from
0.6
method
0.2
Ranking
Comparison be- tween different feature embed- der architectures on inspecting 50k samples from CIFAR-10 10 with 25% mislabeled data.
Figure 10:
B.2.3 LABEL WEIGHT
Next, we shift focus to label weight. We examine the effect upweighting the label distance, while keeping the feature weight In Figure (b), as the label weight increases, the detection rate performance deteriorates. When we increase the label distance, the feature information becomes neglected, which is not as effective as the balanced weights between feature and label distances.
LAVA TracIn-Self Tractu-Clean
KNN-SV
Random
1.0
Detretion Rate
0.8
0.6
B.2.4 FEATURE EMBEDDER
0.4
We use feature embedder to extract features for the feature distance part in our method. We train the feature embedder on the accessible validation set until the convergence on the train accuracy. Different architectures of the embedder might be sensitive to different aspects of the input and thus result different feature output. Nevertheless, as we observe in Figure 10 the detection performance associated with different model architectures of feature embedder similar. Hence, in practice, can flexibly choose the feature embedder be used tandem with our method as long as it has large enough capacity. Furthermore, note that that these feature embedders
0
25000 50000
Data Value Ranking
Figure 11: Detection rate by various methods on misla- beled CIFAR- 10 using valida- tion size of 500.
19

---

Published as a conference paper at ICLR 2023
LAVA
Validation Model
Eackdoou Detection (5%)
Puisun Detection (0.1%)
Noisy Features (25%)
Noisy Labels (25%)
Detection Rate
Detocction Rate
Detocttions Dote
Detoctioon Botd
(a)
Data Valton Ranking
(b)
Data Va ton Penkking
Daraa Velton Ren-cing
(d)
Owtn Valion Ranking
Figure 14: Detection performance comparison between LAVA and the model trained on validation data of size 500 on various use cases in CIFAR-I0.
LAVA
Validation Model
Rackdoor Detoction (5%)
Phison Detection (0.1%)
Noiey Features (25%)
Noisy Labels (25%)
0--
000
0.
(a)
Dona Valae Rantiing
(b)
Duto Valce Roiliing
Dan Va7ae Ronking
(d)
23400 Data Villo Sanking
23003
Figure 15: Detection performance comparison between LAVA and the model trained on validation data of size 10, 000 on various use cases in CIFAR-10.
have not learned the clean distribution from the validation data, e.g. in CIFAR-10 10 the model trained on 10K validation data achieves only around 65% accuracy trained on 500 validation data achieves around 25% accuraracy. We additionally show in Figure 14 that method significantly out- performs the PreActResNet 8 model trained directly on validation data of size 500 and 10K in detecting bad data, which clearly dis- tinguishes LAVA from simple feature embedders.
LAVA
TracinsClean
KNNN SV Thacdis-Sad
Random
50K clean datapoints and the model
Clac: CHIMB-E,, Daba 32500
Mottal Auuracy
8D
79
78
77
vis
2000 Data
B.3 BALANCING UNBALANCED DATASET
Comparison of various methods on rebalanc- ing an unbalanced dataset on CIFAR-10 with the class Frog being unbalanced.
Figure 12:
Although machine leaning practitioners might be using clean data for training& model, the dataset can be often unbalanced which can lead to model performance degradation (Thai-Nghe et al.) 2009). To recover higher model accuracy, datasets by removing points that cause such disproportion. We
rebalance unbalanced
showcase how LAVA effectively rebalance the dataset by removing points with poor values and keeping points with best values. We consider CIFAR-10 dataset with class Frog being unbalanced and containing 5, 000 samples while other classes have only half as much (i.e. 500 samples). In Figure 12. we demonstrate the effectiveness of LAVA valuation which not only reduces the dataset by removing poor value points but also improves the model accuracy. While at the same time other valuation methods were not able to steadily increase the model accuracy and quickly downgraded the model performance, which in turn shows an even stronger effectiveness of our method.
LAWA
Bracila
KNN
Hurdom
Trario
Bedaee Datrert CIPAR 10, N. Dats 20000
Model Accuracy (%)
78-
76
74
3000
6000
Thrown
Figure 13: Comparison of var- ious methods on reducing dataset size based valuation of datapoints on CIFAR-10.
B.4 REDUCING TRAINING SET SIZE
With the growing size of the training dataset, the computation cost and memory overhead naturally increase which might deem impos-
20

---

Published as a conference paper at ICLR 2023
sible for some practitioners with limited resources to train model. Therefore, the ability to reduce the training dataset size (Sener & Savarese 2018) will free up some computation burden and thus allow ones with limited resources to fully apprectate the model training process. Motivated by the given challenge, we want to leverage our data valuation method to significantly decrease the training dataset size while maintaining the model performance. Similarly in the previous section, the idea is to keep subset of datapoints with best values and remove poor valued ones. To demonstrate the effectiveness of our LAVA'S valuation, we perform such task on clean CIFAR-I0 dataset with 2. 500 samples from each class and compare with other data valuation methods. As presented in Figure [3] demonstrated that the performance is well maintained even with smaller subsets of the original dataset. Remarkably, even reducing clean training set (25,000 samples) by 15% based on our method's s valuation, the performance can still stay relatively high while outperforming other valuation baselines.
B.5 DATA SUMMARIZATION
With growing dataset sizes, grows the space needed store data. Thus, the buyer often would like to decrease the dataset to minimize resources but to retain the performance. Unlike reducing training set size as provided in Section B.4 in this experiment, select a smaller, representative subset of the whole datasct that can maintain good performance. To measure the performance of each subset, we measure the validation performance of the model trained on that subset subtracted by the validation performance of the model trained on a random subset of the same size, the experiment which performed in Kwon & Zou 202T). In Figure [6we can observe that our method can select a small subset that performs better than the subsets chosen by the baseline methods most of the time.
Accurocy Differencet 9%
will
1000
2000
4000
Added Data
Figure 16: Comparison of var- ious methods on data summa- rization based on valuation of datapoints on CIFAR-10.
B.6 SCALABILITY EXPERIMENT
Lww.hherpaieteec.e Crdd CD
In the main paper, we have demonstrated time complexity compar- ison between LAVA and other valuation methods. We have reported runtime comparisons only for 2,000 test samples as this is the scale existing methods can solve in a not excessively long time (within a day). It showcases the advantageous computing efficiency that the proposed approach enjoys over other methods. We further want to emphasize the computational efficiency of LAVA and demonstrate computation efficiency on a larger scale dataset (100,000 samples) evaluate
250
Toue
150
30
25000
50000
Training Data Size
Figure 17: Near-linear time complexity of LAVA shown on CIFAR-10.
with higher dimensions, ImageNet-100 100. Additionally, other baselines which are able to finish within a day of computation to highlight the advantage of our method as presented in Table Moreover, we highlight the near-linear time complexity of LAVA on CIFAR- 10, which shows practical computation efficiency of our method as shown in Figure 17
B.7 GENERALIZATION TO OTHER TYPES OF BACKDOOR ATTACKS
Trojan-SQ
Trojan-WM
As we have provided the results of the Trojan square attack (Trojan-
Blend
Random
SQ) (Liu et al. 2017) in Section 4 we now apply LAVA to other back- door attacks, which are Hello Kitty blending attack (Blend) (Chen let al. 2017) and Trojan watermark attack (Trojan- WM) (Liu et al. 2017). and evaluate the efficacy of our method in detecting different types of backdoor attacks. We simulate these attacks by selecting the target class Airplane and poisoning 2, 500 (5%) samples of the CIFAR-10 10 dataset of size 50, 000. The backdoor trigger adopted in each attack is portrayed Figure g In Figure [8| we observe that our method can achieve superior detection performance on all the at- tacks considered. The reason is that despite the difference in trigger pattern, all of these attacks modify both the label and the feature of a poisoned image and thus result in the deviation of our distributional distance that defined over the product space of feature and label.
Pat. of Selected Poisuns
1.0
0.8
0.6
0.4
0.2
0.0
25000
50000
Data Value Ranking
Figure 18: Detection rate of various backdoor attacks by LAVA.
21

---

Published as a conference paper at ICLR 2023
B.8 IMPLICATIONS OF THE PROPOSED DATA VALUATION METHOD TO REAL-WORL WORLD DATA MARKETPLACES
Method
Time
One concern in the real-world data marketplace is that data is freely replicable. However, replicates of data introduce no new information and therefore the prior work has argued that data utility function should be robust to direct data copying (Xu al. 202T). One advantage of using the class-wise Wasserstein distance to measure data utility is that it is robust to duplication. Our method by its natural distributional formulation will ignore duplicates sets. As shown in Table although we have repeated the set even five times more than the original source set, the distance remains the same. Additionally, with small noise changes in the features, the distance metric barely affected. Another concern the real-world marketplace is that one might find single data that has highest contribution and duplicate it to maximize the profit. However, again due to the nature of our distributional formulation, duplicating a single point multiple times would inerease the distance between the training and the validation due to the imbalance in training distribution caused by copying that point.
LAVA
hr 54 min
KNN-SV TracIn-Clean TracIn-Self
hr 21 min
7 hr 50 min
7 hr 51 min
Table 1: Comparison of runtime be- tween various methods needed to valuate ImageNet-100.
B.9 DETAILED EXPERIMENTAL SETTINGS
Datasets and Models. Table summarizes the details the dataset, the models, as well as their licenses adopted in our experiments.
Hardware. server with an NVIDIA Tesla P100-PCIE-16GB graphic card is used as the hardware platform in this work.
Software.
Dataset Size
OT Dist
For our implementation, we use PyTorch for the main frame- work (Paszee et al. 2019), assisted by three main libraries,
Direct
Near
which are otdd (optimal transport calculation setup with datasets) (Alvarez-Melis & Fusi, (2020), geomlos oss (actual
5000
195.64
+0.98
2 x 5000
+0.00
+0.98
optimal transport caleulation) (Feydy et al. 2019), and numpy (tool for array routines) (Harris et al. 2020
3 5000
+0.00
+0.98
4 x 5000
+0.00
+0.98
4.5 5000
+0.07
+0.98
5 x 5000
+0.00
+0.98
Table 3: Class-wise Wasserstein distance behavior under dataset di- rect duplication and its near dupli- cates.
22

---

Published as a conference paper at ICLR 2023
Table 2: Summary of datasets and models and their licenses used for experimental evaluation. (Note: "Detail" column implicitly refers to training data, unless explicitly noted.)
Experiment
Train/
Type
Dataset
Lácense
Model
Valid Size
Detail
Wassentein vs
STLID
Not Applocable
GoogLeNet
MIT
SK/8K
15% Mislabeled 0%, 29%, 5%% 15%
Perforaance [
Midel
CIFARIO
ResNet18
MTT
50K/IOK
0%, 5%,, 10%, 18% Mislabeled
CIFARIOD
MIT
ReaNer50
MIT
50K/10K
01%, 29, 3%, 10%, 15% Mislabeled
Backdoor:
Thojan (Fig)
CIFARIO
MIT
ResNet18
MIT
50K/10K
5% Poisoned
Collision (Fig
Poisoning:
CIFARIO
50K/10K
Poisoned
Naiey Feature (Pg
CIFARIO
MIT
ResNet18
MIT
50K/10K
25% Noiey Daza
Noisy Labels (Fi
CIFARIO
MIT
ResNet18
MIT
50K/LOK
25% Noisy Data
Target Class Spread
Inclevant Data (Fip
CIFARIO
RexNet18
MIT
50K/10K
Inko Other Clasess
VS Perf (Fig 5
Runtime
CIFARIO
MTT
Ret18
MIT
2K/1K
10% Rackdones
Backdaur: Blend 6
358HN/
GTSRB
CCU 1.0
ResNet18
MIT
12360
5% Poisonad
Noisy Feature 6Fig
MNIST
CCA- SA 3.0
ReaNet18
PreAct-
MIT
60K/TOK
25% Noisy DMt
Time Complexity (Table
-100
ImageNet
Not Applicable
RerNer50
100K/10K
Classes
Mislabeled
Inrelevnnt Data (Pig
CIFARIO0
MIT
ResNet34
PreAct-
MIT
50K/10K
Inko 99 Other Classes
Target Class Specad
Noisy Label (Fig 10
CIFARIO
MIT
ResNet18
MIT
50K/10K
25% Noisy Labe
VGG16
CC
BY 4.0
ResNe
MIT
Noisy Label 9
CIFARIO
MIT
ResNet18
MIT
50K/LOK
Different Feature
Weights 1,5,10,100
Different Lahee
Weights 1,10,50,100
50K/10K
50KUSK
Different Validation
50K/2K
50K/0.55
Siies
50K0)22K
18 Trojun. (Fig
Backdoor: Blend.
CIFARIO
MIT
Not Applicable
Not Applicable
50K/10K
Visualization of Attacks
Detection Rate of LAWA
Duplication Training Set
Duplication (Table
Applicable
Not Applicable
Nor Appllicable
Noe Applicabli
SK/SK
Datasct Reduction (Fig
13
CIFARIO
MIT
ResNet18
PreAct-
MIT
25K/10K
2.5K Sumples From Each Class
Data Sumrarization (Fig 16
CIFARIO
MIT
ResNet18
MIT
25K/10K
2.5K Samples From Each Class
PreAct-
SK Sumples From Class Frog
Unholanced Dataset (Fig
12
CIFARIO
MIT
ResNe118
MIT
27.5K/10K
2.5K Sumples From Other Classex
Time Complexity (Fig
17
CIFARIO
MIT
ResNe118
MIT
50K/10K
SK From Each Class
23


Reviews:
[{"review_id": "hx3gHPbI2xG", "reviewer": "Reviewer_BSJ2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a datapoint valuation method, LAVA, that does not require a pre-defined learning algorithm, which is a common assumption in the existing literature. It utilizes the Wasserstein distance between the training set and the validation set with respect to a hybrid cost that considers both feature and label distances. The authors prove that the distance has theoretical connections with the validation performance (i.e., the utility) and show that the distance can be efficiently calculated using existing solvers. With that, the authors propose to use calibrated gradient to account for a datapoint’s contribution to the distance and thus its value. The paper has done extensive empirical experiments on 5 important application scenarios and demonstrated superior performances. Ablation studies are also done to better understand the behaviors of the proposed method. ", "summary_of_the_review": "Overall, I like the idea of a label-aware dataset distance measure as a data valuation metric despite borrowed from the OT literature. The method is backed by theoretical connections to validation performance, which is of interest in the topic of data valuation. The datapoint’s sensitivity to OT distance also naturally fits the marginal contribution concepts often used in data valuation. If my concerns above can be addressed, I think this work could contribute value to the community.", "strength_and_weaknesses": "Advantages: \n1. The paper is well-written and easy to follow. The authors additionally give lots of interpretations after results or formulations to help with the understanding. \n2. Label information is incorporated into the dataset distance design.\n3. The theoretical part of the paper is sound. Also, the connection from OT distance sensitivity to individual datapoint value is neat and natural.\n4. The author provides rather extensive empirical validations of the method and showed state-of-the-art performance. An interesting new application on “irrelevant data detection” is also included, which was originally often discussed as mislabeled data detection.\n5. Discussions on the limitations of LAVA in the conclusion are valid and indeed insightful.\n\nDisadvantages:\n1. The motivation for developing a learning-agnostic valuation method, especially in the context of the existing works with similar dataset distance approaches could be improved.\n2. Some small parts of the experiment details require clarification.\nFor more details, see below.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "dMKT5vhmjrk", "reviewer": "Reviewer_uRtv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a data valuation method of individual training data points that does not requires learning algorithms via the gradient of the Wasserstein distance between the training set and validation set w.r.t. the perturbations on the probability mass of a data point. While it is based on existing work on the hierarchically-defined Wasserstein distance between datasets, the paper provides new insight into the connection between this distance and the validation performance which is crucial for data validation. Furthermore, it proposes an efficient data valuation method of individual training data points based on the sensitivity of this distance, which has a wide range of use cases as demonstrated in the experiments.", "summary_of_the_review": "While limited to pointwise data valuation, this work proposes a new perspective in constructing a data valuation method without a learning algorithm and empirically evaluates the performance in various use cases. Thus, I believe the contribution and quality of the paper are sufficient.\n", "strength_and_weaknesses": "The strength of the paper is in the application of the existing Wasserstein distance between datasets to the data valuation problem with the new insights on the connection between the distance and the validation performance. Additionally, it demonstrates many use cases of the proposed data valuation method in the experiments. The paper is also well-written so that readers can understand the main idea easily.\n\nThe main weakness of the paper is probably due to the fact that the proposed data valuation only works for individual data points. I have several questions as follows.\n\n1. The proposed approach requires a validation dataset with labels. How would the Wasserstein distance be modified to measure the distance between a training set and a 'reference dataset' without labels?\n\n2. While the paper motivates the problem of data valuation as a central method to the emerging data economy (in data exchange), the proposed method cannot value data sources (which consist of multiple data points). Hence, I am wondering how this approach can be applied in data exchange (between multiple organizations/companies with different datasets).\n\n3. It is often the case that there are duplicates of data points (or redundant data points that are very similar to one another) in the real-world dataset. For simplicity, let us consider a dataset consisting of 3 data points x1,x2,y where x1 and x2 are duplicates of each other; and y is different from x1,x2. Intuitively, removing x1 does not affect the value of the dataset (since x2 contains the same information as x1), so the value of x1 is low. Hence, point-wise values of x1 and x2 are low. However, if we remove both x1 and x2 (since they have low valuation), then it is problematic because y does not contain information in x1 and x2. How does the proposed pointwise data valuation method work in this case?\n\n4. Like the work of Koh & Liang (2017), can the proposed method be used to explain a particular prediction of the model by finding the training data point that is responsible for the prediction? In this case, the analogous notion of a validation set contains only a single data point (the prediction to be explained), so I am wondering if the approach can still work.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RiVQ-qaO4u", "reviewer": "Reviewer_5BsF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a learning-agnostic data valuation framework based on optimal transport (OT). The authors suggest using a Class-wise Wasserstein distance between two datasets as a surrogate for validation performance, thus alleviating the need to pre-specifying the learning algorithm in advance. The authors then propose a new data valuation metric based on the gradient of the OT distance with respect to the perturbation on the probability mass associated with each data point. Even though this data valuation metric is difficult to compute, the paper points out that the difference can be calculated efficiently, allowing for an efficient ranking of the data points. The paper then presents empirical results to demonstrate the efficiency of the proposed methods on several different problems.", "summary_of_the_review": "The paper offers a fresh perspective on the problem of data valuation using ideas from optimal transport. However, the proposed framework is not sufficiently justified, both theoretically and empirically. The presentation of the paper can be improved.\n\n======= Post Rebuttal =======\n\nThe authors address some of my concerns and I have increased the score accordingly.", "strength_and_weaknesses": "Strengths: \n\n(+) The paper is sufficiently novel and the approach is interesting.\n\nWeaknesses: \n\n(-) The proposed approach lacks justification.\n\n(-) The experiment setups are unclear.\n\n(-) The presentation can be improved.\n\nDetailed comments:\n\n- (main concern - soundness) Theorem 1 resembles a statistical learning generalization bound, where we have an out-of-sample error (in this case, the validation set’s error) upper bounded by the training set’s error and some surplus term (the OT distance). By arguing that the training set’s error is close to 0 for sufficiently complex models, the authors justify the use of OT distance as a surrogate for the training set’s error by this theorem. However, one can apply the same logic to other generalization bounds (e.g., one based on VC dimension) to justify the use of VC dimension as a surrogate for the validation error. I find that this theorem does not satisfactorily justify the use of OT distance as a surrogate for the validation error.\n\n- (main concern - soundness) Theorem 1 is vacuous and follows almost immediately from the assumptions that $\\mathcal{L}$ is $k$-Lipschitz and the norm of $f$ is bounded by V. Could the authors elaborate on the challenges/difficulty in the proof of Theorem 1.\n\n- The authors did not explain the experiment setups (not even in the appendix). What is the validation dataset here? And in the mislabeled or noisy feature experiments, are the validation data corrupted too? It is unclear how the proposed framework is applied in these experiments.\n\n- (presentation) In the paragraph “Radius for accurate predictions…”, can the authors be more specific about the results in Bertsimas & Tsitsiklis (1997). I find this paragraph a bit hand-wavy.\n\n- (presentation) I do not follow the argument in this sentence (at the beginning of Section 3.1): “OT distance is known to be insensitive to small differences while also being not robust to large deviations”. I think the phrase “not robust” is not appropriate here. Also, I’m not sure why that is a desirable property in data valuation.\n\n- (presentation) Please use more equation numbering: Throughout the paper, the authors refer to various quantities/definitions via section number. This is very challenging for readers to follow. Could you please put important quantities/definitions in equation environments with numbers and refer to them?\n\n- (minor aesthetic comment - presentation) The results in Figures 2 and 3 are blurry. Although I can still understand the results, it would be nicer if the authors can include clearer versions of these plots.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P7zQpPxFXQ2", "reviewer": "Reviewer_7VZM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a data valuation method that is oblivious to the downstream learning algorithm. The main idea is to evaluate the training data by a class-wise Wasserstein distance between the training and the validation set. They prove that the class-wise Wasserstein distance approximates the performance for any given model under certain Lipschitz conditions. They also propose a method to evaluate individual data by the sensitivity analysis of this class-wise Wasserstein distance. Finally, the paper empirically evaluates the performance and efficiency of their methods. They show that their method improves the state-of-the-art performance while being orders of magnitude faster.\n", "summary_of_the_review": "Overall, I think this is a good paper with nice conceptual contribution and solid theoretical analysis and extensive empirical evaluations that show the efficacy of their data valuation approaches in practical use cases.", "strength_and_weaknesses": " The paper studies an interesting problem and proposes a novel data valuation method using a natural measure based on the class-wise Wasserstein distance. They provide solid theoretical justification for their approach by proving that their measure characterizes the upper bound of the validation performance of any given models. They also propose an interpretable and easily-computable measure for individual data valuation. Finally, they conducted extensive experiments to test the efficacy and efficiency of their approaches in practical use cases.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%