acceptodds
Under review as a conference paper at ICLR 2027

Dataset Pruning from First Principles: A Label-Free Linear Programming Approach

Abstract

Dataset pruning reduces a large training set to a representative subset while preserving model performance. Existing geometry-based methods typically assume that nearby points in embedding space share similar properties. Rather than imposing this assumption, we derive geometric selection criteria by reformulating unbiased subset selection as a variance minimization problem. Unbiasedness ensures that unweighted subset averages recover full-dataset averages in expectation, including losses and gradients at fixed model parameters. Specifically, we characterize a family of unbiased subset selection algorithms as a high-dimensional polytope. In this context, minimizing the expected sampling variance is a linear objective. Differences in sampling variance, averaged over rigid motions, admit closed-form pairwise expressions. Because the polytope has high dimension, directly applying standard linear programming is impractical. We instead use these expressions to construct an efficient vertex walk that optimizes an approximation of the variance objective while preserving unbiasedness, yielding a method that requires neither labels nor model training during selection. Across CIFAR-10, MNIST, and CelebA benchmarks, our method matches or exceeds uniform sampling in mean test accuracy at every evaluated budget and outperforms competing geometric methods in several settings, particularly at small selection budgets. Beyond dataset pruning, the same framework reduces stochastic-gradient variance by increasing diversity within mini-batches while keeping the batch size unchanged.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
dataset pruning, coreset selection, unbiased sampling, variance reduction, linear programming

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_uaE4OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a training-free, label-free dataset pruning method that frames unbiased subset selection as optimizing an orientation-averaged variance surrogate over the polytope of unbiased kk-selections, using closed-form pairwise kernels on the sphere and torus and a swap-based vertex walk.

Critical strengths

The paper provides a theoretical framework connecting unbiased selection, convex polytope vertices, and orientation-averaged variance on the sphere/torus, replacing geometric heuristics with a derived objective.

Critical weaknesses

The inverse-distance surrogate v~X(x,y)=1/(∥x−y∥+0.01)\tilde{v}_{\mathcal{X}}(x,y)=1/(\|x-y\|+0.01) is motivated by kernel envelopes, but the paper does not prove that decreasing it decreases the true orientation-averaged variance.

Algorithm 1 precomputes all pairwise scores at O(∣T∣2)O(|\mathcal{T}|^2) cost, which is prohibitive for large datasets (e.g., ImageNet).

The paper benchmarks against herding, kk-center greedy, and uniform sampling, but does not compare against other recent training-free, label-free methods.

The paper argues that biased selections can drive accuracy below uniform sampling under class imbalance, but does not test this claim empirically. All experiments use relatively balanced datasets (CIFAR-10, MNIST, CelebA, IMDb), leaving the class-imbalance motivation unvalidated.

Questions for authors

The models tested are relatively small and old (ResNet, VAE, and MLP). It is not clear whether the finding holds for large-scale modern LLMs/VLMs, for which the scale of the training data is crucial. Can you apply the method to GPT-style models?

1 comment

We thank the reviewer for the comments and for recognizing that the paper replaces geometric heuristics with a derived objective. We address each weakness and the question below.

W1. The inverse-distance surrogate is not proven to decrease the true variance. The surrogate has an upper-bound interpretation rather than being the exact orientation-averaged variance objective. Over the bounded distance range, inverse distance can be positively rescaled and shifted to bound a decreasing envelope without changing the optimization. Choosing the smallest such shift gives a nontrivial bound, whose minimum lies below the envelope's maximum. This does not guarantee that decreasing the surrogate decreases the true orientation-averaged variance. We have clarified this interpretation and its limitation in Appendix A.2, referenced from Section 4.

To examine the practical relationship with gradient variance, we have added an experiment comparing 18 partitions along three optimization paths on 2,048 CelebA images, with ResNet-18 fixed at initialization and batch size 128. Lower inverse-distance scores generally correspond to lower gradient variance (Pearson r=0.93r=0.93), with final variances 14.2–22.5% below their random-start values, although the reductions are not monotone. Section 6.2 and Figure 5 report this diagnostic, which provides empirical support rather than a monotonicity guarantee.

W2. Quadratic cost of Algorithm 1. For large datasets, we provide the fast variant in Section 5, which avoids storing pairwise scores by using binary embeddings and per-bucket bit counts. Excluding encoding, its assignment cost is O(mNb∣T∣)O(mN_b\lvert\mathcal{T}\rvert), linear in dataset size for a fixed selection fraction and number of bits. The runtime benchmark records 153.1 seconds for 222≈4.22^{22}\approx4.2 million 4096-dimensional embeddings on one GPU (Figure 4). By streaming inputs and outputs in fixed-size chunks, the fast variant can also keep GPU working memory independent of dataset size at a fixed selection fraction (Appendix B.4). We also use this variant in the new experiment on 3.84 million reviews, obtaining significantly lower Qwen3-0.6B gradient variance than uniformly random mini-batches of the same size (Section 6.2, Table 5 of the revised manuscript).

W3. Other training-free, label-free baselines. We selected herding and kk-center greedy because they are the two methods covered in the training-free, geometry-based category of Moser et al. (2026, Section III-B), alongside uniform sampling as a reference baseline. Across the four pruning benchmarks, our evaluation comprises 13,000 selection-and-training runs. Comparisons with additional methods would exceed our computational budget. We have added this baseline-selection rationale to the introduction.

W4. The class-imbalance motivation is not tested. We have reworded the motivation in Section 2 to state that geometry-based methods can perform worse than uniform sampling even on balanced datasets. The revised text points to our CIFAR-10 and MNIST results (Table 1), which directly illustrate this behavior, rather than invoking class imbalance.

Q. Large modern models. We have added an experiment with Qwen3-0.6B, a modern autoregressive language model, on 3.84 million reviews. At fixed model weights, our fast variant reduces gradient variance relative to uniformly random mini-batches of the same size by 7.2% with pretrained weights and 1.9% at random initialization. Both reductions are statistically significant (Table 5 of the revised manuscript). The experiment is described in Section 6.2 of the revised manuscript.

We thank the reviewer for encouraging us to clarify the theoretical connection and extend the evaluation to larger datasets and modern language models.

Reviewer_4dJKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes an unbiased dataset pruning method based on convex polytope theory. The authors model the subset selection algorithm as a probability distribution on a probability simplex and, under the assumption of "no preferred orientation," characterize the set of unbiased selection algorithms as a high-dimensional polytope. They then formulate the problem of minimizing sampling variance as a linear program over this polytope and solve it using an efficient vertex walk algorithm. Compared to traditional geometric methods such as k-center greedy and herding, this method has rigorous unbiasedness guarantees and can minimize the variance of a single implementation while maintaining unbiasedness, so that repeatedly running the method yields more stable subsets. In addition, the selection process of this method requires neither labels nor model training (referring to the selection step itself). Experimental results on MNIST, CelebA, and CIFAR-10 show that its performance is slightly better than uniform sampling. The method can also be extended to the mini-batch construction scenario, reducing gradient variance while maintaining unbiased gradient estimates.

Critical strengths

First, it proposes an unbiased variance-minimizing sampling method that outperforms uniform sampling, with mathematically rigorous unbiasedness guarantees for subset means, while minimizing variance to yield theoretically more stable subsets across multiple runs.

Second, the selection process does not use a trained model or additional labels, avoiding the high cost associated with training signals, which makes it applicable to scenarios where labels are difficult to obtain or where training a downstream model is not feasible, giving it a broad range of applicability.

Third, the theoretical derivation in this paper is elegant — through the technique of averaging over orientations, it naturally transforms variance differences into pairwise geometric functions of selected points without depending on unknown downstream functions, thereby directly constructing optimization objectives that depend only on the geometry of the data.

Critical weaknesses
  1. Some of the author's terminology may need further elaboration and clarification. While the reviewer is not entirely certain about this principle, the authors' "principle of no preferred orientation" — is it actually implicit in, or equivalent to, the isotropy assumption in random field modeling? Or, for the method of averaging over rigid motions, would "invariance under the action of a group" be more accurate? Or does choosing this "principle of no preferred orientation" assume that the data distribution has a symmetry assumption, i.e., that data is roughly uniform in all directions? Or does it not require the data distribution to satisfy any prior assumptions, and the phrase merely describes that the proposed method has no preference for any orientation of the distribution?

  2. The authors emphasize large-scale training scenarios at the beginning, but are the datasets used actually small in scale? CIFAR-10 (50K), MNIST (60K), and IMDb (around 50K) are all relatively small datasets, and CelebA (about 200K) cannot be called large-scale either. Without validation on large-scale data, the paper's claim that the method is designed for "large-scale training" scenarios lacks sufficient justification. It is recommended to validate on at least one million-scale dataset, or to clearly specify the applicable scenario in the paper.

  3. On CIFAR-10, where most of the data pruning methods are evaluated, the authors have not compare with training-oriented methods (e.g., gradient norms, gradient matching, or bilevel formulations), making it difficult to comprehensively assess the method's competitiveness. I do understand that this work is an unbiased and training-free data pruning method, but the comparison, especially the performance comparison, is still the most important signal for all data pruning methods.

  4. The method should be evaluated through repeated sampling of small subsets, and the variance or range of each method's metrics should be reported, rather than only reporting gradient variance. Only then can the core selling point of this paper — "unbiased + low variance" — be directly demonstrated.

  5. The authors emphasize that the method is training-free and label-free. However, the embeddings used are obtained from pre-trained models (ResNet-18, VAE, Qwen3-Embedding-8B), and the computational cost of these pre-training processes cannot be ignored. It is recommended that the paper honestly clarify "the selection process is training-free/label-free," avoiding giving readers the impression of "zero additional cost."

Questions for authors

Please refer to the Critical Weaknesses

2 comments

We thank the reviewer for the detailed summary and for finding the theoretical derivation elegant. We answer each weakness below.

W1. The principle of no preferred orientation. The principle of no preferred orientation defines our objective for unbiased subset selection. For a fixed dataset T\mathcal{T} and downstream function ff, the variance of a subset estimate depends on how ff is oriented relative to the data. Without information about this alignment, we give equal weight to all orientations and seek an unbiased sampling distribution that minimizes the orientation-averaged variance. Since the exact objective depends on the unknown function ff, we instead optimize a surrogate corresponding to an upper bound. The first paragraph of Section 4 explains this interpretation and specifies the transformations used on the sphere and torus.

No symmetry or uniformity of the data distribution is required: the absence of a preferred orientation concerns our objective, not the data. On the sphere, averaging over the rotation group can equivalently be viewed as inducing an isotropic random field by randomly rotating ff. However, we do not assume that the actual downstream function is isotropic. The group-action interpretation is therefore appropriate there. On the torus, we use the rotation, translation, and wrapping construction specified in Theorem A.1; these transformations do not form a group under composition.

W2. Scale. To extend our evaluation beyond the smaller pruning benchmarks, we have added a mini-batch variance experiment on 3.84 million Amazon Reviews 2023 Video Games reviews using Qwen3-0.6B at fixed model weights. Compared with uniformly random mini-batches of the same size, our fast variant reduces gradient variance by 7.2% with pretrained weights and 1.9% at random initialization. Both reductions are statistically significant: the 95% intervals for the variance ratios lie entirely below one (Table 5 of the revised manuscript). The experiment is included in Section 6.2 of the revised manuscript.

W3. Comparison with training-oriented methods. We share the reviewer's concern about placing our results within the existing literature. On CIFAR-10 and MNIST, we used the hyperparameters of the DeepCore benchmark (Guo et al., 2022), which implements and reports the training-oriented methods mentioned by the reviewer (gradient norms, gradient matching, bilevel formulations). Our experimental setting is therefore closely aligned with DeepCore's CIFAR-10 benchmark, except that we do not enforce class-balanced quotas because doing so requires labels. The introduction motivates our use of DeepCore, while Section 6.1 and Appendix B.1 describe the protocol and explicitly state that selection does not use class-balanced quotas.

W4. Variance across repeated selections. The variance studied in our framework is that of a subset estimate of a fixed quantity, such as a gradient at fixed model parameters (Sections 3.2 and 4 of the manuscript). Our mini-batch experiments evaluate precisely this variability across sampled subsets. On CelebA, we compare random and optimized partitions at fixed model parameters and report gradient-variance estimates with confidence intervals across 256 paired runs (Section 6.2, Table 4).

We have added a new experiment tracking gradient variance over 18 partitions along three vertex-walk trajectories on 2,048 CelebA images, with ResNet-18 fixed at initialization and batch size 128. Variance shows an overall downward trend as the vertex walk proceeds, ending 14.2–22.5% below the random-start values, although reductions are not monotone. Section 6.2 and Figure 5 of the revised manuscript present these trajectories.

W5. Cost of the pretrained embeddings. Training-free and label-free describe the selection step given the embeddings, not their construction. Obtaining embeddings can require substantial computation, including training and feature extraction; using a pretrained model does not eliminate this cost. Section 6.1 and Appendix B already describe how the embeddings are obtained, including supervised training for CIFAR-10 and MNIST. We have now made the scope explicit in the introduction and clarified in Section 6.1 that these experiments evaluate label-free selection, not a fully label-free pipeline.

We thank the reviewer for prompting clearer explanations of orientation averaging, the scope of label-free selection, and large-scale applicability.

Reviewer_4dJKOpenReview ↗

response to authors

I appreciate the authors' effort during this phase. Although W1 and W4 are solved, some problems (like W3, W5) still remains and may need further exploration and experiments. I think the author could find a real world senario where those SOTA and polular training methods cost a lot of computation to complete the whole selection procedure but the proposed method can meet the cost budget and achieve a decent result. I decide to keep my score at 2 unless more large scale and solid evidence or results are released.

Reviewer_WuncOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies dataset pruning by selecting small, unweighted subsets while keeping the estimates unbiased. The authors provide a theoretical analysis of selection strategies and propose a method that divides data into balanced groups and randomly selects one. They also introduce a faster version using binary embeddings. Experiments on four datasets and CelebA evaluate the effectiveness of the approach.

Critical strengths
  • Clear theoretical motivation: The paper connects unbiased selection with variance reduction, supported by well-presented theoretical results.

  • Useful unbiasedness property: The selected subsets better preserve the original data distribution and avoid class imbalance (Figure 1).

  • Good scalability: The faster variant processes 4 million high-dimensional embeddings in 153 seconds without losing accuracy.

Critical weaknesses
  • Limited improvements over random sampling: The gains over uniform sampling are generally small and mostly within the confidence intervals, with only one clear improvement on MNIST. Other methods also perform better in several settings. Interestingly, the fast variant performs similarly to the full method, raising questions about the importance of the proposed optimization.

  • Gap between theory and implementation: The proposed method uses an inverse-distance heuristic rather than the exact objective derived in the theory. There are no experiments comparing alternative objectives or optimization settings, making it unclear how much the theoretical analysis contributes to the practical results.

Questions for authors
  • Could the authors report final-epoch results, or validation-selected results if available, for Tables 1–3? Confidence intervals for improvements over uniform sampling would also help clarify whether the small-budget gains remain without selecting the best test epoch.

  • Could the authors examine whether reducing the inverse-distance score also reduces gradient variance across partitions, using an existing Table 4 checkpoint? Even a small analysis would help justify the proposed objective.

  • The paper claims to be label-free, but the embeddings for CIFAR-10 and MNIST come from models trained on the full labeled datasets. So, as I understand it, only CelebA and IMDb are fully label-free. It would be good to clarify this.

2 comments

We thank the reviewer for the positive assessment of our theoretical motivation, the unbiasedness property, and the scalability of the fast variant, and for the concrete suggestions.

W1. Limited improvements over random sampling. Following the reviewer's suggestion in Q1, we assess significance using unrounded statistics and unadjusted 95% Wald confidence intervals for the difference Ours −- Uniform. The improvement is significant in 14 of 18 settings, and no interval lies entirely below zero. Other methods do not achieve this consistency, and in practice using these alternatives carries a real risk of reducing accuracy. We have added the accuracy significance comparison to Section 6.1 of the revised manuscript.

In a separate large-scale experiment, our fast variant reduces Qwen3-0.6B's gradient variance relative to uniformly random mini-batches of the same size by 7.2% with pretrained weights and 1.9% at random initialization, on a pool of 3.84 million reviews. Both reductions are statistically significant (Table 5 of the revised manuscript).

W2. Gap between theory and implementation. The reviewer raises an important concern: how do the surrogate objectives fit into the theory, given that they differ from the exact envelopes? We have added the explanation below to Appendix A.2 of the revised manuscript and referenced it in Section 4.

The surrogate objectives do not need to match the exact envelopes: they can instead minimize nontrivial upper bounds on them. Both inverse distance (full variant) and negative Hamming distance (fast variant) can be interpreted this way after a positive rescaling and a shift, neither of which changes the optimization. Here, nontrivial means that the bound's minimum is strictly below the envelope's maximum. For the fast variant, this interpretation applies in the binary geometry; encoding remains an approximation to the original embedding geometry.

The envelopes decrease with distance, on the torus and on the sphere for positive inner products. Over the bounded range of pairwise distances, a continuous, strictly decreasing score can be shifted to lie above the envelope. Choosing the smallest such shift makes the bound touch the envelope, ensuring that its minimum lies below the envelope's maximum. This justifies the surrogate as an upper-bound objective. We examine its empirical relationship with gradient variance in Q2 below.

Q1. Final-epoch results. We did not retain final-epoch checkpoints for the 7,500 CIFAR-10 and MNIST selection-and-training runs, so we cannot reevaluate those models at the final epoch. However, we address the statistical comparison with uniform sampling in W1.

Q2. Does reducing the inverse-distance score reduce gradient variance? We compared 18 partitions along three vertex-walk trajectories on 2,048 CelebA images, with ResNet-18 fixed at initialization and batch size 128. Gradient variance shows an overall downward trend as the vertex walk proceeds, ending 14.2–22.5% below the random-start values. We have added this analysis to Section 6.2, Figure 5 of the revised manuscript.

Q3. Label-free claim on CIFAR-10 and MNIST. Yes, your observation is correct. The CIFAR-10 and MNIST embeddings come from models trained with labels. Here we followed the protocol of DeepCore (Guo et al., 2022), a widely adopted dataset-pruning benchmark, for two reasons. First, a recognized benchmark with its standard settings shows that our experimental choices are not tailored to our method. Second, DeepCore found that uniform random selection remains a strong baseline that competing methods do not consistently outperform, so it is a demanding setting for the comparison with uniform. However, as the reviewer pointed out, these experiments are not completely label-free, and the selection rule itself is the only label-free part (see Appendix B).

Our other experiments are fully label-free, on text and images: Qwen3-Embedding-8B embeddings for IMDb, a variational autoencoder for CelebA, and the new experiment on 3.84M Amazon Reviews 2023 Video Games reviews. Section 6.1 and Appendix B already describe the supervised embedding construction and the motivation for following DeepCore. We have now made the scope explicit in the introduction and clarified in Section 6.1 that these experiments evaluate label-free selection, not a fully label-free pipeline.

We thank the reviewer for the suggestions on statistical comparisons and the surrogate–variance relationship, which helped strengthen our evaluation.

I appreciate the authors’ response and additional analyses. The significance analysis and the consistency relative to uniform sampling are convincing. However, since unbiased selection cannot fall far below uniform sampling by construction, the gains remain below one point in 17 of 18 settings, which in my view limits the practical contribution.

I also noticed that most of the Ours and Ours (fast) entries in Tables 1 and 2 changed in the revision. For example, CIFAR-10 at 0.005 (Ours) went from 31.30 to 31.50, MNIST at 0.005 (Ours) from 88.44 to 88.19, and CIFAR-10 at 0.05 (Ours (fast)) from 63.63 to 63.07, which is now slightly below Uniform (63.22). If the selection-and-training runs were repeated, final-epoch accuracy could likely have been recorded in those same runs, which would address my earlier question about best-epoch test selection.

Given these points, I believe the work does not yet meet the bar for ICLR, and I will keep my score at 2.

Comments on the paper

1 comment

We thank the reviewers for highlighting the theoretical formulation, the unbiasedness guarantees, and the scalability of the fast variant. Their main concerns involve the connection between the theory and practical surrogates, the scope and scale of the empirical evaluation, and the distinction between label-free, training-free selection and embedding construction. Below, we summarize the new experiments and manuscript revisions addressing these concerns.

Million-scale evaluation with a modern language model. We added a gradient-variance experiment using Qwen3-0.6B on 3.84 million Amazon Reviews 2023 Video Games reviews. At fixed model weights and batch size, our fast variant reduces gradient variance relative to uniformly random mini-batches by 7.2% with pretrained weights and 1.9% at random initialization. Both reductions are statistically significant (Table 5 of the revised manuscript).

Gradient variance during the vertex walk. We added an experiment tracking gradient variance along three vertex-walk trajectories on 2,048 CelebA images, with ResNet-18 fixed at initialization and batch size 128. Variance shows an overall downward trend as the vertex walk proceeds, ending 14.2–22.5% below the random-start values. Section 6.2 and Figure 5 present these trajectories.

Clarifying gains over uniform selection. Using 95% Wald confidence intervals for Ours −- Uniform, improvements are significant in 14 of 18 settings, with no interval entirely below zero. Section 6.1 now reports this comparison.

Scope and theoretical connection. Appendix A.2, referenced in Section 4, now explains how our theory supports surrogate objectives that penalize nearby points. The introduction and Section 6.1 now explicitly distinguish label-free, training-free selection from embedding construction, which may require labels and training. The introduction also explains our baseline choices, and Appendix B.4 describes the fast variant's streaming memory requirements.

We also corrected random remainder handling and final-partition sampling, reran the affected CIFAR-10, MNIST, and CelebA settings, and updated the reported results. The updated results preserve the finding that Ours exceeds uniform selection in mean accuracy at every evaluated budget.

We appreciate the reviewers' careful reading and constructive feedback, which helped us improve both the presentation and the empirical evaluation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.