Source-linked AI summary
Dataset Pruning: Reducing Training Data by Examining Generalization Influence
Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, Ping Li
TL;DR
Large-scale training data impose substantial computational costs, while the contribution of individual examples to generalization remains difficult to assess efficiently. The paper introduces optimization-based dataset pruning using influence-based parameter-change estimates and constrained subset selection. It reports theoretically bounded generalization effects and practical savings, including pruning 40% of CIFAR-10 examples with a 1.3% test-accuracy decrease and halved convergence time.
Problem
The paper addresses how to reduce redundant training data while preserving model generalization and avoiding infeasible retraining over all subsets.
Method
The method estimates parameter changes from omitted examples with influence functions and selects the largest subset satisfying a constrained parameter-change criterion.
Results
40% of CIFAR-10 training examples are pruned, halving convergence time with only a 1.3% test accuracy decrease; empirical generalization behavior substantially matches theory.
Takeaways & Limitations
Dataset pruning reduces training data and improves training efficiency while maintaining model generalization within the proposed theoretical and empirical scope.
Takeaways & Limitations
The analysis assumes local network smoothness and includes an assumption that n2 is negligible relative to ϵ.
Abstract
from arXiv · showhide
The great success of deep learning heavily relies on increasingly larger training data, which comes at a price of huge computational and infrastructural costs. This poses crucial questions that, do all training data contribute to model's performance? How much does each individual training sample or a sub-training-set affect the model's generalization, and how to construct the smallest subset from the entire training data as a proxy training set without significantly sacrificing the model's performance? To answer these, we propose dataset pruning, an optimization-based sample selection method that can (1) examine the influence of removing a particular set of training samples on model's generalization ability with theoretical guarantee, and (2) construct the smallest subset of training data that yields strictly constrained generalization gap. The empirically observed generalization gap of dataset pruning is substantially consistent with our theoretical expectations. Furthermore, the proposed method prunes 40% training examples on the CIFAR-10 dataset, halves the convergence time with only 1.3% test accuracy decrease, which is superior to previous score-based sample selection methods.
1 INTRODUCTION
Deep learning’s data demands create major training and tuning costs, motivating dataset pruning to identify redundant examples while preserving generalization. The proposed optimization-based method combines theoretical guarantees with joint influence modeling and reports faster CIFAR-10 training with a small accuracy decrease.
- Deep learning’s reliance on increasingly large datasets creates substantial computational and infrastructural costs for training and parameter tuning.
- Evaluating every possible removed subset would require 2^n retrainings, making efficient generalization-influence estimation a central challenge.
- The optimization-based method uses influence functions to approximate parameter changes without retraining and accounts for the joint influence of collected samples.
- 40% of CIFAR-10 training examples are pruned, halving convergence time with only a 1.3% test accuracy decrease.
- Dataset pruning formulates subset selection under a generalization constraint rather than a fixed cardinality budget.
- Theoretical analysis bounds the generalization gap through a constrained parameter change, while experiments report effectiveness for training and architecture-search efficiency.
2 RELATED WORKS
Dataset pruning is distinguished from few-shot learning, data selection, and dataset distillation or condensation by its goal of removing original examples while retaining performance. Prior approaches variously select representative data or synthesize compact alternatives.
- Few-shot learning improves performance with limited data, whereas dataset pruning reduces training data while aiming to preserve performance.
- Data selection methods identify representative samples for clustering, continual learning, or active learning.
- Dataset distillation and condensation synthesize small informative datasets as alternatives to the original large dataset.
- Influence-function research studies how removing or reweighting training points changes model parameters, robustness, or related outcomes.
3 PROBLEM DEFINITION
Dataset pruning seeks the largest redundant subset whose removal minimally changes learned-model performance. The formulation uses parameter proximity as the operational route to controlling the generalization gap.
- Dataset pruning identifies and removes as many redundant samples as possible from a dataset D to reduce training cost.
- The pruned and unpruned models should have very similar test performance.
- Because neural networks are locally smooth, keeping the post-pruning parameters close to the original parameters is used to target similar generalization performance.
- An ϵ-redundant subset is defined through a sufficiently small parameter change, and dataset pruning seeks the largest such subset.
4 METHOD
The method estimates the influence of removing training examples with influence functions, aggregates those effects for subsets, and solves a discrete optimization problem. It maximizes the removable subset subject to a parameter-change or generalization constraint without exhaustive retraining.
- 4 METHOD: Exhaustive evaluation of all subsets would require 2^n retrainings, so the method approximates subset influence without retraining.
- 4.1 PARAMETER INFLUENCE ESTIMATION: For one example, the method estimates the parameter change from omission instead of retraining n times, which is impractical for large datasets.
- 4.1 PARAMETER INFLUENCE ESTIMATION: Influence functions provide a fast approximation of parameter change caused by weighting an example and, equivalently, removing it under the described perturbation.
- 4.1 PARAMETER INFLUENCE ESTIMATION: Subset influence is approximated by accumulating the individual influences of its examples, which can reflect the influence of removing a group of data.
- 4.2 DATASET PRUNING AS DISCRETE OPTIMIZATION: The discrete optimization uses binary variables W to maximize the number of selected removable samples under an influence or parameter-change constraint.
- 4.2 DATASET PRUNING AS DISCRETE OPTIMIZATION: Algorithm 1 constructs the largest ϵ-redundant subset from W and returns the original dataset with that subset removed.
5 GENERALIZATION ANALYSIS
The analysis derives an upper bound on dataset-pruning generalization gaps using influence functions and Taylor approximations. The proposed optimization controls the parameter-change term, and experiments report small, theoretically consistent gaps.
- Influence functions approximate the test-loss change from removing one or multiple training samples without retraining.The multidimensional influence function uses an N × m matrix, where N is the number of network parameters.
- The analysis defines the generalization gap as the absolute difference between expected test loss before and after pruning.
- Theorem 1 provides an upper bound on the expected test loss for a pruned dataset under the stated assumptions.The proof uses a first-order Taylor approximation and bounds the remaining second-order term.
- The pruning optimization targets the parameter-change constraint because reducing ϵ decreases the upper bound on the generalization gap.
- O(10^-3) is the estimated generalization-gap magnitude on CIFAR-10 and CIFAR-100, more than one order of magnitude smaller than random dataset pruning.
6 EXPERIMENT
Experiments test the theoretical guarantee, compare optimization-based pruning with baselines across datasets, assess generalization to larger architectures, and measure training and architecture-search efficiency.
- Dataset pruning: Optimization-based pruning outperforms sample-selection baselines, especially at high pruning ratios, by accounting for the group effect of jointly pruned examples.The comparison includes random pruning, herding, forgetting, GraNd, EL2N, and influence-score selection.
- Theoretical analysis verification: The observed test-loss generalization gap is highly consistent with the theoretical expectation, and optimization-based pruning achieves smaller parameter influence and better generalization than random pruning.The analysis omits m/n^2 because it is much smaller than ϵ/n.
- Unseen architecture generalization: Datasets pruned with smaller networks generalize well when used to train larger and previously unseen architectures, including ResNet18 and ResNet50.The cross-architecture evaluation uses CIFAR10 pruned with a smaller network and tests networks with different parameter complexities.
- Experimental setup: The experiments evaluate dataset pruning on CIFAR10, CIFAR100, and TinyImageNet, with controlled training settings and comparisons against several selection baselines.Baselines include random pruning, herding, forgetting, GraNd, EL2N, and influence-score selection.
- Dataset pruning improves training efficiency: 40% pruning nearly halves convergence time while reducing test accuracy by only 1.3%, and the pruned dataset supports more efficient hyper-parameter and architecture search.The architecture-search experiment evaluates 720 ConvNets using 100 images per class in each proxy dataset.
7 CONCLUSION
The paper frames dataset pruning as removing redundant training examples while preserving model performance. It uses constrained optimization and theoretical influence analysis to improve training efficiency while maintaining generalization ability.
- Dataset pruning removes redundant training examples with minor impact on model performance.
- The method models sample selection as constrained discrete optimization, limiting network parameter change while maximizing removable examples.
- Theoretical and empirical studies show improved training efficiency while maintaining the model’s generalization ability.