Efficient Top-m Data Values Identification for Data Selection

Authors: Xiaoqiang Lin, Xinyi Xu, See-Kiong Ng, Bryan Kian Hsiang Low
Primary area: interpretability and explainable AI
Keywords: data selection, data valuation, top-m arms identification

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.

Decision: accept (poster)
Reviewer scores: 5, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1730660037043

thread_type:
official_review

<thread_object>
creator: reviewer_psf4

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

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

questions:
Minor issue: It seems not all of the experiments include error bars? What is the confidence level?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730698441599

thread_type:
official_review

<thread_object>
creator: reviewer_km2u

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

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.

questions:
• What is the benefit of using GP instead of directly using neural networks or other dimension reduction methods?     
    • What is the rate of diminishing return in Section 4.2 – is p here assumed to be of scale Cn (C is a constant)?

——————————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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730741100899

thread_type:
official_review

<thread_object>
creator: reviewer_gpqr

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

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.

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

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

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

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

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?

2. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731023261632

thread_type:
official_review

<thread_object>
creator: reviewer_7tcq

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

strengths:
- The motivating problem of identifying valuable samples in large data sets is challenging but important
- The problem of fixed confidence top-k Gaussian process bandits is interesting
- The presentation overall is good – I found the paper to be well organized and written
- 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)
- The use of GPs (compared to linear) for feature mappings is good.
- The authors include a number of experiments

weaknesses:
### Major
- 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?
    - 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.

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

- Proposition 4.4, Figure 1, and discussion between
    - 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. 
    - 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.
    -  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.


     – 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$ 



### Very minor (Typos/etc.)
- for subset $S$ cardinality, $\ell$ can be easy to read as super/sub script than $l$
- Figure 1 caption “Diminish return”
- Figure 7 – the curves are quite crowded; hard to tell, but it might be a little easier to read if the curves are transparent

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733290013559

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the discussion during the rebuttal period

comment:
We sincerely appreciate the efforts of all our dedicated reviewers. The constructive feedback in the reviews significantly enhanced the quality of our paper. We are very grateful!

We are happy to know that most reviewers have acknowledged that their concerns were addressed during our discussion period. Please refer to the individual responses for detailed explanations, and we provide a summary of the discussion here:


- On the design choice of using GP [**Reviewer gPqR and Reviewer kM2u**]: We have provided both empirical and theoretical justification of why GP is a good choice in modeling data values, we have also discussed the advantage of GP over neural networks.

- On the improvement of memory and computational efficiency of GP [**Reviewer gPqR and Reviewer kM2u**]: We have discussed our implementation of GP to improve the computational efficiency and provided reference to these existing works on GP that can be directly used to improve the memory and computational efficiency of GP in our algorithm.

- On the diminishing return [**Reviewer 7tcQ and Reviewer kM2u**]: We have provided additional empirical verification of diminishing return for data points with top-$m$ data values and discussed its relationship with our theoretical results in our response for Reviewer 7tcQ. We have discussed the factors that affect the rate of diminishing of the return in the response for Reviewer kM2u.

- On the use of Shapley value for data selection and other applications [**Reviewer 7tcQ**]: We have provided justification (both theoretical and empirical verification from existing works) on the ubiquity and effectiveness of using Shapley value for data selection, noise data detection, and data debugging.

- On the technical challenges of the proof of our theoretical results [**Reviewer 7tcQ**]: We have pointed out the significant challenges that can not be directly solved from the proof of existing works and described our ways to tackle these challenges in our proof.

- On the assumption of sub-Gaussian [**Reviewer gPqR**]: We have provided additional discussions on why the sub-Gaussian holds for common utility functions used in data valuation even if the utility function is not bounded.

- On the choice of hyperparameters [**Reviewer gPqR**]: We have provided additional explanations on why all theoretical results hold with a single set of hyperparameters and how to choose $\lambda$ to achieve theoretical guarantee and empirical results.

- On the comparison of query complexity with existing baselines [**Reviewer PSf4**]: We have provided the complexity of approximating Shapley value (instead of finding top-$m$) directly using Monte-Carlo-based methods which serves as a peek at the theoretical improvement of query complexity of our method over existing baselines. We have also provided a discussion on the challenges of comparing the query complexity directly with existing baselines.


We are happy to see that most concerns mentioned above have been addressed which the reviewers have acknowledged in their response during the discussion period. We have updated our PDF to incorporate these useful suggestions. Again, we would like to extend our thanks to the reviewers for their constructive feedback and valuable insights.

Best wishes,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces the GPGapE algorithm, combining Gaussian Processes with top-m best arm identification. Theoretical analysis covers sample complexity and PAC guarantees. A simplified version of GPGapE is also explored, reducing computational complexity while achieving even better performance in numerical experiments. 

This paper addresses a relevant problem where the integration of Gaussian Processes (GP) with top-m best arm identification is a natural and effective approach. Both the theoretical analysis and experimental results are solid, providing a strong foundation for the proposed method. However, there is a minor concern regarding the setting of the GP parameter, which requires knowledge of an upper bound on the sample complexity to achieve theoretical guarantees. Introducing the idea of using diminishing returns to simplify the GPGapE algorithm is also novel.

Considering the above novelties, I recommend acceptance of the paper; please incorporate all the reviewer's feedback in the final version.