PaperlayerView exact revision on arXiv

Source-linked AI summary

Data pruning and neural scaling laws: fundamental limitations of score-based algorithms

Fadhel Ayed, Soufiane Hayou

arXiv:2302.06960v3stat.MLcs.LG

TL;DR

High-compression pruning matters for improving dataset-size scaling, but the properties needed for effective score-based methods remain unclear. The paper analyzes score-based pruning theoretically and empirically, finding limitations at high compression and exploring calibration with randomization. Its theory does not cover settings where both parameter count and sample size grow without supplementary assumptions.

  • Problem

    High-quality pruning is sought to improve dataset-size power-law scaling, but the properties such algorithms should satisfy remain unclear.

    Source: §1.1 · p. 2

  • Method

    The paper analyzes score-based pruning through its induced data distribution and uses calibration that combines scored signal points with random exploration.

    Source: §3.1 · p. 6, §4 · p. 11

  • Results

    In logistic regression, calibrated GraNd outperforms random pruning, requiring on average two to three times fewer data for the same generalization error.

    Source: §5.1 · p. 14

  • Takeaways & Limitations

    At small compression levels, GraNd can cease to provide useful information, while calibration can mitigate the unproductive signal subset and preserve benefits from informative points.

    Source: §5.1 · p. 14

    The theory does not cover the regime where both parameter count p and sample size n grow to infinity, except under certain supplementary assumptions.

    Source: §7.3 · p. 20

Abstract

from arXiv · show

Data pruning algorithms are commonly used to reduce the memory and computational cost of the optimization process. Recent empirical results reveal that random data pruning remains a strong baseline and outperforms most existing data pruning methods in the high compression regime, i.e., where a fraction of $30\%$ or less of the data is kept. This regime has recently attracted a lot of interest as a result of the role of data pruning in improving the so-called neural scaling laws; in [Sorscher et al.], the authors showed the need for high-quality data pruning algorithms in order to beat the sample power law. In this work, we focus on score-based data pruning algorithms and show theoretically and empirically why such algorithms fail in the high compression regime. We demonstrate ``No Free Lunch" theorems for data pruning and present calibration protocols that enhance the performance of existing pruning algorithms in this high compression regime using randomization.

1 Introduction

Data pruning selects a smaller representative subset to reduce computational cost, but score-based methods can distort the data distribution. The paper analyzes their limits at high compression and proposes calibration using random exploration.

1 Introduction

  • Data pruning selects a small representative sample to reduce computational cost, with applications including neural architecture search and continual learning.These applications use subsets to estimate hyperparameter performance or retain representative examples from past observations.Source: §1 · p. 1

1.1 Connection to Neural Scaling Laws

  • At compression levels r ≤ 30%, score-based pruning is argued to be generally unsuitable and unable to improve power-law scaling without adaptation.The paper identifies this as a regime where high-quality pruning is sought, while the properties such algorithms should satisfy remain unclear.Source: §1.1 · p. 2
  • Score-based pruning can induce distribution shift that changes the training objective and may create local minima associated with deteriorated performance.GraNd is used to illustrate how the data distribution changes as compression increases.Source: §1.1 · p. 2

1.2 Contributions

  • The paper develops an asymptotic framework, proves No-Free-Lunch results for score-based pruning, and proposes random-exploration calibration to address its limitations.The calibration protocol adds noise to pruning; theoretical and empirical results support it on toy datasets, with promising results on image classification tasks.Source: §1.2 · p. 3

2 Learning with data pruning

The paper formalizes training on pruned subsets and studies whether pruning preserves performance as the sample size grows. It relates validity to limiting data distributions and shows that consistency is sufficient for validity.

2.1 Setup

  • Pruning trains a model on a selected subset to reduce training cost while aiming to retain essential information from the full dataset.The setup considers iid data, empirical risk minimization, and random pruning, which uniformly selects a fraction r of the data.Source: §2.1 · p. 4

2.2 Valid and Consistent pruning algorithms

  • Validity requires the performance gap to vanish almost surely as sample size grows; non-valid pruning can underperform random pruning in the abundant-data regime.The paper characterizes validity through convergence of the trained parameter to the minimizers of the original generalization loss.Source: §2.2 · p. 5
  • A limiting distribution for the pruned data supports asymptotic analysis, and consistency—matching the original data distribution—suffices for validity.Random pruning is consistent and therefore valid under the paper’s general assumptions; consistency also permits estimating generalization error from the retained subset.Source: §2.2 · pp. 5–6

3 Score-Based Pruning Algorithms and their limitations

Score-based pruning ranks examples by a score and retains those deemed most relevant. The section shows that, under stated conditions, this approach can ignore parts of the data space and fail consistency or validity, including for sufficiently expressive neural networks.

3.1 Score-based Pruning algorithms

  • Score-based pruning ranks examples by a score, but discontinuities or tied scores can destabilize selection; adapted scores are continuous and have zero-measure level sets.The score convention treats lower scores as more relevant.Source: §3.1 · pp. 6–7

3.2 Asymptotic behavior of SBPA

  • As data grows, score-based pruning behaves like deterministic rejection below a score quantile, ignoring entire regions that can become arbitrarily large at small compression levels.The section investigates consistency and validity under mild assumptions, with specialized results for binary classification and a separate general-problem result.Source: §3.2 · p. 7

3.3 Binary classification problems

  • In binary classification, universal approximation and loss assumption (i) imply that some hyperparameters make any adapted-score SBPA inconsistent.The theorem applies to any binary-classification generating process in the stated class.Source: §3.3 · p. 8
  • With a label-dependent score, universal approximation and assumptions (i)–(ii) yield low-compression non-validity; the theorem also reports worse generalization error than random pruning in the abundant-data regime.Assumption (ii) does not hold for hinge loss.Source: §3.3 · p. 8

Applications: neural networks

  • For sufficiently wide or deep feed-forward networks under the stated activation conditions, adapted-score SBPAs are inconsistent, and label-dependent SBPAs are also non-valid.The wide-network result uses sufficiently large width and bounded-weight radius; the deep-network result uses sufficiently many layers and a sufficiently large radius.Source: Applications: neural networks · p. 9

3.4 General problems

  • When model classes admit two examples with disjoint loss minimizers, Theorem 3 gives a data distribution making an SBPA non-valid at low compression, without requiring universal approximation.The section notes that such pairs generally occur in practice and that random pruning is valid for any generating process under the general assumptions.Source: §3.4 · pp. 9–10

4 Solving non-consistency via randomization

Exact Calibration (EC) combines score-based selection with random exploration from the rejected data region. With any nonzero exploration budget, EC makes score-based pruning consistent and its calibrated loss unbiased at finite sample sizes.

4 Solving non-consistency via randomization

  • Score-based pruning transforms the data distribution, distorting the loss landscape and potentially worsening generalization, especially at smaller compression ratios.As r decreases, the acceptance region becomes arbitrarily small and concentrated.Source: §4 · p. 10
  • EC divides the retention budget between the highest-scoring points and uniform random exploration from the points rejected by score-based pruning.The signal proportion α sets the share allocated to score-based selection; the remainder explores the rejected region.Source: §4 · p. 11
  • The calibrated loss weights signal and exploration contributions inversely to their acceptance probabilities within each region.The procedure uses a weighted sum of the contributions from the two budgets.Source: §4 · p. 11
  • Any SBPA calibrated with EC is consistent when exploration is nonzero, and its calibrated loss is unbiased for generalization loss at every finite n > 0.The consistency proof uses an adapted law of large numbers for dependent variables.Source: §4 · p. 11
  • EC is a soft-pruning wrapper for SBPA: every point has nonzero selection probability, and α = 1 and α = 0 recover SBPA and random pruning, respectively.Lower-scoring samples receive higher acceptance rates, with their loss contributions weighted accordingly.Source: §4 · p. 11
  • EC does not systematically outperform random pruning, and designing protocols tailored to specific algorithms and problems is outside this work’s scope.The authors present EC as an illustration of a framework for analyzing pruning algorithms and their limitations.Source: §4 · pp. 11–12

5 Experiments

Across the experiments, score-based pruning often struggles at high compression, while calibration with random exploration can reduce the performance gap. Results vary by dataset and pruning method, and calibration does not always outperform random pruning.

5.1 Logistic regression:

  • Without calibration, the logistic-regression performance gap does not vanish even with abundant data, alongside a pruning-induced distribution shift that alters the loss landscape and can create new minima.The neural-network experiments also associate distribution shift with new bad minima as compression increases.Source: §5.1 · p. 13, §5.2 · p. 15
  • With exact calibration at α = 90%, allocating 10% of the budget to exploration makes the logistic-regression performance gap vanish with enough data at any compression ratio.Importance weights correct the distribution shift, and the empirical losses overlap even when the predominant labels are swapped.Source: §5.1 · p. 13, Figure 7 · p. 13
  • GraNd’s logistic-regression signal region combines near-boundary points with far points whose realized labels are least probable; calibration mitigates the unrepresentative far-point component.The near-boundary subset provides finer-grained visibility in the critical region.Source: §5.1 · p. 14
  • For calibrated GraNd, the logistic-regression results show an average two to three times fewer data can achieve the same generalization error as Random, but at r = 0.1 Random outperforms both GraNd versions.The authors suggest allocating more budget to random exploration at high compression in this setting.Source: §5.1 · p. 14, Figure 9 · p. 14

5.2 Scaling laws with neural networks

  • On nonlinear and noisy datasets, GraNd performs poorly at high compression, whereas calibrated GraNd becomes valid across compression rates; whether calibration can beat power-law scaling remains open.For the linear dataset, GraNd can beat power-law scaling given enough data; nonlinear scaling may have multiple phases.Source: §5.2 · p. 15, Figure 10 · p. 15
  • Random pruning’s results are consistent across compression levels when subset size is held fixed, unlike GraNd’s dataset-dependent results.Figure 10 compares test error for a three-layer MLP across linear, nonlinear, and nonlinear-noisy datasets.Source: §5.2 · p. 15, Figure 10 · p. 15

5.3 Image recognition

  • For small compression ratios (r < 0.3), SBPA methods (GraNd, DeepFool, Uncertainty) consistently perform worse than Random pruning; calibration consistently boosts performance in the high-compression regime, though gains over Random are not always significant.DeepFool is generally the strongest SBPA method and competes with Random when selection occurs at training epoch 1; finding the optimal signal proportion α can be difficult.Source: §5.3 · p. 17

6 Related work

The related work places coreset selection in the transition from classical methods to approaches adapted for deep learning. It surveys score-based selection families and contrasts them with other coreset and data-distillation approaches.

6 Related work

  • Classical coreset approaches were model-independent or designed for simple models, while deep learning motivated methods adapted to more complex models.The section also notes that coreset selection has a long history in classical machine learning and statistics.Source: §6 · pp. 17–18

6.1 Score-based methods

  • Score-based methods include geometry-, uncertainty-, error-, and decision-boundary-based selection, targeting redundancy, difficulty, loss contribution, or proximity to a boundary.Examples include herding and k-centroids, uncertainty measures, gradient-norm and forgettability scores, and boundary-distance heuristics.Source: §6.1 · pp. 18–19

6.2 Non-SBPA methods

  • Other approaches preserve desired properties through gradient-based selection, two-stage subset optimization, or likelihood and submodular criteria; data distillation instead synthesizes smaller datasets but faces interpretability and computational-cost concerns.The section highlights interpretability as a concern for real-world applications, particularly high-stakes fields.Source: §6.2 · p. 19

7 Discussion and Limitations

The discussion identifies regimes where the asymptotic analysis has limits, while noting broad theoretical coverage and practical pruning-time costs. It also distinguishes fixed-parameter results from the unresolved case where model size and sample size both grow.

7.1 Extreme scenarios

  • When n is small, the asymptotic results may not reflect pruning’s impact on loss; when r = Θ(n^-1), the effective sample size stays constant and the empirical mean need not converge to the asymptotic mean.The authors note that pruning generally offers no practical benefit when the original sample is small.Source: §7.1 · p. 19

7.2 Asymptotic results:

  • The theorems cover broad classes of models, pruning algorithms, data-generating processes, and losses, but may concern unrealistically large models; ResNet-on-CIFAR experiments also show a drop versus random pruning.Theorem 3 further gives, for any SBPA, datasets on which it fails at small compression ratios, even when the function class may be insufficiently rich.Source: §7.2 · pp. 19–20

7.3 Overparameterized Regime

  • The framework does not cover the regime where both parameter count p and sample size n grow; extending concentration arguments to neural networks is generally intractable without supplementary assumptions.The proof difficulty arises because the weights depend on p, making the fixed-p law-of-large-numbers argument inapplicable; the relevant retained terms may also be dependent.Source: §7.3 · p. 20

7.4 Pruning Time Vs Training Time

  • One-shot GraNd and Uncertainty pruning typically take less time than one training epoch, whereas DeepFool pruning can take time comparable to 10 epochs.Second-order criteria, multiple perturbations, and multi-shot pruning can require more resources than full-data training.Source: §7.4 · p. 20

A.1 Proofs of Section 2

The appendix proves convergence claims using compactness and continuity arguments, then applies them to valid pruning algorithms. Its proof strategy relies on subsequence convergence to establish the needed limits.

Proofs of Section 2

  • Compactness and continuity support a subsequence argument showing that the relevant distance converges to zero.The proof extracts a convergent further subsequence and uses continuity of the distance and Lπ.Source: §A.1 · p. 23
  • Uniform continuity on the compact parameter set lets the proof transfer convergence of the parameter sequence into convergence of its loss.The appendix notes that dominated convergence makes Lπ continuous under the stated assumptions.Source: §A.1 · pp. 23, 25

Corollary 2

  • For a valid pruning algorithm, the loss converges almost surely to the minimum over the parameter set.The proof of Corollary 2 invokes Proposition 2 and continuity on the compact parameter space.Source: §A.1 · p. 25

A.2 Proof of Proposition 3

Proposition 3 characterizes the limiting distribution of score-based retained samples. Its proof establishes weak convergence by controlling empirical averages over continuous test functions.

Proposition 3

  • The empirical measure of retained samples converges almost surely and weakly to νr, defined using the set Ar of examples whose score is at most the rth score quantile.The proof identifies the limiting measure through the restriction of the data distribution to Ar.Source: §A.2 · p. 25

Proof of Proposition 3

  • The proof tests convergence over continuous functions and bounds the error by two random terms that it shows converge almost surely to zero.It uses empirical-cdf convergence and the general Glivenko–Cantelli theorem for metric spaces.Source: §A.2 · pp. 25–26
  • Continuity of the score function and the quantile-set construction let the proof approximate the retained set with continuous test functions.The argument compares nested quantile sets and controls their empirical mass.Source: §A.2 · p. 26

A.3 Proof of Theorem 1

The proofs establish inconsistency or invalidity results for score-based pruning in model classes with the universal approximation property, treating adapted scores generally in Theorem 1 and label-dependent scores under additional loss assumptions in Theorem 2. One proof segment establishes an excess-risk lower bound: the predictor’s μ-risk exceeds the best risk in F by ε.

A.3 Proof of Theorem 1

  • With an adapted score and a model-class union having the universal approximation property, Theorem 1 guarantees hyperparameters for which the algorithm is not consistent.The proof handles label-independent scores through Proposition 5 and then addresses the remaining label-dependent case.Source: §A.3 · pp. 27–28

A.4 Proof of Theorem 2

  • For any SBPA A with an adapted score function g that depends on labels, Lemma 7 gives a compression level r > 0 and ε > 0 such that the two stated conditions exclude each other for every f0 ∈ F.Source: §A.4 · p. 31
  • Under universal approximation and loss assumptions (i) and (ii), Theorem 2 guarantees hyperparameters θ1, θ2 for which the algorithm is not valid on Wθ1 ∪ Wθ2.The theorem concerns an SBPA whose adapted score depends on the labels.Source: §A.4 · p. 33
  • The output predictor’s µ-risk exceeds the infimum µ-risk over F by ε.Eµℓ(yout(X; w), Y) > inf_f∈F Eµℓ(f(X), Y) + ε.Source: §A.4 · p. 34

A.5 Proof of the Corollaries 3 and 4

The appendix derives neural-network corollaries from universal approximation, proves Theorem 3’s non-validity construction for adapted-score pruning, and establishes consistency and unbiased loss estimation for exact calibration when α<1.

A.5 Proof of the Corollaries 3 and 4

  • Universal approximation transfers Theorems 1 and 2 to wide neural networks, yielding non-consistency and invalidity beyond architecture width and radius thresholds.The corollaries extend these results to all K and R meeting the corresponding thresholds.Source: §A.5 · p. 34

A.6 Proof of Theorem 3

  • Theorem 3’s proof constructs a generating process concentrating most probability near a point where the adapted score is not minimal, showing non-validity at sufficiently small compression ratios.The construction applies to generating-process classes satisfying convexity and the stated concentration condition.Source: §A.6 · pp. 35–36

A.7 Proof of Proposition 4

  • Exact Calibration with an SBPA is consistent whenever α<1, and its calibrated loss is an unbiased estimator of generalization loss at every finite sample size n>0.Source: §A.7 · p. 38

B Technical results

This appendix collects technical results used in the paper, including approximation and continuity theorems and a strong law for conditionally centered triangular arrays.

B Technical results

  • For non-polynomial activation ϕ, one-hidden-layer networks approximate every continuous function on a compact domain, with output C^Tσ(Ax+b).Source: B Technical results · p. 39
  • The technical tools include continuous separation of disjoint closed sets, Lusin’s compact-set continuity result, and continuous extension from compact domains.Source: B Technical results · p. 39

B.1 A generalized Law of Large Numbers

  • The paper proves a strong law for triangular arrays with conditional zero means, within-row identical (not necessarily independent) variables, and uniformly bounded fourth moments.The proof uses the Chebychev inequality to upper-bound the fourth moment of the mean.Source: §B.1 · pp. 39–40

C Additional Theoretical Results

The appendix defines convolutional neural networks and extends the pruning limitations to ReLU CNNs with bounded filters and biases.

C Additional Theoretical Results

  • These CNNs use J filters of length s with bounded weights and biases, recursively convolve and activate representations, then linearly read out the final representation.Source: C Additional Theoretical Results · p. 40
  • For ReLU CNNs with filter length s∈[2,d_x], adapted-score SBPA is non-consistent beyond filter-count and radius thresholds; label-dependent scores also yield non-validity.Source: C Additional Theoretical Results · p. 40

D Experimental details

The appendix specifies experimental hyperparameters and describes the MLP used for scaling-law experiments.

D Experimental details

  • GraNd(10) averages ten initializations, and training uses cosine-annealed learning rates with ηmax=0.1 and ηmin=10^-4, matching Guo et al. (2022).The training learning rate follows a cosine schedule; the passage also distinguishes it from the coreset-selection learning rate.Source: D Experimental details · pp. 40–41

D.1 MLP for Scaling laws experiments

  • The scaling-law MLP has 1000-dimensional inputs, two 128-unit hidden layers, and a 2×128 output weight matrix.Source: §D.1 · p. 41

Related papers

Loading 2302.06960v3…