Coverage-centric Coreset Selection for High Pruning Rates

1 INTRODUCTION

• CCS uses a variation of stratified sampling across importance scores to improve coverage, rather than selecting only the highest-importance examples.The paper frames CCS as addressing the high-pruning accuracy drop by improving data coverage.Source: §1 · p. 2
• At 90% pruning, CCS reaches 85.7% accuracy versus 34.03% for forgetting-score selection on CIFAR10, and exceeds random sampling by 7.04% on CIFAR10 and 5.02% on ImageNet.The evaluation covers five datasets; CCS also outperforms concurrent Moderate by 5.04% on CIFAR10 and 5.20% on ImageNet at 90% pruning.Source: §1 · p. 2
• The paper extends geometric set cover to density-based distribution cover and derives a theoretical bound on model loss from coreset coverage properties.Source: §1 · pp. 1–2
• AUCpr is introduced to quantify how well a dataset covers a distribution.The authors describe it as the first such coverage metric, to their knowledge.Source: §1 · p. 2
• At high pruning rates, SOTA coreset selections have worse data coverage than random selection, suggesting a link between poor coverage and catastrophic accuracy loss.Source: §1 · pp. 1–2
• CCS significantly outperforms baselines and random selection at high pruning rates while achieving comparable performance at low pruning rates.The reported evaluation compares CCS with six baselines across five datasets.Source: §1 · p. 2

2.1 ONE-SHOT CORESET SELECTION

• One-shot coreset selection chooses a subset before training to maximize model accuracy, while common methods rank examples by difficulty or importance and retain more important examples.Forgetting score counts incorrect classifications after earlier correct classification; AUM identifies mislabeled data, and EL2N estimates difficulty using the L2 norm of error vectors.Source: §2.1 · pp. 2–3

2.2 CATASTROPHIC ACCURACY DROP WITH HIGH PRUNING RATES

• At 90% pruning, forgetting-number and AUM methods achieve 34.03% and 28.06% accuracy, respectively, versus 79.04% for random sampling.The SOTA methods outperform random sampling below 70% pruning but considerably underperform it at 90%.Source: §2.2 · p. 3
• The paper hypothesizes that biased pruning by importance-based methods causes poor data coverage and the observed accuracy drop.Source: §2.2 · p. 3

3.1 DENSITY-BASED PARTIAL COVERAGE

• The p-partial r-cover framework measures the probability mass covered by radius-r balls around a coreset, making coverage percentage p explicit alongside radius r.Source: §3.1 · pp. 3–4
• Theorem 1 bounds risk for a p-partial r-cover coreset under Lipschitz loss and regression functions and zero training error on the coreset; the authors note the zero-error assumption may be unrealistic.The bound becomes uninformative at low cover percentage.Source: §3.1 · p. 4
• AUCpr summarizes the p-r coverage curve; lower values indicate better coverage and correspond to lower expected minimum distance from distribution examples to the coreset.In practice, the expected minimum distance can be estimated using a test set.Source: §3.1 · p. 5

3.2 COVERAGE ANALYSIS ON CORESETS

• At pruning rates above 70%, forgetting- and AUM-selected CIFAR10 coresets have larger AUCpr than random, while their AUCpr is similar at 30% and 50%.Larger AUCpr indicates worse coverage.Source: §3.2 · p. 5, Table 1 · p. 5
• Pruning easy examples can remove high-density regions at high pruning rates, reducing coverage and raising AUCpr, potentially increasing loss and lowering accuracy.Source: §3.2 · p. 5
• Figure 3 generally associates higher AUCpr with lower model accuracy across methods and pruning rates.Larger plotted circles indicate higher pruning rates.Source: §3.2 · p. 5, Figure 3 · p. 5

3.3 METHODOLOGY: COVERAGE-CENTRIC CORESET SELECTION

• CCS prunes a configurable share of hardest examples, then stratifies by importance scores and allocates sampling budgets across strata to retain coverage at high pruning rates.If a stratum has fewer examples than its budget, the excess is evenly reassigned; hard-example pruning is intended to free budget for high-density strata.Source: §3.3 · pp. 6–7

4 EVALUATION

• The evaluation compares CCS with six baselines on CIFAR10, CIFAR100, SVHN, CINIC10, and ImageNet, using over 800 trained models.Training was repeated with five random seeds, and mean accuracy and standard deviation were calculated.Source: §4 · p. 7

4.2 ABLATION STUDY & ANALYSIS

• With k = 1 and β = 0, CCS is equivalent to random sampling; larger k can help stratification, while large k values are not a sensitive hyperparameter.The authors state that appropriate hyperparameters guarantee CCS will not underperform random sampling.Source: §4.2 · pp. 7–8

4.1 CORESET PERFORMANCE COMPARISON

• 7.04% better accuracy than random sampling on CIFAR10 and 5.08% better on ImageNet at 90% pruning; CCS outperforms all baselines at high rates across five datasets.At low pruning rates, CCS achieves comparable accuracy.Source: §4.1 · p. 7, Figure 5 · p. 8

4.2 ABLATION STUDY & ANALYSIS

• The optimal β increases as pruning rises, and is 0 at 30% and 50% pruning on CIFAR10.A larger β shifts more budget toward high-density strata; grid-search tuning adds coreset-selection cost.Source: §4.2 · p. 8, Figure 6 · p. 8
• At 80% and 90% pruning, stratified sampling alone remains below random sampling, while pruning hard examples beats pruning easy examples but remains below CCS.These comparisons use the forgetting score on CIFAR10.Source: Table 2 · p. 8, §4.2 · p. 9
• A proportional importance-sampling strategy that aimed to improve coverage underperformed random sampling at high pruning rates.The authors conclude that beating random sampling at high pruning rates is non-trivial, even for a strategy intended to improve coverage.Source: §4.2 · p. 9

• K-means and greedy k-center can select coresets with good coverage, but their distance-matrix calculations have O(n^2) time complexity and are expensive to scale.The cited methods include Sorscher et al. (2022) for k-means and Sener & Savarese (2017) for greedy k-center.Source: §5 · p. 9
• Active learning can use diversity or coverage, but selects data based on the current model for subsequent training rounds, unlike model-agnostic one-shot coresets for training from scratch.BADGE, for example, selects using k-means++ on gradient embeddings from the latest model and repeats the process in later rounds.Source: §5 · p. 9
• Active-learning queries across rounds can exceed a one-shot coreset in total size; BADGE queried different 10K-example sets each round on CIFAR-10, while CCS can select a fixed 10% subset.The passage notes that BADGE's total number of distinct queried examples across rounds is even larger.Source: §5 · p. 9
• Clustering coresets often rely on mathematical properties of classical clustering, and importance sampling used for clustering does not generalize well to deep-learning classification.The cited clustering coreset work includes Feldman et al. (2020), Feldman & Langberg (2011), Cohen-Addad et al. (2021), and Huang et al. (2019).Source: §5 · p. 9

6 CONCLUSION

• The paper extends geometric set cover to density-based partial cover, proposes a coverage metric, and designs CCS, which empirically outperforms baselines on five datasets.The authors describe better-than-random accuracy at high pruning rates as possible and position CCS as a baseline for future research.Source: §6 · p. 9

A OVERVIEW

• The appendix provides experimental details, proofs for Theorem 1 and Proposition 1, results on SVHN and CINIC10, and a study of CCS coreset transferability.Source: A OVERVIEW · p. 13

B DETAILED EXPERIMENTAL SETTING

• CIFAR10, CIFAR100, SVHN, CINIC10, and ImageNet use ResNet18 except ImageNet, which uses ResNet34, with dataset-specific training iterations and augmentation settings.CINIC10 training combines its training and validation sets; its test set is used for accuracy measurement.Source: B DETAILED EXPERIMENTAL SETTING · p. 13
• Difficulty scores use different training horizons: 200 epochs for CIFAR10/CIFAR100, 100 for SVHN/CINIC10, and 90 for ImageNet, with EL2N based on the first 10 epochs.Entropy is calculated from the last checkpoint for CIFAR10/CIFAR100, SVHN, and CINIC10.Source: B DETAILED EXPERIMENTAL SETTING · p. 13
• CCS uses k = 50 across datasets and pruning rates, while β is selected by grid search and varies by dataset and pruning rate.For CIFAR10, the listed β values rise from 0 at 30% and 50% pruning to 30% at 90% pruning.Source: B DETAILED EXPERIMENTAL SETTING · p. 13

C.1 PROOF OF THEOREM 1

• Theorem 1 states a probabilistic risk bound for a p-partial r-cover coreset under Lipschitz loss and regression-function assumptions, bounded loss, and zero coreset training loss.The proof uses the probability of finding a nearby selected zero-loss example and Lipschitz bounds to derive a per-example loss bound of r(λ_l + λ_ηLC).Source: §C.1 · p. 14

C.2 PROOF OF PROPOSITION 1

• AUCpr(S) equals the integral of the cover-radius function fr(p) over p in [0, 1], provided fr is Riemann-integrable.The proposition states this for a metric space, distribution, cover percentage, and set S.Source: §C.2 · p. 15
• The proof approximates the integral with an evenly partitioned Riemann sum, using the increments Δi = fr(pi) − fr(pi−1).It relies on fr being increasing and fr(0) = 0.Source: §C.2 · p. 15
• AUCpr(S) is the expectation of the minimum distance from a point to data in S.The proof concludes this interpretation for the distribution Pµ.Source: §C.2 · p. 15

D.1 EVALUATION RESULTS ON SVHN AND CINIC10

• CCS has higher accuracy than random and baseline coreset methods on both SVHN and CINIC10 at higher pruning rates.The comparison also includes a 95% pruning rate for SVHN.Source: §D.1 · p. 15
• CCS achieves comparable accuracy to other methods at low pruning rates on SVHN and CINIC10.Source: §D.1 · p. 15
• The evaluation compares CCS and baseline methods on SVHN and CINIC10, with results reported in Tables 5 and 6, respectively.Source: §D.1 · p. 15

D.2 CORESET COVERAGE ANALYSIS

• CCS has lower AUCpr and better accuracy than vanilla forgetting at the same pruning rate, which the authors say suggests improved coreset coverage.Table 7 also reports lower AUCpr for CCS and associates it with better data coverage.Source: §D.2 · p. 15, Table 7 · p. 17
• At 70%, 80%, or 90% pruning on CIFAR10, and at higher pruning rates on CIFAR100, CCS outperforms baselines; on CIFAR100 it also outperforms random.At 30% or 50% pruning on CIFAR10 and at low pruning rates on CIFAR100, CCS has comparable accuracy to baselines.Source: Table 3 · p. 16, Table 4 · p. 16

D.3 TRANSFERABILITY OF CORESETS

• Coresets selected by CCS show good transferability from ResNet18 selection to ResNet50 training on CIFAR10.The transferability experiment selects coresets using forgetting scores calculated from ResNet18 training information.Source: §D.3 · p. 16, Table 8 · p. 17
• Figure 7 compares AUCpr and accuracy across pruning ratios and reports lower AUCpr and better accuracy for CCS with forgetting scores than for vanilla forgetting.Circle size encodes pruning ratio.Source: Figure 7 · p. 16
• Tables 5 and 6 report testing accuracy for SVHN and CINIC10; CCS is comparable at 30% or 50% pruning and outperforms baseline methods at the listed higher rates.The higher rates are 70%, 90%, or 95% on SVHN and 70%, 80%, or 90% on CINIC10.Source: Table 5 · p. 17, Table 6 · p. 17

D.4 ADDITIONAL EVALUATION ON IMAGENET

• The ImageNet evaluation applies CCS only to AUM and trains each model once because of the dataset’s large training cost.Source: §D.4 · p. 18
• At high pruning rates on ImageNet, CCS outperforms all baseline methods and achieves comparable performance at low rates; at 90% pruning, it improves 5.02% over random sampling.EL2N and AUM also experience a catastrophic accuracy drop at high pruning rates.Source: §D.4 · p. 18, Table 9 · p. 18
• The authors think forgetting performs similarly to random at high pruning rates because 90 training epochs cap forgetting counts at 45, creating many ties that lead to random selection.Source: §D.4 · p. 18

D.5 DISCUSSION ON IMPORTANCE SAMPLING BASED METHOD

• The preliminary CIFAR10 scheme samples examples by importance-based probabilities, using AUM scores and a softmax function.Because smaller AUM scores indicate greater importance, the probability calculation uses the maximum possible AUM score and the number of examples.Source: §D.5 · pp. 18–19
• The relationship between heuristic deep-learning importance scores and effective sampling probabilities is not obvious, making probability design nontrivial.The authors do not rule out a better-designed importance-sampling technique and describe CCS’s stratified sampling as a useful baseline for further work.Source: §D.5 · pp. 18–19
• On CIFAR10, importance sampling beats AUM at high pruning rates but performs worse than random sampling and CCS; the experiments also report that it fails to beat random.The authors used Table 10 to compare CIFAR10 testing accuracy across pruning rates.Source: §D.5 · p. 18, Table 10 · p. 19