Data Pruning via Moving-one-Sample-out

1 Introduction

• Large datasets can strain computational and storage resources, and may contain redundant, irrelevant, or harmful samples.Data pruning seeks a smaller core set while maintaining model performance.Source: §1 · p. 1
• Importance-based pruning uses difficulty metrics, while other approaches select by coverage or diversity or by optimization.The introduction characterizes importance-based methods as the most effective and popular group.Source: §1 · p. 1
• Existing methods may mistake noisy samples and outliers for informative hard samples, while converged-surrogate approaches may miss importance at earlier training stages.These limitations motivate assessing sample importance across the training process.Source: §1 · p. 2
• MoSo scores samples by the change in optimal empirical risk when they are removed, with an efficient first-order approximator based on gradients across training stages.The method is intended to distinguish informative samples from harmful noise rather than relying only on sample difficulty.Source: §1 · p. 2
• MoSo significantly surpasses previous state-of-the-art methods, especially at high pruning ratios, across CIFAR-100, Tiny-ImageNet, and ImageNet-1K.The introduction also reports generalization to unseen networks and strong average performance under synthetic label noise.Source: §1 · p. 2

Pruning by importance criteria

• Difficulty-based importance scores can confuse noisy samples and outliers with useful hard examples; MoSo instead scores the change in optimal empirical risk after removal.Examples include EL2N, GraNd, Forgetting, Memorization, and Diverse Ensembles.Source: §2 · p. 2

Coverage or diversity driven methods

• Coverage and diversity methods select for data coverage or distribution balance, including greedy k-center [32], BADGE, CCS, and Moderate.Some diversity-driven methods can use an importance criterion such as EL2N as their selection basis.Source: §2 · p. 3

Optimization-based methods

• Optimization-based pruning includes gradient matching, bi-level optimization, and submodularity, but commonly uses only final-model information.The paper says this can favor samples influential late in training rather than across the full process.Source: §2 · p. 3

3.1 Background

• The setup formulates pruning as finding a representative subset of a training set drawn i.i.d. from an underlying distribution, given a pruning ratio and parameterized network.The SGD update uses the average cross-entropy loss on a mini-batch.Source: §3.1 · p. 3

3.2 Definition for Moving-one-Sample-out

• A sample’s MoSo score reflects how empirical risk on the remaining set changes when that sample is removed: useful samples tend to have positive scores, while harmful noisy samples can have negative scores.An unrepresentative sample is described as having a score near zero.Source: §3.2 · pp. 3–4

3.3 Gradient-based approximator

• The first-order approximator scores a sample by expected gradient alignment with the remaining training set across training iterations, reducing exact leave-one-out scoring from quadratic to linear complexity.Gradient consistency indicates that optimizing with the sample has a similar effect on remaining samples.Source: §3.3 · p. 4

3.4 Theoretical analysis of tightness and complexity

• The approximation has a theoretical error guarantee under stated Lipschitz-loss and bounded-gradient assumptions; error grows with training duration, gradient norm, and learning rate.The authors limit surrogate training to a small number of epochs in practice to control approximation error.Source: §3.4 · p. 4
• The approximator has O(Tn) complexity, and sampling a few training steps can reduce the computation below O(Tn).The exact score is described as quadratic in dataset size and training iterations.Source: §3.4 · p. 4, §3.3 · p. 4

3.5 Data Pruning with MoSo

• For data pruning, MoSo samples training steps to estimate scores, then removes the proportion of samples with the lowest scores specified by pruning ratio δ.The pipeline uses the approximated score from Eq. (4).Source: §3.5 · p. 5
• When multiple GPUs are available, the dataset can be partitioned into non-overlapping subsets for parallel scoring; the partition count is limited by available devices.The authors state that sufficiently large subsets approximately represent overall dataset statistics and reduce computation time by a factor of I.Source: §3.5 · p. 5

4.1 Main Results

• MoSo surpasses most baselines, especially at high pruning rates; it beats the state-of-the-art method on CIFAR-100 and Tiny-ImageNet and performs satisfactorily on ImageNet-1K.Some baselines, including EL2N on CIFAR-100, fall below random selection at high pruning rates, whereas MoSo does not.Source: Figure 1 · p. 6, §4.1 · p. 6
• At 80% pruning on CIFAR-100, class-wise accuracy before and after MoSo pruning correlates at Spearman 0.913 (P=0.0295), with no significant category-specific improvement or harm.Source: Figure 2 · p. 6, §4.1 · pp. 6–7
• MoSo generalizes from ResNet-50 scoring to SENet and EfficientNet-B0, and under 20% synthetic label noise performs comparably to Herding, trailing by less than 1% Top-1 accuracy.Source: Figure 3 · p. 7, §4.1 · p. 7

4.2 Computational Efficiency

• MoSo offers the best trade-off between computational requirements and performance, outperforming Moderate while remaining more efficient; OPT is significantly more time-consuming.The time comparison includes training the surrogate network; OPT's large-scale linear programming in scoring accounts for its higher time cost.Source: Figure 4 · p. 7, §4.2 · pp. 7–8

4.3 Further Study

• With training-dynamics awareness, MoSo outperforms the last-epoch gradient-norm variant across pruning rates on CIFAR-100.The comparison indicates that gradient norm from a converged network alone is insufficient for measuring sample importance.Source: Figure 5 · p. 8, §4.3 · p. 8
• As the time-step sampling rate decreases, mean coreset performance falls and variance rises, trading estimation efficiency against selection quality.The ablation uses CIFAR-100 with ResNet-50 at a 0.4 pruning ratio.Source: Figure 5 · p. 8, §4.3 · p. 8
• Partitioning the dataset reduces time overhead by a factor of I, and using more subsets can improve pruning performance.The table reports partitioning effects at a 0.2 pruning ratio; the bold setting is the one used in this work.Source: Table 1 · p. 8, §4.3 · p. 9
• Extending surrogate training from 50 to 200 epochs yields only a 0.82 Top-1 accuracy gain while quadrupling time.The authors relate this to approximation error increasing with training time T.Source: §4.3 · p. 9

• Table 2 examines surrogate-network training epochs and final data-pruning performance at a pruning ratio of 0.2.Source: Table 2 · p. 9
• MoSo measures sample importance by the change in optimal empirical risk after removing a sample, using an estimator with linear complexity and approximation-error guarantees.Source: §5 · p. 9
• The estimator incorporates training dynamics by considering gradient differences across epochs.Source: §5 · p. 9
• MoSo's usefulness is not guaranteed when noise dominates, and the paper evaluates it only on classification tasks.Source: §5 · p. 9
• MoSo may benefit data collection and data-efficient AI, reduce training workload and dataset storage costs, and pose risks if deployed for inhumane web-data monitoring.Source: §5 · p. 9