SAVA: Scalable Learning-Agnostic Data Valuation

## Abstract

Abstract Selecting suitable 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 artifacts will impact the performance and generalization of the model. 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 ) successfully 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 whole dataset as an input, this limits its application to large 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. We perform extensive experiments, to demonstrate that SAVA can scale to large datasets with millions of data points and doesn’t trade off data valuation performance.

## 1 Introduction

Neural scaling laws empirically show that the generalization error decreases according to a power law as the data a model trains on increases. This has been shown for natural language processing, vision, and speech (Kaplan et al.,, ; Henighan et al.,, ; Rosenfeld et al.,, ; Zhai et al.,, ; Radford et al.,, ). However, training neural networks on larger and larger datasets for moderate improvements in model accuracy is inefficient. Furthermore, production neural network models need to be continuously updated given new utterances that enter into common everyday parlance (Lazaridou et al.,, ; Baby et al.,, ). It has been shown both in theory and in practice that sub-power law, exponential scaling of model performance with dataset size is possible by carefully selecting informative data and pruning uninformative data (Sorscher et al.,, ), and that generalization improves with training speed (Lyle et al.,, ). Therefore, valuing and selecting data 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.,, ; Tirumala et al.,, ).

Figure: Figure 1: Overview of the proposed *SAVA* method. Instead of solving a single, but expensive, OT problem on the whole *dataset*, *SAVA* considers solving multiple cheaper smaller OT problems on *batches* of data points, and integrates the resulting calibrated gradients together for a data valuation task. $\text{OT}(\bar{\mu_{t}},\bar{\mu_{v}})$ denotes the OT cost and $\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})$ is its associated optimal transport plan. $\text{OT}(\mu_{B_{i}},\mu_{B_{j}^{\prime}})$ is the OT between a uniform distribution of points in the batch $B_{i}$ from the training set and the batch $B^{\prime}_{j}$ in the validation set. $s_{k}$ is *SAVA*’s final valuation score for training data point $z_{k}$. We provide a visualization of these artifacts generated by *SAVA* in Figure 12.
Refer to caption: x1.png

Popular data selection and data pruning methods use variations of the model loss to value data points (Jiang et al.,, ; Pruthi et al.,, ; Paul et al.,, ). Crucially, these methods depend on 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 a 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 on a neural network model, a promising idea is to leverage optimal transport (OT) between a training distribution and a clean validation distribution as a 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 and Fusi,, ; Just et al.,, ). *LAVA* (Just et al.,, ) 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 $\mathcal{O}(N^{2})$ with the dataset size $N$. This hinders *LAVA* from scaling to large datasets.

In this paper, we 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 computations on batches instead of on the entire dataset like *LAVA* (hence the analogy to the stochastic approach to gradient computation). Specifically, *SAVA* uses ideas from hierarchical optimal transport (Yurochkin et al.,, ; Lee et al.,, ) to enable OT calculations on batches instead of the entire dataset. We can scale up OT-based 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:

1. We introduce a novel scalable data valuation method called *SAVA* that leverages hierarchical optimal transport (Yurochkin et al.,, ; Lee et al.,, ) which performs OT computations on batches of data points, enabling OT-based data valuation to large datasets.

2. We provide an extensive experimental analysis to demonstrate the improved scalability with increasing dataset sizes with respect to baselines.

## 2 Optimal Transport for Data Valuation

### 2.1 Optimal Transport for Labeled Datasets

Let ${\mathcal{X}}$ be the feature space, and $V$ be the number of labels. We write $f_{t}:{\mathcal{X}}\mapsto\left\{0,1\right\}^{V}$ and $f_{v}:{\mathcal{X}}\mapsto\left\{0,1\right\}^{V}$ for the labeling functions for training and validation data respectively. Given the training set ${\mathbb{D}}_{t}=\left\{(x_{i},f_{t}(x_{i}))\right\}_{i=1}^{N}$ and the validation set ${\mathbb{D}}_{v}=\left\{(x^{\prime}_{i},f_{v}(x^{\prime}_{i}))\right\}_{i=1}^{
N^{\prime}}$, the corresponding measures for sets ${\mathbb{D}}_{t},{\mathbb{D}}_{v}$ are $\mu_{t}(x,y)=\frac{1}{N}\sum_{i=1}^{N}\delta_{(x_{i},y_{i})}$ and $\mu_{v}(x^{\prime},y^{\prime})=\frac{1}{N^{\prime}}\sum_{i=1}^{N^{\prime}}
\delta_{(x^{\prime}_{i},y^{\prime}_{i})}$ respectively where $\delta$ is the Dirac function, and $y,y^{\prime}$ are labels of $x,x^{\prime}$ respectively. For simplicity, let ${\mathcal{Z}}=({\mathcal{X}},{\mathcal{Y}})$ where ${\mathcal{Y}}$ is the space of labels. For ease of reading, we summarize all notations in Appendix Table 1.

Following Alvarez-Melis and Fusi, (), we compute the distance between two labels by leveraging the OT distance between the conditional distributions of the features given each label. More concretely, for label $y_{t}$ in $\mu_{t}$, the conditional distribution of the features given $y_{t}$ in $\mu_{t}$ is as
$\mu_{t}(\cdot|y_{t})=\frac{\mu_{t}(\cdot)I[f_{t}(\cdot)=y_{t}]}{\int\mu_{t}(
\cdot)I[f_{t}(\cdot)=y_{t}]}$,
where $I$ is the indicator function (similarly for label $y_{v}$ in $\mu_{v}$). Let d be the metric of the feature space ${\mathcal{X}}$, e.g., we use the Euclidean distance for d in practice. The distance between labels $y_{t}$ and $y_{v}$ is $\textnormal{OT}_{{\textnormal{d}}}(\mu_{t}(\cdot|y_{t}),\mu_{v}(\cdot|y_{v}))$, i.e., the metric of the label space ${\mathcal{Y}}$. Thus, we can compute the transport cost function between feature-label pairs in ${\mathcal{Z}}=({\mathcal{X}},{\mathcal{Y}})$ as follows

$$ ${\textnormal{C}}((x_{t},y_{t}),(x_{v},y_{v}))={\textnormal{d}}(x_{t},x_{v})+c \,\textnormal{OT}_{{\textnormal{d}}}(\mu_{t}(\cdot|y_{t}),\mu_{v}(\cdot|y_{v})),$ (1) $$

where $c>0$ is a weight coefficient.
Given the cost matrix C for labeled data points (i.e., feature-label points in ${\mathcal{Z}}$) in Eq. (1), we can use the OT on the represented measures $\mu_{t},\mu_{v}$ to compute the distance between the training and validation sets, i.e., $d({\mathbb{D}}_{t},{\mathbb{D}}_{v})$, without relying on external models or parameters. It is worth noting that the cost matrix is hierarchically defined; it is dependent on the solution of the OT problem between labels Eq. (1). More concretely, we have

$$ $\textnormal{OT}_{{\textnormal{C}}}(\mu_{t},\mu_{v})=\min_{\pi\in\Pi(\mu_{t}, \mu_{v})}\int_{{\mathcal{Z}}\times{\mathcal{Z}}}{\textnormal{C}}(z,z^{\prime}) d\pi(z,z^{\prime}),$ (2) $$

where $\Pi(\mu_{t},\mu_{v})$ is the set of transportation couplings which have marginals as $\mu_{t}$ and $\mu_{v}$. To simplify notations, we drop C, and use OT when the context is clear. We further write $\pi^{*}$ for the optimal transport plan in Eq. (2). To deal with high computational complexity, i.e., super cubic w.r.t. the number of supports of input measures, an efficient approach utilizes entropic regularization (Cuturi,, ) to reduce its complexity into quadratic, defined as

$$ $\displaystyle\textnormal{OT}_{\varepsilon}(\mu_{t},\mu_{v})=\min_{\pi\in\Pi( \mu_{t},\mu_{v})}\int_{{\mathcal{Z}}\times{\mathcal{Z}}}{\textnormal{C}}(z,z^{ \prime})d\pi(z,z^{\prime})+\varepsilon H(\pi\mid\mu_{t}\otimes\mu_{v}),$ (3) $$

where $\otimes$ is the product measure operator, and $H(\pi\mid\mu_{t}\otimes\mu_{v})=\int_{{\mathcal{Z}}\times{\mathcal{Z}}}\log
\left(\frac{d\pi}{d\mu_{t}d\mu_{v}}\right)d\pi$.

Additionally, the OT problem in Eq. (2) is a constrained convex minimization, it is naturally paired with a dual problem, i.e., constrained concave maximization problem, as follows:

$$ $\textnormal{OT}_{{\textnormal{C}}}(\mu_{t},\mu_{v})=\max_{(f,g)\in{\mathcal{R} }({\textnormal{C}})}\left<f,\mu_{t}\right>+\left<g,\mu_{v}\right>,$ (4) $$

where ${\mathcal{R}}({\textnormal{C}})=\left\{(f,g)\in{\mathcal{C}}({\mathcal{Z}})
\times{\mathcal{C}}({\mathcal{Z}}):\forall(z,z^{\prime}),f(z)+g(z^{\prime})
\leq{\textnormal{C}}(z,z^{\prime})\right\}$, ${\mathcal{C}}$ is a collection of continuous functions, and $\left<f,\mu_{t}\right>=\int_{{\mathcal{Z}}}f(z)d\mu_{t}(z)$, similarly for $\left<g,\mu_{v}\right>$.

### 2.2 LAVA: Data valuation via calibrated OT gradients

As mentioned in Just et al., (), the OT distance is known to be insensitive to small differences while also being not robust to large deviations. This feature is naturally suitable for detecting abnormal data points, i.e., disregarding normal variations in distances between clean data while being sensitive to abnormal
distances of outlying points. Therefore, the gradient of the OT distance w.r.t. the probability mass associated with each point can be leveraged as a surrogate to measure the contribution of that point. More precisely, the gradient of the OT distance w.r.t. the probability mass of data points in the two datasets can be expressed:

$$ $\nabla_{\mu_{t}}\textnormal{OT}(f^{*},g^{*})=(f^{*})^{T},\hskip 3.99994pt \nabla_{\mu_{v}}\textnormal{OT}(f^{*},g^{*})=(g^{*})^{T}.$ (5) $$

Note that we can leverage the Sinkhorn algorithm to solve the entropic regularized OT, i.e., $\textnormal{OT}_{\varepsilon}(\mu_{t},\mu_{v})$, and obtain the optimal dual variables $(f^{*},g^{*})$ as its by-product, for computing the gradient of entropic regularized OT w.r.t. the mass of support data points of input measures.

The dual solution is unique, up to a constant due to the redundant constraint $\sum_{i=1}^{N}\mu_{t}(z_{i})=\sum_{i=1}^{M}\mu_{v}(z^{\prime}_{i})=1$. Therefore, for measuring the gradients of the OT w.r.t. the probability mass of a given data point in each dataset, Just et al., () calculate the *calibrated gradients* (i.e., a sum of all elements equals to a zero vector) as

$$ $\frac{\partial\textnormal{OT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{i})}=f^{*}_ {i}-\sum_{j\in\left\{1,...,N\right\}\textbackslash i}\frac{f^{*}_{j}}{N-1},$ (6) $$

The calibrated gradients predict how the OT distance changes as more probability mass is shifted to a given data point. This can be interpreted as a measurement of the contribution of the data point to the OT. Additionally, if we want a 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 to reduce their OT distance. Therefore, as demonstrated in Just et al., (), 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,, ) still runs in quadratic memory complexity $O(N^{2})$ 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 a dense square (float) matrix of size $N=10^{5}$ will require at least $74$ GB of RAM and $N=10^{6}$ 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 on 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 hierarchically defined OT as in *LAVA*, but it performs OT on batches of data points instead of on the entire dataset as in *LAVA*. We introduce *SAVA* in the next section.

It is worth noting that the OT-based data valuation we introduced in this section focuses on the *gradient* of the OT instead of the OT *distance* itself. Therefore, some popular scalable OT approaches, e.g., sliced-Wasserstein (Rabin et al.,, ), tree-sliced-Wasserstein (Le et al.,, ), or Sobolev transport (Le et al.,, ), may not be suitable to data valuation. In the next section, we introduce our novel scalable approach for computing the gradient of the OT using hierarchical OT approach (Yurochkin et al.,, ; Lee et al.,, ). We focus on the problem of data valuation but our work can be readily applied for other large-scale applications where the gradient of the OT is required.

## 3 SAVA: S calable D a ta V a luation

We present *SAVA*, a scalable data valuation method, scaling *LAVA* to a large-scale dataset. Instead of solving a single (but expensive) OT problem for distributions on the entire datasets, i.e., $\textnormal{OT}(\mu_{t},\mu_{v})$ in *LAVA* with the pairwise cost matrix size ${\mathbb{R}}^{N\times N^{\prime}}$, we 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.

Figure: Algorithm 1 Scalable Data Valuation (*SAVA*)

Hierarchical OT.
We follow the idea in hierarchical OT approach (Yurochkin et al.,, ; Lee et al.,, ) to partition the training dataset ${\mathbb{D}}_{t}$ of $N$ samples into $K_{t}$ disjoint batches ${B}=\left\{{B}_{i}\right\}_{i=1}^{K_{t}}$. Similarly, for the validation set ${\mathbb{D}}_{v}$ of $N^{\prime}$ samples into $K_{v}$ disjoint batches ${B}^{\prime}=\left\{{B}^{\prime}_{j}\right\}_{j=1}^{K_{v}}$. Additionally, for all $i\in[K_{t}],j\in[K_{v}]$, let the number of samples in batches $B_{i},B^{\prime}_{j}$ as $N_{i},N^{\prime}_{j}$ respectively. The corresponding measures of the training and validation sets w.r.t. the batches are defined as: $\bar{\mu}_{t}({B})=\frac{1}{K_{t}}\sum_{i=1}^{K_{t}}\delta_{({B}_{i})}$ and $\bar{\mu}_{v}({B}^{\prime})=\frac{1}{K_{v}}\sum_{j=1}^{K_{v}}\delta_{({B}^{
\prime}_{j})}$ respectively. We then define a distance between the datasets as the hierarchical optimal transport (HOT) between the measures $\mu_{t},\mu_{v}$ as OT distance for corresponding represented measures on batches, i.e., $\bar{\mu}_{t}$ and $\bar{\mu}_{v}$ as in Sec. 2.1 as follows:

$$ $d(\mu_{t},\mu_{v}):=\textnormal{HOT}(\mu_{t},\mu_{v}):=\textnormal{OT}(\bar{ \mu}_{t},\bar{\mu}_{v}).$ (7) $$

It is worth noting that HOT finds the optimal coupling at the batch level, but not at the support data point level as in the classic OT. Therefore, it can be seen that

$$ $\text{OT}(\mu_{t},\mu_{v})\leq\text{HOT}(\mu_{t},\mu_{v}).$ $$

The equality happens when either each batch only has one support or each dataset only has one batch.

Our goal is to estimate the gradient $\frac{\partial d(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{k})}=\frac{\partial
\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{k})}$ where $\textnormal{HOT}(\mu_{t},\mu_{v})$ 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}_{i},{B}^{\prime}_{j}):=\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{
j}})$, where $\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}}$ are corresponding measures for batches ${B}_{i},{B}^{\prime}_{j}$ respectively, and subsequently a cost matrix ${\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}$ on pairwise batches for input measures over batches; (ii) $d(\mu_{t},\mu_{v})=\textnormal{HOT}(\mu_{t},\mu_{v}):=\textnormal{OT}_{{\color
[rgb]{.5,0,.5}\bar{\textnormal{C}}}}(\bar{\mu}_{t},\bar{\mu}_{v})$.

Pairwise cost between batches.
We estimate the distance between two batches as the OT problem between ${B}_{i}$ and ${B}_{j}$, i.e., $d({B}_{i},{B}^{\prime}_{j}):=\textnormal{OT}({B}_{i},{B}^{\prime}_{j})$ as discussed in Sec. 2.1 by viewing the OT problem between two labeled (sub)datasets or batches ${B}_{i}$ and ${B}^{\prime}_{j}$.

More precisely, to solve this OT problem, we calculate the pairwise cost for data points between two batches ${\textnormal{C}}_{kl}(B_{i},B^{\prime}_{j})\in{\mathbb{R}}^{N_{i}\times N^{
\prime}_{j}}$, where $\forall k\in[N_{i}],\forall l\in[N^{\prime}_{j}]$, the element ${\textnormal{C}}_{kl}(B_{i},B^{\prime}_{j})$ is the cost between two labeled data points $(x_{k},y_{k})\in B_{i}$ and $(x^{\prime}_{l},y^{\prime}_{l})\in B^{\prime}_{j}$, calculated as

$$ ${\textnormal{C}}_{kl}\bigl{(}B_{i},B^{\prime}_{j}\bigr{)}={\textnormal{d}}(x_{ k},x^{\prime}_{l})+c\,\textnormal{OT}_{{\textnormal{d}}}\bigl{(}\mu_{B_{i}}( \cdot|y_{k}),\mu_{B^{\prime}_{j}}(\cdot|y^{\prime}_{l})\bigr{)}.$ (8) $$

Given the cost matrix ${\textnormal{C}}(B_{i},B^{\prime}_{j})$, we solve $\textnormal{OT}_{{\textnormal{C}}}(\mu_{{B}_{i}},\mu_{{B}^{{}^{\prime}}_{j}})$ to get dual solutions ${\color[rgb]{1,0,0}f^{*}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})},g^{*}(\mu_{{B}
_{i}},\mu_{{B}^{\prime}_{j}})$, and the OT distance for $d({B}_{i},{B}^{\prime}_{j})$, i.e., $\textnormal{OT}_{{\textnormal{C}}}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})$.

We repeat this process and solve the OT problem for each pair of $(B_{i},B^{\prime}_{j})$, i.e., OT problem for distributions on batches of data points, across the training and validation datasets, i.e., for all $i\in[K_{t}],j\in[K_{v}]$. This enables us to define the cost matrix for pairwise batches in $\bar{\mu}_{t},\bar{\mu}_{v}$, denoted as ${\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}(\bar{\mu}_{t},\bar{\mu}_{v})\in{
\mathbb{R}}^{K_{t}\times K_{v}}_{+}$ where we recall that $K_{t}$ and $K_{v}$ are the number of batches in training and validation sets. Hence, for this cost matrix ${\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}$, the element ${\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}_{ij}$ is computed as $\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})$, for all $i\in[K_{t}],\forall j\in[K_{v}]$.

Batch valuation.
Given the pairwise cost matrix across batches ${\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}$, we compute the data valuation for each batch via the gradient of the distance $\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}}(\bar{\mu}_{t},
\bar{\mu}_{v})$ w.r.t. the probability mass of batches in the two datasets, i.e., $\frac{\partial\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}}(
\bar{\mu}_{t},\bar{\mu}_{v})}{\partial\bar{\mu}_{t}({B}_{i})}$.
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, let $\bar{f}^{*},\bar{g}^{*}$ be the optimal dual variables of $\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}}(\bar{\mu}_{t},
\bar{\mu}_{v})$, then the data valuation of the batch $B_{i}$ in the training set ${\mathbb{D}}_{t}$ is estimated as follows:

$$ $\frac{\partial\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}}( \bar{\mu}_{t},\bar{\mu}_{v})}{\partial\bar{\mu}_{t}({B}_{i})}=\bar{f}_{i}^{*}.$ (9) $$

Since the optimal dual variables are only unique up to a constant, we follow Just et al., () to normalize these optimal dual variables such that the sum of all elements is equal to a zero vector:

$$ $\frac{\partial\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}}}( \bar{\mu}_{t},\bar{\mu}_{v})}{\partial\bar{\mu}_{t}(B_{i})}=\bar{f}_{i}^{*}- \sum_{j\in\left\{1,...,K_{t}\right\}\backslash i}\frac{\bar{f}^{*}_{j}}{K_{t}- 1}.$ (10) $$

Using batch valuation for data point valuation. After solving the OT problem over batches, we obtain the optimal transport plan ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}$ which is used to compute the data evaluation over individual data points:

$$ ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}=\text{diag}{( \bar{f}_{k}^{*})}\exp\Bigl{(}-\frac{{\color[rgb]{.5,0,.5}\bar{\textnormal{C}}} (\bar{\mu}_{t},\bar{\mu}_{v})}{\epsilon}\Bigr{)}\text{diag}{(\bar{g}_{k}^{*})},$ (11) $$

where $\text{diag}(\cdot)$ is matrix diagonal operator.

For a data point $z\in{B}_{i}\subset{\mathbb{D}}_{t}$, its data valuation score can be computed as follows:

$$ $\sum_{j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{\mu}_{t},\bar{ \mu}_{v})}\frac{\partial\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})} {\partial\mu_{{B}_{i}}(z)}.$ (12) $$

Using HOT, we can measure the gradients of the OT  distance w.r.t. the probability mass of a given data point in each dataset via the calibrated gradient summarized in the following Lemma 1. We refer to Appendix Table 1 for the notations.

###### Lemma 1 .

The data valuation, i.e., the calibrated gradient for a data point $z_{k}$ in the batch ${B}_{i}$ in ${\mathbb{D}}_{t}$ can be computed as follows:

$$ $\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{k})}=\sum_ {j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{\mu}_{t},\bar{\mu}_{v })}\frac{\partial\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}{ \partial\mu_{{B}_{i}}(z_{k})},$ (13) $$

where the calibrated gradient of OT for measures on batches is calculated as follows:

$$ $\displaystyle\frac{\partial\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j} })}{\partial\mu_{{B}_{i}}(z_{k})}={\color[rgb]{1,0,0}f^{*}_{k}(\mu_{{B}_{i}}, \mu_{{B}^{\prime}_{j}})}\hskip 10.00002pt-\sum_{l\in\left\{1,...,N_{i}\right\} \setminus k}\frac{{\color[rgb]{1,0,0}f^{*}_{l}(\mu_{{B}_{i}},\mu_{{B}^{\prime} _{j}})}}{N_{i}-1},\forall j\in[K_{v}].$ (14) $$

As the common practice in computing the OT via its entropic regularization, using the Sinkhorn algorithm (Cuturi,, ), we quantify the deviation in the calibrated gradients caused by the entropy regularizer. This analysis provides foundations on the potential impact of the deviation on the applications built on these gradients.

###### Lemma 2 .

Let $\textnormal{HOT}(\mu_{t},\mu_{v})$ and $\textnormal{OT}_{\epsilon}(\mu_{t},\mu_{v})$ be the HOT and entropic regularized OT between the measures $\mu_{t}$ and $\mu_{v}$ associated with the two datasets ${\mathbb{D}}_{t}$ and ${\mathbb{D}}_{v}$ respectively. The difference between the calibrated gradients for two data points $\{z_{l},z_{h}\}\in B_{i}\subset{\mathbb{D}}_{t}$ can be calculated as

$$ $\displaystyle\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}( z_{k})}-\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{l} )}=\sum_{j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{\mu}_{t},\bar {\mu}_{v})}\Bigl{[}\frac{\partial\textnormal{OT}_{\epsilon}(\mu_{{B}_{i}},\mu_ {{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z_{k})}-\frac{\partial\textnormal{ OT}_{\epsilon}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z_ {l})}$ $\displaystyle-\epsilon\frac{N_{k}}{N_{k}-1}\left(\frac{1}{(\bar{\pi}^{*}_{ \epsilon})_{l,j}}-\frac{1}{(\bar{\pi}^{*}_{\epsilon})_{k,j}}\right)\Bigr{]}.$ (15) $$

###### Proof.

Refer to Appendix C for the Proof.
∎

We make a similar observation in *LAVA* that the ground-truth gradient difference between two training points $z_{k}$ and $z_{l}$ is calculated based on the HOT formulation and can be approximated by the entropic regularized formulation $\textnormal{OT}_{\epsilon}$, such as via Sinkhorn algorithm (Cuturi,, ). In other words, we can calculate the ground-truth difference based on the solutions to the regularized problem plus some calibration terms that scale with $\epsilon$. In addition, in our case with HOT, the gradient difference also depends on the additional optimal assignment across batches ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}$ which is again estimated by Sinkhorn algorithm.

###### Lemma 1 .

###### Lemma 2 .

###### Proof.

## 4 Properties and Discussions

The *SAVA* Algorithm.
We outline the computational steps of *SAVA* in Algorithm 1. From Lines 1 to 5, we solve multiple OT tasks for data points between two batches $B_{i},B^{\prime}_{j}$. We obtain the dual solution ${\color[rgb]{1,0,0}f^{*}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}\in{\mathbb{R}}
^{N_{i}}$. Additionally, these OT distances are used to fill in the cost matrix for pairwise batches ${\color[rgb]{.5,0,.5}\bar{{\textnormal{C}}}_{ij}(\bar{\mu}_{t},\bar{\mu}_{v})}
=\textnormal{OT}(\mu_{B_{i}},\mu_{B^{\prime}_{j}})$. Here, the cost matrix C is of size $N_{i}\times N^{\prime}_{j}$ where the batch sizes $N_{i},N^{\prime}_{j}\ll N$. The required memory complexity is at least $\tilde{\mathcal{O}}(N^{2}_{i})$.

We then solve the OT problem across batches $\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{{\textnormal{C}}}}}(\bar{\mu}_{t},
\bar{\mu}_{v})$ to get the optimal plan ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}$ in line 6 Algorithm 1. The cost matrix is of size $K_{t}\times K_{v}$ which is typically small and so less expensive compared to the previous OT tasks. Finally, from Lines 7 to 10, we estimate valuation scores for training data using the auxiliary matrices computed in the previous steps, including ${\color[rgb]{1,0,0}f^{*}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}$ and ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}$.

*SAVA* Memory Requirements.
The Sinkhorn algorithm computational complexity is at least $\tilde{\mathcal{O}}(N^{2})$ where $N$ is the number of samples. This comes from the main OT  step of $\textnormal{OT}(\mu_{t},\mu_{v})$ over the full cost matrix C of size $N\times N^{\prime}$ to subsequently calculate the calibrated gradient in Eq. (6) where $N$ and $N^{\prime}$ are the training and validation dataset sizes. *SAVA* overcomes this limitation by solving multiple smaller OT problems $\textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})$ on distributions for batches of data points only.

Figure: 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 a prefix of size $N/4$ as the detection rate (where $N$ is the training set size). The star symbol (${\color[rgb]{0.3984375,0.76171875,0.6484375}\bigstar}$) denotes the point at which *LAVA* is unable to continue valuing training due GPU out-of memory (OOM) errors.
Refer to caption: x2.png

Practical Implementation with Caching.
While yielding a significant memory improvement, *SAVA*’s runtime is not necessarily faster than *LAVA*. To speed up *SAVA*, we propose to implement Algorithm 1 by caching the label-to-label costs between points in the validation and training batches: $\textnormal{OT}_{{\textnormal{d}}}(\cdot,\cdot)$ in Eq. (1) so that it is only calculated once in the first iteration of Algorithm 1 and reused for subsequent batches. This significantly reduces *SAVA* runtimes with no detriment to performance Figure 9. All experimental results in Section 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 is 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 a certain batch size, when increasing the batch size $N_{i}$, HOT converges to the OT, but its memory complexity also increases, i.e., $\mathcal{O}(N^{2}_{i})\rightarrow\mathcal{O}(N^{2})$. On the other hand, if the batch size $N_{i}$ is too small, the number of batches $K_{t}$ will be large. As a result, the memory complexity will also be high (i.e., for solving $\textnormal{OT}_{{\color[rgb]{.5,0,.5}\bar{{\textnormal{C}}}}}(\bar{\mu}_{t},
\bar{\mu}_{v})$ in Algorithm 1). Thus, the batch size will trade off the memory complexity and the approximation of HOT to OT.

## 5 Experiments

We aim to test two following hypotheses(^1^11The code to reproduce all experiments can be found at [https://github.com/skezle/sava](https://github.com/skezle/sava).):

1. Can *SAVA* scale and overcome the memory complexity issues which hinder *LAVA*?

2. Can *SAVA* scale to a large real-world noisy dataset with over a *million* data points?

### 5.1 Dataset Corruption Detection

We test the scalability of *SAVA* versus *LAVA* (Just et al.,, ) by leveraging the CIFAR10 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., (); Just et al., (), we sort the training examples by their values. An effective data valuation method would rank corrupted examples in a 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 E, Figure 6).

Figure: Figure 3: *SAVA* can scale to the full CIFAR10 dataset enabling 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 (${\color[rgb]{0.3984375,0.76171875,0.6484375}\bigstar}$) denotes the point at which *LAVA* is unable to continue valuing training due to GPU out-of memory (OOM) errors.
Refer to caption: x3.png

Setup. We consider $4$ different corruptions (see Appendix D for details) that are applied to the training data following the settings in Just et al., (): (i) *noisy labels*, (ii) *noisy features*, (iii) *backdoor attacks* and (iv) *poison detections*. All experiments are run on a Tesla K$80$ Nvidia GPUs with $12$GB GPU RAM. Unless otherwise stated, all results reported are a mean $\pm 1$ standard deviation over $5$ independent runs.

Baselines. Our main baseline is *LAVA* which shares the same design scheme based on hierarchically defined OT for data valuation Eq. (1). For *SAVA* and *LAVA* we use features from a pre-trained ResNet18 (He et al.,, ). For *SAVA*, we use a default batch size of $N_{i}=1024$ which is its main hyperparameter.(^2^22See Appendix G for the study of the sensitivity of the batch size $N_{i}$ in *SAVA*.) We also consider *KNN Shapley* (), 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 ResNet18 features to calculate Shapley values, we tune $k$ as its performance is sensitive to this hyperparameter. We also consider *TracInCP* (Pruthi et al.,, ) which measures the influence of each training point by measuring the difference in the loss at the beginning versus the end of training (see Section F.1 for details). We also compare with *Influence Function* (Koh and Liang,, ) 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 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 a data point level within a batch without a batch level OT problem, line 6 Algorithm 1. 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 G).

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 $50$K points. In contrast, *SAVA*, *Batch-wise LAVA* *KNN Shapley* can consistently value and detect all corruptions when inspecting $12.5$K 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., (). Consequently, when pruning $30\%$ of the data, *SAVA* can consistently improve its accuracy on the test set as the training set size increases (Figure 3).

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 $10$K, some runs have OOM errors when embedding the entire training set into memory and when calculating the full cost matrix for OT problem in Eq. (1). 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*, albeit its detection rate is lower than *SAVA*. *TracInCP* 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 a Trojan square attack (Liu et al.,, ). *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 $50$k points. *TracInCP* and *Influence Functions* both struggle to detect backdoored training points and have long runtimes.

Poisoning attacks. We corrupt $10\%$ of the data with a poison frogs attack (Shafahi et al.,, ). We find in Figure 2 that *SAVA* and *Batch-wise LAVA* can scale and maintain a high detection rate. In contrast, *KNN Shapley* struggles to detect many corrupted data points after inspecting $25\%$ of the ordered training data. Both *TracInCP* and *Influence Functions* struggle to detect the corrupted data.

Pruning. We can prune the $N/4$ data points and train a classifier on the pruned dataset in Figure 3. *SAVA* can value a 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 on a training set of size $50$K. As a result, the performance of the ResNet18 model does not improve when valuing larger training sets with *LAVA*.

### 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 Clothing1M (Xiao et al.,, ) where the training set has over $1$M images whose labels are noisy and unreliable. However, the validation set has been curated. Clothing1M is a $14$-way image classification problem and has been used for previous work on online data selection (Mindermann et al.,, ). We consider *SAVA* and other data pruning methods as baselines to remove low-value training data points before training a ResNet18 classifier.

Figure: Figure 4: *SAVA* can scale to a large web-scrapped dataset. We use *SAVA* and other baselines, to value data points in the noisy training set and then prune a certain percentage of the dataset. The resulting dataset is used for training a classifier.
Refer to caption: x4.png

We compare to *Batch-wise LAVA*, introduced in Section 5.1. We also compare to *EL2N* (Paul et al.,, ) 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 a cross-validate a sliding window of values to decide which *EL2N* values to keep (see Section F.2.2 for details). We also consider supervised prototypes (Sorscher et al.,, ) which prunes image embeddings according to how similar they look to cluster centers after clustering image embeddings (see Section F.2.3 for details).

If we were to train a classifier on the full noisy training set, we would obtain an accuracy of $67.6\pm 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 is 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 gradient of the OT across the validation dataset using optimal plan across batches ${\color[rgb]{1,.5,0}\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})}$ rather than *Batch-wise LAVA*’s uniform weighting. *SAVA* produces the best accuracy model of $70.0\pm 0.2$ in Figure 4.

## 6 Conclusions

We have presented a scalable extension to *LAVA* to 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 those individual batches. We empirically show that *SAVA* maintains performance in data valuation tasks while successfully scaling up to handle a large real-world noisy dataset. This makes the data valuation task feasible for large-scale datasets.

Limitations. HOT finds the optimal coupling at the batch level, but not at the global level as in the traditional OT, i.e., $\text{OT}(\mu_{t},\mu_{v})\leq\text{HOT}(\mu_{t},\mu_{v}).$, which makes the validation error bound looser (Just et al.,, , 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.

## 7 Acknowledgements

The authors would like to thank Hoang Anh Just for helpful discussions. TL acknowledges the support of JSPS KAKENHI Grant number
23K11243, and Mitsui Knowledge Industry Co., Ltd. grant.

## 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 in §D. In §E, 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 §F. In §G, we provide further empirical results. In §H, we present and discuss further related works. We also provide a visualization for the artifacts in *SAVA* in §I, and other further discussions in §J.

**Table 1: Notations used throughout the paper. We use column vectors in all notations.**
| Variable | Definition |
| --- | --- |
| $z=(x,y)\in{\mathbb{R}}^{|\mathcal{X}|}\times\{0,1\}^{V}$ | Datapoint feature and label where $V$ is #label and $\mathcal{X}$ is a feature space. |
| ${\mathbb{D}}_{t},{\mathbb{D}}_{v}$ | Datasets for training ${\mathbb{D}}_{t}=\left\{(x_{i},f_{t}(x_{i}))\right\}_{i=1}^{N}$ and validation ${\mathbb{D}}_{v}=\left\{(x^{\prime}_{i},f_{v}(x^{\prime}_{i}))\right\}_{i=1}^{<br>N^{\prime}}$. |
| $B=\{B_{i}\}_{i=1}^{K_{t}},B^{\prime}=\{B^{\prime}_{j}\}_{j=1}^{K_{v}}$ | Disjoined batches for ${\mathbb{D}}_{t}$ and ${\mathbb{D}}_{v}$ where $K_{t},K_{v}$ are the number of batches. |
| $B_{i}=\{z_{k}\}_{k=1}^{N_{i}}$ | Batch of datapoints where $N_{i}$ is the number of datapoints in the batch $i$. |
| $\mu_{B_{i}}=\frac{1}{N_{i}}\sum_{t=1}^{N_{i}}\delta_{(z_{t})}$ | Measure over labeled datapoints for the batch $B_{i}$. |
| $\mu_{t}(x,y)=\frac{1}{N}\sum_{i=1}^{N}\delta_{(x_{i},y_{i})}$ | Measure over training set. |
| $\mu_{v}(x,y)=\frac{1}{N^{\prime}}\sum_{i=1}^{N^{\prime}}\delta_{(x_{i},y_{i})}$ | Measure over validation set. |
| $\bar{\mu}_{t}=\frac{1}{K_{t}}\sum_{i=1}^{K_{t}}\delta_{({B}_{i})}$ | Measure over batches for the training set. |
| $\bar{\mu}_{v}=\frac{1}{K_{v}}\sum_{j=1}^{K_{v}}\delta_{({B}^{\prime}_{j})}$ | Measure over batches for the validation set. |
| $\bar{C}\in{\mathbb{R}}_{+}^{K_{t}\times K_{v}}$ | Cost matrix over batches, each element $\bar{C}_{i,j}=d(B_{i},B^{\prime}_{j})$. |
| $C\in{\mathbb{R}}_{+}^{N_{i}\times N^{\prime}_{j}}$ | Cost matrix over labeled datapoints within batches $B_{i}$ and $B^{\prime}_{j}$, each element $C_{kl}=d(z_{k},z^{\prime}_{l})$. |
| $f^{*}\in{\mathbb{R}}^{N_{i}}$, $g^{*}\in{\mathbb{R}}^{N^{\prime}_{j}}$ | Dual solutions of the OT  over a cost matrix $C\in{\mathbb{R}}^{N_{i}\times N^{\prime}_{j}}$. |
| $\pi^{*}\in{\mathbb{R}}^{N_{i}\times N^{\prime}_{j}}$ | OT  plan over a cost matrix $C\in{\mathbb{R}}^{N_{i}\times N^{\prime}_{j}}$. |
| $\bar{f}^{*}\in{\mathbb{R}}^{K_{t}}$, $\bar{g}^{*}\in{\mathbb{R}}^{K_{v}}$ | OT  dual solutions over a cost matrix over batches $\bar{C}\in{\mathbb{R}}^{K_{t}\times K_{v}}$. |
| $\bar{\pi}^{*}\in{\mathbb{R}}^{K_{t}\times K_{v}}$ | OT  plan over a cost matrix between batches $\bar{C}\in{\mathbb{R}}^{K_{t}\times K_{v}}$. |

## 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 performance, 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, an 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 a harmful validation dataset, leading to the training of models on dangerous or unethical data. This underscores the importance of vigilance and ethical considerations in dataset creation and curation.

## Appendix B Limitations

One theoretical limitation, stated in Section 6 regards a looser validation error bound (Just et al.,, , Eq. (1), Theorem 1) due to the use of hierarchical optimal transport (Yurochkin et al.,, ; Lee et al.,, ). However, the validation error bound for *SAVA* remains useful as in *LAVA* since it can be interpreted that minimizing either the OT or hierarchical OT between training and validation sets, and will bound the model’s validation error. As we observe in practice, there is little difference in performance between *SAVA* and *LAVA* (Just et al.,, ).

Another limitation of our work is that the ground cost we consider Equation 1 is limited to labeled datasets.(^3^33For unlabelled datasets, in some sense, it is equivalent to set the weight coefficient $c=0$, to ignore the contribution of label information for the ground cost.) We have not explored different ground truth costs for text data or speech data.

## Appendix C Details of Theoretical Results

We present the Proof of Lemma 2 as follows.

###### Lemma 3 (restated) .

Let $\textnormal{HOT}(\mu_{t},\mu_{v})$ and $\textnormal{OT}_{\epsilon}(\mu_{t},\mu_{v})$ be the HOT and entropic regularized OT between the empirical measures $\mu_{t}$ and $\mu_{v}$ associated with the two datasets ${\mathbb{D}}_{t}$ and ${\mathbb{D}}_{v}$ respectively. The difference between the calibrated gradients for two datapoints $\{z_{l},z_{h}\}\in B_{i}\subset{\mathbb{D}}_{t}$ can be calculated as

$$ $\displaystyle\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}( z_{k})}-\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{l})}$ (C.1) $\displaystyle=\sum_{j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{ \mu}_{t},\bar{\mu}_{v})}\Bigl{[}\frac{\partial\textnormal{OT}_{\epsilon}(\mu_{ {B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z_{k})}-\frac{\partial \textnormal{OT}_{\epsilon}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_ {{B}_{i}}(z_{l})}-\epsilon\frac{N_{k}}{N_{k}-1}\left(\frac{1}{(\bar{\pi}^{*}_{ \epsilon})_{l,j}}-\frac{1}{(\bar{\pi}^{*}_{\epsilon})_{k,j}}\right)\Bigr{]}.$ $$

###### Proof.

Let $\textnormal{OT}(\mu_{t},\mu_{v})$ be the OT formulation between empirical measures $\mu_{t}$ and $\mu_{v}$, we present the proof as follows

$$ $\displaystyle\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}( z_{k})}-\frac{\partial\textnormal{HOT}(\mu_{t},\mu_{v})}{\partial\mu_{t}(z_{l})}$ (C.2) $\displaystyle=\sum_{j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{ \mu}_{t},\bar{\mu}_{v})}\Bigl{[}\frac{\partial\textnormal{OT}(\mu_{{B}_{i}}, \mu_{{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z_{k})}-\frac{\partial \textnormal{OT}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z _{l})}\Bigr{]}$ $\displaystyle=\sum_{j=1}^{K_{v}}{\color[rgb]{1,.5,0}\bar{\pi}^{*}_{ij}(\bar{ \mu}_{t},\bar{\mu}_{v})}\Bigl{[}\frac{\partial\textnormal{OT}_{\epsilon}(\mu_{ {B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_{{B}_{i}}(z_{k})}-\frac{\partial \textnormal{OT}_{\epsilon}(\mu_{{B}_{i}},\mu_{{B}^{\prime}_{j}})}{\partial\mu_ {{B}_{i}}(z_{l})}-\epsilon\frac{N_{i}}{N_{i}-1}\left(\frac{1}{(\bar{\pi}^{*}_{ \epsilon})_{l,j}}-\frac{1}{(\bar{\pi}^{*}_{\epsilon})_{k,j}}\right)\Bigr{]}$ (C.3) $$

where Eq.(C.2) follows the definition of HOT and Eq. (C.3) utilizes Theorem 2 in Just et al., ().
∎

###### Lemma 3 (restated) .

###### Proof.

## Appendix D Data Corruptions Descriptions

Figure: Figure 5: Examples of the data corruptions used in our experimental setup. Examples of data from the CIFAR$10$ dataset where the images have corruptions: noisy features, trojan square, and poison frogs corruptions respectively.
Refer to caption: x5.png

We consider $4$ different corruptions in our experiments (Section 5) that are applied to the training set following the settings in Just et al., ():

##### Noisy labels.

We corrupt a proportion of the labels in the training set by randomly assigning the target a different label. This is a common corruption found in webscale vision (Xiao et al.,, ) and speech (Radford et al.,, ) for instance.

##### Noisy features.

We add Gaussian noise to a certain proportion of the images in the training set to simulate common background noise corruptions that might occur in real datasets.

##### Backdoor attacks.

A certain proportion of the training set is corrupted with a Trojan square attack Liu et al., (), e.g., corrupted images have $10\times 10$ pixel square trigger mask added with random noise and are relabeled to the trojan “airplane” class, see Figure 5 for an example of a corrupted image.

##### Poison detections

A certain proportion of training data from a specific base class is poisoned such that the features look similar to a target class (Shafahi et al.,, ). Our target is the cat class from the CIFAR$10$ dataset, which is a randomly chosen image of a cat from the test set. We take a certain percentage of the base class which, in our case is the frog class from the CIFAR$10$ 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 a pre-trained feature extractor model (in our case a 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 is a very difficult attack to detect, and the features of frogs are poisoned to look like cats and labels remain uncorrupted. See Figure 5 for an example of a poisoned frog image.

Figure: Figure 6: 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 2 and Figure 3.
Refer to caption: x6.png

## Appendix E 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 et al., (), 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 our detection rate to measure the effectiveness of various methods in Figure 2. See Figure 6 for an example of this using a poison frogs (Shafahi et al.,, ) corruption on $10\%$ of a dataset of size $5$k on CIFAR$10$.

## Appendix F Implementation Details

### F.1 CIFAR10 Corruption Detection

We use a single Nvidia K80 GPU to run all experiments.

##### TracInCP.

In practice, TracInCP measures the influence of a 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 on 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 over the entire model and use every second checkpoint to calculate TracInCP values, these design choices result in fewer approximations than the original implementation (Pruthi et al.,, ).

##### Influence Functions.

We use the following repository for obtaining results on influence functions with default parameters [https://github.com/nimarb/pytorch_influence_functions](https://github.com/nimarb/pytorch_influence_functions).

##### KNN Shapley.

The method is very sensitive to $k$ which is a hyperparameter in the KNN algorithm used to approximate the expensive calculation of the Shapley value. We do a grid search over $k\in\{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 CIFAR10 training set. Our implementation is the same as that used in the LAVA.

##### 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 a ResNet18 with the SGD optimizer with weight decay of $5\times 10^{-4}$ and momentum of $0.9$ for $200$ epochs with a 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$.

Figure: Figure 7: *SAVA* can value more data as a 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 (${\color[rgb]{0.3984375,0.76171875,0.6484375}\bigstar}$) denotes the point at which *LAVA* is unable to continue valuing training due GPU out-of memory errors.
Refer to caption: x7.png

### F.2 Clothing1M

For all experiments, we use a node with $8$ Nvidia K$80$ 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 of different sizes depending on the amount of pruning. We train for a fixed number of $100$k steps. We use a learning rate schedule where for the first $30$k steps the learning rate is $0.1$ then the next $30$k steps the learning rate is $0.05$ then the next $20$k steps the learning rate is $0.01$, then the next $10$k steps the learning rate is $0.001$, then the next $5$k steps the learning rate is $0.0001$ then for the final $5$k steps the learning rate is $0.00001$.

#### F.2.1 SAVA

*SAVA* has remarkably few design choices in comparison to other data pruning methods like EL2N Section F.2.2 and supervised prototypes Section F.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 4, we only use the large noisy training set for obtaining the results in Figure 4. We use a batch size of $2048$ for valuation and we use label-2-label matrix caching Appendix G.

#### F.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{,}570$.

We also hyperparameter optimize the offset $\in\{0.0,0.05,0.1\}$ using a sliding window which covers $90\%$ of points §4 (Paul et al.,, ). 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.

#### F.2.3 Supervised Prototypes

We train an image encoder using a classification objective on the clean training set provided in the Clothing1M 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 so are not used for the results in Figure 4.

We use mini-batch 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 centroids over the grid $\{1{,}000,2{,}000,5{,}000,10{,}000\}$ using the intra cluster mean-squared error on the validation dataset.

The best configuration uses a 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 a classifier on the pruned dataset.

## Appendix G Additional Experiments

Figure: Algorithm 2 Incremental learning experimental setup.

Figure: Figure 8: *SAVA* performance as function of the batch size, $N_{i}$. The CIFAR$10$ dataset with noisy label detection. Left: Detection rate. Right: detection runtimes in seconds.
Refer to caption: x8.png

### G.1 Incremental learning

We split the CIFAR10 dataset into $5$ equally sized partitions with all classes, and we incrementally build up the dataset such that it grows in size as one would train a production system (Baby et al.,, ). We inject the data with noisy labels and noisy feature corruptions, then perform the data valuation. We compare our proposed method with *LAVA* (Just et al.,, ). After valuing our training 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 to the validation set and train on the pruned dataset. We report the final accuracy of a ResNet18 (He et al.,, ) model. We summarize this experimental setup in Algorithm 2.

### G.2 Performance as a function of batch size

Following the discussion on the batch size in Section 4, we measure our model performance w.r.t. different batch sizes $N_{i}\in\{128,256,...,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 of detection rate while the batch size of $4{,}096$ will consume less time for computation of the cost across batches, since there are less and $K_{t}$ is lower.

### G.3 Label-to-label distance caching

We study the difference in performance and runtime between *SAVA* Algorithm 1 and using *SAVA* with label-to-label (l2l) matrix caching discussed in Section 4 using CIFAR$10$ with noisy label corruptions. We show that there are almost identical detection rates between the two variants of *SAVA* with and without l2l caching Figure 9. Meanwhile, the runtime is significantly reduced and is lower than *LAVA*.

Figure: Figure 9: Label-to-label matrix caching significantly reduces runtime. Left: *SAVA* with and without label-2-label (l2l) matrix caching performs similarly in detecting noisy label corruption. Right: *SAVA* with l2l runs significantly quicker and is quicker than *LAVA* in terms of runtime in seconds on the same GPU.
Refer to caption: x9.png

Figure: Figure 10: Randomly sampling data for batch construction is robust. Detection rates for *SAVA* for random sampling to construct a 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 CIFAR$10$ with noisy features.
Refer to caption: x10.png

### G.4 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 a batch with an uneven distribution of classes, this could degrade the calculation of the class-wise Wasserstein distance Eq. (1). To mitigate, against any imbalance we compare random sampling versus stratified sampling which evenly samples from each class to construct a batch. When valuing $10$k points from the CIFAR$10$ dataset with corrupted features, we find little difference in detection rates between these two sampling schemes. This might be a consideration when the ratio of the number of classes in the dataset to the batch size is higher.

### G.5 On the robustness of Batch-wise LAVA

From the corruption detection experiments, we established that *Batch-wise LAVA* has remarkable performance section 5.1. 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 11. For small batches this is due to *Batch-wise LAVA* not having enough clean points in the validation batch to detect corrupt data points in the training batch. For large batches the final batch in the dataloader is usually smaller than the specified batch-size and so these data points in the final batch will also suffer from not enough points in the validation batch to compare against. *SAVA* is able to overcome this issue since the information from all batches is aggregated and weighted by the optimal plan between batches, ${\color[rgb]{1,.5,0}\pi^{*}_{ij}(\bar{\mu}_{t},\bar{\mu}_{v})}$, in lines 7 and 10 in Algorithm 1.

Figure: Figure 11: *Batch-wise LAVA* is not robust to different batchsizes. For $4$ different corruptions on a training dataset of size $5$k with validation dataset size $2$k 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 2.
Refer to caption: x11.png

## Appendix H Related Works

Data valuation. A simple way to value a datapoint is 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. A more efficient way to value data is through the use of Shapley values with a KNN proxy model (; ). Extensions of the Shapley value for data valuation include Data Shapley (Ghorbani and Zou,, ) and Beta Shapley (Kwon and Zou,, ). Instead of using the Shapley value one can use “the core” from the game theory literature for data valuation (Yan and Procaccia,, ). 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.,, ). An initialized model can also be utilized for data valuation where sets are available from contributors (Wu et al.,, ). The Banzhaf value can also be used for data valuation (Wang and Jia,, ). Influence functions (Koh and Liang,, ) approximate LOO retraining using expensive approximations of the Hessian of the NN weights. In a similar vein, TracIn (Pruthi et al.,, ) traces the influence of a training point on a test point by looking at the difference in the loss throughout training. 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.,, ). The OpenDataVal benchmark is available with many implementations of data valuation methods (Jiang et al.,, ).

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,, ). Active learning is related to data valuation since a 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 a probabilistic model (Houlsby et al.,, ), this disagreement can also be obtained from multiple models (Freund et al.,, ). This approach of using the disagreement of a probabilistic 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.,, ; Kirsch et al.,, ). Alternatively picking points to label can be thought of as a summarization problem by obtaining a coreset of representative data (Sener and Savarese,, ; Mirzasoleiman et al.,, ; Coleman et al.,, ). Samples to be labeled can be selected by interpreting the classifier output probabilities as a confidence (Li and Sethi,, ).

Figure: Figure 12: Visualization of the main artifacts in Algorithm 1. For a noisy CIFAR$10$ valuation problem with a training and validation set size of $10$k and *SAVA* batch size of $1024$, we visualize the main artifacts of the *SAVA* algorithm for illustrative purposes. From left to right, from the top row to the bottom row: the first matrix is the cost matrix between batches: $\bar{C}(\bar{\mu_{t}},\bar{\mu_{v}})$ and then the optimal plan $\bar{\pi}^{*}(\bar{\mu}_{t},\bar{\mu}_{v})$ is the associated plan which is the solution to the optimal transport problem. In the second row we visualize $C(\mu_{B_{i}},\mu_{B_{j}^{\prime}})$ the optimal transport distance between points in the final batch $B_{i}$ from the training set and the final batch $B^{\prime}_{j}$ in the validation set and its corresponding optimal plan $\pi^{*}(\mu_{B_{i}},\mu_{B_{j}^{\prime}})$, we have used a $\log$ transform to on the optimal plan between datapoints to help viewing it.
Refer to caption: x12.png

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.,, ). The influence a point has on the training loss as a metric of informativeness has been shown to accelerate the training of neural networks (Loshchilov and Hutter,, ). Similarly picking points that reduce the variance of the gradient speeds up training (Katharopoulos and Fleuret,, ; Johnson and Guestrin,, ). Instead of focusing on the training loss, one can select data according to the influence on the validation loss (Mindermann et al.,, ). 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.,, ). One can also prune data by how similar embeddings are to a cluster center or prototype (Sorscher et al.,, ) and by assessing diversity within each cluster (Abbas et al.,, ; Tirumala et al.,, ). It has also been shown that pruning data according to how easy they are to be forgotten over the course of training - as a measure of difficulty - results in training on less data while maintaining performance (Toneva et al.,, ). 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.,, ) and *SAVA*. Meta-learning is also used to learn datapoint importance weights by evaluating with a clean validation set (Ren et al.,, ). Similarly to *LAVA* and *SAVA* the distributional distance between a 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.,, ).

## Appendix I SAVA Visualization

To gain insight into how the estimated OT matrices from our proposed *SAVA*, we visualize the artifacts  Algorithm 1 in Figure 12.

## Appendix J Other Discussions

Overfitting and Approximation.
Recently, Peyré and Cuturi, (, §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 as a regularization for OT. We show empirically for certain cases that the batch approximation (*SAVA*) performs better than the original OT (*LAVA*) in terms of quality while we surpass *LAVA* in memory requirement.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Other than hierarchical OT and the proposed implementation, there are some other ideas for mitigating OT efficiency issues.

Some 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. 

Another somewhat connected idea is to directly quantize the train and validation distributions (e.g., approximate the distributions via downsampling) to simplify the OT problem.

Hierarchical 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. 

It 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.
soundness: 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.

The proposed method is plausible, leveraging the hierarhical OT framework to aggregate results from batch-wise OT computations and achieving favorable approximation results.

Derivations are comprehensive and are paired with substantial elaborations. Empirical evaluations are diverse and abundant and the results are valid.
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.
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.

Are there results on actual time comparisons for the methods in empirical studies?

The 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.

For 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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See weaknesses.
soundness: 3
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. 

- The writing is good and easy to follow.
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.
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. 

- 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. 

- The authors are suggested to include a table comparing the complexities of LAVA and SAVA. 

- What happens if the validation dataset gets corrupted? 

- In Fig. 3, why is the performance of SAVA dropping at .4 proportion?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: pls see W2
soundness: 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.

[S2] Detailed theoretical proofs and descriptions of previous work are given.

[S3] The article is well-organized and easy to read.
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.
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.

[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? 

[W3] Typos: Line 417, "Batch-wise LAVA KNN Shapley and" -> "Batch-wise LAVA, KNN Shapley, and"

Placing Table 1 in Section 2 would help to improve understanding.

Meta-review: This paper introduces SAVA, a new and more scalable variant of the data valuation method LAVA. LAVA was restricted by the amount of computation required when computing the optimal transport distance. SAVA addresses this problem by computing these metrics in a batch manner. Experiment results successfully showed the promises of the approach.

Decision: Accept (Poster)