Sensitivity Sampling for Coreset-Based Data Selection

We would like to stress that we focus on the regime where we can only make, say, k queries to the model to obtain the loss / gradient / margin scores of a subset of k elements, before sampling the rest. It seems that there is very little work in this mixed regime which provides a limited amount of information from the model. Most prior work either uses very indirect model information (updated embeddings like [1], no use of margin or loss scores), or model information for all the input elements (such as margin scores). Our idea was to provide comparison with the two other extreme methods (indirect information vs information for all elements). It seems that none of the other methods would provide comparison in the mixed model.

Weakness 3.a: Indeed, the assumption we use is that the loss is Holder-continuous w.r.t the embeddings of the points, thank you very much for catching this. If the loss is Holder-continuous in the sample space, then we do not even need to use the embedding and the pre-trained model, and directly cluster in the sample space. However, this assumption looks much stronger than the Holder continuity in the embedding space.

Previous work such as Sener and Savarese also require embeddings.

Note that in many cases, pre-computed embeddings are already provided for the input data.

We believe that since it works for these (as shown in our experiments), then this approach can also work more broadly. Indeed, in many cases, one can obtain generic embeddings that would be good enough. One may for example think of BERT embeddings for text applications. Of course the model embeddings could be more refined but elements that are similar under generic embeddings such as BERT should hopefully be similar in the model embeddings too.

We ran experiments on the data and the Lipschitz constant for MNIST is 0.02. We are computing it for the other datasets and will add this to the draft. We note that assuming Lipschitzness of the loss function is a common assumption, done e.g. by Sener and Savarese. Since Hölder-continuous for z=1 is equivalent to Lipschitz continuous, our assumption is weaker than that.

The expectation of $X_i$ is indeed $\sum \ell(e) / s$, but we apply Bernstein’s inequality to $\sum_{i=1}^s X_i$, whose expected value is therefore $\sum \ell(e)$ as desired. We apologize for the confusion

We would like to mention that previous work that tackle large input data, such as for example the work of Citovsky, DeSalvo, Gentile, Karydas, Rajagopalan, Rostamizadeh, Kumar (Batch Active Learning at Scale) required to compute the margin scores of all the data element. Similarly previous work on active regression all required leverage score computations which are slower and less accurate on some datasets.

We have no way of enforcing it. We postulate that it holds. We are conducting experiments that we will add to the current paper as soon as the results are available. We note that assuming Lipschitzness of the loss function is a common assumption, done e.g. by Sener and Savarese. Since Hölder-continuous for z=1 is equivalent to Lipschitz continuous, our assumption is weaker than that. We ran experiments on the data and the Lipschitz constant for MNIST is 0.02, we are running it on the other datasets and will update the draft.

We have run some experiments to check whether the assumption holds in practice. For the gas sensor dataset:

$||a_i||_2 \leq 300$ for all i's and $\leq 15$ for 90% of i's

$|b_i| \leq 5$ for all i's and $\leq 0.9$ for 90% of i's

$|b_i - b_{​N(i)}| / ||a_i - a_{​N(i)}||_2 \leq 0.87$ for all i and $\le 0.2$ for 90% of i's.

Thus the Lipschitzness condition (Assumption 10) holds.

Yes, that’s right, if we use the $k$-median objective (i.e.: $(k,z)$-clustering with $z=1$), the approach will indeed be more robust against outliers. Thanks a lot for the remark, we will incorporate it into the draft. In particular, the $k$-median objective is similar to the median, which is robust to corruption of 50% of the dataset ; while $k$-means is much more sensitive to outliers, and $k$-center even worse. Note that the result of Sener and Savarese uses the k-center objective and this may be a reason why we are also able to improve upon their work.

The initial model using the uniformly sampled points was trained for 10 epochs. Similarly we will update the manuscript as soon as possible with the running time comparisons. As for the question regarding independent runs in Figure 4, that’s exactly right: We run each sampling algorithm 100 times independently, each time sampling different points. We will make this clearer in the new version.

Regarding the runtimes, we will try to run some runtime experiments during the rebuttal period to collect runtimes and update the manuscript as soon as possible.

That’s correct, we will clarify this. Replacing the centers by their closest input point induces a factor $2^z$ loss in the $(k,z)$-clustering cost.

We have done those runtime experiments on artificial matrices (with i.i.d normal entries), see section C of the appendix. On those examples, the speed-up using our algorithm is roughly a factor 2 compared to computing leverage scores.

We would be happy to answer any further question.

"Given these questions, their overall contribution appears reasonable in terms of the empirical study of their proposed algorithm, but the theoretical contribution is lacking."

We would like to point out that our contribution also consists in showing that one can remove several assumptions made by Sener and Savarese in their theoretical framework. The framework we focus on is much crisper, only relying on the Holder-continuity (which we show holds in practice) and so we can obtain sampling algorithms that are both simpler and achieve better results in practice. Thus, we believe that the new theoretical framework we provide is a new framework for developing algorithms with theoretical guarantees.

We apologize for the general lack of clarity, we are working on an improved version that we will upload as soon as possible. To answer your questions, $\mathcal{A}(e)$ is defined in algorithm 1 as $\text{argmin}_{a \in \mathcal{A}} ||a-e||$, the closest center to e in $\mathcal{A}$. We never use the notation $\mathcal{A}(\mathcal{D})$, which would indeed be conflicting with the previous one. Algorithm 1 is referred to in the proof of Theorem 6, Algorithm 2 in Theorem 10 but we agree that it is good to refer to it more explicitly.

This is a very fair point. We ran experiments on the data and the Lipschitz constant for MNIST is 0.02 and so indeed bounded. We will also provide plots to evaluate the Lipschitz constants on the remaining datasets we used in the updated version of our paper. To be clear, our algorithm does use the Holder-continuity property in the definition of the sampling probabilities (it is the lambda parameter in Algorithm 1).

The runtime of our method is better than the runtime of computing leverage score in theory for high-dimensional input: computing a $k$-median solution can be done in time essentially nnz $+ n/\epsilon^2$, while the state-of-the-art methods for computing the leverage scores require nnz + $d^\omega$ (where nnz is the number of non zero elements in the description of the input, and $\omega$ is the exponent of matrix multiplication). We will soon provide an experimental evaluation to complete the theoretical analysis.

We apologize for those errors, and will soon post an updated version.

We would like to note that the use of our approach is not only faster empirically but also theoretically for high-dimensional inputs: computing a $k$-median solution can be done in time essentially nnz $+ n/\epsilon^2$, while the state-of-the-art methods for computing the leverage scores require nnz + $d^\omega$ (where nnz is the number of non zero elements in the description of the input, and $\omega$ is the exponent of matrix multiplication). Regarding empirical results, we will upload a runtime comparison as soon as possible.

As mentioned in the answer to remark 1, our contribution is mainly in the idea of using the $(k,z)$-clustering scores as a sampling distribution, that serves as proxy distribution to the loss distribution.

The idea is that this error nicely scales with the number of centers chosen, as k grows, the error vanishes (when k=n it is 0). Moreover, the magnitude of this error relative to the actual loss depends on the Lipshitz constant, whenever this constant is of bounded magnitude, the error is bounded compared to the loss.

We ran further experiments and the Lipshitz constant for the MNIST dataset is 0.02. This implies that for this dataset, the additive term is not large compared to the total loss.

More importantly, we demonstrate in practice that this approximation provides competitive results, coming close to very efficient methods (such as margin score) at a much cheaper computational cost.

There is a drastic difference with the result of Sener and Savarese which lies in the fact that the approach considered there does not use any direct model information (such as loss, margin score, or gradient). The empirical success of methods such as margin or confidence sampling has shown that model-based data selection can achieve much higher quality results than model-agnostic selection. Our approach allows using model-based scores (e.g. loss) to improve selection quality, while maintaining the efficiency of coreset selection. As such, even in the era of foundation models and big datasets, our approach allows using a few model queries to obtain proxy estimates for margin, loss, or gradient that gives a better sampling procedure.

Our experimental results agree with this intuition, since our approach yields samples of significantly improved quality compared to Sener and Savarese [SS18]. Moreover, Sener and Savarese also makes such an assumption Since Hölder-continuous for z=1 is equivalent to Lipschitz continuous, our assumption is weaker than that.

I read the other reviews and your answers to the questions. I have improved my score slightly. However, I still feel the paper needs more clarity and novelty for acceptance.