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.
Figures & tables
Figure 1: Left: orientation averaging. The data and the selected subset stay fixed while the function rotates, which is equivalent to rotating the data. The three orientations are illustrative; the estimation error is averaged over all of them. Right: spatial distributions of points selected from a vortex-shaped candidate distribution over Australia, shown in an equal-area projection. The top and middle rows pool 100 and 2,000 selected points from 10,000 and 500 runs, respectively, giving one million selected points per panel; the bottom row shows the first 2,000-point run. KS denotes the pooled two-dimensional Kolmogorov–Smirnov discrepancy against a vortex reference sample (lower is better; not a p-value).
Figure 2: Left: the normalized Bessel factor as a function of the pairwise separation r . Right: the normalized Gegenbauer polynomial Pℓd+1(t) as a function of the inner product t , both for d=5 . Colors identify the frequency norm ∥j∥2 (left) or the degree ℓ (right), from 1 to 7; the constant mode is omitted. Dotted red curves show the envelope of each family, and arrows mark the regions of low correlation that motivate the surrogate.
CIFAR-10
Method / selected fraction
0.005
0.01
0.05
0.1
0.3
Herding
24.65 ± 0.30
30.63 ± 0.39
56.66 ± 0.48
74.76 ± 0.34
90.61 ± 0.07
Ours
31.30 ± 0.25
38.30 ± 0.28
63.84 ± 0.32
76.91 ± 0.26
90.59 ± 0.06
Ours (fast)
31.30 ± 0.28
38.20 ± 0.28
63.63 ± 0.41
76.48 ± 0.21
90.67 ± 0.05
Uniform
30.63 ± 0.54
38.20 ± 0.51
63.22 ± 0.69
76.35 ± 0.36
90.49 ± 0.11
k -center greedy
28.95 ± 0.27
34.93 ± 0.23
60.19 ± 0.51
75.73 ± 0.35
91.03 ± 0.07
Table 1: Test accuracy (%) on CIFAR-10 and MNIST.
Method / selected fraction
0.005
0.01
0.05
0.1
0.3
Herding
82.89 ± 0.04
85.04 ± 0.02
88.56 ± 0.01
89.52 ± 0.01
90.62 ± 0.00
Ours
82.65 ± 0.07
85.08 ± 0.03
88.64 ± 0.01
89.60 ± 0.01
90.66 ± 0.01
Ours (fast)
82.67 ± 0.06
85.02 ± 0.03
88.63 ± 0.01
89.58 ± 0.01
90.64 ± 0.01
Uniform
82.57 ± 0.07
84.95 ± 0.03
88.58 ± 0.02
89.57 ± 0.01
90.65 ± 0.01
k -center greedy
80.18 ± 0.03
81.80 ± 0.07
88.27 ± 0.01
89.46 ± 0.01
90.62 ± 0.00
Table 2: CelebA mean test attribute accuracy (%).
Table 5
Figure 3: Recorded runtime versus input size (linear axes). We select n/128 points from standard-normal, 4096-dimensional float32 embeddings on an NVIDIA GeForce RTX 5090. We use binary representations with 64 k bits.
Epoch
Random variance
Optimized variance
Reduction (%)
2
0.20397 ± 0.00901
0.17367 ± 0.00751
14.85
9
0.23544 ± 0.00827
0.20531 ± 0.00644
12.80
16
0.24042 ± 0.00839
0.21829 ± 0.00651
9.20
23
0.10832 ± 0.00475
0.10365 ± 0.00407
4.32
30
0.00800 ± 0.00018
0.00794 ± 0.00017
0.78
Table 5: Gradient variance of random and optimized mini-batches at fixed batch size.
The rapid growth of modern training datasets has significantly increased computational cost, motivating dataset pruning~(DP) methods which retain only a subset of informative samples to reduce training cost. Existing pruning criteria typically rely on either intrinsic signals that assess samples independently or extrinsic signals that promote diversity via pairwise relations. While effective in their own specific regimes, each captures only one aspect of sample utility and lacks robustness across different pruning ratios or data distribution. In this work, we present a unified graph-based DP framework. By modeling the dataset as a weighted graph, where node weights encode intrinsic value and edge weights encode extrinsic value, DP can be cast as a Maximum Weight Clique Problem (MWCP). Although MWCP is NP-hard, its structure admits a principled greedy solution based on sample-wise marginal gains. Under a few mild conditions, we further prove that this unified objective enjoys a formal approximation guarantee, which applies to a broad family of importance metrics and provides practical design guidelines. Extensive experiments show that our method outperforms existing DP methods while substantially reducing training cost, reducing training time by over 40% without sacrificing accuracy on ImageNet-1k with ResNet-50.
Dongyue Wu, Zilin Guo, Xiaoyu Li +4
State Key Laboratory of Multispectral Information Intelligent Processing Technology, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, China · Ant Group, Hangzhou, China
The performance of deep learning models is affected by not only data quantity but also data quality. Data pruning is a process by which practitioners can reduce the size of a dataset by only keeping the most important training data points, thereby achieving similar test set performance. We empirically investigate two popular data pruning methods under noisy and noiseless conditions and show that these methods fail in the presence of significant label noise. We highlight that the success of data pruning is distinctly affected by three factors: redundancy in the dataset, the presence of problematic samples, and interdependence between samples. We perform a detailed investigation on commonly used benchmark classification datasets and neural network architectures. We find that our observations are consistent across data distributions and training protocols.
Leon Freese, Marthinus W. Theunissen
Faculty of Engineering, North-West University, South Africa · Centre for Artificial Intelligence Research (CAIR), South Africa · National Institute for Theoretical and Computational Sciences (NITheCS), South Africa
Dataset pruning reduces the storage and training costs of deep learning by selecting an informative subset from a large dataset. However, most existing pruning methods require fully labeled data, which limits their applicability in realistic settings where unlabeled data are abundant and annotation is costly. Recent label-free pruning methods address this issue, but they rely on features from pretrained models to estimate example difficulty. This dependence can be unreliable when the target dataset differs substantially from the pretraining distribution. We propose SemiPrune, a label-efficient dataset pruning framework, using only a small randomly labeled subset, that uses semi-supervised learning to generate pseudo-labels for unlabeled data, allowing existing supervised pruning methods that require label information to be seamlessly applied to the resulting pseudo-labeled training pool. We then estimate example difficulty from pseudo-label-induced training dynamics and select a coreset. By learning directly from the target dataset, our method better captures the target distribution and provides more reliable signals for difficulty estimation and coreset selection. We validate our approach on domain-specific, image-corrupted, and long-tailed datasets, where it achieves state-of-the-art performance among label-free and label-efficient baselines, while also demonstrating competitive performance on standard benchmarks.