SAVA: Scalable Learning-Agnostic Data Valuation
Authors: Samuel Kessler
Tam Le
Vu Nguyen
Venue: ICLR 2025 Poster (2025)
Keywords: Data Valuation
Optimal Transport
Data Selection
Active Learning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We propose SAVA, a scalable optimal transport (OT)-based data valuation for large datasets, which performs OT computation on batches instead of on the whole dataset (e.g., LAVA).

Abstract: Selecting data for training machine learning models is crucial since large, web-scraped, real datasets contain noisy artifacts that affect the quality and relevance of individual data points. These noisy artifacts will impact model performance. We formulate this problem as a data valuation task, assigning a value to data points in the training set according to how similar or dissimilar they are to a clean and curated validation set. Recently, *LAVA* (Just et al., 2023) demonstrated the use of optimal transport (OT) between a large noisy training dataset and a clean validation set, to value training data efficiently, without the dependency on model performance. However, the *LAVA* algorithm requires the entire dataset as an input, this limits its application to larger datasets. Inspired by the scalability of stochastic (gradient) approaches which carry out computations on *batches* of data points instead of the entire dataset, we analogously propose *SAVA*, a scalable variant of *LAVA* with its computation on batches of data points. Intuitively, *SAVA* follows the same scheme as *LAVA* which leverages the hierarchically defined OT for data valuation. However, while *LAVA* processes the whole dataset, *SAVA* divides the dataset into batches of data points, and carries out the OT problem computation on those batches. Moreover, our theoretical derivations on the trade-off of using entropic regularization for OT problems include refinements of prior work. We perform extensive experiments, to demonstrate that *SAVA* can scale to large datasets with millions of data points and does not trade off data valuation performance. Our Github repository is available at \url{https://github.com/skezle/sava}.

Published as a conference paper at ICLR 2025
SAVA:
SCALABLE LEARNING-AGNOSTIC DATA VALUATION
Samuel K
Microsoft
samuel kess www.:r/eeemcccsotoooooooo
Tam Le"
The Institute of Statistical Mathematics/ RIKEN AIP tamßishy ac. jp
Vu Nguyen Amazon
vutngn@amazon.com
ABSTRACT
Selecting data for training machine learning models is crucial since large, web- scraped, real datasets contain noisy artifacts that affect the quality and relevance of individual data points. These noisy artifacts will impact model performance. We formulate this problem as a data valuation task, assigning value to data points in the training set according how similar or dissimilar they are to clean and curated validation set. Recently, LAVA (Just et al., 2023) demonstrated the of optimal transport (OT) between a large noisy training dataset and clean validation set, to value training data efficiently, without the dependency on model performance. However, the LAVA algorithm requires the entire dataset this limits its application to larger datasets. Inspired by the scalability of stochastic (gradient) approaches which earry out computations instead of the entire dataset, we analogously propose SAVA, a scalable variant of LAVA with its computation on batches of data points. Intuitively, SAVA follows the same scheme as LAVA which leverages the hierarchically defined OT for data valuation. However, while LAVA processes the whole dataset, SAVA divides the dataset into batches of data points, and carries out the OT problem computation on those batches. Moreover, our theoretical derivations on the trade-off of using entropic regularization for OT problems include refinements of prior work. We perform extensive experiments, to demonstrate that SAVA can scale to large datasets with millions of data points and does not trade off data valuation performance. Our code is available at https: / github.. com/ skezle le/ sava.
input,
batches of data points
INTRODUCTION
Neural scaling laws empirically show that the generalization emrr decreases according to a power law as the data model trains on increases. This has been shown for natural language processing, vision, and speech (Kaplan et al., 2020; Henighan et al., 2020; Rosenfeld et al., 2019; Zhai et al., 2022; Radford et al., 2023). However, training neural networks on larger and larger datasets for moderate improvements in model accuracy is inefficient. Furthermore, production neural network models need be continuously updated given new utterances that enter into common everyday parlance (Lazaridou et al., 2021; Baby et al., 2022). It has been shown both in theory and in practice that sub-power law, exponential scaling
model performance with dataset size is possible by carefully selecting informative data and pruning uninformative data (Sorscher et al., 2022), and that generalization improves with training speed (Lyle et al., 2020). Therefore, valuing and selecting data
cco-fist authors work done while the University of Oxford.

---

Published as a conference paper at ICLR 2025
By
(T Pe)
Validation
(T()
Dean valicaiion anC
B
Large no sy baining
A(Ph. - ((*s,, dOT (a)
Distance between two (labelec) points
Trcihing uolaton
OOTNAB: Bu (Px)
d[B,,B) -OT (kar))
Valuation scone for a point As B,
Figure 1:
Overview of the propased SAVA method. On the left-hand side, SAVA values data points in a noisy training dataset by comparing to a clean validation dataset. SAVA performs scalable data valuation by solving multiple cheap and small OT problems on batches of data points (on the right-hand side). Notations in Orange denote OT distances and plans over training and validation batches, while notations in Green denote OT distances over data points in batch. OT (o)) denotes the OT distance between training and validation batches and # (ju,, (l)) the associated OT plan in Eq. (11), OT(un, MB;) is the OT distance between the batch B; from the training set and the
batch B' in the validation set where we use the feature-label distance in Eq. (1) as the ground cost for labeled data points in these batches. Sy is SAVA's 's final valuation score for training labeled data point 2g in Eq. (12). The hatched box denotes the summation over the validation batches to value the data point Za. We provide visualization of these artifacts generated by SAVA in Figure 12.
points that are informative: which have not been seen by the model, which do not have noisy labels, and which are relevant to the task we want to solve-are not outliers-can help to not only decrease training times, and reduce compute costs, but also improve overall test performance (Mindermann et al., 2022; Tirumala et al., 2023).
Popular data selection and data pruning methods use variations of the model loss to value data points (Jiang et al., 2019; Pruthi et al., 2020; Paul al., 2021). Crucially, these methods depend the model used, and they are vulnerable to prioritizing data points with noisy labels or noisy features; data points that do not resemble the target validation set. When treating data valuation as a function of model performance, we introduce a dependency on a neural network model. This is the case when valuing point using the leave-one-out (LOO) error, i.e., the change of model performance when the point is omitted from training. To rid our dependence to leverage optimal transport (OT) between training distribution and a clean validation distribution as proxy to directly measure the value of data points in the training set in a model-agnostic fashion. In particular, the validation performance of each point in the training set can be estimated using the hierarchically defined Wasserstein between the training and the validation set (Alvarez-Melis & Fusi, 2020; Just et al., 2023). LAVA (Just et al., 2023) has been shown to successfully value data by measuring the sensitivity of the hierarchically defined Wasserstein between training data points and validation distributions in a model-agnostic fashion. However, LAVA requires significant RAM consumption since its memory complexity grows quadratically O(N2) with the dataset size N. This hinders LAVA from scaling to large datasets.
neural network model, a promising idea is
In this paper, present SAVA, a scalable variant of LAVA, for data valuation. Our method completely addresses the bottleneck of RAM requirements in LAVA. Intuitively, SAVA performs the OT com- putations on batches instead of on the entire dataset like LAVA (hence the analogy the stochastic approach to (sub) (sub)gradient computation). Specifically, SAVA uses ideas from hierarchical optimal transport (Yurochkin al., 2019: Lee et al., 2019) enable OT calculations on batches instead of the entire dataset. We can scale up OT- beseaeed data valuation using SAVA to large real-world web-scrapped datasets. On benchmark problems SAVA performs comparably to LAVA while being able to scale to datasets two orders of magnitude larger without memory issues, while LAVA is limited due to hardware memory constraints.
Contributions: In summary, our contributions are three-fold as follows:
We introduce novel scalable data valuation method called SAVA that leverages the (sub)gradient of hierarchical optimal transport which performs OT computations on batches of data points, enabling bT-bd data valuation to large datasets.
2

---

Published as a conference paper at ICLR 2025
We correct the essential theoretical result the trade-off for using entropic regularization to compute the OT (sub)gradient in LAVA (Just et al., 2023, Theorem 2). Consequently, by building upon refined theory, derive the exact trade-off to estimate the (sub)gradient of hierarchical OT with entropic regularization in our framework.
We provide an extensive experimental analysis to demonstrate the improved scalability with increasing dataset sizes with respect baselines.
OPTIMAL TRANSPORT FOR DATA VALUATION
2.1 OPTIMAL TRANSPORT FOR LABELED DATASETS
Let X' be the feature space, and V be the number of labels. We write ft : X + 10, and fo : X +
{0. 13" for the labeling functions for training and validation data respectively. Given the training N' and the validation set D. {=/ fo())) the corresponding measures for sets Do are (4(x, y) = Em 6(.,))) and pe (z'. ./) = NY Σ ((g()))) respectively where o is the Dirac function, and y; y are labels of x. x respectively. For simplicity, let 2 = (X.
D. =
where J/ is the space of labels. For ease of reading, we summarize the notations in Table 1.
Following Alvarez-Melis & Fusi (2020), we compute the distance between two labels by leveraging the OT distance between the conditional distributions of the features given each label, i.e., pe(-lue)
((( for label yt in μt, where is the indicator function. [==)))
Let d be the metric of the feature space X, e.g., the Euclidean distance. The distance between labels y1 and ye is (Ta( (11))). (-1y.))) i.e., the metric of the label space V. Consequently, the cost
between feature-label pairs in 2 (X, )) is
C(( ve), (Ze, Ue)) = d( x.) + CTa (-lvo)))
(1)
where e > 0 is weight coefficient. Therefore, with the cost matrix C, we can use the OT on the represented measures Mt Me compute the distance between the training and validation sets, i.c.. d(D,, D.), without relying on external models or parameters as follows
/ C(2, (22,,
d(De, D.) = OTc(4) = min
(2)
*EI(()GA))) 2xz
where T( Mw)) is the set of transportation couplings with marginals as 14 and p4. To simplify notations, we drop C, and use OT when the context is clear. We further write n" for the optimal transport plan in Eq. (2). In practice, leverage the entropic regularization (Cuturi, 2013) to reduce the OT complexity into quadratic (from super cubic) w.r.t. the number of input supports, defined as
/ C(z, o' (/((///( 2') eH(T Me (p)),
OT, (p))
min xEIl(He.p)) 2
where @ is the product measure operator, and H(T Me @ pv) Jzxz log
dr
dr.
daudaa
Additionally, the OT problem in Eq. (2) constrained convex minimization, is naturally paired with dual problem, i.e., constrained concave maximization problem, as follows:
OTc(Pe, pv) = max (f. pc) + (g. pu). (L.))R(())
(4)
where R(C) = ((f.g) E C(()) C(2): (2,,'), g(2²) S C(2,2')), C is collection of continuous functions, (f. (b) = (2)ddu(())), and similarly (e) = Iz (z))
2.2 LAVA: DATA VALUATION VIA CALIBRATED OT GRADIENTS
As discussed in Just (2023), the OT distance is known be insensitive small differences while also being not robust to large deviations. This feature is naturally suitable for detecting abnormal
See Appendix C.I for the detailed discussion.

---

Published as a conference paper at ICLR 2025
Table 1: A summary of notations.
Notation
Definition
= (a, E RR x 10,
Data point feature and label where V is #label and X' is a feature space Datascts for training D, {(2,, f=( and validation D, = (((,))))
Dr, Dr
B {B.) R. .BB = (
Disjoined batches for Dy and D. where K₁, K2 are the number of batches Batch of data points where N; is the size of the training batch B: Batch of data points where Nj the size of the validation batch Bj Mcasure over labeled data points for the batch B; Measure over training set
B: (xx)
BJ (
MR, N. Ei 8(2)
pu 8) = N 2i= (mas))
pa Lim1 (eroa))
Measure over validation
A. K, Dx1 ((1))
((B.)
Measure over batches for the training set Measure over batches for the validation set Cost matrix over butches, each element Ct,; d(B,, BB) Cost matrix over labeled data points within and Bi, each element Cu d(2k, Dual solutions of the OT over cost matrix C c R NNN OT plan over cost matrix C RN
B.
Ce R
CE NINN,
1' C R of CR ERRAAA / CRR q CRR. I' FRRKIKK OTc(m..)))
OT dual solutions over cost matrix over batches C c RK OT plan over cost matrix between batches C RK.KK, OT solution opt. problem with C' over training and validation measures
data points, i.e., disregarding normal variations in distances between clean data while being sensitive to abnormal distances of outlying points. Therefore. the (sub)gradient of the OT distance w.r.t. the probability mass associated with each point can be leveraged as surrogate to measure the contribution of that point. More precisely, the (sub)gradient of the OT distance w.r.t. the probability mass of data points in the two datasets can expressed:
V pr OT(p, pb) (f*)², Vp,, Hb)= = (g")².
(5)
The dual solution is unique up to a constant due to the redundant constraint Σ (e(2) = 1 = 1. Therefore, for measuring the subgradients of the OT w.r.t. the probability mass of given data point in each dataset, Just et al. (2023) propose to calculate the calibrated gradients (i.e., sum of all elements equals to zero)²
8OT(H4, Hu) = @us(zz))
SJ JE(L.... -
Σ
(6)
The calibrated gradients predict how the OT distance changes as more probability mass is shifted to given data point. This can be interpreted as measurement of the contribution of the data point to the OT. Additionally, if we want training set to match the distribution of the validation dataset, then either removing or reducing the mass of data points with large positive gradients, while increasing the mass of data points with large negative gradients can be expected reduce their OT distance. Therefore, as demonstrated in Just et al. (2023), the calibrated gradients provide a powerful tool to detect and prune abnormal or irrelevant data in various applications.
Memory limitation. While being used with the current best practice, the Sinkhorn algorithm for entropic regularized OT (Cuturi, 2013) still runs in quadratic memory complexity ((N) with the dataset size N, as it requires performing operations on the entire dataset, using the full pairwise cost matrix. Consequently, the memory and RAM requirements for the Sinkhorn algorithm primarily depend on the dataset size N. Additionally, notice that dense square (float) matrix of size N = 1 will require at least 74 GB of RAM and = 10c will take 7450 GB of RAM which is prohibitively expensive. Therefore, LAVA is limited to small datasets.
Scalability. Inspired by the scalability of stochastic gradient approaches where the computation is carried out batches of data points instead of the whole dataset as in the traditional gradient, we follow this simple but effective scheme to propose an analog for OT, named SAVA which is a scalable variant of LAVA with its OT computation on batches. Intuitively, SAVA also leverages the
"To remove the degree of freedom which comes from the fact that one among all row/column sum constraints for the transport polytope is redundant, among the OT subgradients, we fix the zero-sum subgradient following the convention in Cuturi & Doucet (2014) and the calibrated approach in LAVA (Just et al., 2023).
4

---

Published as a conference paper at ICLR 2025
Algorithm Scalable Data Valuation (SAVA) algorithm. More concretely, in Lines 1-5, we solve multiple OT problems between batches. Line 6, we solve the OT problem across batches: o Po). to obtain n² (Fe, Po). In Lines 7-10, estimate valuation scores for training data using the plan H² (De, Fb)) and potentials f (HB, Am;) computed in the previous steps.
Input: a threshold E for Sinkhorn algorithm, let (z, 8)
Output: training data values sy for all & E [N,] for all i [Ki].
for i 1, K2 do for j= = 1..., K, do Compute Car Bi, BJ), wk E [N.] E (N)] by using Eq. (8).
( ( by solving (T(()..PF)) Set (Mt (.) (TC(MB, MBy).
Compute (UB, (B,) ).g
// distance d(B,, B,) batches.
Compute x ("4,, (b)) E -RKIKK by solving OT (Tt, (e) using Eq. (11).
for i = 1, K₁ do
for k = N₂ do WB:
Compute 3pp,(s)) (#x)
Vj E [K,] using Eq. (14).
Compute 8
SHOT Pt using Eq. (13). // valuation score for 2s B.. (F)(
hierarchically defined OT in LAVA, but it performs OT on batches of data points instead of on the entire dataset as in LAVA.
Notice that the scalable OT-based data valuation (i.e., SAVA) we will introduce in the next section focuses on the (sub) (ub)gradient the OT instead of the OT distance itself. Therefore, several popular scalable OT approaches such sliced- Wasserstein (Rabin al., 2011; Bonneel et al., 2015; Nguyen et al., 2024), tree-sliced- Wasserstein (Lee et al., 2019; 2024b; Tran et al., 2025a;b), or Sobolev transport (Le et al., 2022; 2023; 2024a), may not be suitable since they leverage local structures supports (e.g., line, tree, or graph structure respectively) to scale up the computation of OT distance. In the next section, OT using hierarchical OT (Yurochkin et al., 2019; Lee et al., 2019). We focus on the problem of data valuation but our work can be applied to other large dataset applications where the (sub)gradient of the OT is required.
introduce our novel scalable approach for computing the (sub)gradient of the
3 SAVA: SCALABLE DATA VALUATION
In this section, we present SAVA, a scalable data valuation method, scaling LAVA to large-scale datasets. Instead of solving single, but expensive OT problem for distributions the entire datasets, ie., OT(4,, (w) in LAVA with the pairwise cost matrix size NxN' consider solving multiple cheaper OT problems for distributions on batches of data points. For this purpose, our algorithm performs data valuation on two levels of hierarchy: across batches, and across data points within two batches. Thus, SAVA can complement LAVA for large-scale applications.
Hierarchical OT. We follow the idea in hierarchical OT approach (Yurochkin al., 2019; Lee al., 2019) to partition the training dataset D, of N samples into K, disjoint batches Similarly, for the validation set D. of N' samples into K, disjoint batches B' {B,} K. j=1 Addition- ally, for all i E [Kr], E [K,]. let the number of samples in batches B,, B₁ as N₁, N₁ respectively. The corresponding measures of the training and validation sets w.r.t. the batches are defined as: (B) K. E ( and (B') = I Σ 8(Bg) respectively. We then define a distance K.
{B
K,
between the datasets as the hierarchical optimal transport (HOT) between the measures Pt: Phu as OT distance for corresponding represented measures batches, i.e., fa and fh, in 22. as follows:
d(u, Pw)) HOT(μ,, ).)) = OT F.))-
It is worth noting that HOT finds the optimal coupling at the batch level, but not at the support data point level as the classic OT. Therefore. can be seen that
OT(4, pv) & HOT(H,
5

---

Published as a conference paper at ICLR 2025
where the equality trivially happens when either each batch only has one support each dataset only has one batch.
8pe(za) where HOT pv) is defined in the Eq. (7). Computing this derivative involves two OT estimation steps including (i) OT between individual data points within two batches to compute d(B,, B3) == OT("B, where PB, PB,M are corresponding measures for batches B;, B' respectively, and subsequently a cost matrix C on pairwise batches for input measures over batches; (ii) d(pe: pt)) HOT( [o) = OT Po).
Our goal is to estimate the (sub)gradient (Rx)
Od(p (Ho
Pairwise cost between batches. We estimate the distance between two batches as the OT problem between B, and By. i.e., d(B; B3) == OT B;, B3) as discussed $2.1 by viewing the OT problem between two labeled (sub)datasets, i.e., batches B, and B'j
More precisely, to solve this OT problem, we calculate the pairwise cost for data points between two batches Car [B;, B3) E NNN,,, where Vk [N.]. Vl [NJ], the element Cu (B, B3) is the cost between two labeled data points (Ix: Vk) E B, and (2%, v() E BJ, calculated
CuI CRI(,,
B,, B3) = d(rks 2t) + cOTo (UB, (-lux), Moy (-166))
(8)
Given the cost matrix C(B., BJ), we solve OTc(un, MBB) get dual solutions f" (uB.: (UB, MB;), and the OT distance for d(B,, OT OTc(MB.
We repeat this process and solve the OT problem for each pair (B,, (,, i.c., the OT problem for distributions on batches of data points, across the training and validation datasets, for all e [Kel.j E
[. This enables us to define the cost matrix for pairwise batches in Pe. Po. denoted as
C(pe: (.)) E I x= where we recall that K2 and Ke are the number of batches in training and validation sets. Hence, for this cost matrix C, the element Ciy is computed as OT(HB, (B;)) ). for all
i E [K,], Vj E [k,]-
Batch valuation. Given the pairwise cost matrix across batches C, we compute the data valuation for each batch via the (sub)gradient of the distance OTe R.) w.r.t. the probability mass of batches in the two datasets, i.c., (P..(P).
B,) These partial derivatives measure the contribution of the batches to the OT distance, i.e., shifting more probability mass to the batch would result in an increase or decrease of the dataset distance, respectively.
More precisely, /" be the optimal dual variables of OTc(ūe, then the data valuation of the batch B, in the training set ID, is estimated as follows:
(oo fr.
(9)
(
Since the optimal dual variables are only unique up to a constant, we follow Just et al. (2023) to normalize these optimal dual variables such that the sum of all elements is equal to zero:
(pe @p.(B.)
Σ
(10)
K 1
JE(L.....K,))
Using batch valuation for data point valuation. After solving the OT problem over batches, we (e, Rww) which is used to compute the data valuation over individual data point:
obtain the OT plan म (Ne,
C(āe, Rv)
** (Pe, (.)) = diag( ū exp
diag((").
(11)
E
where diag(-) is matrix diagonal operator, (ū", 5*) is a dual solution from Sinkhorn algorithm. Additionally, we have u" = exp(p (') ). = exp(- g following Cuturi (2013, Lemma 2).
For data point E B, C Dr, its data valuation score be computed
Ka
aOT(HB.
my (Pc.
(12)
(2)

---

Published as a conference paper at ICLR 2025
Using HOT, given data point in each dataset via the calibrated gradient summarized in the following Lemma 1. We refer to Table for the notations.
measure the (sub)gradients of the OT distance w.r.t. the probability mass of
Lemma 1.
The calibrated gradient for data point in the butch B; in Dr can be computed as:
HHOT(p:; (pp(
80T(UB, MB;)
Σ
(13)
OuB((zu)
where the calibrated gradient of OT for measures on batches calculated as follows:
,OT(HB,,MB:)
(
SE (BB..
Σ
N: Vjj E [Ko].
(14)
Bu (zk)
is common practice to compute the OT via its entropic regularization, using the Sinkhorn algorithm (Cuturi, 2013). We quantify the deviation in the calibrated gradients caused by the entropy regularizer. This analysis shows the potential impact the deviation on applications built on these gradients.
We refine the theoretical result (Just et al., 2023, Theorem 2), which uses entropic regularization to approximate the OT (sub)gradient in two aspects. Firstly, we take into account the non-negative constraint of the OT plan for entropic regularization.
in the dual formulation. Secondly, correct the discrete formulation
Theorem (Refined Theorem in Just et al. (2023)). The difference between calibrated gradients for two data points in D, is
8OT (Mi, Mw) Ojc (zs) 8ue (Zx)
80T (44,Hr)
00T, (M4,
00T, (pe. (o)
Ope (z:)
0pu, (#x)
(m²)e pe(2))
hig hig
+ E
log
(15)
N
(Tt) (z()z)
where is the corresponding optimal dual variable, accounting for non-negative constraint on the transportation plan in the primal OT formulation.
Proof. Refer to Appendix C.2 for the proof.
The term in the brackets (in blue) is the key difference between our new result and the previous one derived in LAVA (Just et al., 2023, Theorem 2).
Lemma 3 (HOT with entropic regularized OT over batches). The difference between the calibrated } E Bg T3 can be calculated as
gradients for two data points {21, 2x
HHOT( pt) (HOT(M: (p)(za) θ1((z1)
K- Th (Tt, Rro)
TOT, (MB,,ME) Opn,(zz
aoT, (PB, MB))
0un,(21
1=1
N
(T2 (#2)).s/H((Za)
hi - hij (#t)).//((zz)
log
(16)
N
8
Proof. Refer to Appendix C.3 for the proof.
We make a similar observation in LAVA that the ground-truth (sub)gradient difference between two training points žµ and =ı is calculated based the HOT formulation and can be approximated by the entropic regularized formulation OT, over batches, such as via the Sinkhorn algorithm (Cuturi, 2013). other words, we can calculate the ground-truth difference based on the solutions to the regularized problem plus some calibration terms that scale with e. In addition, in our case with HOT, the (sub)gradient difference also depends on the additional optimal assignment across batches (Me, ) which is again estimated by the Sinkhorn algorithm.
See Appendix C.I for the detailed discussion.

---

Published as a conference paper at ICLR 2025
Shapley
Backdoor Detection (10%)
Poison Detection (10%)
Naisy Features (30%)
Noisy Labels (30%)
0.8
0.8
Detection
0.8-
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.1
0.5 2.0 5.0
0.1
0.5 10
2.0
5.0
0.1
0.5 1.0 2.0 5.0
0.1
0.5 1. 2.0 5.0
Training Set Size x30*
Training Set Size x101
Training Set Size x10*
Training Set Size x1o
Figure 2: SAVA can value the full CIFAR10 dataset with various corruptions, while LAVA has out-of-memory (OOM) issues. We sort training examples by the highest OT gradients in Eq. (6) and Eq. (12) for LAVA and SAVA respectively, and use the fraction of corrupted data recovered for prefix of size N/4 as the detection rate (where N is the training set size). The star symbol (*) denotes the point at which LAVA is unable to continue valuing training due GPU out-of memory (OOM) errors.
PROPERTIES AND DISCUSSIONS
The SAVA algorithm. We outline the computational steps of SAVA in Algorithm 1.
In Lines 1-5, solve multiple OT tasks for data points between two batches B,, B',- We obtain the dual solution I (PB,: MBB)) E NR Additionally, these OT distances are used to fill the cost matrix for pairwise batches Cip (Fe, Fb)) OTc(HB,, MBB)) Here, the cost matrix C is of size N₂ x N3 where the batch sizes N,, NJ < N. The required memory complexity O(N; x Nj).
In Line 6 Algorithm 1, we solve the OT problem across batches OTe F..) to obtain #t (ae. P.). The cost matrix is small, of size K, x Kn, so less expensive compared to working with the full dataset Just et (2023). Finally, in Lines 7-10, we estimate valuation scores for training data using the auxiliary matrices computed in the previous steps, including f (NB, (B)) and Rt (Pe, Po).
The memory complexity of LAVA is O(N N') where N and N' are the training and validation dataset sizes. This comes from the main OT step of ( Mb) over the full cost matrix C of size N x N' to subsequently calculate the calibrated gradient Eq. (6). SAVA overcomes this limitation by solving multiple smaller OT problems OT(HB,, HB;) (B;)) on distributions for batches of data points only: if batches B; and B/ are of size N; and Ný, respectively, then the memory complexity is ON,, Nf). See Appendix D for an analysis of the time complexity.
SAVA memory requirements.
Practical implementation with caching. While yielding significant memory improvement, SAVA's runtime is not necessarily faster than LAVA. To speed up SAVA, we propose to implement Algorithm by caching the label-to-label costs between points in the validation and training batches: O- in $2.1 so that it is only calculated once in the first iteration of Algorithm and reused for subsequent batches. This significantly reduces SAVA runtimes with no detriment to performance Figure 9, All experimental results in $5, unless otherwise stated, implement this caching strategy.
Batch sizes. If we consider Eq. (7), HOT provides the upper bound for the OT since its optimal coupling on batches of data points. HOT recovers the OT when either batch only has one support or each dataset only has one batch. Consequently, up to certain batch size, when increasing the batch size N₂, HOT converges to the OT, but its memory complexity also increases, i.e., O(N; x NT) - ONN x N'). On the other hand, if the batch size N; is too small, the number of batches K, will be large. As result, the memory complexity will also be high, i.e., ( f.) in Algorithm 1. Thus, the batch size will trade off the memory complexity and the approximation of HOT to standard OT.
5 EXPERIMENTS
We aim to the test two following hypotheses: (i) Can SAVA scale and overcome the memory complexity issues which hinder LAVA while maintaining similar performance? (ii) Can SAVA scale to a large real-world noisy dataset with over million data points?
8

---

Published as a conference paper at ICLR 2025
5.1 DATASET CORRUPTION DETECTION
We test the scalability of SAVA versus LAVA (Just et al., 2023) by leveraging the CIFAR10 10 dataset, introducing a corruption to a percentage of the training data, but keeping the validation set clean. We then assign a value to each data point in the training set. Following Pruthi et al. (2020); Just et al. (2023), we sort the training examples by their values. An effective data valuation method would rank corrupted examples in prefix of ordered points. We use the fraction of corrupted data recovered by the prefix of size N/4 / as our detection rate (see an example in Appendix F, Figure 5).
Setup. We consider 4 different corruptions (see Appendix E for details) applied to training data following Just et al. (2023): (i) noisy labels, (ii) noisy features, (iil) backdoor attacks and (iv) poison detections. All experiments are run a Tesla K80 Nvidia GPUs with 12GB GPU RAM. Unless otherwise stated, all results reported are a mean 11 standard deviation over 5 independent runs.
Baselines. Our main baseline is LAVA. For SAVA and LAVA we use features from a pre-trained R (He et al., 2016). For SAVA, we use a default batch size of N; = 1024 which is its main hyperparameter. 4 We consider KNN Shapley (Jia et al.. 2019a), the Shapley value measures the marginal improvement in the utility of a data point and uses KNN to approximate the Shapley value. KNN Shapley also uses 1 features to calculate Shapley values, we tune it as its performance is sensitive to this hyperparameter. We consider TracInCP (Pruthi et al., 2020) which measures the influence of each training point by measuring the difference in the loss at the beginning versus the end of training. We also compare with Influence Function (Koh & Liang, 2017) which approximates the effect of holding out a training point on the test error, it uses expensive approximations of the Hessian to calculate the influence of a training point. We also consider Data- Data-OOB (Kwon & Zou, 2023) which uses bagging estimators to value data points, data points are embedded using a pre-trained feature extractor, and the bagging estimator is decision tree (see Appendix G.1 for implementation details). We finally consider a naive OT baseline which obtains values for data points at a batch level, and aggregates values across validation batches; the baseline essentially performs LAVA only at data point level within a batch and averaging values across validation batches. We call this baseline Batch-wise LAVA. Although Batch-wise LAVA obtains good corruption detection results, it is very sensitive to the batch size (see Appendix H.6).
Noisy labels. We corrupt 30% of the labels in the training set by randomly assigning the target a different label. From Figure 2, we can see that LAVA has an out-of-memory (OOM) issue when valuing the full training set of 50K points. In contrast, SAVA, Batch-wise LAVA, KNN Shapley and Data-OOB can consistently value and detect all corruptions when inspecting 12.5K ordered samples by values. Influence Functions matches the performance of SAVA, but is very expensive to run on large datasets. TracInCP is unable to detect noisy labels better than random selection, similar to the observations in Just et al. (2023). Consequently, when pruning 30% of the data, SAVA can consistently improve its accuracy the test set as the training set size increases (Appendix H.
Noisy features. We add Gaussian noise to 30% of the training images to simulate feature corruptions that might occur in real datasets. From Figure 2, LAVA obtains good performance for moderate dataset sizes, but for training set sizes above 10K, some runs have OOM errors when embedding the entire training set into memory and when calculating the full cost matrix for OT problem. In contrast, SAVA can consistently value and detect corruptions. Batch-wise LAVA is also able to scale and gets similar performance to SAVA. As can KNN Shapley and Data-OOB, albeit its detection rate is lower than SAVA; as we prune 30% of the data for larger and larger dataset sizes performance of SAVA outperforms KNN Shapley Figure 7. TrachnCP and Influence Functions both struggle to detect noisy data points, both methods were originally shown to detect noisy labels, so we do not expect them to work well beyond noisy label detection.
Backdoor attacks. We corrupt 10% of the data with Trojan square attack (Liu et al., 2018). SAVA, Batch-wise LAVA and KNN Shapley can scale as the dataset size increases while LAVA has an OOM error when valuing the largest dataset with 50k points. TrucInCP and Influence Functions both struggle to detect backdoored training points and have long runtimes. Data-OOB also struggles to value data points in this scenario, this is in line with recent surveys which show less strong performance when valuing data with noisy features (Jiang et al., 2023).
*See Appendix H for the study of the sensitivity of the hatch size N; in SAVA.
9

---

Published as a conference paper at ICLR 2025
Poisoning attacks. We corrupt 10% of the data with poison frogs attack (Shafahi al., 2018). We find in Figure that SAVA and Batch-wise LAVA can scale and maintain a high detection rate. In contrast, KNN Shapley struggles to detect corrupted data points after inspecting 25% of the ordered training data. TracInCP, Data-OOB and Influence Functions struggle to detect the corrupted data.
5.2 LARGE SCALE VALUATION AND PRUNING
We test our second hypothesis: whether SAVA can scale to a large real-world dataset. We consider the web-scrapped dataset Clothing IM (Xiao et al., 2015) where the training set has over 1M images whose labels are noisy and unreliable. However, the validation set has been curated. Clothing IM 14-way image classification problem and has been used for previous work online data selection (Mindermann et al.. 2022). We consider SAVA and other data pruning methods as baselines remove low-value training data points before training a ResNet18 classifier.
We compare to Batch-wise LAVA, intro- duced in $5.1. We also compare to EL2N (Paul et al., 2021) which values training points using the loss on several partially trained networks to decide which points to remove. We train 10 models for 10 epochs, we perform cross validate sliding window of values to decide which EL2N values to keep (see Appendix G.2.2 for details). We also consider supervised prototypes (Sorscher et al., 2022) which prunes image embeddings according to how similar they look cluster centers af- ter clustering image embeddings (see Ap- pendix G.2.3 for details).
Test Accuracy
70
No Pruning
69
Random Pruning
Supervised Protolypes
68
EL2N
Batch-wise
67
0.0
0.1
0.2 0.3
Proportion Data Pruned
Figure 3: SAVA can scale to large web-scrapped dataset. We use SAVA and other baselines, to value data points and then prune certain percentage of the noisy training set. The resulting dataset used for training a classifier.
If we were to train a classifier on the full noisy training set, we would obtain an accuracy of 67 6 0.2, this remains constant as we randomly prune more data. Supervised prototypes obtains better results than random, and improves slightly over random pruning. This is expected since supervised prototypes a semantic deduplication method and ignores label information. SAVA, Batch-wise LAVA and EL2N perform well and we find that SAVA performs better than both EL2N and Batch-wise LAVA. This shows the benefit of the SAVA's weighting of the (sub)gradient the OT across the validation dataset using optimal plan across batches म (Pe, (.y) rather than Batch-wise LAVA's 's uniform weighting. SAVA produces the best accuracy model of 70.0 + 0.2 in Figure
6 CONCLUSIONS
We have presented scalable extension LAVA address the challenges posed by large-scale datasets. Instead of relying on the expensive OT computation on the whole dataset, our proposed SAVA algorithm involves jointly optimizing multiple smaller OT tasks across batches of data points and within individual batches. We empirically show that SAVA maintains performance in data valuation tasks while successfully scaling up to handle large real-world noisy dataset. This makes the data valuation task feasible for large-scale datasets. Our proposed method, along with the theoretical correction (Just et al., 2023, Theorem 2), will complement, strengthen and improve (in terms of efficiency) OT-based data valuation.
Limitations. HOT finds the optimal coupling at the batch level, but not at the global level as in the traditional OT, i.e., OT(H; Mo) < HOT(pu; Pw), which makes the validation error bound looser (Just et al., 2023, Eq. (1), Theorem 1). However, our experiments indicate little performance degradation for small datasets between SAVA and LAVA. See Appendix B for further discussion on limitations.
ACKNOWLEDGEMENTS
We thank the chairs, anonymous reviewers for their comments, and Hoang Anh Just for helpful discussions. TL acknowledges the support of JSPS KAKENHI Grant number 23K 1243, and Mitsui Knowledge Industry Co., Ltd. grant.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We have described in detail our algorithm in Section 3 with Algorithm 1. All implementation details for our method and baselines are described in Section and expanded on in Appendix G. The code to reproduce all experiments can be found at https:://// pettps://githbee /ttttut..../g.o///g///ggg....t com/ skezle/ssssse sava.
REFERENCES
Amro Kamal Mohamed Abbas, Kushal Tirumala, Daniel Simig, Surya Ganguli, and Ari S Morcos. Semdedup: Data-efficient learning at web-scale through semantic deduplication. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models. 26
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed. Massively scalable Sinkhorn distances via the Nyström method. In Advances in Neural Information Processing Systems, pp. 4429-4439, 2019, 20
David Mevarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21428 22239,,,,, 2020. 3,
Deepak Baby, Pasquale D' Alterio, and Valentin Mendelev. Incremental learning for RNN-Transduce
based speech recognition models. 2022. 1, 23
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22-45 2015. 5
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference Learning Representations, 2019. 26
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances Neural Information Processing Systems, pp. 2292-2300, 2013. 3, 4, 6, 7,
M. Cuturi and A. Doucet. Fast computation of Wasserstein barycenters. In International conference on machine learning, pp. 685-693, 2014.
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's 's algorithm. In International
conference on machine learning, pp. 1367-1376. PMLR, 2018. 19
Aden Forrow,,Jn--hristeee Jan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference
on Artificial Intelligence and Statistics, pp. 2454-2465, 2019. 20
Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine learning. 18:133-168. 1997. 26
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183-1192, PMLR, 2017. 26
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large- scale optimal transport. In Advances in neural information processing systems, pp. 3448, 2016. 17
Aude Genevay, Gabriel Peyre, and Marco Cuturi. Learning generative models with Sinkhorn divergences. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, pp. 1608-1617) 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. 25
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016. 9, 24
11

---

Published as a conference paper at ICLR 2025
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXfv:2010.14701, 2020.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprini arxiv:/112.000
2011. 1. 26
Ruoxi Jia, David Dao, Boxin Wang, Frances A Hubis, Nezihe M Gürel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proceedings of the VLDB Endowment, 12( ((11):1610-162) 2019a. 25
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 on the Shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019b. 25
Angela Jiang, Daniel L-K Wong. Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary C Lipton, et al. Accelerating deep learning by focusing on the biggest losers. arXiv preprint 1xXiv:1900.0000 2019.
Kevin Fu Jiang, Weixin Liang, James Zou, and Yongchan Kwon. Opendataval: a unified benchmark for data valuation. 2023. URL https: /ttp///pppweeeeee////e/ee/ wwwp:/eeeffoffmmomm 9egXe3.. 26
Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate impor- tance sampling. Advances in Neural Information Processing Systems, 31, 2018. 26
Hoang Anh Just, Feiyang Kang, Tianhao Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. LAVA: Data valuation without pre-specified learning algorithms. International Conference on Learning Representations, 2023. 1, 2, 3, 4, 6, 7, 8, 9, 10, 16, 17, 18, 19, 20, 23, 26
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint vrXiv:2001.08360 2020.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International Conference Machine Learning, pp. 2525-2534. PMLR, 2018. 26
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in Neural Information Processing Systems, 32, 2019. 26
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894. PMLR, 2017. 9, 9,25
Yongchan Kwon and James Zou. Beta Shapley: unified and noise-reduced data valuation framework for machine learning. In International Conference on Al and Statistics, 2022. 25
Yongchan Kwon and James Zou. Data-oob: Out-of-bag estimate as a simple and efficient data value. In International Conference on Machine Learning, pp. 18135-18152. PMLR, 2023. 9, 26
Angeliki Lazaridou, Adhi Kuncoro, Elena Gribovskaya, Devang Agrawal, Adam Liska, Tayfun Terzi, Mai Gimenez, Cyprien de Masson d' Autume, Tomas Kocisky, Sebastian Ruder, et al. Mind the gap: Assessing temporal generalization in neural language models. Advances in Neural Information Processing Systems, 14:29348-29366 2021. 1
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of Wasserstein distances. In Advances in neural information processing systems, pp. 12283-12294, 2019, 5
Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. In International Conference on Artificial Intelligence and Statistics, pp. 1844-9868 PMLR, 2022. 5
12

---

Published as a conference paper at ICLR 2025
Tam Le, Truyen Nguyen, and Kenji Fukumizu. Scalable unbalanced Sobolev transport for measures on a graph. In International Conference on Artificial Intelligence and Statistics, pp. 8521-8560, 2023. 5
Tam Le. Truyen Nguyen, and Kenji Fukumizu. Generalized Sobolev transport for probability measures on a graph. In Forty-first International Conference on Machine Learning, 2024a.
Tam Le, Truyen Nguyen, and Kenji Fukumizu, Optimal transport for measures with noisy tree metric. In International Conference on Artificial Intelligence and Statistics, pp. 3115-3123, 2024b. 5
John Lee, Max Dabagia, Eva Dyer, and Christopher Rozell. Hierarchical optimal transport for multimodal distribution alignment. Advances in Neural Information Processing Systems, 32, 2019. 2,5, 16
Mingkun Li and Ishwar K Sethi. Confidence-based active learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(8):1251-120) 2006. 26
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuad Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In 25th Annual Network And Distributed System Security Symposium (NDSS 2018). Internet Soc, 2018. 9, 20
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv: 1.KKv:151110034444 1.06433, 2015. 26
Clare Lyle, Lisa Schut, Robin Ru, Yarin Gal, and Mark van der Wilk. A bayesian perspective on training speed and model selection. Advances in Neural Information Processing Systems, 33: 10396-10408, 2020.
Sören Mindermann, Jan Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Prioritized training on points that are learnable, worth learning, and not yet learnt. In International Conference Machine Learning. pp. 15630-15666 15649. PMLR, 2022. 2, 10, 26
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960. PMLR, 2020. 26
Khai Nguyen, Shujian Zhang, Tam Le, and Nhat Ho. Sliced Wasserstein with random-path projecting directions. In International Conference on Machine Learning, 2024.
Dongmin Park, Dimitris Papailiopoulos, and Kangwook Lee. Active learning strong baseline for data subset selection. In Has it Trained Yet? NeurlPS 2022 Workshop, 2022. 26
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. Advances Neural Information Processing Systems, 34: 20596-20607, 2021. 2, 10, 22,27 26
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends@ in Machine Learning, 11(5-6)335--077) 2019. 26
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. 2, 9, 21, 25
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 435-446, 2011.
Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. In International Conference on Machine Learning, pp. 18492-28511 PMLR, 2023. 1,
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pp. 4334-43444 4343. PMLR, 2018. 26
13

---

Published as a conference paper at ICLR 2025
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representations, 2019.
Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank Sinkhorn factorization, International Conference Machine Leurning (ICML), 2021. 20
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018. 26
Burr Settles. Active learning literature survey. 2009. 26
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. 10, 20, 21
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35: 15:13993-19928 2022. 1, 10, 26
Kushal Tirumala, Daniel Simig, Armen Aghajanyan, and Ari S Morcos. D4: Improving Ilm pretraining via document de-duplication and diversification. Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. 2, 26
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. 2018. 26
Hoang V. Tran, Thanh Chu, Minh-Khoi Nguyen-Nhat, Huyen Trang Pham, Tam Le, and Tan Minh Nguyen. Spherical tree-sliced Wasserstein distance. In The Thirteenth International Conference on Learning Representations, 2025a. 5
Hoang V. Tran, Khoi N.M. Nguyen, Trang Pham, Thanh T. Chu. Tam Le, and Tan M. Nguyen. Distance-based tree-sliced Wasserstein distance. In The Thirteenth International Conference on Learning Representations, 2025b. 5
Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelliencee and Statistics, pp. 6388-6421. PMLR, 2023. 26
Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. Threshold kNN- Aha-llapley: A linear-time and privacy-friendly approach to data valuation. arXiv preprint arXiv:2308. 15709, 2023. 25
Jiachen T Wang, Prateek Mittal, and Ruoxi Jia. Efficient data Shapley for weighted nearest neighbor algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 2557-2565
PMLR, 2024. 25
Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Davinz: Data valuation using deep neural networks at initialization. In International Conference on Machine Learning, pp. 24150-24176. PMLR, 2022. 26
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2691-2699, 2015. 10,20
Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy S Liang. Data selection for language models via importance resampling. Advances Neural Information Processing Systems, 36: 34201-34227, 2023. 26
Xinyi Xu, Zhaoxuan Wu. Chuan Sheng Foo, and Bryan Kian Hsiang Low. Validation free and replication robust volume- based data valuation. Advances Neural Information Processing Systems, 34:10837-10848 2021. 26
14

---

Published as a conference paper at ICLR 2025
Tom Yan and Ariel D Procaccia. If you like Shapley then you'll love the core. In Proceedings of the AAAI Conference on Artificial Intelligncce, volume 35, pp. 5751-5759, 2021. 26
Mikhail Yurochkin, Sebastian Claici, Edward Chien, Farzaneh Mirzazadeh, and Justin M Solomon. Hierarchical optimal transport for document representation. Advances in Neural Information Processing Systems, 32, 2019. 2, 5, 16
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12104-12113, 2022.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
In this appendix, we provide discussion regarding the border impact of our work in $A and the limitations of our work in $B. We also provide details of theoretical results in $C, describe the data corruptions used in our experiments $E. In &F, we further discuss how we calculate detection rates and discuss data valuation rankings. We also give details for the implementations used in the experiments in $G. In $H, we provide further empirical results. In $I, we present and discuss further related works. We also provide visualization for the artifacts in SAVA in $J, and other further discussions in K.
APPENDIX A BROADER IMPACT
Data selection in deep learning for training neural networks can significantly enhance the efficiency and effectiveness of model training. By enabling faster training and improved generalization perfor- mance, data selection techniques reduce the computational resources and time required, leading to notable environmental benefits such as lower energy consumption and reduced carbon footprint. By using, optimal transport approach to data valuation ensures high-quality, relevant data is selected, improving model performance. However, this approach also carries risks: a malicious actor could curate harmful validation dataset, leading the training of models dangerous unethical data. This underscores the importance of vigilance and ethical considerations in dataset creation and curation.
APPENDIX B LIMITATIONS
One theoretical limitation stated Section regards looser validation error bound (Just et al., 2023, Eq. (1), Theorem 1) due to the use of hierarchical optimal transport (Yurochkin et al., 2019; Lee et al., 2019). However, the validation error bound for SAVA remains useful as in LAVA since can be interpreted that minimizing either the OT or hierarchical OT between training and validation sets, and will bound the model's 's validation error. As we observe in practice, there is little difference in performance between SAVA and LAVA (Just al., 2023). Another limitation of OT-based data valuation methods is their dependence on a clean validation dataset.
Another limitation of work is that the ground We have not explored different ground truth costs for text data or speech data, which are interesting directions for future investigation.
consider is limited labeled datasets."
APPENDIX C DETAILS OF THEORETICAL RESULTS
C.I EXISTING THEOREM IN JUST AL. (2023)
Theorem 4 (restated Theorem in Just al. (2023)). The difference between calibrated gradients for two data points in D, and D. can be calculated as
0T (Pe,Pe) 0T (pu, Pw) 00T, (Pr, Üp, (2x)
00T, (MuHHe) 0p, (2x) N -
N
1
Öp4 (z+)
Öj4 (2,)
(x²)
( Dig
(C.1)
The above theorem analyzes the trade-off of using entropic regularization to estimate the OT gradient. However, the theoretical result suffers two key drawbacks that we correct below:
1. The original derivation ignores the positive constraint when deriving its dual formulation:
π 2 This positivity is essential to have the OT plan in the valid domain.
For unlabelled datasets, in some sense, it is equivalent to set the weight cnefficient 0, ignore the contribution of lahel information for the ground cost.
16

---

Published as a conference paper at ICLR 2025
2. In the proof of (Just al., 2023, Theorem 2), the authors have incorrectly written the relative entropy (i.e., Kullback-Leibler divergence) term for the discrete case
N N'
H @ no) =
log
(C.2)
=1
However, the correct term should be written follows used in (Cuturi, 2013; Genevay et al., 2016; 2018)
N
N'
(TE)
HT 8
=
Te
log
(z(z)))oozz)
(C.3)
1=
C.2 PROOF OF THEOREM 2
Theorem 5 (restated Theorem 2 in the main paper). The difference between calibrated gradients for two data points in D. and D. can be calculated as
00T (m) 00T (p), a0T, (14,, pr)
00T, (Me,
0pe (2+) 0p (2k)
0p4 (2:)
Opt (2k)
N
(TT))s (e(
hig his
+ N
log
(C.4)
(TT) (e()
where he is the corresponding optimal dual variable, accounting for non-negative constraint on the transportation plan in the primal OT formulation.
Proof. Using the same notation in LAVA (Just et al., 2023), the Lagrangian function for the standard OT formulation between datasets T3 and D..
b, f.9) (T, C) + (h, x) IN 0.) + 93 [N - b1)
(C.5)
where consider the dual variable for the corresponding constraint æ 0 in the primal OT, which was overlooked in LAVA. Additionally, fi with 1 < < N and 9j with 1 S < N are corresponding dual variables for the marginal constraints in OT.
The Lagrangian function for entropic regularized OT formulation between datasets D3 and D. is
N
N!
(Te)
Lg (Te. 9c) = (Tee C)
+
(Te) log
Me (zi) My (Ej)
1=1
N
Σ (fe); (Te) IN - ie (zi) +
Σ (ge) (IN (Te), tr (zj)), (C.6) j=1
where we correct the discrete formulation of entropic regularization (used in LAVA) in the second term the right-hand side. We have used the following notations:
I (1, ... 1) E ERR' Similarly, IN E Nx1,
is primal variable (i.e., the OT assignment matrix transporation plan). n.. is the 7th row of the matrix и. is the 7th column of matrix л.
The subscript é indicates primal/dual variables for corresponding entropic regularized OT:
Using the first-order necessary condition, have
VL (nt h² f" 0
(C.7)
V (Le) (Th fe g.) = 0
(C.8)
This could be typo within the derivation from Just al. (2023).
17

---

Published as a conference paper at ICLR 2025
where x² is the optimal solution to the primal formulation, and (h" f g9* are optimal solution to the dual problem.
For Vi {1,2..... ................................ NJ. and Vj
we have
VLx (T" 1 ,"), Cip + hig + f + 9 -0
(C.9)
(TE)
V (1e fe = Cis + log pe(z)))u(z))
+ + (fe) + (0=)
(C.10)
Let's subtract Eq. (C.10) from Eq. (C.9), we have
[ (fa);] [] [ge) +his logg (m))ag
Ne (e(z)) +1 0.
(C.11)
Similarly, Vk # i, k E {1, N.. we have
(mt) [ - (ff) + [j [9=) + thg - (log (r(zx)uo(Zz)
+1) = O.
(C.12)
Let's subtract Eq. (C.12) from Eq. (C.11) and rearrange, we have
[(fe); - ((t) - (f: ft) (hi hij) & log (TE) 25 (2()))
(C.13)
(Tt) pu (=A)
Additionally, from the definition of the calibrated (sub)gradient, we have
80T (Mt Me)
80T (Mes (e))
N
(fi - 12)
(C.14)
Ojh, (z:)
Oum (zk)
N
80T, (He, pw)
80T, (Mts (ut)
N
[(Gb] - (fe)
(C.15)
3p (z:)
Üht (zt)
N-1
Let's substract Eq. (C.14) from Eq. (C.15) and rearrange, we have
00T, (Pes
00T, (Me)Me)
80T (Me,
80T (M))
(C.16)
Op. (z:) 0p, (zx)
0p, (z:) Op, (Ex)
+ N
[(fe]] (fe) - (ff [f()]
(C.17)
Plugging Eq. (C.13) in Eq. (C.17), we have
80T, (He,Po)
80T, (He))e)
00T (p),
0OT Mu)
0c: (24) 0p, (Zk)
Opt (zx)
Opt (2k)
N
(mt)ss /14(2))
hij - h2
log
(C.18)
(TT) /Mb(zz)
Rearranging it again to be aligned with the result in Just et al. (2023), we conclude the proof
OOT (He,
00T (Hi,
Duc (2i)
Opc (2k)
a0T, (14))
80T, (Me.po)
N
log (r))g/mo(z)) + hig 1i3 ) (C.19) (Tt) Mo(2z)
Opc (zx)
Ope (zk)
N -
The term log (m²) (pp()) (01hy/P(ss)
is correction with respect to the corrected discrete formula for entropic
regularization. In addition, we have an extra term Ai where h² is the corresponding optimal dual variable, which accounts for 2 0 in the primal ÔT formulation.
18

---

of points from training class y/ and validation class v/y- N; and N are the number of points in Published as a conference paper at ICLR 2025
C.3 PROOF OF LEMMA
We present the Proof of Lemma 3 as follows by building upon the refined theory in Theorem 2 (i.e., the corrected version for Theorem 2 in Just et al. (2023)).
Lemma (restated Lemma the main paper). The difference between the calibrated gradients for two data points (=1, ( E B; C D. can be calculated as
(H 0pe(zz)
OHOT(HE,Ho) 0pr(z)
Kv
(Te
(Zk)
0μB, (21)
j=1
N₂ log
(Th (#t)as/He(z))
hi hkg )
]
+ N₂
(C.20)
(#t)ss/M(z))
where h is the corresponding optimal dual variable, accounting for nonnegative constraint on the transportation plan (i.e., क 2 0) in the primal OT formulation.
Proof. Let (T My) be the OT formulation between empirical measures and Mox we present the proof follows
HHOT(HI, @pe(zk)
(HOT(H:
(p)
(OT(HB,
プラ Ku my (o)
(C.21)
Ope, (Fk)
00T (H
a0T, (
Σj= Ty (We,
0pB, (=x)
0yz, (2r)
) .C222)
(log (8 (1)))//)))))) (#2)../paaa)
+ Mi -ig
N. -1
e
where Eq. (C.21) follows the definition of HOT and Eq. (C.22) utilizes our Theorem 2.
APPENDIX D SAVA TIME COMPLEXITY
Table Time complexity comparison for LAVA and SAVA methods. and V are the number of classes in the training and validation sets, the classes the same for the experiments in this paper. N and N' are the number of points in the training and validation sets, Ny, and No are the number
training and validation batch. K, and K, are the number of batches in the training and validation sets.
Time Complexity
LAVA
V X V Ny. Nr x log Ny. + N x N' x log N
SAVA
V x V' x No
log log Ne + K, K x log Ke Nog x log No,: + K, x K, N x N
For simplicity, we assume N > N', then Sinkhorn complexity is Ö(N x N' x N) (Dvurechensky al., 2018).
For LAVA, for the training dataset (i.e., big dataset), let V be the number of classes, N be the number of instances in class yt, then the total number of samples N Σ, Ny. Note that we use V N'. N' for the validation dataset (i.e., small dataset), and for simplicity, assume that N N' and Ng, > No To compute class-wise Wasserstein distance, we need to solve V x V OT problems with the
19

---

Published as a conference paper at ICLR 2025
Figure 4: Examples of the data corruptions used in our experimental setup. Examples of data from the CIFAR10 dataset where the images have corruptions: noisy features, trojan square, and poison frogs corruptions respectively.
complexity ÖNNg, x XNN' x log Ny.) Totally, the complexity ΣX= Σ/= Ö(N, NNy xlog Ny.) Additionally, we also need to solve OT between two datasets with complexity Ö(N x N' x log N). For SAVA, with the label-to-label eaching implementation, for the classwise Wasserstein distance, the total complexity is Σ'= Σ ÖNNig x N3 x log Niy.) where for each class yr, V'j, we sample Nig.: Niy; respectively for these classes. Let N₁, Ný be the number of samples in batches and K, K2 be the number of batches respectively, the total complexity to solve all batch level OT problems is Σ Kr Σ/= ONN N3 x log N:). Additionally, we need to solve more OT problem between batches Ö(K, x Ke x log K.). These time complexities are summarized in Table 2.
Further reducing computational complexity for Sinkhorn approach. One may leverage recent advanced techniques to further speed up the computation of Sinkhorn algorithm, e.g., low-rank approaches (Forrow et al., 2019; Altschuler al., 2019; Scetbon al., 2021).
APPENDIX E DATA CORRUPTIONS DESCRIPTIONS
We consider different corruptions our experiments (Section 5) that are applied to the training set following the settings in Just al. (2023):
Noisy labels. We corrupt a proportion of the labels in the training set by randomly assigning the target different label. This is common corruption found in webscale vision (Xiao et al., 2015) and speech (Radford et al., 2023) for instance.
Noisy features. We add Gaussian noise to certain proportion of the images in the training set to simulate common background noise corruptions that might occur in real datasets.
Backdoor attacks. certain proportion of the training is corrupted with a Trojan square attack Liu et al. (2018), e.g., corrupted images have 10 x 10 pixel square trigger mask added with random noise and are relabeled to the trojan "airplane" class, see Figure 4 for an example of corrupted image.
Poison detections. A certain proportion of training data from specific base class poisoned such that the features look similar to target class (Shafahi et al., 2018), Our target is the cat class from the CIFAR10 dataset, which is a randomly chosen image of cat from the test set. We take certain percentage of the base class which, in our case is the frog class from the CIFARI0 training dataset. Then we optimize the poisoned images themselves using gradient descent such that the feature spaces are close in Euclidean distance to the target cat image's features using pre-trained feature extractor model (in our case pre-trained ResNet18 model). This means that the poisoned images contain features that look like the cat class and the labels are kept the same, meaning that this a very difficult attack to detect, and the features of frogs are poisoned to look like cats and labels remain uncorrupted. See Figure 4 for example of poisoned frog image.
20

---

Published as a conference paper at ICLR 2025
1.00
Detection rate
0.75
LAVA
Random
0.50
KNN Shapley
TracInCP
0.25
SAVA
0.00
2000
4000
Data Value Ranking
Figure 5: Data value rankings for various methods for the 10% poison frogs corruption. The number of corrupt datapoints in the prefix determines the detection rate. The black dashed line represents the N/4 prefix which is used for calculating the detection rates in Figure and Figure 7.
APPENDIX F DATA VALUATION RANKINGS
Corrupt data points are likely to be assigned a high value (a low value for KNN Shapley) and so can be used for ranking the data by importance. Therefore, following Pruthi al. (2020), we sort the training examples by their value in descending order (ascending order for KNN Shapley). An effective data valuation method would rank corrupted examples toward the start of the data valuation ranking. We use the fraction of corrupted data recovered by the prefix of size N/4 as detection rate to measure the effectiveness of various methods in Figure 2, See Figure for an example of this using a poison frogs (Shafahi et al., 2018) corruption on 10% of dataset of size 5k CIFAR10.
APPENDIX G IMPLEMENTATION DETAILS
G.1 CIFARIO CORRUPTION DETECTION
We use a single Nvidia K80 GPU to run all experiments.
SAVA. For both SAVA and LAVA the metric between label spaces computed using the the exact OT distances between conditional empirical measures for each label and we do not use Gaussian approximations proposed in Alvarez-Melis & Fusi (2020).
TracInCP. In practice, TracInCP measures the influence of training point by the dot product of the gradient of the NN model parameters evaluated on the validation set and the gradient of the NN model parameters evaluated the specific training points, summed throughout training using saved checkpoints of a ResNet18 model trained for 100 epochs and achieves a test accuracy of 83% and training accuracy of 99%. We calculate gradients checkpoint to calculate TracInCP values, these design choices result in fewer approximations than the original implementation (Pruthi et al., 2020).
the entire model and use every second
Influence Functions. We use the following repository for obtaining results on influence functions with default parameters as given iireence_functionn
KNN Shapley. The method is very sensitive to which is hyperparameter in the kNN algorithm used to approximate the expensive calculation of the Shapley value. We do grid search k E {5, 10, 20, 50, 100, 200, 500, 1,000, 2,000} on a validation set of size 1,000 and training set of size 2,000, where the validation set is taken from the CIFARIO training set. Our implementation is the same as that used in the LAVA.
Data-OOB. We use the default hyperparameters and use the implementation, given https: wtccchuuu.oommm/ www.oo////o//. com/ykwon0407 dat
//github.
Pruning. For the pruning experiments we greedily prune N/4 of the ranked points with the lowest value; the highest gradient of the OT for SAVA and LAVA. We then train ResNet 88 with the SGD
21

---

Published as a conference paper at ICLR 2025
Noisy Labels
Noisy Features
95
Pruned Test Acc.
90
90
80
85
LAVA
LAVA OOM
80
KNN SV
70
SAVA
75
60
2
2
Task
Task
Figure 6: SAVA can value more data as dataset incrementally increases in size. For each task, we value the data and prune 30% of the data which we then train a CNN to obtain a test accuracy. Left: 30% noisy labels setting. Right: 30% noisy feature setting. The star symbol (*)) denotes the point at which LAVA is unable to continue valuing training due GPU out-of memory errors.
optimizer with weight decay of 5 x 10 and momentum of 0.9 for 200 epochs with learning rate schedule where for the first 100 epochs the learning rate is 0.1, then for the next 50 epochs the learning rate is 0.01, then the final 50 epochs the learning rate is 0.001.
G.2 CLOTHINGIM
For all experiments, we use node with Nvidia K8O GPUs.
We use a ResNet18 model for feature extraction and for obtaining a final performance metric. We use an Adam optimizer with a weight decay of 0.002. Since the pruned datasets can be different sizes depending the amount of pruning. We train for fixed number of 100k steps. We use a learning rate schedule where for the first 30k steps the learning rate 0.1 then the next 30k steps the learning rate is 0.05 then the next 20k steps the learning rate is 0.01, then the next 10k steps the learning rate 0.001, then the next 5k steps the learning rate is 0.0001 then for the final 5k steps the learning rate 0.00001.
G.2.1 SAVA
SAVA has remarkably few design choices in comparison to other data pruning methods like EL2N (Ap- pendix G.2.2) and supervised prototypes (Appendix G.2.3). We train a ResNet18 encoder using the clean training set of size 47,570. Note we do not use this training set to obtain final accuracies in Figure 3, we only use the large noisy training set for obtaining the results in Figure 3. We use a batch size of 2048 for valuation and use label-2-labe matrix caching (Appendix H).
G.2.2 EL2N
To obtain values for the points in our noisy training set to then decide which training points to prune, we obtain our EL2N scores by training for 10 epochs 10 separate ResNet18 models on the clean training set of size 47,5 47,570.
We also hyperparameter optimize the offise E {0.0, 0.05, 0.1) using sliding window which covers 90% of points $4 (Paul et al., 2021). This is to decide which range of ranked values to keep/ prune. We find that using an offset of 0.0 worked best, so high values of the EL2N score will get pruned.
G.2.3 SUPERVISED PROTOTYPES
We train image encoder using classification objective the clean training set provided in the Clothing IM dataset of size 47,570. Note, that we do not use this dataset to train to augment the pruned noisy training sets after valuation and
not used for the results in Figure 3.
We use batc- k-means clustering to obtain centroids for our image embeddings. We tune the mini-batch k-means learning rate over the grid (0.1, 0.05, 0.01, 0.005, 0.001) and the number of
22

---

Published as a conference paper at ICLR 2025
LAVA
LAVA DOM
KNN Shapley
SAWA
Noisy Features (30%)
Noisy Labels (30%)
90
Pruned Test Acc.
80
80
70
60
50
0.5
1.0
2.0
5.0
0.5
1.0
2.0
5.0
Training Set Size x10*
Training Size
x10*
Figure 7: SAVA can scale to the full CIFAR10 dataset emabling better data selection performance. After valuation, we prune a prefix of size N/4 and train a ResNet18 model on the remaining points to report test accuracy. The symbol (+) denotes the point at which LAVA is unable to continue valuing training due to GPU out-of memory (OOM) errors.
Algorithm 2 Incremental learning experimental setup.
Input: noisy training dataset initally empty D, := Ø and clean validation set Tr,, data pruning proportion E [0, 1].
Output: trained model M. for 1,.., T do
Get new data DT.- Merge Dr, with existing dataset D3; D, Dy, Get valuation scores for D, by comparing to D.. Prune proportion p with the highest data values: ID. Train model M on D, and evaluate M on ID,.
centroids over the grid (1,000, 2,000, 5,000, 10,000} using the intra cluster mean-squared error the validation dataset.
The best configuration uses k-means clustering learning rate of 0.05 and 10,000 cluster centers. Then we can obtain cosine distances between every data point and its assigned cluster center and prune points which look the most prototypical before training classifier the pruned dataset.
APPENDIX H ADDITIONAL EXPERIMENTS
H.1 CORRUPTION EXPERIMENTS PRUNING PERFORMANCE
We can prune the N/4 data points and train a classifier on the pruned dataset in Figure 7. SAVA can value larger and larger pool of training data. The subsequently pruned dataset provides better and better performance as more clean data-which resembles the validation set-is used for training. In contrast, LAVA has an OOM issue for the largest dataset when running the Sinkhorn algorithm training set of size 50K. As result, the performance of the ResNet18 model does not improve when valuing larger training sets with LAVA.
H.2 INCREMENTAL LEARNING
We split the CIFARIO dataset into equally sized partitions with all classes, and we incrementally build up the dataset such that it grows in size one would train production system (Baby et al., 2022). We inject the data with noisy labels and noisy feature corruptions, then perform the data valuation. We compare set which is incrementally updated and grows in size throughout the incremental learning, we greedily discard 30% of the data that are the most dissimilar the validation and train the pruned
proposed method with LAVA (Just et al., 2023). After valuing
training
23

---

Published as a conference paper at ICLR 2025
x10"
Detection rate
Runtime (secs.)
0.975
0.950
0.925
0.900
128
256 512 10242048
128 512 102420484096 Batch size
Batch size
Figure 8: SAVA performance as function of the batch size, N₁. The CIFAR10 dataset with noisy label detection. Left: Detection rate. Right: detection runtimes in seconds.
Detection rate
0.850
Runtime (sec.)
104
SAVA
0.825
LAVA
KNN Shapley
0.800
Batchwise LAVA 12I
0.775
SAVA 121
102
0.750
0.1
0.5 2.0
5.0
0.1
0.5 1.0 2.0
5.0
Training Set Size
x10*
Training Set Size
x10*
Figure 9: Label-to-label matrix caching significantly reduces runtime. Left: SAVA with and without label-2-label (121) matrix caching performs similarly detecting noisy label corruption. Right: SAVA with 121 runs just quickly as LAVA in terms of runtime in seconds on the same GPU.
dataset. We report the final accuracy of ResNet18 (He et al., 2016) model. We summarize this experimental setup in Algorithm 2.
H.3 PERFORMANCE FUNCTION OF BATCH SIZE
Following the discussion the batch size in Section 4, we measure our model performance w.r.t. different batch sizes N; {128, 4.096.. We show that the performance converges with increasing batch sizes. In this particular setting, the batch sizes of 1,024, 2,048, and 4,096 will perform comparably in terms detection rate while the batch size 4,096 will consume less time for computation of the cost across batches, since there are less and K; is lower.
H.4 LABEL-TO-LABEL DISTANCE CACHING
We study the difference in performance and runtime between SAVA Algorithm and using SAVA with label-to-label (12l) matrix caching discussed in Section 4 using CIFAR10 with noisy label corruptions. We show that there are almost identical detection rates between the two variants of SAVA with and without 121 caching Figure 9. Meanwhile, the runtime is significantly reduced using this caching strategy and is similar to LAVA despite having to solve quadratic number of small batch-level OT problems.
H.5 CONSTRUCTING BATCHES
We explore two options for constructing the batches including random sampling and stratified sampling in Figure 10. Since (uniformly) random sampling could result in batch with uneven distribution classes, this could degrade the calculation of the wliss-wise Wasserstein distance Eq. compare random sampling
(8). To mitigate, against any imbalance which evenly samples from each class to construct a batch. When valuing 10k points from the CIFAR10 1 dataset with corrupted features, find little difference in detection rates between these
stratified sampling
24

---

Published as a conference paper at ICLR 2025
0.8
Detection rate
0.7
0.6
Strat. Sampling Rand. Sampling
128
256
512 1024 2048 4096 Batch size
Figure 10: Randomly sampling data for batch construction robust. Detection rates for SAVA for random sampling construct batch versus stratified sampling which evenly samples data from different classes. The detection rates are calculated after valuation by inspecting the fraction of corrupted data for a prefix of size N/4 for CIFAR10 with noisy features.
Batch-wise LAVA
SAVA
Backdoor Det.
Poison Det.
Noisy Features
Noisy Labels
1.0
1.0
Detection rate
0.95
0.8
0.90
0.9
0.85
0.4
0.8
0.80
0.2
0.4
128 256
102420484096
128
142424440096
128 256 102420484096
128 256 102420484096
Batch size
Batch size
Batch size
Batch size
Figure 11: Batch-wist wise LAVA is not robust to different batchsizes. For 4 different corruptions training dataset of size 5k with validation dataset size 2k we measure the detection rate for varying batch sizes for SAVA and Batch-wise LAVA. The dashed grey line centered on 1024 denotes the batch size used in Figure
two sampling schemes. This might consideration when the ratio of the number classes in the dataset to the batch size is higher.
H.6 ON THE ROBUSTNESS OF BATCH-WISE LAVA
From the corruption detection experiments, we established that Batch-wise LAVA has remarkable performance in Section 5. However, as we vary the batch-size we notice that for small batch-sizes and large batch-sizes Batch-wise LAVA performance deteriorates dramatically Figure 1. For small batches this is due to Batch-wise LAVA not having enough clean points the validation batch to detect corrupt data points in the training batch. For large batches the final batch in the dataloader usually smaller than the specified batch-size and so these data points the final batch will also suffer from not enough points in the validation batch compare against. SAVA is able to overcome this issue since the information from all batches aggregated and weighted by the optimal plan between batches, my (fe; Po), in lines and 10 in Algorithm 1.
APPENDIX RELATED WORKS
Data valuation. simple way to value datapoint through the leave-out-out (LOO) error; i.e. the change in performance when the point is omitted, this is inefficient to perform in practice. Influence functions (Koh & Liang, 2017) approximate LOO retraining using expensive approximations of the Hessian of the NN weights. In similar vein, TracIn (Pruthi et al., 2020) traces the influence of training point on a test point by looking at the difference in the loss throughout training. Another way to value data is by using data Shapley values Ghorbani & Zou (2019); Jia et al. (2019b), extensions include the Beta Shapley (Kwon & Zou, 2022). K-nearest neighbour models can address the computation cost of the data Shapley (Jia et al., 2019a; Wang al., 2023; 2024). Instead of using
25

---

Published as a conference paper at ICLR 2025
the Shapley value one can use "the core" from the game theory literature for data valuation (Yan & Procaccia, 2021). An entire dataset can be valued by its diversity, practically this can be done by assessing its volume: the determinant of the left Gram (Xu et al., 2021). An initialized model can also be utilized for data valuation where sets are available from contributors (Wu et al., 2022). The Banzhaf value can also be used for data valuation (Wang & Jia, 2023). Data valuation using out-of-bag estimators have also been shown to be effective (Kwon & Zou, 2023). Our approach builds upon LAVA which uses the gradient OT distance between the validation and training sets to assign a value to training points (Just et al., 2023). The Open Val benchmark is available with many implementations of data valuation methods (Jiang et al., 2023).
Active learning. Active learning is characterized by selecting points from an unlabeled pool of data for labeling and then using the newly labeled datapoint to update a model (Settles, 2009). Active learning is related to data valuation since notion of importance is needed to value unlabeled points to then select a label. Unlabeled samples can be valued by using the prediction disagreement from probabilistic model (Houlsby et al., 20.1). this disagreement can also be obtained from multiple models (Freund et al., 1997). This approach of using the disagreement of probabílistic model can also be thought of as selecting points to label which are the most uncertain via the predictive entropy using probabilistic neural networks (Gal et al., 2017; Kirsch et al., 2019). Alternativly picking points to label can be thought of summarization problem by obtaining a coreset of representative data (Sener & Savarese, 2018; Mirzasoleiman et al., 2020; Coleman et al., 2019). Samples to be labeled can be selected by interpreting the classifier output probabilities as a confidence (Li & Sethi, 2006).
Data selection. Active learning is used to select points to label and so its importance metric doesn't ' use label information, however, it has been shown to achieve competitive results for data selection; speeding up the generalization curve over the course of training (Park et al., 2022). The influence a point has on the training loss as metric of informativeness has been shown to accelerate the training of neural networks (Loshchilov & Hutter, 2015). Similarly picking points that reduce the variance of the gradient speeds up training (K (Katharopoulos & Fleuret, 2018; Johnson & Guestrin, 2018). Instead of focusing on the training loss, one can select data according to the influence on the validation loss (Mindermann et al., 2022). Instead of selecting data to train on, one can equivalently prune away uninformative data. The data's contribution of the gradient norm of the loss with respect to model parameters is a natural measure for deciding which datapoints to prune from a dataset (Paul et al., 2021). One can also prune data by how similar embeddings are to a cluster center or prototype (Sorscher et al., 2022) and by assessing diversity within each cluster (Abbas et al.: Tirumala et al., 2023). It has also been shown that pruning data according to how easy they are to be forgotten over the course of training as measure of difficulty results in training on less data while maintaining performance (Toneva et al., 2018). These data selection methods although related, do not directly measure the importance of each training datapoint with respect to a clean validation set like LAVA (Just et al., 2023) and SAVA. Meta-learning is also used to learn datapoint importance weights by evaluating with a clean validation set (Ren et al., 2018). Similarly to LAVA and SAVA the distributional distance between clean validation set and a large noisy dataset can be assessed using n-grams in NLP for selecting data to train large language models (Xie et al., 2023).
APPENDIX J SAVA VISUALIZATION
To gain insight into how the estimated OT matrices from our proposed SAVA, we visualize the artifacts Algorithm in Figure 12.
APPENDIX K OTHER DISCUSSIONS
Overlitting and Approximation. Recently, Peyré & Cuturi (2019, $8.4) revealed an important property that solving exactly the OT problem may lead to overfitting. Therefore, investing excessive efforts to compute OT exactly would not only be expensive but also self-defeating since it would lead to overfitting within the computation of OT itself. As a result, our batch approximation can be considered a regularization for OT. We show empirically for certain cases that the batch approximation (SAVA) performs better than the original OT (LÁVA) in terms of quality while we surpass LAVA in memory requirement.
26

---

Published as a conference paper at ICLR 2025
Cij(Pi pho)
This (Tte, (bbe
Costs Across Batches
Plan Across Batches
19
18
17
K
16
1.5
0.02
1.4
K
Ck (B;
कe (LB,, HBB)
Cost Across Datapoints in B;, B'
Plan Across Datapoints in B;, B3
20000
17500
15000
12500
N
10000
7500
16
5000
-19
2500
N
Figure 12: Visualization of the main artifacts in Algorithm For a noisy CIFAR10 valuation problem with a training and validation set size of 10k and SAVA batch size of 1024, we visualize the main artifacts of the SAVA algorithm for illustrative purposes. From left to right, from top row to the bottom row: the first matrix is the cost matrix between batches: C( (ba) and then the optimal plan # (Ma F.)) the associated plan which the solution to the optimal transport problem. In the second row visualize C(HB, (B;) ) the optimal transport distance between points in the final batch B, from the training set and the final batch B' in the validation and its corresponding optimal plan x (J MB;)), we have used a log transform to on the optimal plan between datapoints to help viewing
27


Reviews:
[{"review_id": "S2ePN70JFQ", "reviewer": "Reviewer_94Rm", "summary": "This paper investigates of the problem of extending Optimal Transport (OT) distance-based data valuation methods for larger scale problems. The paper points out that for current methods, the quadratic overhead for expensive GPU memory constrained the scale of problems they can be applied to. Correspondingly, this paper proposes to compute the OT problem in a batch-wise fashion where the batch-wise results are aggregated via an hierarchical OT framework to produce data point valuations. This approach allows converting intractable large-scale OT problems into a series of smaller problems that can be solved efficiently. Empirical results on a variety of tasks show the proposed approach achieves competitive performance compared to original methods while being applicable to larger-scale problems.", "questions": "Other than hierarchical OT and the proposed implementation, there are some other ideas for mitigating OT efficiency issues.\n\nSome standard approaches include low-rank approximation to the transportation matrix C, which is often possible for practical cases. This allows representing the large matrix C with multiplication of smaller matrices and avoids directly materilizing the large matrix C and OOM issues. \n\nAnother somewhat connected idea is to directly quantize the train and validation distributions (e.g., approximate the distributions via downsampling) to simplify the OT problem.\n\nHierarchical OT can also be conducted with clustering methods. For example, at the lower level, group all the samples into a number of clusters, and at the higher level, solve the OT problem between the centroids of clusters. \n\nIt will be very interesting to see how to connect the proposed framework to these ideas and whether they may help further improving the computation complexity or accuracy.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well-contextualized and the motivation is clear. Structure of the paper is well balanced and the elaborations are coherent. It is straightforward for readers to understand the scope and target of the paper and the proposed technical approaches.\n\nThe proposed method is plausible, leveraging the hierarhical OT framework to aggregate results from batch-wise OT computations and achieving favorable approximation results.\n\nDerivations are comprehensive and are paired with substantial elaborations. Empirical evaluations are diverse and abundant and the results are valid.", "weaknesses": "I am still somewhat concerned about the computation overhead for SAVA. Even it avoids directly solving large-scale OT problems and circumvents OOM issues, it now requires solving a quadratic number of OT problems between every pair of batches and aggregating their results. This could also take a significant amount of time if the number of batches are high.\n\nAre there results on actual time comparisons for the methods in empirical studies?\n\nThe structure of the paper still has room to improve. The current layout is dense where there are many equations and lemmas interleaved with elaborations. There's an overhead for the readers to familiarize with the notations before being able to catch up with the ideas. It could be made more straightforward.\n\nFor example, the crucial Figure 1 and Algorithm 1 are not self-contained. Many of the involved notations are not straightforward and also not introduced in the captions. It still requires readers to first read through the texts and derivations to understand what is being done. Strongly suggests authors to make an effort to improve these visualizations, which could substantially improve the paper's accessibility and impact.", "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": "", "extra_scores": {}}, {"review_id": "cpGPMHNbvU", "reviewer": "Reviewer_ckNn", "summary": "This paper develops a variant of LAVA, called SAVA, for scalable data valuation. The idea is perform data valuation on batches of data instead of on the entire dataset. Extensive numerical results are presented to demonstrate SAVA's efficiency.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The experimental results are convincing. The authors compared to SOTA methods for data valuation across various data corruption scenarios. The results demonstrate that SAVA is scalable to large datasets. Also, the results included a dataset of size larger than 1 million samples, in which the proposed method outperforms benchmarks. \n\n- The writing is good and easy to follow.", "weaknesses": "- The reviewer's biggest concern is related to novelty. Currently, SAVA seems a very natural extension of LAVA for data valuation on batches. The submission seems to be on the incremental side, unless the authors can clearly state the technical challenge when calculating on batches. \n\n- The choice of batch size is a key hyper-parameter in SAVA (and key difference to LAVA). The authors are suggested to include formal theoretical analysis to quantify the tradeoff in choosing batch size between memory and calculation approximation. Also, Appendix G should appear in the main text. \n\n- The authors are suggested to include a table comparing the complexities of LAVA and SAVA. \n\n- What happens if the validation dataset gets corrupted? \n\n- In Fig. 3, why is the performance of SAVA dropping at .4 proportion?", "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": "", "extra_scores": {}}, {"review_id": "lZ3FTyhwCu", "reviewer": "Reviewer_RqVV", "summary": "This paper proposes a new learning-agnostic data valuation approach that assigns a value to each data point in the training set based on its similarity to the validation set. They introduce SAVA, a scalable variant of the LAVA algorithm, which uses optimal transport (OT) sensitivity to value training data without directly concerning model performance efficiently. Unlike LAVA requiring the entire dataset as input, SAVA operates on batches of data points, making it has a smaller memory consumption. Thus, SAVA can make the valuation taks of larger datasets possible. The authors conduct extensive experiments showing that SAVA can effectively scale to large datasets and maintain data valuation performance across various downstream tasks.", "questions": "pls see W2", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "[S1] An interesting approach leveraging the idea of batches to solve the memory bottleneck encountered in OT solver as optimizer in model training.\n\n[S2] Detailed theoretical proofs and descriptions of previous work are given.\n\n[S3] The article is well-organized and easy to read.", "weaknesses": "[W1] My biggest concern is the proof of the upper bound does not adequately explain why this proxy can work.  Detailed analysis on the upper bound of the proxy practicability should be taken.\n\n[W2] My second concern is that the paper lacks of time complexity analysis. And SAVA in Figure 2 seems to be no better than Batch-wise LAVA. In the appendix Figure 9, why not compare Batch-wise LAVA in running time metric? \n\n[W3] Typos: Line 417, \"Batch-wise LAVA KNN Shapley and\" -> \"Batch-wise LAVA, KNN Shapley, and\"\n\nPlacing Table 1 in Section 2 would help to improve understanding.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)