Efficient Top-m Data Values Identification for Data Selection
Authors: Xiaoqiang Lin
Xinyi Xu
See-Kiong Ng
Bryan Kian Hsiang Low
Venue: ICLR 2025 Poster (2025)
Keywords: data selection
data valuation
top-m arms identification
Primary area: interpretability and explainable AI
TL;DR: We propose an efficient top-m data values identification algorithm for data selection with both theoretical results and empirical efficiency

Abstract: Data valuation has found many real-world applications, e.g., data pricing and data selection. However, the most adopted approach -- Shapley value (SV) -- is computationally expensive due to the large number of model trainings required. Fortunately, most applications (e.g., data selection) require only knowing the $m$ data points with the highest data values (i.e., top-$m$ data values), which implies the potential for fewer model trainings as exact data values are not required. Existing work formulates top-$m$ Shapley value identification as top-$m$ arms identification in multi-armed bandits (MAB). However, the proposed approach falls short because it does not utilize data features to predict data values, a method that has been shown empirically to be effective. A recent top-$m$ arms identification work does consider the use of arm features while assuming a linear relationship between arm features and rewards, which is often not satisfied in data valuation. To this end, we propose the GPGapE algorithm that uses the Gaussian process to model the \emph{non-linear} mapping from data features to data values, removing the linear assumption. We theoretically analyze the correctness and stopping iteration of GPGapE in finding an $(\epsilon, \delta)$-approximation to the top-$m$ data values. We further improve the computational efficiency, by calculating data values using small data subsets to reduce the computation cost of model training. We empirically demonstrate that GPGapE outperforms other baselines in top-$m$ data values identification, noisy data detection, and data subset selection on real-world datasets. We also demonstrate the efficiency of our GPGapE in data selection for large language model fine-tuning.

Published as a conference paper at ICLR 2025
EFFICIENT TOP-m DATA VALUES IDENTIFICATION FOR DATA SELECTION
Xiaoqiang Lin'r, Xinyi Xu', See-Kiong Ng². Bryan Kian Hsiang Low! Department of Computer Science, National University of Singapore, Singapore Institute of Data Science, National University of Singapore, Singapore x xiaoqiang.. linuu. nus. edu, xinyi. xuêu. rus. edu, seekiongénus, edu. sg, lowkh@comp. nus. edu.sg
ABSTRACT
Data valuation has found many real-world applications, c.g., data pricing and data selection. However, the most adopted approach Shapley value (SV) is computationally expensive due to the large number of model trainings required. Fortunately, most applications (e.g., data selection) require only knowing the data points with the highest data values (i.e., top-m data values), which implies the potential for fewer model trainings as exact data values are not required. Existing work formulates top-m Shapley value identification as top-m arms identification in multi-armed bandits (MAB). However, the proposed approach falls short because it does not utilize data features to predict data values, a method that has been shown empirically to be effective. A recent top-mn arms identification work does consider the use of arm features while assuming linear relationship between arm features and rewards, which often not satisfied in data valuation. To this end, we propose the GPGapE algorithm that uses the Gaussian process to model the non-linear mapping from data features to data values, removing the linear assumption. We theoretically analyze the correctness and stopping iteration of GPGapE in finding an (e, apppproxinnttoon to the top-m data values. We further improve the computational efficiency, by calculating data values using small data subsets reduce the computation cost of model training. We empirically demonstrate that GPGapE outperforms other baselines in top-m data values identification, noisy data detection, and data subset selection on real-world datasets. We also demonstrate the efficiency of our GPGapE data selection for large language model fine-tuning.
INTRODUCTION
Data is essential to obtaining a good-performing machine learning (ML) model. Data valuation (Ghorbani & Zou, 2019) quantifies the contribution of each data point to the model performance. The contribution estimate (i.e., data value) can be used in data pricing (Agarwal et al., 2019), data debugging by identifying noisy data (Koh & Liang, 2017: Kwon & Zou, 2021), data selection (Nohyun et al., 2022), and incentive design in collaborative machine learning (CML) (Sim et al.. 2020; Xu et al., 2021), 1). The most commonly adopted data valuation approaches (Ghorbani & Zou, 2019; Jia al., 2019b) are based on the Shapley value (SV) due its desirable properties (e.g., fairnes)) and good empirical performance in data selection (Ghorbani & Zou, 2019; Wang et al., 2024). Specifically, the data value, precisely SV, is defined as the (average of) changes in model performance (i.e., marginal contribution) when the data point is removed from different subsets of the training dataset (see Equ. (1)). However, the computation of exact data values requires n! (where # data points) model trainings, posing a significant challenge to applying it to real-world large datasets. Although existing approaches have explored several sampling-has based approximations (Ghorbani Zou, 2019; Okhrati & Lipani, 2021), the computational cost remains high, especially when complex models such as neural networks (NNs) are used.
Fortunately, most applications only require knowing the m data points with the highest data values (i.e., top-m data values). For example, data marketplaces, buyers with limited budgets will only
"Corresponding authors.

---

Published as a conference paper at ICLR 2025
buy data with the largest m data values (Ghorbani et al., 2022). In noisy data detection, noisy data are specified by data with m lowest data values (Wang et al., 2020; Schoch et al., 2022). In CML, some incentive designs reward only the top-m highest contributing participants (Zhang et al., 2021). Certain fairness properties are preserved when using top-m data values in incentive design (see Appendix A. Intuitively, identifying the top-m data values can incur a lower computational cost than directly approximating data values since it does not require either approximating the exact data values well or knowing the exact ranking of these data values. How obtain top-m data values efficiently without directly approximating the exact data values?
An existing work (Ghorbani et al.. 2022) has empirically shown that data features are predictive of the data value of the corresponding data point. Intuitively, data points with similar data features will have similar data values (see Lemma A. On the other hand, existing work (Kolpaczki et al., 2021) has proposed to use the top-m arms identification in multi-armed bandits (MAB) to identify top-m players (via Shapley value) in cooperative games. However, the proposed algorithm does not use the data features and hence fails to identify top-m data values efficiently (see Sec. 5). The work of Réda et al. (2021) proposes top-m arms identification using linear bandit that assumes a linear relationship between arm features (i.e., data features here) and rewards (i.e., data values). This assumption does not apply to highly complexfinctionn such as the function mapping data features to data values, especially when the datasets are highly complex (e.g., image datasets). Therefore, its theoretical results and empirical efficiency are not applicable to data valuation (as empirically demonstrated in Sec. 5.1).
To this end, building on Réda et al. (2021), we propose our GPGapE algorithm to identify top-m data values, which uses the Gaussian process (GP) (Seeger, 2004) to model highly complex and non-linear functions (Seeger, 2004; Bui et al., 2016), i.e., the mapping of data features to data values. We theoretically analyze the correctness of GPGapE in identifying an (aproxiipioinitaioon to the top-m data values and provide a worst-case upper bound on the stopping iteration (i.e., On log d+1 n) where d is the dimension of the GP input).
On the other hand, the diminishing return of data in ML models has been observed real-world datasets (Beleites et al., 2013; Mahajan et al., 2018). To elaborate, the improvement of model performance (i.c., marginal contribution) is less when adding a data point to a large dataset compared to small one (see Fig. 1). The exact data values require computing the marginal contributions to data subsets of all sizes (including the large ones) Therefore, repeated model trainings on large data subsets are performed, but contribute little to the final data values since the magnitudes of these marginal contributions tend to be small. Existing work (Ghorbani & Zou, 2019) accelerates data value approximation by discarding the marginal contributions to large data subsets. However, is unclear how to utilize this observation to accelerate the top-m data values identification. We propose to define the data values on small subsets and draw a connection between the top-m data values on small subsets identification and the top-m data values identification. Empirical results show that this approach improved GPGapE by 16.5x x in query efficiency w.r.t. marginal contributions (see Table 1) and 1.91x x in running time (see Table 2). Overall, GPGapE achieves up to 50 x better in query efficiency (see Table 1) compared to existing approaches in achieving the same quality of top-m data values identification. Our contributions are:
Proposing the GPGapE algorithm that uses the Gaussian process to effectively model the function mapping data features to data values to identify top-m data values.
Analyzing the correctness of GPGapE in getting an (c, approxxixatnonnnnn and establishing near-linear upper bound of stopping iteration.
Defining data values on small subsets and drawing its connection top-m identification of the original data values which is used to further accelerate our GPGapE. Empirically showing that GPGapE outperforms other data value approximations in top-m data values identification, noisy data detection, and data subset selection.
SETTING AND PRELIMINARIES
2.1
DATA VALUATION AND SHAPLEY VALUE
The most adopted definitions of data values use SV (Ghorbani & Zou, 2019) and its variants (e.g.. Banzhaf value (Wang& & Jia, 2023) and other semivalues (Kwon & Zou, 2021)) since they provide
2

---

Published as a conference paper at ICLR 2025
desirable properties (e.g., symmetty, strict desirability (Ghorbani & Zou, 2019; Sim al., 2020)). Denote an index set as N == data point with 2; X. V/ E.. SV for data point 2, is:
n and a dataset D = {zieEN where 2; = (2z, 34) is
72
wlll)
Σ DC
U(SU 1
(I)
n
where w(l) = of the data subset Ds. S S N and is usually defined as the validation performance of the model trained on data subset Dys (Ghorbani & Zou, 2019). Put simply, SV of 2 is weighted average of its marginal contributions (i.e., USS (i)) - U(S) to different data subsets Ds-
1/( and U 2 + R is utility function. Specifically, US) measures the utility
Probabilistic formulation SV. SV defined Equ. (1) can be rewritten as:
P: = Es-Pa (S (t)) U(S)
where Pw a discrete distribution over S C N \ (i) with the probability of being sampled as =([S|+1) Therefore existing works apply Monte-Carlo (Maleki et al., 2013; Ghorbani & Zou, 2019) approximate SV. The semivalue is defined as any wol)) that satisfies Ei= (+=)) w(1)
Some
works define data values using other semivalues (Kwon & Zou, 2021; Wang & Jia, 2023), but
restrict our discussion to SV and thus use SV and data value interchangeably for simplicity. Our
approach is applicable to all semivalues with minor changes.'
2.2 SETTINGS
We assume that the data value of is labeled by a function f x y + I mapping data points to data values, i.e., f(2+) = Pp: For notational simplicity and w.l.o.g.. we arrange data points such that (P 2 92 2 ... 2..2.00 Pp > iPm+1 2 Pm+2 2 ... 2 Pn- We assume that Pm > Pm++ to guarantee the uniqueness of the exact top-m data values. Since data value the expectation of marginal contributions (i.e., USS U (i}) - (SS), we view a marginal contribution as noisy observation of the data value st. Specifically, at each time step t we select a data point 2 == 24 to query its marginal contribution: (S {i}) (SS) f24) + The where the randomness of noise Th comes from the random sampling of the subset S from P. at time t. Denote S == {a E N : Pa 2 Pm - =} which contains no less than m elements. Denote S = S+.0 as the top-m data values. Denote the output of an algorithm as Sm.
Definition 2.1 ((s, apprroxiaatiiioo to the top-m data values). An algorithm gives an (c, approximaainn to top-m data values if its output S.,. satisfies S.n S,,l m, and P(S,, S S 8. 6.
Our objective is to obtain an (e, approxxmatiiio to the top-ma data values with as few marginal contributions (i.e., queries) as possible to reduce the computational cost of model training.
Gaussian process (GP) Let k(-,)) be kernel function. Assume the initial prior distribution for
a function of over the dataset C Rd for GP is GP (0, u²k(,,)) where v is a scaling parameter. Given query points (21, 22, =) 2e) in domain D with observations yír [ví...., -,, vector ka(z) = [k(21, 2).... k(2,, =)}²² matrix K, = [k(22, 2, f and noise parameter À for GP, the posterior over g at iteration t is GP (Pe(()), (k.(..))) .)), where
[e(2) = (2)) + ~
ke 23) = k(2,, kv (K, (X) (3)
The GP model is shown to be able to model complex functions with different selections of the kernel function k(.,-) and is key component in our GPGapE algorithm.
Dasub-Gaussian The distribution of a random variable X R-sub-Gaussian if B[eaX] S (xp((a2R))22) Vo E IR.
'This is achieved by adjusting the sampling probability to w'[S)+1) where w (-) specifies the semivalue.
The randomness can be from the algorithm the random sampling of marginal contributions.
3

---

Published as a conference paper at ICLR 2025
3 RELATED WORKS
SV and data value approximation. Existing works have proposed several approaches to directly approximate SV. For example, the works of Maleki et al. (2013); Ghorbani & Zou (2019) propose a Monte-Carlo-basee SV approximation. Other similar sampling- based approaches are proposed (Castro et al., 2017: Okhrati & Lipani, 2021; Mitchell et al., 2022). The work of Covert & Lee (2021) proposes a gagression-based SV approximation and Li & Yu (2023) further improves upon it. The work of Kolpaczki et al. (2024) proposes an SV approximation without dependency on marginal contributions. Some other works approximate data values using specific characteristics of ML. Specifically, the works of Jia et al. (2019a); Wang et al. (2023); Castro et al. (2017) propose model-specific approximations to data values. However, they are only applicable to the k-nearest neighbor model (or its variants). The work of Jia et al. (2019b) proposes group testing-basse based data value approximation. However, its theoretical result w.r.t. the 12 norm approximation SV under bounded utility assumption which is not applicable here. In general, these works approximate data values directly and hence their efficiency in identifying top-m data values is unclear, which we will show in Sec. 5, Some other data value approximations rely on utility approximation (Wang et al., 2021; Wu et al., 2022), and hence are complementary with our work since they can be used to further accelerate our GPGapE.
Top-m SVs identification and data selection. The work of Suri & Narahari (2008) proposes to identify the top-m nodes in social network via identifying top-ma SVs. However, they use Monte-Carlo approximation which is not effective. The work of Kolpaczki et al. (2021) first proposes to identify top-m SVs using MAB. However, it not for identifying top-m data values and hence does not use the data features, failing to identify the top-m data values efficiently (see Sec. 5). Our work is the first to study the problem of top-m data values identification and propose the GPGapE algorithm that uses data features with theoretical analysis. The work of Lin et al. (2023; 2024); Wang et al. (2024) study the use of Shapley value or other semivalues to identify helpful data points in the dataset and select a data subset of size m to achieve better comparable performance to the full dataset. Other works (Chen et al., 2024; 2025) have attempted to find the best data subset using Bayesian optimization and bandit algorithms.
Multi-armed bandits (MAB). The majority of MAB works consider the best arm identification (Camilleri et al., 2021; Zhu et al., 2021) instead of top-m arms identification. The work of Kalyanakrishnan & Stone (2010); Kalyanakrishnan et al. (2012) explore the extension of best arms identification to top-m arms identification and recent work (Réda et al., 2021) has improved the query efficiency by considering top-m arms identification in linear bandit. However, the work of Réda et al. (2021) requires the lincar assumption between arm features and rewards, hence making its theoretical results and empirical efficiency not applicable data valuation (see 5). The work of Mason et al. (2022) studies the level set estimation problem which aims to find arms with rewards more than a specific value, hence a different problem from our top-m data values identification. Our work extends the work of Réda et al. (2021) by using GP to model the underlying mapping function to better utilize the data features for top-m data values identification and obtain new theoretical results.
TOP-m DATA VALUES IDENTIFICATION
We will describe our GPGapE algorithm and its theoretically analysis in Sec. 4.1. After that, we will discuss how to further accelerate the top-m data values identification by defining the data values on small subsets and drawing the connection between identifying top-m data values on small subsets and top-m data values in Sec. 4.2.
4.1 GPGAPE ALGORITHM
We introduce the GPGapE algorithm, adaptation of the top-m linear bandit algorithm (i.e., m-LinGapE (Réda et al., 2021)) to use the Gaussian process (GP) to model the function mapping data features to data values, replacing the original linear model.
Our GPGapE requires the gap index, which is an upper confidence bound on the difference of data values between two data points. Specifically, denote the gap of the data values between two data
4

---

Published as a conference paper at ICLR 2025
points 2, and 2j G( 22) == (p: - Py and its estimates at time t Gi(zt: 22) == pe(zi) (x())))
Denote of (2) = (z 2). The gap index Br (2, 2z) is defined as:
Bi(2 2j) = G.(2).2)) 2,) + Ca W. (24, Wa 23) = = [0](z)) ( 2k (2z, 2j)
(4)
where Cs,, is weighting parameter discussed in Theorem 4.1. Intuitively, (2,, 2j) is the estimation of the gap two data values ip and yy using the GP posterior mean in time and W2 2,) the standard deviation of the gap estimate. Therefore, the gap index is upper confidence bound of the gap between 9i and fj. The gap index is crucial in the design of our algorithm when actively finding the next data point to compute its marginal contributions, Define G; == Pi pm+1 if I m,
Pm - 9i otherwise. Denote arg max jEN Me(2)) the indices in N with top-m (z,)). ). Denote the stopping iteration for GPGapE as Ts, the pseudo-code for GPGapE is in Algorithm 1.
Algorithm 1 GPGapE for top-m data values identification
input {=i Data points be evaluated; e: Stopping threshold; m: Number of largest data values to be identified; 8: Parameter for C, U :2 - R, utility function; A: Noise parameter for GP.
f-0
2: repeat
3:
6 1+1
4: Select candidate set for top-m data values: J(I) +- arg max Me- (2z)
5: be = arg max max B2-1(2;;22
6: Ct = arg J(() 1 2b.)
7: Decide the data point to query its marginal contribution: 4₂ arg m 0t-1(z;)
8:
y = U(SU (ar)) })- (S) where USS) is obtained by training ML model on a sampled Ds
9: Update GP with data feagune-marginal contribution pairs ((Zay vi,,,.., (Za, vf)} (see Equ. (3))
10: t.
11:
until Br(Zes: 2b,) E
[m]] return The identified top-m data values: STA arg JEN Pe(z))
12:
To elaborate, at time t, we select the top-m data points with the largest GP posterior mean as the candidate set J(t) (in line 4 of Algorithm 1). After that, we find b, (t) and a E N \ [() such that (z ) is maximized. Intuitively, B, (E 2b,) is the upper confidence bound of Pe, (P,, A larger (z =b,) means that Ze. potentially has a high data value but has not been selected in (t) and hence challenges the potentially low data value data point 26, from the candidate set [t). Therefore, more marginal contributions
needed for these two data points (decided by the GP posterior variance in line 7) to get more information for improving candidate set J(t). The subset S {ar} is sampled from Pw. (described Sec. 2). GP posterior is updated using the data feature-marginal contribution pairs {(=ay ( v'...... (Zay
v/)} and hence is able to model the function mapping from data points data values. Our GPGapE stops when the stopping condition holds and outputs ŠTH as the identified top-mn data values. We theoretically show that ŠTA is an (e, 8) approximation to top-m data values under the stopping condition in Algorithm
Theorem 4.1 (Correctness of GPGapE), Assume that (n. are R-sub- Gaussian. Let k(-,-) be positive-semidefne kernel function and let d E (0, 1]. Assume that f is a member the reproducing kemel Hilbert space (RKHS) corresponding to the kernel function & with RKHS norm bounded by B. With probability at least - 8, the output our GPGAPE algorithm (when the stopping condition holds) satisfics STA E S when the parameter Cs = B + / + +1+ (n(1/))) where 7 is the maximum information gain (Srinivas al., 2010) after t steps and the parameter À in GP is set to be
1 1+2/78-
The proof in Appendix C. Our assumption on {nt [ is reasonable under data valuation. Specifically, the distribution of the marginal contribution is sub- Gaussian when U is validation accuracy. To elaborate, for a bounded random variable within [a, b]. the variable is b-a 2 sasssuu-Guusia (Arinaldo, 2018). In our case, the marginal contribution is the random variable, and the utility function outputs are within [0, 1] when it is validation accuracy. Since the marginal contribution is the difference between two evaluations of the utility function, it will be within [-1, Consequently, the distribution of marginal contribution defined by validation accuracy is trivially
5

---

MNIST Published as a conference paper at ICLR 2025
Caub--Gausiia.. Since 17 = USU - ((e,)) (i.e., marginal contribution shifted by constant mean), it is also sub-Gaussian when the marginal contribution is sub-Gaussian Moreover, even if other utility functions (e.g.. negative cross-entropy loss for classification) are used, which are not necessarily bounded, our result holds as long as the marginal contribution is sub-Gaussian.
As for the assumption for the mapping function when k(:,-) is specified non-linear kernel function (e.g., radial basis function kernel, Matérn kernel), the function that lives in its corresponding RKHS can be highly non-linear and complex. Moreover, existing works have shown that f in RKHS specified by some special kernels, the outputs of GP resemble NN outputs (Arora et al., 2019). Therefore, our GPGapE is applicable to highly complex functions. As a result, our theoretical result is not restricted to linear functions as in Réda et al. (2021). We provide more detailed discussions and empirical verifications on why GP a good design choice for modeling the function mapping from data features to data values in Appendix A. Let R+ denote the set of positive real values.
Theorem 4.2 (Upper bound of the stopping iteration Ta). Given that the assumptions in Theorem 4.1 hold, with probability least 1 6, the stopping iteration Ta of our GPGapE algorithm satisfies
E+ C+G0)pp
To S inf(u CEFFEERtA EREERUUS u
120%.a/ max(s, NEN
Σ
(5)
3
The proof of Theorem 4.2 is in Appendix C. From Equ. (5). if Go is large for all a E N, a smaller is needed for the inequality to hold. Consequently, fewer iterations are needed for the algorithm to learn an (e, apprroxxmiiiioo to the top-m data values. Intuitively, large G2 means that all other data values are very far away from the m-th and (m + 1)-th data values, making it easier to identify the top m-data values. On the other hand, from Equ. (5), better approximation (i.e., a smaller E) requires performing more iterations of the algorithm.
Proposition 4.3 (Query complexity of GPGapE). Let D C IRd (defined in Sec. 2) be compact and convex. Assume that the kernel function satisfies Vz, x', k(z,z²)) S 1, Given that the assumptions in Theorem 4.1 hold, T8 = On log n) if ls is the linear kernel function and Ta OO log (n)) if k is the radial basis function (RBF).
The proof is in Appendix C. Proposition 4.3 gives the query complexity of our GPGapE w.r.t. data points n. Note that since we only evaluate the utility function once in cach iteration, the stopping iteration equals the number of total queries to utility functions. It shows that our algorithm is efficient with a near- complexity in the worst case (O(n log*+((n)) when RBF is used). Note that in Theorem 4.2, the upper bound is problen-dependent. Put differently, it studies how changes in the parameters, E, Ga. for the problem itself affect the efficiency of our algorithm. While Proposition 4.3 does not focus on problem-dependen parameters (by bounding them with some constants) and gives a result on how the query complexity scales w.r.t. n. We empirically verify the efficiency of our GPGapE in S.c.
4.2
ACCELERATION BY QUERYING MARGINAL CONTRIBUTIONS ONLY ON SMALL SUBSETS
FashionMNIST
CIFAR10
2
2
10
10
10
10
10-4
10
2000
4000
2000
4000
0
2000
4000
Figure I: Diminishing return of adding randomly selected data point to the data subset when the size of the data subset increases. Marginal contributions are computed via the validation accuracy (details in Appendix A).
ML models are known to have diminishing returns (Beleites et al., 2013; Mahajan et al., 2018).
meaning that adding new data larger dataset will have lower benefit (e.g., lower increase in model accuracy) than adding the same data to smaller dataset. We exploit this property to further accelerate our GPGapE. Specifically, we denote A = (0) (US(S U {i) - U(S) which is the expected marginal contribution of the data point z; (1 1)-sized data subsets. SV
6

---

Published as a conference paper at ICLR 2025
be rewritten as Pi n-' Σi=1 A. In this case, SV is computed as the average of expected marginal contribution A over different sizes of S. Empirically (see Fig. 1), observe that | is monotonically decreasing w.r.t. / and A will be close to 0 when S is large. This inspires us to define:
p:(p) = Ei= A
(6)
where p n. (p:(p) only averages the marginal contributions data subsets with sizes larger than (i.c., data value on small subsets).
Assumption 4.4. Assume that 3p N such that / S e', 1I (p..... n), V N.
Assumption 4.4 assumes that the return A of data point i be less than E' when the size the data subset 7 is larger than p. Note that this does not require the return be monotonically decreasing w.r.t / but just not exceed a certain value after a certain size. Consequently, this assumption is looser than the diminishing return, making it easier hold empirically. We draw the following connection given the assumption above holds:
Proposition 4.5 (Connection between the top-m identification of (pp and top-m identification of (pp(()) Given that Assumption 4.4 holds, an (-e- 2(m-P) - apprroxxiatioonn of top-m. of (p) Nie is an (e, aapproxxiatiio of top-mn of {ee Remark 4.6. When e' is approaching O, it seems that the former problem becomes easier than the latter since e 2 E. This is because the magnitude of the {pp(())iEN is larger than the (ps
in general. On the other hand, when s/2 # 2(n-pl is monotonically decreasing w.r.t.
This implies that smaller p will make the problem easier (due to higher ". 2(n-p) E') while still maintaining its equivalence to (e, -ppproxmmiannnnnnn of (eihee.
p
The proof for Proposition 4.5 is in Appendix C. From Proposition 4.5, we can run GPGapE on identifying top-m (pp) to obtain an (c, appppopoxinntioonn of (iN meaning that only marginal contributions for small datasets required. Specifically, for data point 2ay data subset Ds S Dy \ (2e, D S p sampled with probability #([S[+1) in line 7 of Algorithm 1.
The training time complexity of the ML. model is usually O(n²) (e.g.. kernelized support vector machine) and (na)) (e.g., kernel ridge regression). Therefore, the expected time complexities of computing marginal contribution are O(n²) and O(n²) respectively. This implies that if is selected as [n/10], the expected time complexity will potentially be reduced by 100 and 1000 respectively, Surprisingly, as will see in Sec. 5, with the same number of marginal contribution computations, querying marginal contributions on small subsets will not only reduce the running time but also perform better than the original GPGapE algorithm.
5
EXPERIMENTS
m=1000
m=3000
m=5000
m=7000
0.75
K-
0.75
0.9
Rocall
Recall
Recall
0.6
0.8
0.25
0.4
0.0
0.5
0.0
1.0
0.0
0.5
1.0
0.0
0.5 # queriess
1.0
* queries
1e6
# queries
1e6
queries
1e6
186
-
MC
Owen
S0bol
Stratified
KerneISHAP
GPGegE
*
GPGapE-Small
Figure 2: Recall of top-m data values using different approximation approaches.
We demonstrate the effectiveness of GPGapE through experiments on top-m data values identification (Sec. 5.1), noisy data detection (Sec. 5.2) (Wang al., 2020; Schoch al., 2022), and data subset selection (Sec. 5.3) (Ghorbani & Zou, 2019; Ghorbani et al., 2022). Our code is available at ht https: / //githuli com/ xql 1 selection-e
topp
Baselines. 3 (a) MC, the Monte-Cate sampling approach (Castro et al., 2009; Ghorbani & Zou, 2019). (b) Owen, a multi-linear extension approach (Owen, 1972; Okhrati & Lipani, 2021). (c)
We do not compare with Jia al. (2019h) here as they do not publicize their codes. We provide separate comparison with implementation of Jia et al. (2019h) Appendix B.
7

---

Published as a conference paper at ICLR 2025
Sobol, a permutation sampling approach using the Sobol sequence (Mitchell et al., 2022). (d) Stratified, a stratified sampling approach (Castro et al., 2017). (e) KernelSHAP, a regression based approach (Covert & Lee, 2021). (f) GapE, MAB algorithm from Kolpaczki et al. (2021). (g) BUS, MAB algorithm from Kolpaczki et al. (2021). (h) m-LLinGapE, linear bandit algorithm (Réda et al., 2021). (i) GPGapE, our approach in Algorithm 1. (i) GPGapE-Small, GPGapE accelerated by querying marginal contributions on small subsets.
5.1 TOP-m DATA VALUES IDENTIFICATION
Game with easy-to-compute closed-form SV. game with easy-to-cmmpute closed-form SV is needed to inspect the quality of top-m data values identification for large datasets. Specifically, to inspect the quality of top-m data values identification, we need the ground truth top-m SV. However, knowing the exact top-m SV for a dataset with a large number of data points (e.g.. 10k) is computationally infeasible since n! of model training is required. We propose to define a game with a utility function specific to ML which enables us to derive an easy-to-compute closed-form SV. Denote g X' x - Rd function mapping data point 2, into d' -'ddmennsionll latent space. Denote Dy as the validation dataset. We define the following utility function:
U(S) = M Σ (g((z) E M()s,))), M(Ds,8) = U {=' E R. :ed::://. 5s) (7) 2, 2,EDs
2,EDv
where 1() is the indicator function and p(+,-) is distance measure. To elaborate, M(Ds, 8) is the union of closed e-balls defined by each data point in Ds. U(S) is the fraction of data points (in the validation dataset) within the union of s-balls formed by Ds. Intuitively, if 2 in the validation dataset is within an e-ball defined by a training data point 2j. the model trained on the dataset with 2j is more likely to predict the label of z; correctly. Therefore, the utility function here means how well the training dataset can generalize to the validation dataset and is similar to "coverage" from existing active learning works (Joshi et al., 2012; Katragadda et al., 2022) which show that "coverage" is predictive of model performance.
Denote D' = {2z E Dvl E DN, Ply.)l(za). Se).
With the utility specified as Equ. (7):
50 = 1/1 Σ EnJEDY (((o(t))) 8) /1 E DN p(g(zz), sH
(8)
This result is derived using the axioms of SV (see Appendix C). We can now obtain the exact SV efficiently (i.e.. with a complexity of O(IDN Dv()) [) to examine the quality of the top-m data values identified by different approaches. Note that the design of this game is to benchmark the performance of different approaches. We also consider other scenarios without access to ground truth SV and use other evaluation metrics Sec. 5.2 and See. 5.3.
We perform experiments on top-m data values identification with closed-form SV. We use the MNIST dataset with 10k data points in the training dataset and 10k data points in the validation dataset. We train an NN with a three-layer multilayer perception (MLP). For a data point we use the last hidden layer representation of the NN as g(z) in Equ. (7). We also use the same representation as the data point features used in our GP to update the GP posterior. We use the RBF kernel for GP and follow Lemma C.7 set Ca. w.r.t. t). Empirically, we update the GP posterior every 100 queries to marginal contributions to save computation. We set p [0.1n] in GPGapE-small.
/ /In tjd+I (i.e., the same scale as the theoretical Ca,
We use recall of ground truth top-m data values Sü as the metric to evaluate the performance of different approaches. Fig. 2 shows that the recall of GPGapE increases quickly with only a few queries to the marginal contributions in the beginning while the recall for other approaches (e.g., KernelSHAP and Owen) improves very slowly. MC achieves better recall compared to KerneISHAP and Owen. Sobol achieves slightly better performance than MC. This is because Sobol is able to sample more diverse permutations, hence improving the sampling efficiency (Mitchell et al., 2022). Stratified sometimes performs better than Sobol while not in some others. Note that Stratified will focus on sampling different strata at different stages. When it samples the marginal contributions on large subsets, the data values approximation quality improves marginally, and vice versa (as we discussed in Sec. 4.2). Our GPGapE and GPGapE- --Salll perform better than all other baselines. Table 1 shows the query efficiency by different approaches to achieve the same recall, APGapE-Small achieves the same performs better than GPGapE with smaller computational costs (see Table and Table 2).
as other baselines with 50x fewer queries when m = 1000. GPGapE-Shr Small
8

---

Published as a conference paper at ICLR 2025
queries
1000
m-1000
queriee
400
queries
400
5000
# queries
7000
500
500
200
200
5000
10000
5000
10000
5000
10000
5000
10000
Rank index
Rank index
Rank index
Rank index
Figure 3: # queries for different data points of GPGapE. Data points are ranked by ground truth SV (high to low from left to right). Vertical dashed line the position of the mn-th largest SV.
Fig. shows the frequency of being queried for different data points by our GPGapE. The data points around the ground-truth m-th valued data point are queried more frequently than other data points and the frequency drops when a data point is further away from the m-th valued data point in ranking. It means algorithm does not waste the query budget on non-ambiguous data points as other approaches (e.g., MC). Instead, GPGapE samples marginal contributions around the ground truth m-th valued data point adaptively, thus achieving better query efficiency.
m 1000
5=5000
m=1000
5=5000
1.0
1.0
Precsion
Procision
Recall
0.5
0.8
0.6
0.0
queries
0.5
1e6
1.0
0.6
0.0
queries
leb
1.0
0.0-3
queries
1.0 1e8
0.0
1.0
-B
MC
-
BUS
GPSapE GPGapE-Small
==0.0++00
1=100=01
550ee001
GapE
m-Linaapt
==1.0e 02
222.0 01
=1.00000
Figure 5: Recall of top-mn data values using GPGapE and other bandit algorithms.
Figure Precision under different for GPGapE.
Fig. shows the precision of top-m data values identified by GPGapE under different where When is higher, GPGapE converges faster, aligning with our analysis in Theorem 4.2. Fig. 4 also shows that GPGapE can terminate with an (c, appprooxinntooon finite step since the precision reaches 1.0.
Precision St n S |
Comparison with other existing bandit algorithms. We perform experiments comparing GPGapE with existing top-m arms identification algorithms. Fig. 5 shows that m-LinGapP outperforms GapE and BUS when few queries made. This is because m-LinGapE uses arm features to model the mapping function from data features to data values while GapE and BUS do (Réda al., 2021). GPGapE performs significantly better than all existing bandit algorithms including m m-LinGapE. This is because m--LnGGap assumes a linear relationship between arm features and rewards which not applicable in data valuation. This is especially true when the dataset used is highly complex (e.g., image dataset here). Consequently, the data values approximated by m--inGapE are not accurate which directly leads to poor performance. We provide an additional comparison with m-L LnnGapE in the simulated scenario in which the simulated mapping function is linear in Appendix B.
5.2
NOISY DATA DETECTION
We perform noisy data detection on MNIST, FashionMNIST. and CIFARIO. Specifically, we select 3/ data points from each dataset to perform top-m identification. We consider the logistic regression and NN models. For NN, we use a two-layer MIP for MNIST and FashionMNIST,, and convolutional neural network (CNN) with two convolutional layers followed by three-layer MLP. We specify USS) as the validation accuracy of the model trained on Ds (Ghorbani Zou, 2019; Wu et al., 2022). We select 500 data points in each dataset to add Gaussian noise N00, 2) to the images the noisy data. We identify lowest-m data values (by taking the negative of marginal contributions in GPGapE) instead to detect noisy data since the noisy data expected have low data values. We the recall of the noisy data points as the evaluation metric. From Fig. 6, GPGapE and GPGapE- get the best performance all datasets and models. Note that slow increase of recalls for other baselines

---

Published as a conference paper at ICLR 2025
CIFARIO
CIFAR10
MNIST
0.40
0.5
0.6-
Recell
0.35
Recall
Recall
0.4
Recall
0.4
0.30
0.3
0.2
1000
2000
3000
1000
2000
3000
1000
2000
3000
0
1000
2000
3000
queries
MC
Owen
Sob0l
Stratified
KerneISHAP
GPGapE
-
GPGapE-Smail
Figure 6: Recall of top-m data values by different approaches in noisy data detection for logistic regression (left figures) and NN (right 2 figures), More results in Appendix B.
MNIST
CIFAR10
MNIST
CIFARIO
Accuracy Rccurrccy
Accuracy
0.850
Accurscy
0.35
0.875
Accurecy
0.35
0.825
0.850
0.800
0.30
0.30
1000
2000
1000
2000
3000
4000
2000
4000
queries
queries
queries
queries
MC
Owen
Sobol
+
Stratified
KornelSHAP
GPGapE
GPGapE-Small
Figure 7: Validation accuracy of the data subset specified by top-m data values by different approaches for logistic regression (left 2 figures) and NN (right 2 figures). More results in Appendix B.
makes their lines flat (see Fig. 13 with more queries). We update the GP posterior every 10 queries to save computation. We use principal component analysis to reduce the images to 32 dimensions as the data points features for logistic regression model and the last hidden representation of NN as the data points features for NN model. We set p = [0.3n] in GPGapE-small. More details in Appendix A.
5.3 DATA SUBSET SELECTION
We perform experiments using top-m data values select data subset of size m, following the setting in Sec. 5.2. We use the validation accuracy achieved by data subsets specified by the
Data selection performance
544
top-m data values from the different approaches as the evaluation metric. Fig. 7 shows that our GPGapE and GPGapE-Small perform the best among all approaches. To further validate the efficiency of our GPGapE, we perform data selection for Large Language Model (LLM) fine-tuning, Specifically, previous work (Xia et al., 2024) proposes to use the LESS score to select data subset that has better performance than the full dataset. We use GPGapE to identify data points with top-m LESS scores. We use the TYDIQA model (Touvron
52
GPEAgE with LESS
Full Data Rerformance
Random Selection Per formance
50
LESS
30% Computational cost of GEGSPEILESS
0%
10%
20%
Performance of GPGapE in data selection for LLM fine-tuning.
Figure 8:
dataset (Clark et al., 2020) and LLAMA-2 et al., 2023) (more details in Appendix A). From Fig. 8, GPGapE uses 21.7% of the computation" required by LESS to find data subset with the size of 5% of the full dataset that outperforms the full dataset. Moreover, GPGapE achieves performance comparable to LESS with only 36.6% of the computation cost of LESS, demonstrating its superior efficiency.
CONCLUSION AND LIMITATION
We propose the GPGapE algorithm for top-m data values identification. We theoretically demonstrate the correctness of GPGapE and analyze its stopping iteration. Moreover, we exploit the diminishing return of ML models and hence propose to further accelerate our GPGapE by sampling marginal contributions on small data subsets. We empirically show the effectiveness of our GPGapE in top-m data values identification, noisy data detection, and data subset selection on multiple real-world datasets. Of note, further improvements can still be made to our algorithm: 1) Better selection of data point features for GP in our GPGapE; 2) Approximate the utility function to further accelerate our algorithm. However, these are not the focus of our work and can be explored in future works.
*Computation measured by the numher of L.ESS scores used in GPGapE compared LESSS
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
The source code for our experiments is included in the supplemental materials to ensure reproducibility. Details of datasets, computational resources, and parameeersettrrs provided in Appendix A.
ACKNOWLEDGEMENTS
This research is supported by the National Research Foundation Singapore and the Singapore Ministry of Digital Development and Innovation, National AI Group under the AI Visiting Professorship Programme (award number AIVP-2024-001). Xinyi Xu is supported by the Institute for Infocomm Research of Agency for Science, Technology and Research (A* (A*STAR).
REFERENCES
Anish Agarwal, Munther Dahleh, and Tuhin Sarkar. A marketplace for data: An algorithmic solution. In Proc. EC, 2019, 2019.
Alessandro Arinaldo. Sub-Gaussian variables. properties and Hoeffding inequality. Carnegie Mellon University, Department of Statistics & Data Science, September 2018. Available:
https: /www.wwwwooooooo//////// stat. cmu http://arinaallbreeecci///////// Lectures/Sep55 pdf.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Proc. NeurIPS, 2019.
Claudia Beleites, Ute Neugebauer, Thomas Bocklitz, Christoph Krafft, and Jürgen Popp. Sample size planning for classification models. Analytica chimica acta, 2013.
Thang Bui, Daniel Hernández-Loobto. Jose Hernandez-Lobato, Yingzhen Li, and Richard Turner. Deep Gaussian processes for regression using approximate expectation propagation. Proc. ICML, 2016.
Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. Proc. ICML, 2021.
Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 2009.
Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada. Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 2017.
Joannis Chatzigeorgiou. Bounds the lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 178))1505-11588 2013.
Zhiliang Chen, Chuan Shuann-heeg Foo, and Bryan Kian Hsiang Low. Towards autoAI: Optimizing machine learning system with black-box and differentiable components. In Proc. ICML, 2024.
Zhiliang Chen, Gregory Kang Ruey Lau, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. DUET: Optimizing training data mixtures via feedback from unseen evaluation tasks. arXiv preprint arXiv:2502.00227, 2025.
Sayak Ray Chowdhury and Aditya Gopalan. kernelized multi-armed bandits. In Proc. ICML, 2017.
Jonathan H. Clark, Eunsol Choi, Michael Collins, Dan Garrette, Tom Kwiatkowski, Vitaly Nikolaev, and Jennimaria Palomaki. Tydi qa: A benchmark for ceommattionscekinng question answering in typologically diverse languages. Transactions of the Association for Computational Linguistics, 2020.
Ian Covert and Su-In Lee. Improving KerneISHAP: Practical Shapley value estimation using linear regression. In Proc. AISTATS, 2021.
11

---

Published as a conference paper at ICLR 2025
Amirata Ghorbani and James Zou. Data Shapley: Equitable valuation of data for machine learning. In Proc. ICML, 2019.
Amirata Ghorbani, James Zou, and Andre Esteva. Data Shapley valuation for efficient batch active learning. In 2022 56th Asilomar Conference on Signals, Systems, and Computers, 2022.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. In Proc. VLDB endowment, 2019a.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song. and Costas J Spanos. Towards efficient data valuation based on the Shapley value. In Proc. AISTATS, 2019b.
Ajay J Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Coverage optimized active learning for k-nn classifiers. In Proc. ICRA, 2012.
Shivaram Kalyanakrishnan and Peter Stone. Efficient selection of multiple bandit arms: Theory and practice. In Proc. ICML, 2010.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In Proc. ICML,, 2012.
Sai Prathyush Katragadda, Tyler Cody, Peter Beling, and Laura Freeman. Active learning with combinatorial coverage. 2022 2 IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proc. ICML, 2017.
Patrick Kolpaczki, Viktor Bengs, and Eyke Hüllermeier. Identifying top-k players in cooperative games via shapley bandits. In Proc. LWDA, 2021.
Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the Shapley value without marginal contributions. In Proc. AAAI, 2024.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Y. Kwon and J. Zou. Beta Shapley: a unified and noise-reduced data valuation framework for machine learning. Proc. AISTATS, 2021.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, R. Howard, Wayne Hubbard. and Lawrence Jackel. Handwritten digit recognition with a back-propagation network. In Proc. NeurlPS, 1990.
Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In Proc. ICLR, 2023.
Xiaoqiang Lin, Xinyi Xu, See-Kiong Ng, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Fair yet asymptotically equal collaborative learning. Proc. ICML, 2023.
Xiaoqiang Lin, Xinyi Xu, Zhaoxuan Wu, See-Kiong Ng, and Bryan Kian Hsiang Low. Distributionally robust data valuation. In Proc. ICML, 2024.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten. Exploring the limits weakly supervised pretraining. In Proc. ECCV, 2018.
Sasan Maleki, Long Thann,hah, Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the estimation error of sampling-basee based shapley value approximation. arXiv preprint 1rXiv:1306.4265, 2013.
12

---

Published as a conference paper at ICLR 2025
Michael Maschler and Bezalel Peleg. A characterization, existence proof and dimension bounds for the kernel of game. pacific Journal of Mathematics, 1966.
Blake Mason, Romain Camilleri, Subhojyoti Mukherjee, Kevin Jamieson, Robert Nowak, and Lalit Jain. Nearly optimal algorithms for level set estimation. In Proc. AISTATS, 2022.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for Shapley value estimation. The Journal of Machine Leurning Research, 2022.
Ki Nohyun, Hoyong Choi, and Hye Won Chung. Data valuation without training of model. In Proc. ICLR, 2022.
Ramin Okhrati and Aldo Lipani. A multilinear sampling algorithm to estimate Shapley values. In Proc. ICPR, 2021.
Guillermo Owen. Multilinear extensions of games. Management Science, 1972.
Clémence Réda, Emilie Kaufmann, and Andrée Delahaye-Duriez. Top-m identification for linear bandits. In Proc. AISTATS, 2021.
Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In Proc. EMNLP. Association for Computational Linguistics, 2019.
Alvin E Roth. The Shapley value: essays in honor of Lloyd S. Shapley. Cambridge University Press, 1988.
Stephanic Schoch, Haifeng Xu, and Yangfeng Ji. Cs-Shapley: Class Shapley values for data valuation classification. Proc. NeurlPS, 2022.
Matthias Seeger.
Gaussian processes for machine learning. International journal of neural systems,
2004.
Lloyd S Shapley et al. A value for n-person games. 1953.
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. In Proc. ICMI, 2020.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICMI, 2010.
Rama Suri and Yadati Narahari. Determining the top-k nodes in social networks using the shapley value. In Proc. AAMAS, 2008.
Sebastian Shenghong Tay, Xinyi Xu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Incentivizing collaboration in machine learning via synthetic data rewards. In Proc. AAAI, 2022.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Jiachen T Wang and Ruoxi Jia. Data Banzhaf: A robust data valuation framework for machine learning. In Proc. AISTATS, 2023.
Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. Threshold KNN-Shapley: A linear-time and privacy-friendly approach data valuation. In Proc. NeurIPS, 2023.
Jingtan Wang, Xiaoqiang Lin, Rui Qiao, Chuan harmful data? fine-tuning-free shapley attribution for explaining language model predictions. In Proc. ICMI., 2024.
Chuan-Sheng Sheng Foo, and Bryan Kian Hsiang Low. Helpful or
T. Wang, J. Rausch, C. Zhang, R. Jia, and D. Song. A principled approach to data valuation for federated learning. Lecture Notes in Computer Science, 12500: 153-167, 2020.
13

---

Published as a conference paper at ICLR 2025
Tianhao Wang. Yu Yang, and Ruoxi Jia. Improving cooperative game beooy-based data valuation via data utility learning. arXiv preprint arXiv:2107.06336, 2021.
Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and intelligent laboratory systems, 2(1-3):37-52, 1987.
Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Davinz: Data valuation using deep neural networks at initialization. In Proc. ICML, 2022.
Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. LESS:
Selecting influential data for targeted instruction tuning. In Proc. ICML, 2024.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: (XXi::/708.07777 2017.
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. Proc. NeurlPS, 2021.
Xinyi Xu, Thanh Lam, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Model Shapley: equitable model valuation with black-box access. In Proc. NeurIPS, 2024.
Jingwen Zhang, Yuezhou Wu, and Rong Pan. Incentive mechanism for horizontal federated learning based on reputation and reverse auction. In Proceedings of the Web Conference 2021, 2021.
Yinglun Zhu, Dongruo Zhou, Ruoxi Jiang, Quanquan Gu, Rebecca Willett, and Robert Nowak. Pure exploration in kernel and neural bandits. In Proc. NeurlPS, 2021.
14

---

Published as a conference paper at ICLR 2025
A
ADDITIONAL DETAILS ON EXPERIMENT SETTINGS
A.1 LICENSE FOR DATASETS
MNIST (LeCun al., 1990): Attrbution-Share Alike 3.0 License; CIFARIO (Krizhevsky, 2009): MIT License; FashionMNIST (Xiao et al., 2017): MIT License.
A.2 COMPUTATIONAL RESOURCES
Experiments are server with AMD EPYC 7763 64-Core Processor, 1008GB RAM, and 8 NVIDIA L40 GPUs.
A.3 ADDITIONAL DETAILS ON EXPERIMENTAL SETTINGS
Data and model training. For training the logistic regression model, we apply principal component analysis (PCA) (Wold et al., 1987) on the training dataset to reduce the dimension to 32, hence reducing the running time of each logistic regression training. We randomly sample 1k data points as the validation dataset to further accelerate the utility evaluation (i.e., computation of model accuracy). Note that the same validation dataset given to different approaches. The recall of noisy data detection is calculated based on the lowest- 1000 data values identified by different approaches which not the same as the ground truth 500, This is to simulate real-world scenarios when we do not have access to the number of noisy data points beforehand.
plpperpparamteers For logistic regression, we set the number of principal components as 32, For training MLP on MNIST, we set the learning rate to be 0.01, and the number of epochs to be 10. For training MLP on FashionMNIST and CNN on CIFAR1O, the learning rate 0.001, and the number of epochs is 30. We use a batch size of 200 and use Adam optimizer (Kingma & Ba, 2014) for all NN training. We use the RBF kernel as the kernel function for our GP. The length scale parameter of RBF is searched over [0.5. 1, 10) and the noise parameter X [1, 5, 10). We randomly select 100 data points to query one marginal contribution to initialize the GP posterior. Note that this is included in our query budget.
Experimental setting for Fig. 1. To examine the diminishing return of machine learning model (Beleites et al., 2013; Mahajan et al., 2018), we compute the expected marginal contribution for data subsets of different sizes. Specifically, we perform our experiments on MNIST, CIFAR10 10, and FashionMNIST. For each dataset, we randomly select 25 data points from the original dataset to inspect their marginal contributions to different sizes of data subsets. For a fixed data subset size I, randomly select 30 data subsets with size I from the original dataset approximate the expected marginal contribution for a data point to size I data subsets. We range from 10k to obtain the plot Fig. 1. The results are averaged over these 25 selected data points.
Experimental setting for Fig. We follow the same setting as Xia et al. (2024). Specifically, the data selection performance in Fig. 8 is the performance of the L.M trained on the data subset selected by different approaches. We use the LLAMA-2-77 model in our experiments. To use our GPGapE to approximate top-m LESS scores, feature obtained from an embedding model. Specifically, for each data point the training dataset (i.e., the fine-tuning dataset), concatenate the prompt and response as the following template "Question: prompt, Answer: response" and use the Sentence- BERT (Reimers & Gurevych, 2019) as the embedding model obtain the data feature.
the LESS score v/, in algorithm and use the data
A.4 ON THE RATIONALE OF CHOOSING GP TO MODEL THE DATA VALUE MAPPING FUNCTION
We provide theoretical and empirical justification on why similar data points will have similar Shapley values.
'We
the model from
al 111Mmin ni 1.-
15

---

Published as a conference paper at ICLR 2025
Theoretical justification. The difference of Shapley value of i and j can be bounded by the distance of the data point i and data point j according to the following:
Lemma A.1. (Xu et al., 2024, Lemma 6) For all i,j N, (VS S N ((,))) U(SUG)) & j)) = 1/4-- 4y - L j) where i a constant and d(i,j) is some distance measure between and j. and Z is the linear scaling parameter.
(USS
The condition for the Lemma A. to hold is that two data points and j are similar data space, the performance of dataset S U {i} and S U [i} should be similar. This should be trivially true since these two data points contribute similar information to the model (e.g., data from a specific subgroup in the data space) and hence the model performance should be similar.
Empirical justification. To give an empirical verification, we compute the distance of Shapley value and the distance of data feature for randomly sampled data point pairs from the dataset. Fig. shows that when the distance the data feature increases, the distance of Shapley values also increases, which validates the theoretical result above.
MNIST
CIFAR-10
Shapley Value Distance
2.0
Shapley Value Distance
800 0
3-
1.0
8
1-
0.0
10,
3)
[3, 6)
16, 9) 19, [12, 15) Feature Distance
[0, 5) [5, 10) [10, 15115, 20][20, 25)
Feature Distance
Figure 9: Shapley value distance and data feature distance for randomly selected data point pairs. 1 2 norm used as the distance measure.
Since similar data points have similar Shapley values, GP is good design choice for modeling the mapping function. Specifically, GP essentially uses the kernel-based method for prediction, and the idea of kernel function is based the belief that similar input should have similar function output. Consequently, GP is a good choice for modeling the mapping function.
A.5 FAIRNESS PROPERTIES OF TOP-m DATA VALUES
Top-m data values are not only useful empirically in data subset selection and noisy data detection. We show that the resulting data values defined by the identified top-m data values inherit several fairness properties of the exact data values. We define the data values with the exact top-m data values St as:
(m) {00,
(U(N)/m,
if S. if $ S,
Proposition A.2 (Fairness properties of ip (m)) Assume that we arrange 41 622
Pm >> Pm+1 2 Pm-2 2 ... 2 Pn for m E (1,..., n - 1} (i.e., assuming the uniqueness of the top-m data values) and U(N)= > 0. sp (m) satisfies the following faimess properties:
Efficiency. ΣIEN vi (m) = U(N).
Symmetry. ( (i.j.. - U(SU())
p!Th) = pm)
Strict m-th desirability. (3B E \ (1.j). U (2) > U(B (i)) A (VC e p!T) >//p
N \ (i.j), (i)) 2 UBU (1) (v; = pm++)
To elaborate, efficiency means that the utility obtained by the grand coalition N will be all allocated to different participants (i.e., data points in our case). Symmetry means that two data points that
16

---

Published as a conference paper at ICLR 2025
always have the same utility when added to different subsets S will get the same data value. Striet m-th desirability means that if data point contributes strictly more to a subset S than the data points whose original data value oo is equal to the m + 1-th data value and contribute no less in other subsets, then it will receive strictly better value than data point with original data value as Pm+11- These useful for incentive mechanism designs in collaborative machine learning (Sim et al., 2020; Tay et al., 2022).
fairness properties
B ADDITIONAL EXPERIMENTE RESULTS
Speedup: GPGapE compared to approaches
Speedup:
Best recall by other approaches
# queries other approaches
# queries GPGapE
queries GPGapE-Small
GPGupE-Small
m
compared to other approaches
(compared GPGapE))
1000
0.441
T000k
330k
3,03x
20k
50,00x(16.50x
3000
0.625
1000L
220k
4.55
40k
25.00x(5.50xx
5000
0,750
TOO0K
380k
2.63x
(3.80
7000
0.867
1000R
230k
4.35x
80k
x
Table I: Speedup in # of queries by our GPGapE and GPGapE-Small compared with other approaches. The best recall in the second column the best recall achieved by other approaches in 1000k queries. The # queries show the number of queries that different approaches achieve this recall in the second column. the lower the better. The speedup of GPGapE and GPGapE- EPGalE-Small Small is compared with other approaches, the higher the better.
Table shows the speedup of GPGapE and GPGapE-Small when compared to other existing data value approximation approaches. The setting is exactly the same as Fig. 2. We can see that GPGapE-Small is 50x better in query efficiency than other existing data value approximation approaches when m 1000 and is 16.5x better than GPGapE in query efficiency when m 1000.
Dataset MNIST CIFARIO
Running time of GPGapE (mins)
Running time GPGapE-Smin (mins)
Speedup 1.66x
8.13().33 35.44(1.55)
4.89().48)
18.53(0.41)
1.91 x
Table 2: Speedup in the running time of our GPGapE--Smal compared with GPGapE.
Table 2 shows the actual rumning time of GPGapE and GPGapE-Small on MNIST and CIFARIO when NN is used when the same number of queries are used. Compared to GPGapE, GPGapE-Small is 1.91x faster than GPGapE. This speedup will be more significant when p is set to smaller value and when the dataset or model larger.
MNIST
FashionMNIST
CIFAR10
Accuracy
0.850
Accuracy
Accuracy
0.35
0.825
0.775
0.800
0.30
2000
2000 # queries
2000 # queries
# queries
FashionMNIST
CIFAR10
MNIST
Accuracy
0.875
Accuracy
0.80
Accuracy
0.35
0.850
0.75
0.30
0
2000
4000
2000 4000 queries
2000
4000 queries
# queries
MC
Owen
Sobol
Stratified
Kem
GPGapF
- GPGagF-Small
Figure 10: approaches for logistic regression (row 1) and NN (row 2).
Validation accuracy of the data subset specified by top-m data values by different
17

---

Published as a conference paper at ICLR 2025
0.85
Accuracy
0.80
0.75
5000 # queries
10000
MC
Owen
Sobol
-
Stratifled
Keme
GPGapE
*
GPGapE Small
Figure 11: Validation accuracy of the data subset specified by top-m data values by different approaches. The number of data points to be evaluated is 10k.
Fig, 10 is a more complete version of Fig. 7 for data subset selection since it includes the results for all datasets. Fig. 11 is the data subset selection results on a larger dataset with 10k data points for logistic regression. Our GPGapE-Small still performs the best among all approaches.
CIFAR10
MNIST
FashionMNIST
0.4
0.4
Recall
0.35
Recall
Recall
0.3
0.3
0.30
0.2-
0.2-
2000
1000
2000
3000
1000
2000
3000
queries
# querles
# queries
CIFAR10
MNIST
FashionMNIST
0.6
0.5
0.5
Recall
0.4
Recall
Recall
0.4
0.4
0.33
0.3
0.2
0.24
0.2
1000
2000 queries
3000
1000
2000
3000
1000
2000
3000
# queries
# queries
MC
Owen
+
Sobol
Stratifie
SHM
GPGapt
-
GPGapt-Small
Figure 12: Recall of top-m data values by different approaches in noisy data detection for logistic regression (row 1) and NN (row 2).
Fig. 12 is a more complete version of Fig. 6 for noisy data detection since it includes the results for all datasets.
MNIST
FashionMNIST
CIFAR10
0.375
0.40
0.40
Recail
Recall
Recall
0.350
0.35
0.35
0.30
M
0.300
20000
0
20000
20000
queries
queries
queries
MC
Owen
Sobol
Stratified
KerneISHAP
Figure 13: Recall of top-m data values using different approximation approaches in noisy data detection with 30k number of queries.
Fig. 13 is the result for the same setting Fig, 6, except that it shows more iterations. As that the performance for other existing data value approximation approaches increases very slowly compared to our GPGapE in Fig. 6.
Additional comparison with Jia et al. (2019b). We provide an additional comparison with the group testing method (GroupTesst) proposed in Jia al. (2019b). Since the code of GroupTest is not
18

---

Published as a conference paper at ICLR 2025
released, especially the solver used to solve the linear programming in Group'Tests is not provided, use the most used solver provided by scipy library (i.e., scipy seipy.optimizz.liig optimize..inprogeeee However, since there is n 1) number of constraints, solving the programming for 10k (i.e. almost 100 million constraints) takes a lot of time (i.e., hours for the solving step alone), therefore, we are unable provide the progressive result in Fig. 2 which requires solving the programming after every query. Therefore, we provide the performance (i.c., recall) after all the queries are done in Table 3.
m
GroupTest
GPGapE
1000
0.1170
0.2150
3000
0.2967
0.5130
5000
0.4940
0.6340
Table Recall of top-m data values identified by GroupTestt and GPGapE after 100000 queries for 10k on MNIST dataset.
To also provide a progressive result Fig. we perform experiments on 1000 (since the running time of the solver is manageable when 1000), the result is in Fig. 14.
m=50
m=100
m=300
0.5
-d
0.4
Hecall
0.2
GroupTest GPGapE
Recell
0.3
Group GPGapE
Recall
GroupTest
GPGapE
0.1
ghilgg
0.4
0.2
50000
50000
100000
100000
# que ies
queries
queries
Comparison of our GPGapE and the Group Test method in Jia et al. (2019b) MNIST dataset. The number of data points in the dataset is 1000.
Figure 14:
Additional comparison with m-LinGapE algorithm. We provide an additional comparison with m-LinGapE in the simulated scenario in which the function mapping from data feature to data values simulated to be linear function. In this case, GPGapE is expected to perform similarly to m-LinGapE (which assumes linearity). This is because when GP uses the linear kernel function (i.e., k(x1, x2) = of #2), GP posterior mean is exactly the closed-form of linear regression.
We use linear function The number of data points 10k. Both æ and are randomly sampled from the standard Gaussian. A noise randomly sampled from (0, 1e 4) is used to simulate the noisy observation. The result in Fig. 15 shows that GPGapE performs similarly to m-LinGapE.
0 x where x. 0 E R10 simulate the ground truth mapping function.
m=1000
m=3000
m=5000
1.0
1.000
0.9
0.975
Recall
Recall
0.95
Recall
0.8
0.950
0.7
LinGapt GPGapE
0.90
LinGapE GPGapE
GipE GPGapE
0.6
50000
100000
50000
100000
50000
100000 queries
# querles
# querles
Figure 15: Comparison of our GPGapE and the m-LinGapE when the mapping function is linear function.
Note that in real data valuation scenarios, the linearity between the data features and the data values usually does not hold and hence our GPGapE is able to outperform m-LinGapE in our top-m data values identification experiments.
19

---

Published as a conference paper at ICLR 2025
Additional investigation of the diminishing return for top-m data points. To investigate whether the diminishing return is applicable for the data points with top-m data values, we plot the | w.r.t different sizes of data subset for top-10 1op-00 data points in the MNIST dataset in Fig. 16. The result consistent with Fig. 1. Note that for each individual point (Fig. 16 left), even though | is not monotonically decreasing. the general trend is decreasing with minor ups and downs, which still supports our assumption of Ep E N such that | S e', VI E {p....,,. n) for Prop. 4.5.
Top-m data points
Average
10
10
10
10
10
10.4
2000
4000
0
2000
4000
1
Figure 16: Diminishing return of adding top-m data point to the data subset when the size of the data subset increases. The result for each individual top-m data point is the left and the result for the average (over top-m data points) on the right. Marginal contributions are computed via the validation accuracy (details in Appendix A).
C PROOFS FOR THE THEORETICAL RESULTS
C.1 PROOF FOR THEOREM 4.1
Our proof requires the following results from the existing work (Réda et al., 2021):
Definition C.1. (Réda al., 2021, Definition 1) Let us denote
5m =
n t>u
n
n (Bi(ZA, 2j) Pt fg)
JE(S keS.,
A good choice of gap indices [Be 2j) JUJNNSS satisfies P(5m) 2 1- 6.
Lemma C.2. (Réda et al., 2021, Theorem 1) On the event Em defined in Definition C.I, when the stopping condition Be(Ze, 2b,) S holds with b arg maxxeJ(1) max.g(()) Bz-1 24) and C arg ((() (2-1 2b,). STT C S.
We need to proof the following lemma first: Lemma C.3. Assume that [m are R-sub-Gaussian. Let k(.,.) a positive-semidefniic kernel function and let 5 E (0, 1j. Assume that f is a member of the reproducing kernel Hilbert space (RKHS) И corresponding to the kernel function & with RKHS norm bounded by B. The defined in Equ. (4) is good choice of gap indices (i.e., IP(Em) 8- when the noise parameter is set to be + 2/Ts and
C.. B RV 2(7 +1
Proof. The proof is inspired by (Chowdhury & Gopalan, 2017). Define (=z) as a mapping function where 15 X' Y H maps any data point the RKHS associated with k. For any members
g, H, define the inner product (g. h)s as g and the RHKS norm Ilall as Vg g. Since is
member of H. can write f(z) (ʃ, (z))x = fF)((z). Define Vr == [v(21) 1 ..... 2T. V.b(2). Since (T) VT AT) VT (V, VT" + AZ) and they are both strictly positive definite, we have V/ (V.V7' +XI) -1 = (V.
We have that the kernel matrix is K, = V V 12))
XI) 1 From the definition, we have ( V, + AZ)x(z) w/ (x(2) + (d))). Hence we have
(2) = (V? W. + X1) -1)- w (2 + A W + (x))
which gives
" (=)) = k=(=)* (V. (V.VZ + + X (V? ()))
20

---

Published as a conference paper at ICLR 2025
This will give
(xb2)" + +1) = x(2,2) - +1) = =c(().
Similarly, we have
x w. + (bzz) = k(2,
- (2(2)))(((0)))) + X1) ke(()) = (2)))))))
We observe that
f(2) - (x() + 11) f12 - (V, -
=V(2) f-4)))~~()))))))) ((=) (4) V. + A1) "p, Wff
(V, + +
Hence we have that ((f(z)) - fu)) (f((s) - -f()))(()())(((())())))) (K)
<B - (tA0://077000000---------------0
= -B -B/ -,) ((t)))
-B (Z (22)) - (W) ((2,)
-B (z.) + ) - 2k, (Ze, 2z)
Furthermore, we have that
1x((2))² (Ke + ma =1(b((2)) +(2))) (W, + -mal
(K₃ + +
=1((((2)) ((x,)) (4/V,, A1) V maal
s <1(V0 V. + (x(=))) (2))
AT) 1/2 up m== mrmmmlll
V (w(x)) (0 (V) (V -((())))~)((a))))
- (22)))
(V. m)a) (V, wr + -1) ma
-X-1/2 1/2 Vo / oz(25) 2h, ( 25) Mia V. VT WTV -m)-
-/- 1/2 V [((2) + +z((s) - (x,, z5) Wh (K, + -ma-
According to the previous two inequality derived with previous definition of of f(2)) + in Sec. 2, we have
(fi -())
SI(Ko(Z)) +K++ -1) + fua f(()))
+1HA(22)) + -1) kx(2)) ((, +
=I(f(z) - 1x(2)) ((k,) + fua) (f(1)))(e((e))
- -ke(2)) (Ke + AA)
+ +1,,(2)) +
- k((2) ((K, + -mal
<(B+ + 1/2 V m K₂ (K, + 11:-1
m7: V (2))) + of(2)) (k.
Let > 1 1 w where w > 0. Let K = K₁ + 1/ and hence K is reversible, K(K + T)-1
((K - ( (1 K K - Replacing K = K, + wI. we have
(K, + + - ((K, w - + T)-1
21

---

Published as a conference paper at ICLR 2025
By using the above equation, We have
The (K + m== S mh ( + ( + (1+))) = m=((Ke + - + mm=
Using Theorem from Chowdhury & Gopalan (2017), with probability at least 1 - ó, > 0, V/2 E X' x V, we have
M.((K, -wl + 11 1-00mp n. R/2m detl (1 [1+ +W]T+ K₂)
6
RV 21n /del(T + (1+ det((1 + w)
RV Int/eee(ee(1111 + w Kt)) + Lnn(1 +w) + 2ln(1/6)
R//2, wt 2 (
We choose a small w 2/r8 where Tá the termination iteration for the algorithm. Hence we get
v Maa(KK - - Rv 2( +1+ In(1/6)) (n((16))
Therefore, we have that with probability at least
6, 44 > 0, E x V we have
((((=))-=((t))(((())))))) (BCe)))))((BBBBBB) (B+Ry2(1) + +1
( 2kir
Rearrange the above equation, we get:
9;
of(z)) + +f(z)) /o(
(kg 24) B,(2,
where (2 2ÿ) is defined with C5 = (B+R 2 + 1 +n ln(1/)))) According to Definition C.I. (z 2z) is a good choice of gap indices.
Proof of Theorem 4.1. Combining Lemma C.3 and Lemma C.2, we have that the output by GPGapE STA E S with probability at least
C.2 PROOF FOR THEOREM 4.2
We need the following results from the existing work (Réda al., 2021):
Lemma C.4. (Réda al., 2021, Lemma 4) In Algorithm 1, for any selection rule, event
E == O (G(zi, 2y) (-B,(zz; 22), Be(2, 2y))), with the form of B, 2z) (.(z,,
iJEN
Wr(zi, for. all t > 0, (,c,,, S min( max(Gr,, Go,) + 2 20,) 2,,),) + We(zh, Ze,) Lemma C.5. (Réda al., 2021, Lemma 6) Let T N x (0, 1) x N + R+ be a function that is nondecreasing in and I, is the set of pulled arms at time t. Let be event that for all t < Ts, 8 E 10, 3a, E I, the number of arm pulls (a,)) at time t for the arm a, satisfies Ne(a:) < T (ac; 6, 1). Then holds the event & that Ta T(u, 8) where
T(,, 8) inf E R 1+ Σ (a,
GEN
We need proof the following lemma first:
Lemma C.6. Vt. > 0, > f, Ne,s) S T (at, 8, t), where ot E N is the index of a queried point at time and (ar) is number of queries done for a, during time t, and
(" 6,t) 12C2, max(e, E Go
3
Proof. Since at the stopping iteration 73 we have
8 < (2 2b,) min(- max(Gr, G..)) + 3Wo( Reg). We( 22,))
22

---

Published as a conference paper at ICLR 2025
The inequality above is from Lemma C.4. Hence we have
max(e, 8 +
&GGb, Gas
s We( za.) - Caty of(()) of (zxa) 2hi (2ce Tbo
3 3
I ((C5,0((2a.)
(where at
max oe oz(=a))
aE(b,,))
= =, (et A1) - (
Coall(( (++A)=
C Il Nolos(E.DDtt)))..)
[ )l
<221/2
Cs. (Nr(ar)
Hence we have,
4XC%
Ne((e) <
max st )2
12C
T (a,,
max <+Gas
The last inequality is because À = 1 2/T6 S 3 (see the proof for Theorem 4.1).
Proof of Theorem 4.2. Combining Lemma C.5 and Lemma C.6, we get the result that
max(e, + Ga -
Ta E inf u>> 1 12 Σ
(10)
3
aEN
C.3 PROOF FOR PROPOSITION 4.3
Our proof relies on the following results:
Lemma C.7. (Srinivas et al., 2010, Theorem 5) Let C Rd be compact and convex, denote the dimension of 2 as d N. Assume that the kernel function satisfies V2, k(2, 1.
If k is the linear kernel function: 7 O log ().
If k is the RBF kernel function: 7/1 (llogt)
Lemma C.8. (Chatzigeorgiou, 2013, Theorem 1) The Lambert function W W-1(-e-x-1) for > 0
bounded follows
2 3
-1 -1 - x < < -1 /2r
Proof of Proposition 4.3, When le is the RBF kernel function, since 7/- = O(logt)at) according to Lemma C.7, can find and to such that when 2 to. % con We have:
C2 BB+Rv 1+
(B + 2(co Int)d-1 +
(m(0))))
23

---

Published as a conference paper at ICLR 2025
where recall that B is the upper bound for the norm of f and R is the parameter for the sub-Guu Gaussian. Denote M max (max(es, Stge)) 2-). From Equ. (10), we have:
max(E, Ga C )
< in R :u> 1 12
Σ
NEN
s Sinffu e R uu> 1+ 3, M}
2 Sinffu R :>> 1 + 12n B + Ry 2 ((000l + +n(11)5) M).
O(n(law)e+1)
We see that the right-hand side of the inequality in the brackets is (I 1). Therefore, there exists a c1 > 0 and a 4 > 0 such that when u 2 4, we have the right-hand side of the inequality in the brackets is larger than cin(In u d) Therefore,
have:
To f inf u E R u > cin(In 2)
(11)
= inf R+
(In > cnj
Let function h(u) u/(Inu) We have:
ah(u) In(u) (d (1
du
d d
Therefore, when < ed+1 h(u) is monotonically decreasing. When 2 ed+1 h(u)) is monotonically increasing. Since the upper bound the To is the minimum u such that h(u) ern (according to Equ. (11)). Therefore, we have I [r'] where h(r') cin and 7' > e+1 Consequently, have:
In(r')at1 = T In(r') = //((4)1) (cin)
Denote == 7=d((((++1) (monotonically increasing w.r.t. T'). We have:
In(7(d+1) = F/(cin)\((aH)
(d+ ln)) = =F/(cin) -F/(ci))/(att)) In()) (dd 1)((cn)) (((c(n)(((++1)) /(at1)
= eld) 1/(04)
Here, we introduce Lambert W function x = W(y), y xe. Let y = -1/c ---y=-1oe and x = = = we have that x' -- s.t. == =²' ///c. Therefore, we have that f -e22W-1//// where
C2 (d 1)(cm))/(d+1), Since - 11/2 S -1/e2 < 0 and according to (Chatzigeorgiou, 2013), W has two real-valued branch Wo and W_1 and Wo(x) 2 -1 this case. Therefore, W = Wo. we have F < -2 * (-1) = 62 In this case 7 (d++))) Therefore, 7' = ;d+1 O()). Consequently = O(n). If W W. according to Lemma C.8 where we let In(c2) 1, we have:
w--1/o2) -1 2((n((2)) 1) (In(c2) - -1).
Hence
==-coW(-1/o) <c2 02 2(1((2)))) 1) c2(1n(22) -1)
Therefore, we get 7 = In(e))) ((n1((4)) log(n)). Consequently, T' = 7d+1 (n logg*((())) (n)). Hence we have Ta Onn log ++1 (n)). Following the same proof technique, we have that when & is linear kernel, T5 On logn)
C.4 PROOF FOR PROPOSITION 4.5
We need proof the following result first:
24

---

Published as a conference paper at ICLR 2025
Lemma C.9. For ranked values (01 2 P2 2 Pm -m++1 2 2 Pn. each element yi is added with a number b, which satisfies |6;| I E' and hence results in vp = pp + by. Rank the new values (Pl)ee from high to low and denote the m-th ranked value as Po... We have that 1 Pm S e'.
Proof. Denote the In = fl..... m and denote I'm the indices of the top-m values among (p' where [Tm = m. Note that T might not be unique. Denote i' arg min s/. We consider the following situations
(a) If I m, we have that Pp 2 Pm. According to the definition of i', we have that Po... PPr by I Pm bm- Hence Po.m - im bm. We have that V'n. AFr + by 2 Pm + by. Hence, we have Po... .mmm 2 by. Consequently, we have that lipo.. Pm S max(Ibml. b..1) S c'.
(b) If > m, there exits I such that (o, + by I Sa... This is because intuitively i' N In is included in T and hence there exists at least an element in In will be excluded from In and to be included in N Inp such that [Tm = m. Hence s'.. - Pj 2 bj. Since we have that ypr < pm according to the definition, &' = for + by < pm + bp, Consequently, we have &' Pm < by. Finally, we get I ipm S max( 1b+l) (1bbb1b),,bbr1)) S E.
Therefore, in all cases, 1sp'... smml S s'.
Proof of Proposition 4.5. Denote sam (p) the m-th largest value among ((i()))ieN. Define the following value:
A
k=1
Denote I an (s, apprrooxinntoo to the top-m of (p)(N) where I is the index set with [Z] = m. Hence we have that with probability at least
(p;()) 2 Po. (p) Vj EI.
Since pp(p) = v. (p), we have that (r)( 2 Pom ee, which gives
( 2 & (p) P Vje
Since | S E', vk E {p....,.)) n) according the assumption, have
Ip: - -i(()) = 1
Σ
A
n2
k=p+1
1
A
k=
11 E
According to Lemma C.9 we have
1 (p) -mmm <
11 p
Hence, we get the following
2 n2 R-P
p5(()) 2 Voom (p) P 2 pm
n1 n-p- P
P Vjvjezz
Hence, with probability at least - 5
2(n p) P -e,veee n n
84 2 Pm
In other words, I is p(m-p) he, approximmttoo to the top-m of (PilieN. Equivalently, n
we have that an (- 2(n-p) e', approximation to the top-m of pi(p)e is also an (c, apprroxaxxiiiioonnnn of the top-m of (se)ie
p
n
25

---

Published as a conference paper at ICLR 2025
C.5 PROOF FOR EQu. (8)
Proof. We restate the efficiency, symmetry. and additivity axioms of SV from (Shapley et al., 1953; Roth, 1988):
Efficiency. The sum of SV equals the utility of the grand coalition, i.e., EiEN 9: = U(N).
Symmetry. (S (t)) = US U1),8 e N {i,j), we have yps 4p
Null player. US (1)) U(S), VS N {d), we have 9i O.
SV defined by Uz. If U(S) U,S,,,, C N, have Additivity. Denote si (1) 12 Σy
Since utility function defined in Equ. (7) can be rewritten as:
U(S) E U)(S),
2jEDv
(12)
U,(S)= = Dv (g(z)) M(Ds,e))
Therefore, according to the additivity of SV, we have si = E, vp!0) where pp SV defined by US) in Equ. (12).
Denote Di {z E Dv E Dx, p(g(Zz) g(2))) S Se).ie i.e. data points in the validation dataset that have at leat one data point from the training dataset Div that within e distance to them. this case we have (N)
b V22 Dy. Denote the set Dj f2x DN ((),))))))))))))))))))))(())(( I =}
where 2j E Dyy In this case since every 24 E Dv, 24 D we have U, U {b} (S According to null player,
= E Dv, 2k $ D/.- PR
(
(13)
While for 2k, 21 E D/. we have that (SU((()) (1)) VS S N [K. l}. and hence yp = ((())
for all 2k, 21 Dj (i.e., symmetry). We have that ΣXEN (/6 (N |Dv| (i.e., efficienty). Therefore we have:
( 1
Pk
DD'
Vzk E D'S
(14)
Combining Equ. (13) and Equ. (14), we have:
1 (((g(z)). ((t))
Mzj E D'y
(15)
Dvl
Similarly, for 2j & Dy,,, 2j E Dv, we have that U2(N) = and according to the efficiency and 0, vk E N. According the additivity, have that:
symmetry, have that 90k
(i)
1 (p(o(Z)) VK E N.
6 = Σ
Σ
Σ
12J1 Dvl
Dv
ZjED
EYED
C.6 PROOF FOR PROPOSITION A.2
Proof. Efficiency, According to the definition in Equ. (9), we have
(m)
Σ U(N)mm=
IEN
iESt.
Therefore efficiency holds.
26

---

according to the Published as a conference paper at ICLR 2025
Symmetry. According to the symmetry of (V) = ( N (i. f}. we have
P: = Py. According to the assumption that 91 2 92 2 ... 2 Pm > pm+1 2 pm+ 2 2 Pn. (m)
have that either i,j Sm i, & S in either case, we have (m) = Pj definition in Equ. (9).
Striet m-th desirability. According the strict desirability of SV (Maschler & Peleg, 1966), have that (3B E N \ {i,j), (B U (i}) > U(B U (i)) A (AC' E N (i.j). (BB.).BBBBBU U {it > (() = Pi Pi 19.. Therefore, we have that (3B N (BU
(DDA E (.
2 ((BU(i))) = Pm+1) = 4i Pm+11 According 2 Pm > Pm+1 Pm+2 2 2 Pnn we have S
to the assumption that 61 2 92
and j & S (since Pj pm++1) Therefore, po; ((N) > 0 (since U(N) > 0 according to the
assumption) and P) (mm) = 0 according to the definition Equ. (9). Hence vp > 9j p7
(m)
27


Reviews:
[{"review_id": "pLVBWncsFb", "reviewer": "Reviewer_7tcQ", "summary": "The authors consider the problem of identifying a small set of samples in a data set with high value for training.  Shapley value is used for measuring individual samples’ value, but is prohibitive to compute.  The authors propose that since only identifying the samples is necessary, not identifying their values, this problem can be viewed as a top-m multi-armed bandits problem to more efficiently solve it.  Furthermore, since training samples’ values may depend on rich features, similarity in (non-linear) feature space can be modeled using Gaussian processes.  The authors propose a top-m GP algorithm, including with a variant involving sampling rewards via computing Shapley values using small cardinality sets.  The authors also analyze regret and provide experiments.", "questions": "- Can you discuss what technical challenges there were for obtaining the high-probability guarantees and bounding query complexity, given prior work like Reda et al for the linear setting and past work on Gaussian process bandits?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The motivating problem of identifying valuable samples in large data sets is challenging but important\n- The problem of fixed confidence top-k Gaussian process bandits is interesting\n- The presentation overall is good – I found the paper to be well organized and written\n- The authors identified high-probability guarantees of their method and show for linear and RBF kernel functions nearly linear query complexity (in terms of # of samples)\n- The use of GPs (compared to linear) for feature mappings is good.\n- The authors include a number of experiments", "weaknesses": "### Major\n- I think the technical problem setting (top-m bandit) is poorly motivated for the domain problem (Shapley value). If you are only going to select $m\\ll N$ data points, why would you use Shapley value as the utility?  Shapley value is a fair allocation of joint/group value, which could be very different than what is achieved by groups of size $m$.  If it were easy to compute, I could see it potentially as a heuristic, but given the challenge in computing it, in some sense is it worth putting effort into using as a metric when it does not necessarily tell us how different groups of size $m$ will perform?\n    - for top $m$, wouldn’t we either care about the top m data points in terms of marginal value to the primary utility function $U$ over which Shapley value is to be computed, eg if $U$ (1) is the overall utility function then $U({x_i})$ if the data points could be used/sold individually, or their value as a set A of size $m$, $U(A)$.  It seems implicit in your set up that you are looking at the top $m$ in terms of an alternate utility function, namely the Shapley value, which depends on both the actual utility of interest $U$ and set of all data $N$, looking at arms whose individual Shapley values are the highest.\n\n### Minor\n- Lines 313-320 there is an argument that since individual data points tend to have diminishing value with larger data sets, one can sample smaller subsets S to get bounds; certainly if (a) that holds uniformly and (b) the computational complexity increases with cardinality of $S$, that seems smart.  But is that diminishing returns empirically true for most samples or for samples on average?  Eg in Figure 1 is that for randomly sampled points?  Did you also check if that holds for the top $m$ points too, esp if $m\\ll N$?  For instance, I don’t work in vision or NLP, but I could imagine that for some samples of rare classes, if there’s too few samples the ML model would not learn about those rare classes and those samples could have low Shapley value (not contributing to the learned common classes), but with larger $N$, those rare classes could be learned by the ML model leading to higher accuracy and subsequently higher Shapley value for those samples from rare classes.\n\n- Proposition 4.4, Figure 1, and discussion between\n    - Prop 4.4 statement includes an assumption $|\\Delta_i^\\ell| \\leq \\epsilon’, \\ \\forall \\ell \\in \\{p,\\dots,n\\}$; it would be better to have that assumption (as in a theorem environment as Assumption 4.4) and discussed in relation to lines 313-323. \n    - Figure 1 caption says “Diminish return of adding new data points to the dataset when the size of the dataset increases.” But the x-axes are $l$, the subset size $S$.  “adding new data points to the dataset” means going from $N$ data points to $N+10$ or $N+100$.  In the main text, it mentions both “adding new data” (line 314) and (lines 319-320) that $|\\Delta_i^l|$ is decreasing in $l$; both phenomena may happen and potentially be useful for speeding up methods.\n    -  The Prop 4.4 statement (at least per sample $i$) $|\\Delta_i^\\ell| \\leq \\epsilon’, \\ \\forall \\ell \\in \\{p,\\dots,n\\}$ seems to be combining both  “adding new data points to the dataset” and $|\\Delta_i^l|$ is decreasing in $l$, as it is bounding $|\\Delta_i^l|$ in an absolute sense seemingly implicit that for sufficiently large $N$, not only will $|\\Delta_i^l|$ be small (small enough one could use the bound as a surrogate $\\epsilon$ for the top-m threshold) but also that (N fixed) there will be a subset cardinality $l=p$ for which all larger cardinalities will not have a larger value.\n\n\n     – also $\\exists p \\in N$  should there be a $\\forall i\\in N$ there?  The conclusion involves bounding all $\\varphi_i$ for all $i\\in N$ \n\n\n\n### Very minor (Typos/etc.)\n- for subset $S$ cardinality, $\\ell$ can be easy to read as super/sub script than $l$\n- Figure 1 caption “Diminish return”\n- Figure 7 – the curves are quite crowded; hard to tell, but it might be a little easier to read if the curves are transparent", "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": "jphLqurX3a", "reviewer": "Reviewer_gPqR", "summary": "This paper studies the problem of identifying the top-m data points with the largest Shapley Value (SV), which can be viewed as a top-m best arm identification problem. The paper models the relationship between the data feature and the value as a Gaussian Process (GP) and proposes an algorithm called GPGapE. The algorithm uses GP to update the estimation statistics and then designs which arm to sample based on GapE, a popular top-m best arm identification algorithm. Theoretical analysis of the sample complexity and PAC guarantee is provided, and extensive numerical experiments are conducted to showcase the performance of GPGapE. Interestingly, the paper makes use of the diminishing returns of ML models to propose a simplification of GPGapE, which achieves even better empirical performance.", "questions": "1. For Theorem 4.1, Theorem 4.2, and Proposition 4.3, can we choose the same hyperparameter inputs to obtain all results simultaneously? Can we preset the inputs ahead of time or does it require tuning?\n\n2. The current algorithm requires storing all historical data feature-marginal contribution pairs. Could you provide some insights on whether this is theoretically necessary? or is there a more memory-efficient implementation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Formulation and Algorithm: This paper combines the GP with the top-m best arm identification. The proposed GPGapE algorithm is novel, and the studied top data values identification problem has practical value.\n\n2. Analysis: The sample complexity and the PAC guarantee are analyzed theoretically under the standard assumptions of both GP and top-m best arm identification. Extensive numerical experiments are provided to showcase the performance of the proposed algorithm\n\n3. Computation Efficiency: A simpler version of GPGapE is also studied to reduce the computational complexity, where the paper makes equivalence arguments that the performance of GPGapE can be achieved using the simpler version. The numerical experiments interestingly show that the simpler version achieves even better performance.", "weaknesses": "1. GP: This paper inherits the weaknesses of the GP literature, which requires strong assumptions that the studied function is in RKHS. And all theoretical results are based on it. It remains a little unclear to me for general data value modeling, why GP is a good approximation that can provide the significant improvement shown in the numerical section. Justifications should be more detailed.\n\n2. Sub-Gaussian: The authors also mentioned in the paper that some utility functions such as cross-entropy loss are not bounded, justifications on why sub-Gaussian noise is still a good assumption in this setting should be given and detailed.\n\n3. Presentation: The presentation of the paper could be improved, notations are used without illustration and are causing ambiguity, e.g., in Theorem 4.1, when choosing C_{\\delta,t}, what is B? the format of information gain \\gamma_t is not explained, and how do you know the random stopping time \\tau_\\delta ahead of time to set the parameter \\lambda in GP?", "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": "pYeTw9I0Z9", "reviewer": "Reviewer_kM2u", "summary": "This paper studies top-m Shapley value identification problem, formulated as top-m arm identification in multi-armed bandit. While traditional multi-armed bandit problems estimate arm values use reward feedback only, this paper utilizes data features and uses the Gaussian process to model the nonlinear mapping from data features to data values. The authors prove theoretically that the Gaussian process based top-m nonlinear bandit algorithm finds an $(\\epsilon, \\delta)$ approximation to the top-m data values. Extensive numerical experiments on three different tasks are provided to demonstrate the model performance.", "questions": "• What is the benefit of using GP instead of directly using neural networks or other dimension reduction methods?     \n    • What is the rate of diminishing return in Section 4.2 – is p here assumed to be of scale Cn (C is a constant)?\n\n——————————After Rebuttal—————————Thank you for your response. I’m surprised to see the GP significant improvement without the newest tricks. I don’t have further questions and I’ll keep my current score.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper improves on existing literature by removing the linearity constraint of arm feature and arm value mapping. Different aspects (correctness, stopping iteration and query complexity) of the theoretical analysis are carefully addressed and compared to the linear baseline. Computational costs are further reduced by querying marginal contributions only on small subsets. Extensive experiments are conduct to convince the reader that the method indeed outperforms existing methods.", "weaknesses": "Gaussian process is commonly known as computationally expensive when it comes to online updating. At each iteration t, new data points are decided to query and then GP is updated with the improved candidate set $J(t)$. It would be good to discuss what methods or tricks can be used to decrease the computational cost for this setting.", "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": "G5TmsJBMSo", "reviewer": "Reviewer_PSf4", "summary": "The paper proposes a bandit-based method for identifying the top-data from a dataset in terms of data values. The main contribution is the incorporation of data features, specifically a non-linear structure assumed via a Gaussian process. The proposed algorithm is shown to have a PAC guarantees and is validated through a set of experiments on different applications.", "questions": "Minor issue: It seems not all of the experiments include error bars? What is the confidence level?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is an interesting combination of Gaussian processes and data valuation problem. The proposed solution addresses the problem where the linearity assumption is impractical for some applications, which is important. The algorithm is analyzed within the common bandit framework for its correctness and stopping time. A good amount of comprehensive experiments are included to demonstrate the effectiveness.", "weaknesses": "- It is a bit misleading in Theorem 4.2 and Proposition 4.3 that the same notation $\\tau_\\delta$ is called stopping iteration and query complexity differently.\n- The query complexity / stopping time is lack of comparison with any prior works or lower bounds, making it a bit hard to evaluate the theoretical contribution.", "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)