Data pruning and neural scaling laws: fundamental limitations of score-based algorithms
Authors: Fadhel Ayed
Soufiane Hayou
Venue: Accepted by TMLR ()

Abstract: Data pruning algorithms are commonly used to reduce the memory and computational cost of the optimization process. Recent empirical results (Guo, B. Zhao, and Bai, 2022) 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; see (Sorscher et al., 2022), where 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 discuss potential solutions to these limitations.

Published in Transactions on Machine Learning Research (11/2023)
Data pruning and neural scaling laws: fundamental limita- tions of score-based algorithms
Fadhel Ayed*
fodhel. aabhel.aye@@gmad.. com
Huowei Technologies France
Soufiane Hayou*
hayou edu..g
National University of Singapore
Reviewed on OpenReview: https: // openreview. net/ forum? id- ARTL4pDavo
Abstract
Data pruning algorithms are commonly used to reduce the memory and computational cost. of the optimization process. Recent empirical results (Guo, B. Zhao, and Bai, 2022) reveal that random data pruming remains a strong baseline and outperforms most existing data pruning methods in the high compression regime, i.c. where a fraction of 30% or less of the data is kept. This regime has recently attracted lot of interest a result of the role of data pruming in improving the so-called neural scaling laws; see (Sorscher et al., 2022), where 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 pruming algorithms and show theoretically and empirically why such algorithms fail the high compression regime. We demonstrate "No Free Lunch' theorems for data pruning and discuss potential solutions to these limitations.
1 Introduction
Coresct selection, also known as data pruning, refers to a collection of algorithms that aim to efficiently select a subset from a given dalaset. The goal of data pruning is to identify a small yet representative sample of the data that accurately reflects the characteristics of the entire dataset. Coreset selection is often used in cases where the original dataset is too large complex to be processed efficiently by the available computational resources. By selecting coreset, practitioners can reduce the computational cost of their analyses and gain valuable insights more elficiently. Data pruning has many interesting applications, notably neural architecture search (NAS), where models trained with small fraction of the data serve as a proxy to quickly estimate the performance of a given choice of hyper-paramcters (Coleman et al., 2020). Another application continual (or incremental) learning in the context of online learning; To avoid the forgetting problem, one keeps track of the most representative examples of past observations (Aljundi et al., 2019).
Coreset selection is typically performed once during training, and the selected corcset remains fixed until the end of training. This topic has been extensively studied in classical machine learning and istics (Welling, 2009; Chen, Welling, and Smola, 2012; Feldman, Faulkner, and Krause, 2011; Huggins, Campbell, and Broderick, 2016; Campbell and Broderick, 2019). Recently, many approaches have been proposed to adapt to the challenges the deep learning context. Examples include removing the redundant examples from the feature space perspective (see Sener and Savarese, 2018), finding the hard examples, defined as the ones for which the model the least confident (Coleman et al., 2020), or the ones that contribute the most to the error (Toneva et al., 2019). We refer the reader to Section for a more comprehensive literature review. Most of these methods use score function that ranks examples based on their "importance'. Given desired compression level E (0, 1) (the fraction of data kept after pruning), the coresct is created by retaining only the most important examples based on the scores to meet the required compression level. We
"Equal contribution (Alphabetical order).

---

Published in Transactions on Machine Learning Research (11/2023)
T-0.7
-2
Figure 1: Logistic regression: Data distribution alteration due to pruning for different compression ratios.
Here we use GraNd as the pruming algorithm. Blue points correspond to Y, = 0, red points correspond to Y = 1. More details in Section 5.
refer to this type of algorithms as score-based pruning algorithms (SBPA). A formal definition is provided in Section 2.
1.1 Connection to Neural Scaling Laws
Recently, stream of empirical works have observed the emergence of power law scaling in different machine learning applications (sce e.g. Hestness et al., 2017; Kaplan et al., 2020; Rosenfeld et al., 2020; Hernandez et al., 2021; Zhai et al., 2022; Hoffmann et al., 2022). More precisely, these empirical results show that the performance of the model (e.g. the test error) scales as a power law with either the model size, training dataset size, or compute (FLOPss. In Sorscher et al., 2022, the authors showed that data pruning can improve the power law scaling of the dataset size. The high compression regime (small r) of major interest in this case since it exhibits super-polynomial scaling laws on different tasks. However, as the authors concluded, improving the power law scaling requires high-quality data pruning algorithms, and it is still unclear what properties such algorithms should satisfy. Besides scaling laws, small values of r are of particular interest for tasks such as hyper-parameters selection, where the practitioner wants to select a hyper-parameter from a grid rapidly. In this case, the smaller the value of r, the better.
In this work, we argue that score- scoro-based data pruning is generally not suited for the high compression regime (starting from r s 30%) and, therefore, cannot be used beat the power law scaling. In this regime, it has been observed (see e.g. Guo, B. Zhao, and Bai, 2022) that most SBPA algorithms underperform random pruning (randomly selected subset). To understand why this occurs, we analyze the asymptotic behavior of SBPA algorithms and identify some of their properties, particularly in the high compression level regime. To the best of our knowledge, no rigorous explanation for this phenomenon has been reported in the literature. Our work provides the first thcoretical explanation for this behavior and offers insights on how to address it in practice.
Intuitively, SBPA algorithms induce distribution shift that affects the training objective. This can, for example, lead to the emergence of new local minima where performance deteriorates significantly. To give sense of this intuition, we use toy example in Fig. 1 to illustrate the change in data distribution as the compression level r decreases, where we have used GraNd (Paul, Ganguli, and Dziugaite, 2021) to prune the dataset.
We also report the change in the loss landscape in Fig. as the compression level decreases and the resulting scaling laws. The results show that such a pruning algorithm cannot be used improve the scaling laws since the performance drops siguificantly in the high compression regime and does not tend to significantly decrease with sample size.
Motivated by these empirical observations, we aim to understand the behaviour of SBPA algorithms in the high compression regime. In Section 3, we analyze the impact of pruning of SBPA algorithms on the loss function in detail and link this distribution shift to a notion of consistency. We prove several results showing the limitations of SBPA algorithms in the high compression regime, which explains some of the empirical results reported in Fig. 2. We also propose calibration protocols, that build on random exploration address this deterioration in the high compression regime (Fig. 2).
2

---

Published in Transactions on Machine Learning Research (11/2023)
1.2 Contributions
Our contributions are as follows:
0.4
We propose novel formalism to character- ize the asymptotic properties of data prun- ing algorithms in the abundant data regime.
Loss function
0.3
-40.5
m-077
<lwe)) - min C(w)
10-2-
m10
1000
10"
F00
We introduce Score-Basod Pruning Algo- rithms (SBPA), a class of algorithms that encompasses wide range of popular ap- proaches. By employing our formalism, we analyze SBPA algorithms and identify pho- nomenon of distribution shift, which prov- ably impacts generalization error.
0.0
10-3
1-10
10r
W
m
0.4
0.5
10'2
000
Loss function
0.3
r-0.7
min.mmnw c(w)
5w0.5
<lw)) min
10-3
1=10
We demonstrate No- LunFree-Luunch results that characterize when and why score-based pruning algorithms perform worse than ran- dom pruning. Specifically, we prove that SBPA are unsuitable for high compression scenarios due to a significant drop in perfor- mance. Consequently, SBPA cannot improve scaling laws without appropriate adapta- tion.
0.1
10-
0.0
10
10"
Figure 2: Logistic regression: is the compression level, n the total number of available data and w the learnable paramcter. (Left) The loss landscape trans- formation due to pruning. (Right) The evolution of the performance gap as the data budget m == X n in- creases (average over ten runs). Top figures illustrate the performance of GraNd, bottom figures illustrate the performance of GraNd calibrated with our exact proto- col: we use 90% of the data budget for the signal, i.e. points selected by GraNd, and 10% of the data budget for calibration through random exploration. See Sec- tions 4 and 5 for more details.
Leveraging our theoretical insights, solu- tions can be designed to address these lim- itations. As illustration, we introduce a simple calibration protocol to correct the distribution shift by adding noise to the pruning process. Theoretical and empiri- cal results support the effectiveness of this method on toy datasets and show promising results on image classification tasks.
2 Learning with Data Pruning
2.1 Setup
Consider a supervised learning task where the inputs and outputs respectively in X' C Rd, and ) C Rd,, both assumed to be compact², We denote by D= y the data space. We assumne that there exists μt, atomless probability distribution on D from which poutttu pairs Z = (X,Y) are drawn independently at random. We call such data generaling process. We will assume that. X is continuous while can be either continuous (regression) or discrete (classification). We are given a family of models
Mg = (yout (: w) X y W Wol.
(1)
parameterised by the parameter space Wg, a compact subspace of Rd where 0 E θ is a fixed hyper- parameter. For instance, Mo could be a family of neural networks of a given architecture, with weights w, and where the architecture is given by 0. We will assume that yout is continuous on X W3 For given
II is important to note that the calibration protocul serves example to stimulate further research. We do not claim that this method systematically allows outperform raudom pruning nor to beat the neural scaling laws. 2W further require that the X has isolated points. This technical assumption required to avoid dealing with unnecessary complications in the proofs.
Thii is generally satisfied large class models, including neural networks.
3

---

Published in Transactions on Machine Learning Research (11/2023)
continuous loss function {: + R, the aim of the learning procedure is to find model that minimizes the generalization error, defined by
((w) def
Ep (X;
(2)
We are given dataset Dn composed of 2 1 caput/output pairs (z), iid sampled from the data generating process μ.. To obtain an approximate minimizer of the generalization error (Eq- (2)), we perform an empirical risk minimization, solving the problem
1 (w) def Σ (your (x;; w). vi).
min wEW
(3)
The minimization problem (3) is typically solved using numerical approach, oflen gradient-based, such as Stochastic Gradient Descent (Robbins and Monro, 1951), Adam (Kingma and Ba, 2017), etc. We refer to this procodure as the training algorithm. We assume that the training algorithm is exact, i.c. will indeed return a minimizing parameter w, E argmin Cn(w). The numerical complexity of the training algorithms grows with the sample size n, lypically linearly or worse. When n is large, is appealing extract a representative subset of D, and perform the training with this subset, which would reduce the computational cost of training. This process is referred to data pruning. However, in order to preserve the performance, the subset should relain essential information from the original (full) dalaset. This is the primary objective of data pruning algorithms. We begin by formally defining such algorithms.
Notation. If Z is finite set, we denote by [ its cardinal number, i.e. the mumber of elements in Z. We denote [x] the largest integer smaller than equal to x for R. For some Euclidean space &, denote by d the Euclidean distance and for some set B C & and E &, we define the distance d(e, B) = inf n d(e, b). n2). We denote the set of all 2,1, 21 + 22 F + 2n E D). We call C the finite power finite subsets 'D by C, i.. Un21 (f21, 22,,22.-. 22, 2.,...,,,,,,,.. set of D.
Finally, for two integers < n2, [M1 722 refers to the set {ni, R2 + 1,...,
Definition 1 (Data Pruning Algorithm) We say that a function A : C (0, + C a data pruning algorithm if for all Z C,r (0, such that r|Z] is integer 4, have the following
A(2,r) 2
|A(Zr)) r|
where 1-1 refers to the cardinal number. The number r is called the compression level and refers to the fraction of the dala kept after pruning.
Among the simplest pruning algorithms, we will pay special attention to Random pruning, which selects uniformly at random a fraction of the elements of Z to meet some desired compression level r.
2.2 Valid and Consistent Pruning Algorithms
Given a pruning algorithm A and a compression level r, a subset of the training set is selected and the model is trained by minimizing the empirical loss on the subset. More precisely, the training algorithm finds parameter w,A-" argmin (w)) where
CAr(w) (w) def
Σ (L.)))((D.))
{Vour w) y).
IA(D,, r)
We make this assumption simplify the notations. One can take integer part instead.
4

---

Published in Transactions on Machine Learning Research (11/2023)
This usually requires only fraction of the original energy/time" cost better, given the linear complexity of the training algorithm with respect to the data size. In this work, we evaluate the quality of a pruning algorithm by considering the performance gap it induces, i.e. the excess risk of the selected model
gap [(w min L(w). wEW,
(4)
In particular, we are interested in the abundant data regime: we aim to understand the asymptotic behavior of the performance gap the sample size grows to infinity. We define the notion of valid pruning algorithms as follows.
Definition 2 (Valid pruning algorithm) For a parameler space Wo, pruning algorithm A is valid al compression level E (0, if lim gap,. 0 almost surely. The algorithm is said to be valid if it is valid at any compression level E (].
We argue that valid data pruning algorithm for given generating process μ and family of models Mo should see its performance gap converge to zero almost surely. Otherwise, it would mean that with positive probability, the pruning algorithm induces a deterioration of the out-of-sample performance that does not vanish even when an arbitrarily large amount of data available. This deterioration would not exist without pruming or if random pruning was used instead (Corollary 1). This means that with positive probability, a non-valid pruning algorithm will underperform random pruning in the abundant data regime. In the next result, we show that a sufficient and necessary condition for pruning algorithm to be valid compression level r is that wAr should approach the set of minimizers of the original generalization loss function n increases.
Proposition 1 (Charactorization of valid pruning algorithms) A pruming algorithm A is volid at compression level r E 10, if and only if
d dw Wo(w)) - a.s.
where (p) argmin ((w) C Wo and d (uz Wo(H)) denotes the euclideon distance from the point wAr to the set (H)..
With this characterization in mind, the following proposition provides a key tool to analyze the performance of pruning algorithms. Under some conditions, allows us to describe the asymptotic performance of any pruning algorithm via some properties of probability measure.
Proposition Lel A be a pruning algorithm and E (0, a compression level. Assume that there erists a probability measure Vy on D such that
Ve E Wo, CA'(w)) - Be, E(Vout (X; w), Y) a.s. Then, denoting W7 (ur) argmin R,, (yoou (x; Y) C Wo, we have that
(5)
d (A WT(v.) a.s.
Condition Eq. (5) assumes the existence of a limiting probability measure v, that represents the distribution of the pruned dataset in the limit of infinite sample size. In Section 3, for a large family of pruning algorithms called score-based pruning algorithms (a formal definition will be introduced later), we will demonstrate the existence of such limiting probability mcasure and derive its exact expression.
Let us now derive two important corollaries; the first gives sufficient condition for algorithm to be valid, and the second necessary condition. From Proposition 1 and Proposition 2, we deduce that sufficient condition for an algorithm to be valid is that v, = μ satisfics equation (5). We say that such a pruning algorithm is consistent.
Here the original refers the training cost of the model with the full dataset.
5

---

Published in Transactions on Machine Learning Research (11/2023)
Definition 3 (Consistent Pruning Algorithms) We say that pruning algorithm A is consistent at compression level r E (0,1) if and only if it satisfies
Yw E We, (w)(w) (y (a, w), y)1 [(w) a.s.
(6)
We say that A is consistent if it is consistent at any compression level (0,
Corollary 1 A consistent pruning algorithm A at a compression level r E (0, 1] is also valid at compression level.. r.
A simple application of the law of large numbers implies that Random pruning is consistent and hence valid for any generating process and learning task satisfying our general assumptions.
We bring to the reader's attention that consistency is itself a property of practical interest. Indeed, it not only ensures that the generalization gap of the learned model vanishes, but it also allows the practitioner accurately estimate the generalization error of their trained model from the selected subset. For instance, consider the case where the practitioner is interested in K prper-parameter values 0,,... 0ki these can be different neural network architectures (depth, width, etc.). Using pruning algorithm A, they obtain trained model (Ox) for each parrmmerr 0x, with corresponding estimated generalization error CA- [ (0x)) Hence, the consistency property would allow the practitioner to select the best hyper- parameter value based on the empirical loss computed with the set of relained points (or a random subset of which used for validation). From Proposition 1 and Proposition 2, we can also deduce a necessary condition for algorithm satisfying (5) to be valid:
Corollary 2 Let A be any pruning algorithm and r (0, 1), and assume that (5) holds for a given probability measure V, D. If A is valid, then Wž (v,) (4) + 0; or, equivalently,
min Wr WEW (1%)
L(w)
min L(w). wEW
Corollary will be key ingredient in the proofs on the non-validity of given pruming algorithm. Specifically, for all the non-validity results stated in this paper, we prove that (M,)) 0. In other words, none of the minimizers of the original problem is minimizer of the pruned one, and vice-versa.
3 Score-Based Pruning Algorithms and their Limitations
3.1 Score-based Pruning Algorithms
A standard approach to define a pruning algorithm is to assign to each sample 2; (I1, 1k) score gi = 9(z)) according to some score function 9, where g is mapping from D to R. is also called the pruning criterion. The score function 9 captures the practitioner's prior knowledge of the relative importance of each sample. This function can be defined using a teacher model that has already been trained, for example. In this work, we use the convention that the lower the score, the more relevant the example. One could of course adopt the opposite convention by considering -g instead of g in the following. We now formally define this category of pruning algorithms, which call score-based pruning algorithms.
Definition 4 (Score-based Pruning Algorithm (SBPA)) Let A be a data pruming algorithm. We say that A is score-based praning algorithm (SBPA) if there erists a function g : D - R such that for all Z C, r (0,1), we have that A(Z,r) = (2 E s.t. s.t. g(2) S 1 where g0121 is (r) order statistic of the sequence (9(=))=EZ (frst order statistic being the smallest value). The function g is called the score function.
A significant number of existing data pruning algorithms are scoro-based (for example Coleman20020nneraantty Paul, Ganguli, and Dziugaite, 2021; Ducoffe and Precioso, 2018; Sorscher et al., 2022), among which the recent approaches for modern machine learning. One of the key benefits of

---

Published in Transactions on Machine Learning Research (11/2023)
these methods is that the scores are computed independently; these methods are hence parallelizable, and their complexity scales linearly with the data size (up to log terms). These methods are tailored for the abundant data regime, which explains their recent gain in popularity.
Naturally, the result of such a procedure highly depends on the choice of the score function 9. and different choices of g might yield completely different subsets. The choice of the score function in Definition is not restricted, and there are many scenarios in which the selection of the score function g may be problematic. For example, if has discontimuity points, this can lead to instability in the pruning procedure, as close data points may have very different scores. Another problematic scenario is when assigns the same score to large number of data points. To avoid such unnecessary complications, we define adapted pruning criteria as follows:
Definition 5 (Adapted score function) Let g be a score function corresponding to some pruning algo- rithm A. We say that g an adapted score function if continuous and for any c. E g(D) = (g(=), 2 D), we have >g ((c3) = 0, where X is the Lebesgue measure on D.
In the rest of the scction, we will examine the properties of SBPA algorithms with adapted score function.
3.2 Asymptotic Behavior of SBPA
Asymptotically, SBPA algorithms have simple behavior that mimics rejection algorithms. We describe this in the following result.
Proposition 3 (Asymptotic behavior of SBPA) Let A be SBPA algorithm and lel y be ils corresponding adapted score function. Consider a compression level E (0, 1). Denote by q" the 4 quantile of the random variable g(Z) where Z ~ μ. Denote A, = {2 E D 9(2) S q²). Almost surely, the empirical measure of the relained dala samples converges weakly to Ur +M/ where MA is the restriction of y to the set Ar. In particular, we have that
Vw E We, (w) + Eu, Elyout (X;w), w), Y) a.s.
The result of Proposition implics that in the abundant data regime, SBPA algorithm A acts similarly to a deterministic rejection algorithm, where the samples are retained if they fall in A,, and removed otherwise. The first consequence is that SBPA algorithm A is consistent at compression level if and only if
Yu E Wo. EiiIA ((Vou (X; Y) E,L(your (X; Y),
(7)
The second consequence is that SBPA algorithms ignore entire regions of the data space, even when we have access to unlimited data, i... + cc. Moreover, the ignored region can be made arbitrarily large for small enough compression levels. Therefore, we expect that the generalization performance will be affected and that the drop in performance will be amplified with smaller compression levels, regardless of the sample size n. This hypothesis empirically validated (see Guo, B. Zhao, and Bai, 2022 and Section 5).
In the rest of the section, we investigate the fundamental limitations of SBPA in terms of consistency and validity; we will show that under mild assumptions, for any SBPA algorithm with adapted score function, there exist compression levels for which the algorithm is neither consistent nor valid. Due to the prevalence of classification problems in modern machine learning, we focus on the binary classification setting and give specialized results in Section 3.3. In Section 3.4, we provide a different type of non-validity results for more general problems.
3.3 Binary Classification Problems
In this section, we focus our attention on binary classification problems. The predictions and labels are in y'= [0, 1]. Denote PB the set of probability distributions on X'x x {0, 1), such that the marginal distribution on the input space X is continuous (absolutely continuous with respect to the Lebesgue measure on X) and for which
Px : P 1|X=2] = 2)
is upper semi-continuous for any Pp. We further assume that:
7

---

Published in Transactions on Machine Learning Research (11/2023)
(i) the loss is non-negative and that E(y. 3/) 0 if and only if y = y'.
(ii) For q [0, 11, y + ge(v, 1) (1 g) 0) has unique minimizer, denoted Vn E [0, that is increasing with q.
These two assumptions are generally satisfied in practice for the usual loss functions, such the L,, l2, Exponential or Stoss-Entross losses, with the notable exception of the Hinge loss for which (fi) does not hold.
Under mild conditions that are generally satisfied practice, we show that no SBPA algorithm is consistent. We first define a notion of universal approximation.
Definition 6 (Universal approximation) A family of continuous functions v has the universal approz- imation properly is for any continuous function J X - and > 0, there exists vp E W such that
maxxex(f(x)) vx)x) Se
The next proposition shows that if the set of all models considered Uo has the universal approximation property, then no SBPA algorithm is consistent.
Theorem Consider any generating process for binory classification E Pg- Let A be any SBPA algorithm with an adapted score function. If UaMo has the universal approzimation property and the loss satisfies assumplion (i), then there erist sapeer-prammeers 0 E θ for which the algorithm is not consistent.
Even though consistency is an important property, a pruning algorithm can still be valid without being consistent. In this classification setting, we can further show that SBPA algorithms also have strong limitations in terms of validity.
Theorem Consider any generating process for binary classification μ. PB. Let be a SBPA with an adapted score function g that depends on the labels IJ UgM has the universal approcimation properly and the loss satisfies assurpptions (i) and (ii), then there erist huper-parameters 01, 02 O and ro (0,1) such that the algorithm is not volid for r S for any hyper-paramettr 0 such that Wo, U We, C We.
This theorem sheds light on a strong limitation of SBPA algorithms for which the score function depends on the labels: it states that any solution of the pruned program will induce a gencralization error strictly larger than with random pruning in the abundant data regime. The proof builds on Corollary 2; we show that for such syper-parametted 0, the minimizers of the pruned problem and the ones of the original (full data) problem do not intersect, i.c
(v,), n (1) =
SBPA algorithms usually depend the labels Aelemmnn2220Unceraiiin 2021; Ducoffe and Precioso, 2018) and Theorem 2 applies. In Sorscher et al., 2022, the authors also propose to use a SBPA that does not depend on the labels. For such algorithms, the acceptance region A, is characterized by a corresponding input acceptance region X, SBPA independent of the labels have a key benefit; the conditional distribution of the output is not altered given that the imput is in X,. Contrary to the algorithms depending on the labels, the performance will not necessarily be degraded for any generating distribution given that the family of models is rich enough. It remains that the pruned data give no information outside of X,, and yout can take any value in X' Xr without impacting the pruned loss. Hence, these algorithms can create new local/global minima with poor generalization performance. Besides, the non-consistencyy results of this section and the No-Free-Lunch result presented in Section 3.4 do apply for SBPA independent of the labels. For these reasons, we believe that calibration methods (see Section 4) should also be employed for SBPA independent of the labels, especially with small compression ratios.
Paul, Ganguli, and Dziugaite,
oTe score function g depends on the labels if there exists input the support of the distribution of the input and which g(z, 0) o g(z, 1) and P(Y=1] =1 X 2) E (0, 1) (both labels can happen input x)
8

---

Published in Transactions on Machine Learning Research (11/2023)
Applications: Neural Networks
To exemplify the utility of Theorem 1 and Theorem 2, approximation properties of neural networks to derive the important corollaries stated below
we leverage the existing literature on the universal
Definition 7 For an activation function 0, real number R > 0, and integers H, 2 L, we denote by F (R) the set of fully-connecled feed-forward neural nebworks with H hidden layers, each with K neurons with all weights and biases in [-R, R).
Corollary 3 (Wide neural networks) Let a be any continuous non-polynomial function that is continu- ously differentiable at (at least) one point, with a nonzero derivalive at that point. Consider any generoling process μ E PB. For any SBPA with adapted score function and H 2 1, there erists a rodius Ro and a width Ko such that the algorithm is not consistent on FFNNG N H.. (R) for any K 2 Ko and 2 Ro- Besides, if the score function depends on the labels, then is also not volid on FFNNN, (R) for any K 2 Kij and R R-
Corollary 4 (Deep neural networks) Consider a width K Z d2 2. Let a be any continuous non- polymomial function that is continuously differentiable at (at least) one point, with a nonzero derivative al that poinl. Consider any generaling process μ E Pn- For anyy SBPA with an adapted score function, there erists radius Ro and number of hidden layers Ho such that the algorithm is not consistent FFNNE,, K (R) for any H Z Ho and R 2 Rg. Besides, if the score function depends on the labels, then it is also not volid on FFNND, (R) for any H 2 H'J and R 2 R
A similar result for convolutional architectures is provided in Appendix C. To summarize, these corollaries show that for large enough neural network architectures, any SBPA is non-consistent. Besides, for large enough neural network architectures, any SBPA that depends on the label is non-valid, and hence a performance gap should be expected even in the abundant data regime.
3.4 General Problems
In the previous section, we leveraged the universal approximation property and proved non-validity and non-consistency results that hold for any data-generating process. In this section, we show a different No- free-Lunch result in the general setting presented in Section 2. This result does not require the universal approximation property. More precisely, we show that under mild assumptions, given any SBPA algorithm, we can always find data distribution μ such that the algorithm is not valid (Definition 2). Since random pruning is valid for any generating process, this means that there exist data distributions for which the SBPA algorithm provably underperforms random pruming in the abundant data regime.
For K E N let PK denote the set of gencrating processos for K-classes classification problems, for which the input X is a continuous random variable", and the output Y can lake one of values in y (the same set of values for all क E ))). Similarly, denote PRi the set of generating processes for regression problems for which both the input and output distributions are contimuus. Let P be any set of generating processes introduced previously for regression or classification (either P PK for some K, or P PR). In the next theorem, show that under minimal conditions, there exists data generating process for which the algorithms is not valid.
Theorem Let A be a SBPA with adapted score function. For any hyper-parameterr 0 E O, if there exist (21, (I2, 32) E 'D such that
argmin (youte w), 91) O argmin ((youe(x2) w), y2) = 0,
(HI)
then there erists ro E 1) and a generating process E P for which the algorithm is not valid for r S ro-
The rigorous proof of Theorem 3 requires careful manipulations of different quantities, but the intuition is rather simple. Fig. 3 illustrates the main idea of the proof. We construct a distribution f with the majority
In the sense that the marginal of the input is dominated by the Lebrsgue measure
9

---

Published in Transactions on Machine Learning Research (11/2023)
Select 2, z,and such that (2,) < ((2)
Z2
21
Put small mass of μ around 7
Put the bulk of μ around 22
Figure 3: Graphical sketch of the proof of Theorem 3. The surface represents the loss function f(z,w) ((youe(x), 8) in 2D, where z = =(xx)) (I,
Standard method
Data
SBPA
Subset
Data
SBPA-CO
Subset
Our proposed
Calibration
method
Protocol (CPx)
SBPA
Figure 4: An illustration of how the calibration protocols modify SBPA algorithms.
of the probability mass concentrated around a point where the value of is not minimal. Consequently, for sufficiently small r, the distribution of the retained samples will significantly difler from the original distribution. This shift data distributions causes the algorithm to be non-valid. We see in the next section how we can solve this issue via randomization. Finally, notice that Eq. (H1) is generally satisfied practice since usually for two different examples (21,81) and (I2, y2) in the datasets, the global minimizers of E(yout w)) y1) and (youu (12; w), 122 are different.
4 Solving Non-Consistency via Randomization
We have seen in Section 3 that SBPA algorithms inherently transform the data distribution by asymptotically
rejecting all samples in D \ A,. These algorithms are prone to inconsistency; the transformation of the data distribution translates
a distortion of the loss landscape, potentially leading a deterioration of the generalization error. This effect exacerbated for smaller compression ratios r as the acceptance region becomes arbitrarily small and concentrated.
10

---

Published in Transactions on Machine Learning Research (11/2023)
With this in mind, one can design practical solutions to mitigate the problem. For illustration, propose to resort to a Calibration Protocol to retain information from the previously discarded region DD \ A, The calibration protocols can be thought of as wrapper modules that can be applied on top of any SBPA algorithm to solve the consistency issuc through randomization (sec Fig. 4 for a graphical illustration). Specifically, we split the data budget rn into two parts: the first part, allocated for the signal, leverages the knowledge from the SBPA and its score function g. The second part, allocated for exploration, accounts for the discarded region and consists of subset of the rejected points, selected uniformly at random. In other words, we write Nsignal + Teaploration- With standard SBPA procedures, Teaploration = 0. We define Esignal the proportion of signal in the overall budget. Accordingly, the set of retained points can be expressed as
A(D r, = (D,, U (D,:
where A denotes the calibrated version of A, and the indices 's' and 'e' refer to signal and exploration respectively. In this work, we consider the simplest approach. The "signal subset" is composed of the orn points with the highest importance according to g: i.c. AD,
r(),, The "cxploration subset', Ao(Dn, is composed on average of - a)rn points selected uniformly at random from the remaining samples Dn \ A(D,, each sample being retained with probability Pe = T-ar calibrated loss is then defined as a weighted sum of the contributions of the signal and exploration budgets,
(L-arr independently. The
C.A.na
1 n2
9s
Σ
f(2;w) to
Σ
f(z:w)
zCA.(D..no)
where f(z; w) = (x), y) for z = (x, y) E D and w E Wg. The weights and % are chosen so that the calibrated procedure is consistent; they are inverscly proportional to the probability of accoptance within each region:
= 1
- ar
Te (1 a)r
Proposition 4 hereafter states that any SBPA calibrated with this procedure is made consistent as long as a non-zero budget is allocated to exploration. For this reason, we refer to this method as the Exact Calibration protocol (EC). The proof builds on an adapted version of the law of large numbers for sequences of dependent variables which we prove in the Appendix (Theorem 7).
Proposition 4 (Consistency of Exact Calibration Let A be SBPA algorithm. Using the Exact Calibration protocol with signal proportion a, the calibrated algorithm. Á is consistent if 0, i.e. the exploration budget is not reul.. Besides, under the same assumption 1 - > O, the colibrated loss is an unbiased estimalor of the generalization loss at ony finile sample size 0,
Vw Wo. Vr E (0, E.ArA (w) = L(w).
The proposed EC protocol offers a simple yet effective approach to address the challenges of non-consistency and non-validity. can be seamlessly applied conjunction with any SBPA. The core concept revolves around the implementation of soft-pruning: any data point assigned non-zero selection probability. Samples with lower scores are given a higher acceptance rate. The contribution of each accepted data point to the loss is then weighted accordingly. The EC protocol embodies one specific implementation of soft-pruning, offering the advantage of a single interpretable tuning parameter, the signal proportion a E [0, 1]. By setting a to or 0, one can recover the SBPA and Random pruning as extreme cases.
Proposition 4 states that any SBPA calibrated with EC is made consistent and valid as long as some budget is allocated to exploration. This empirically validated in Section where we show promising results on a Toy example (Logistic regression) and other image tasks. However, the exact calibration protocol does not systematically allow to outperform random pruning.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Tw0.2
Figure 5: Data distribution alteration due to pruning in the logistic regression setting. Here we GraNd the pruning algorithm. Blue points correspond to Y; 0, red points correspond to Y; =7 1.
Besides, it is worth noting that different implementations of the same general recipe can be considered. It is reasonable to expect that more tailored protocols can be designed to suit specific pruning algorithms and problems. Nevertheless, addressing these questions falls outside the scope of the present work which focus is to provide a framework to analyse data pruning algorithms, as well as to identify and understand their fundamental limitations. We propose the EC protocol illustrate how this understanding allows design simple yet efficient solutions to address these limitations..
5 Experiments
5.1 Logistic Regression
We illustrate the main results of this work on a logistic regres- sion task. We consider the following data-generating process
((w()) - min c(w)
10-2
X;
10-3
0
Y X
B
1
0.4
10
0.5
(1, E Rd= U and B are respectively the uniform and Bernoulli distributions. The class of models is given by
where We
1=0
10-3
10a
10a
10a
10
m
1te - xx w E w
M (: w) +
Figure Fvolution of the performance gap as the data budget m = rn increases (aver- age over 10 runs).
where W 100 We train the models using stochastic gradient descent with the cross entropy loss. For performance analysis, we take d, = 20 and = 106. For the sake of visualization, we take d = when we plot the loss landscapes (so that the parameter w is univariate) and dz 2 when we plot the data distributions.
We use GraNd (Paul, Ganguli, and Dziugaite, 2021) as pruming algorithm in a teacher-student setting. For simplicity, we use the optimal model to compute the scores, i.c.
g(X,, Y2) e wo), Y.)
which is proportional to (Vowr (X4; wo) - 2.) Notice that this setting, GraNd and EL2N (Paul, Ganguli, and Dziugaite, 2021) are equivalent*. We bring the reader's attention that r corresponds Random pruning in our plots. Indeed, compare models function of the data budget m rn. But notice that
8Thhis is different from the original version Grald, here, have access the generating process, which the practice.
12

---

Published in Transactions on Machine Learning Research (11/2023)
007
0-0.
r=0.
2 11
2
2
-2
0
r=
0.0
r=0.2
2
0
-2
0
2
2
Figure 8: Prunod data distribution for GraNd calibrated with exact protocol with a 90%. The top figures represent the 'signal' points. The bottom figures represent the 'exploration" points. Blue markers correspond to Y, 0, and red markers correspond to Y, 1.
in the case of Random, for a given m, the values of and n do not affect the distribution of the accepted datapoints, and this distribution is always the same as the original data distribution, i.e. when r=
Distribution shift and performance degradation: In Section 3, we have seen that the pruming algorithm induces a shift in the data distribution (Fig. 5). This alteration most pronounced when r is small; For r 20%, the bottom-left part of the space populated by Y and the top-right by = Notice that it was the opposite in the original dataset (r 1). This translates into a distortion of the loss landscape and the optimal parameters wAr" of the pruned empirical loss becomes different from wo 1. Hence, even when large amount of data is available, the performance gap does not vanish (Fig. 6).
10
r=0.3
Calibration with the exact protocol: To solve the distri-
min
c(w() - WEW
r=0.4
bution shift, we resort the exact protocol with a 90%. In other words, 10% of the budget is allocated exploration. The
005
10-3
1=00
signal points (top images in Fig. 8) are balanced with the ex- ploration points (bottom images in Fig. 8). Even though there are nine times fewer of them, the importance weights allow to correct the distribution shift, as depicted in Fig. 2 (Introduc- tion): the empirical losses overlap for all values of r, even for small values for which the predominant labels are swapped (for example r 20%). Hence, the performance gap vanishes when enough data. is available at any compression ratio (Fig. 7).
10
10-3
10a
10a
10a
10
m
Figure 7: Evolution of the performance gap with calibrated GraNd as the data budget m rn incrcases (average over 10 runs).
Impact of the quality of the pruning algorithm: The calibration protocols allow the performance gap to eventually vanish if enough data is provided. However, from a practical point of view, a natural further requirement that the pruning method should be better than Random, the sense that for given finite budget rn, the error with the pruning algorithm should be lower than the one of Random. We argue that this mostly decided by the quality of the original SBPA and its score function. Let take closer look at what happens in the
13

---

Published in Transactions on Machine Learning Research (11/2023)
logistic regression case. For given X,, denote Y the most probable label for the input, i.c. Y, 1 if Yout (X,, wo) > 1/2, and Y; = 0 hehwwseee. As explained, in this setting, GraNd is equivalent to using the score function g(2)) = -|Y; - Your (X4; wo)l. For a given value of r, consider q" the yoh quantile of g(2).
Notice that g(Z) Σ q" if and only if
( [Houe
2) or (womu(xssw)) (X;: wo) 2
1
1 2 o' and y, + *v,,,
(Xi (1; mo)
S 9-
2
Condition
Condition
Therefore, the signal acceptance region is the union of two disjoint sets. The first set is composed of all samples that are close to the decision boundary, i.e. samples for which the true conditional probability Your (X;; wo) is close to 1/2. The second set is composed of samples that are further away from the decision boundary, but the realized labels need to be the least probable ones (Y: o YJ)- These two subsets are visible in Figs. 5 and 8 for 70% and even more for = 50%. The signal points can be divided into two sets:
the set of points close to the boundary line y = --, where the colors match the original configurations (mostly blue points under the line, red points over the line)
2. the set of points far away from the boundary line, for which the colors are swapped (only red under the line, blue over the line).
Hence, the signal subset corresponding to Condition 1 gives valuable insights; it provides finer-grained visibility in the crit- ical region. However, the second subset is unproductive, as it
10
min (ww (z)
10a
only retains points that are not representative of their region. Calibration allows mitigating the effect of the second subset while preserving the benefits of the first subset; in Fig. 7, we can that the calibrated GraNd outperforms random pruning average
10
((w:)
10
r=0.1
(which corresponds to the two to three times fewer data to achieve the same generaliza- tion error. However, as r becomes lower, '²' will eventually fall under -1/2, and the first subset becomes empty (for example, 0.2 in Fig. 8). Therefore, when r becomes small, GraNd does not bring valuable information anymore (for this particu- lar setting). In Fig. 9, we compare GraNd and Calibrated GraNd (with the exact protocol) to Random with 10%. We can see that thanks to the calibration protocol, the performance gap will indeed vanish if enough data is available. However, Random pruning perporosms both versions of GraNd at this compression level. This underlines the fact that for high compression levels, (problem-spccific) high- quality pruning algorithms and score functions are required. Given the difficulty the task, we believe that in the high compression regime (r < 10% here), one should allocate larger budget to random exploration (take smaller values of a).
curve), requiring
10
calibrated r=0.1
r=1
10
10a
10a
10a
105
10s
Figure 9: Evolution of the performance gap for small value 0.1 for GraNd and its calibrated version with = 90%.
14

---

Published in Transactions on Machine Learning Research (11/2023)
5.2 Scaling Laws with Neural Networks
Random
GraNd
The distribution shift is the primary cause of the observed alteration in the loss function, resulting in the emergence of new minima. Gradient descent could potentially converge to a bad minimum, in which case the performance significantly affected. To illustrate this intuition, we report in Fig. 10 the observed scaling laws for three different synthetic datasets. Let Nerain 10%, Nteat 3-104, d 1000, and m = 100. The datasets are generated as follows:
Error (9)
Limear
10a
10a
10
10
Callbrated Gra
Non Loniinneereiii Woose
Error (%)
10
30
20
1. Linear dataset: we first generale a random vec- tor W ~ V(0,d-'La Then, we generate Nerain training samples and Niest test samples with the rule y = 1 (WTx>0)) where Rd is simulated from (N0,, Ta).
10a
10a
10a
10a
10a
10f
s9
Error (%)
NenLinear
10'
10a
10* Subset size
16'
10
10a
2. NonLinear datasct (Non-lincarity): we first gen- erate a random matrix Win (N,0, d=1 laxm) E Rdxm and a random vector Wout ~ (0, m mm) The samples are then generated with the rule = (Wo.. T)) where E Id is simulated from (00, Ta); and @ is the ReLU activation function. 9
Subset size
Subset size
Test error on a 3-layers MLP (details are provided in Appendix D) on diffcrent pruned datasets for compression levels r E {0.1, 0.2, 0.4, 0.8, 1} where the pruning procedure is performed with Random prun- ing GraNd. The case ing, In all the experiments, the network is trained until convergence.
Figure 10:
corresponds to prun-
3. Nomlánear+NNiis dataset: we first generate a random vector W ~ (0 La). Then, we generate Ntrain training samples and Ntest test samples with the rule y (s0n(TT=4033))0) where x Rdd simulated from (0, Ia) and is simulated from N 1) and 'sin' refers to the sine function.
In Fig. 10, compare the test error of 3-layers MLP trained on different subsets generated with either Random pruming, GraNd. As expected, with random pruning, the results are consistent regardless of the compression level as long as the subset size is the same. With GraNd however, the results depend on the difficulty of the dataset. For the linear dataset, it appears that we can indeed beat the power law scaling, provided that we have access to enough data. In contrast, GraNd seems to perform poorly on the nonlinear and noisy datasets the high compression regime. This is due to the emergence of new local (bad) minima as r decreases as evidenced in Fig. 1. Calibrated with the exact protocol, GraNd becomes valid: we can see that at any compression rate, the error converges to its minimum, which was not the case for 20%. Whether calibration protocols allow data pruning algorithms to beat the power law scaling remains however open question: further research is needed in this direction. It is also worth noting that for the Nonlinear datasets, the scaling law pattern exhibits multi-phase behavior. For instance, for the Nonlinear+ dataset, we can (visually) identify two phases, each one of which follows a different power law scaling pattern.
5.3 Image Tasks
Through our theoretical analysis, we have concluded that SBPA algorithms are generally non-consistent. This effect is most pronounced when the compression level is small. In this case, the loss landscape can be significantly altered due to the change in the data distribution caused by the pruning procedure. Given SBPA algorithm, we argue that this alteration in distribution will inevitably affect the performance of the model trained on the pruned subset, and for small r, Random pruning becomes more effective than the SBPA algorithm.
9The ReLU activation function is given by Ø(2) max(2,0) for R. Here, we abuse the notation bit and write
d(z) (6(z1)... ..., ((zm)) for (#1...., Em) Rm.
15

---

Published in Transactions on Machine Learning Research (11/2023)
In the following, we empirically investigate this behaviour. We evaluate the performance of different SBPA algorithms from the literature and confirm our theoretical predictions with empirical evidence. We consider the following SBPA algorithms:
GraNd (Paul, Ganguli, and Dziugaite, 2021): with this method, given a datapoint 2 (z. y), the score function g is given by g(2) Em, W. w,), 2)1?, where yout is the model output and Wi are the model parameters (e.g. the weights in a neural network) at training step t, and where the expectation is taken with respect to random initialization. GraNd selects datapoints with the highest average gradient norm (w.r.t to initialization..
in this method, the score function is designed to cap- ture the uncertainty of the model in assigning a classification label to a given datapoint 10 Different metrics can be used to measure this assignment uncertainty. We focus here the entropy approach in which case the score function g is given by g(z) Ei Px(x) log(p:(z)) where p,(2)) is the model output probability that x belongs to class i. For instance, in the context of neural networks, we have (pi (x)))) = Softmax(Bour(1, wy)), where is the training step where data pruning is performed.
Uncertainty 2000eman2220Uucertainnn,
DeepFool (Ducoffe and Precioso, 2018): this method is rooted in the idea that in a classification problem, data points that are nearest to the decision boundary are, in principle, the most valuable for the training process. While closed-form expression of the margin is typically not available, the authors use heuristic from the literature on adversarial attacks to estimate the distance to the boundary. Specifically, given datapoint 2 (I, v), perturbations are added to the input x until the model assigns the perturbed input to a different class. The amount of perturbation required to change the label for each datapoint defines the score function in this case (see (Ducoffe and Precioso, 2018) for more details).
We illustrate the limitations of the SBPA algorithms above for small r, and show that random pruning remains strong baseline in this case. We further evaluate the performance of our calibration protocols and show that the signal parameter a can be tuned so that the calibrated SBPA algorithms outperform random pruning for small r. We conduct our experiments using the following setup:
Datasets and architectures. Our framework is not constrained by the type of the learning task or the model. However, for our empirical evaluations, we focus classification lasks with neural network models. We consider two image datasets: CIFAR10 with ResNet18 and CIFAR100 with ResNet34. More datasets and neural architectures are available in our code, which is based on that of Guo, B. Zhao, and Bai, 2022. The code to reproduce all our experiments will be soon open-sourced.
Training. We train all models using SGD with a decaying learning rate schedule that was empirically selected following grid search. This learning rate schedule was also used in Guo, B. Zhao, and Bai, 2022. More details are provided in Appendix D.
Selection epoch. The selection the coreset can be performed at differnt training stages. We consider data pruning at two different training epochs: 1, and We found that going beyond epoch 5 (c.g., using a selection epoch of 10) has minimal impact on the performance as compared to using selection epoch of 5.
Pruning methods. We consider the following data pruning methods: Random, GraNd, DeepFool, Uncertainty. In addition, we consider the pruning methods resulting from applying the proposed exact calibration protocol to a given SBPA algorithm. We use the notation SBPA-CP1 to refer to the resulting method. For instance, DeepFool-CP1 refers to the method resulting from applying (EC) to DeepFool.
Joncertaanty specifically designed be used for classification tasks. This means that it not well-suited for other types of tasks, such as regression.
16

---

Published in Transactions on Machine Learning Research (11/2023)
EC, se=1
EC, se=5
EC, se=1
EC, se=5
70
70
80
60
60
70
70
GraNd
GraNd
50
60
EC (diff ds)
Random
Random
EC [diff as!
40
Random
EC (diff as)
40
EC (diff es) Random
GraNd
GraNd
GraNd
GraNd
40
30
0.2
0.4
0.2
0.1
0.2
0.2
0.4
rackic
70
90
90
80
DeepFool
60
DeepFool
50-
70
FC: (diff ds)
FC [diff as)
EC (diff ds)
EC (diff ds) Random
60
Random
50
Random
40
Random
40
DeepFool
DeepFool
DeepFool
DeepFool
50
40
0.2
0.2
0.4
0.2
0.4
0.2
0.4
70-
70
90
80
80
Uncertainty
60
Uncertainty
60
Random
EC (diff ds)
Random
EC [diff ds!
40
EC (diff as)
Random
40
EC (ditf as)
Random
40
Uncertainty
50
Uncertainty
Uncertainty
Uncertaintyy
0.2
0.2
0.2
(a) ResNet18 on CIFAR10
(b) ResNet34 on CIFAR100
Figure 11: Test accuracy for different pruning methods, fractions r, signal parameters a, and selection epochs (se 1 5). Confidence intervals based on 3 runs are shown.
Poor performance of SBPA in the high compression regime: Fig. 11 shows the results of the data pruming methods described above with ResNet18 on CIFAR10 and ResNet34 on CIFAR100. As expected, we observe a consistent decline in the performance of the trained model when the compression ratio r is small, lypically the region r < 0.3. More importantly, we observe that SBPA methods (GraNd, DeepFool, Uncertaintyin orange) perform consistently worse than Random pruning (in green), confirming our hypoth- esis. We also observe that amongst the three SBPA methods, DeepFool is generally the best in the region of interest of and competes with random pruning when the subset selection is performed at training epoch 1. We noticed that in that setting DeepFool is close to random pruming.
Effect of the calibration protocol Our proposed calibration protocol aim to correct the bias by injecting some randomness in the selection process and keeping (on average) only a fraction a of the SBPA method. We notice that the calibration protocol applied to different SBPA consistently boosts the performance in the high compression regime, as can be observed in Fig. 11. Fig. 12 shows that the calibratod SBPA perform better than Random pruning for specific choices of a. However, the difference not always significant. Besides, finding the optimal proportion of signal be difficult in practice.
17

---

Published in Transactions on Machine Learning Research (11/2023)
EC, se=1
EC, se=5
EC, se=1
EC, se-5
90
60
85
85
GraNd
GraNd
50
80
80
40
75
Random best
75
Random
Random
Random best
best
30
best
30
0.1
0.2
0.3
0.1
0.1
0.2
0.3
0,4
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
90
90
DeepFool
DeepFool
85
50-
80
75
40
40
75
Random
Random
-B. Random
-
Random
best
/0-
best
30
best
30
best
0.1
0.2
0.4
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
Uncertainty
60
Uncertainty
85
80
80
40
40
Random
75
Random
Random best a
-
Random
20
bes:
best
30
30
best
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
(a) ResNet18 on CIFAR10
(b) ResNet34 on CIFAR100
Figure 12: Test accuracy for different pruning methods, fractions r, and selection epochs (se 1 or 5). Best used for calibration. Different values of may have different values.
6
Related Work
As mentioned in the introduction. The topic of coresct selection has been extensively studied in classical machine learning and statistics (Welling, 2009; Chen, Welling, and Smola, 2012; Feldman, Faulkner, and Krause, 2011; Huggins, Campbell, and Broderick, 2016; Campbell and Broderick, 2019). These classical approaches were either model-indopendent or designed for simple models (c.g. lincar modcls). The recent advances in deep learning has motivated the need for new adapted methods for these deep models. Many approaches have been proposed adapt to the challenges of the deep learning context. We will cover existing methods that are part of our framework (SBPA algorithms) and others that fall under different frameworks (non-SBPA algorithms).
6.1 Score-based Methods
These can generally be categorized into four groups:
Geometry based methods: these methods are based on some geometric measure in the feature space. The idca is to remove redundant examples this feature space (cxamples that similar representations). Examples include Herding ((Chen, Welling, and Smola, 2012)) which aims greedily select examples by ensuring that the centers of the coreset and that of the full dataset.
18

---

Published in Transactions on Machine Learning Research (11/2023)
close. A similar idea based on the K-centroids of the imput data was used in (Sener and Savarese, 2018; Agarwal et al., 2020; Sinha et al., 2020).
Uncertainty based methods: the aim of such methods is to find the most "difficult' examples, defined as the ones for which the model is the least confident. Different uncertainly measures can be used for this purpose, see (Coleman et al., 2020) for more details.
3. Error based methods: the goal is to find the most siguificant examples defined as the ones that contribute the most to the loss. In Paul, Ganguli, and Dziugaite, 2021, the authors consider the second norm of the gradicnt as a proxy to find such examples. Indoed, examples with the highost gradient norm tends to affect the loss more significantly (a first order Taylor expansion of the loss function can explain the intuition behind this proxy). This can be thought of as a relaxation of Lipschitz-constan based pruning algorithm that was recently introduced in Ayed and Hayou, 2022. Another method consider keeping the most forgettable examples defined as those that change the most often from being well classified to being mis-classified during the course of the training (Toneva et al., 2019). Other methods in this direction consider a score function based on the relative contribution of each example to the total loss over all training examples (see Bachem, Lucic, and Krause, 2015; Munteanu et al., 2021).
4. Decision boundary based: although this can be encapsulated in uncertainty-based methods, the idea behind these methods is more specific. The aim is to find the examples near the decision boundary, the points for which the prediction has the highest variation (e.g. with respect to the input space, Ducoffe and Precioso, 2018; Margatina et al., 2021).
6.2 Non-SBPA Methods
Other methods in the literature select the coreset based on other desirable properties. For instance, one could argue that preserving the gradient is an important feature to have in the coreset as it would lead to similar minima (Killamsetty, Sivasubramanian, Ramakrishnan, De, et al., 2021; Mirzasoleiman, Bilmes, and Leskovec, 2020). Other work considered the problem of corset selection as a two-stage optimization problem where the subset selection can be seen also as an optimization problem (Killamsetty, Sivasubrananian, Ramakrishnan, and Iyer, 2021; Killamsetty, X. Zhao, et al., 2021). Other methods consider conisder the likelihood and its connection with submodular functions in order to select the subset (kaushal2021priss) Kothawade et al., 2021).
It is worth noting that there exist other approaches to data pruning that involve synthesizing new dataset with smaller size that preserves certain desired properties, often through the brute-force construction of samples that may not necessarily represent the original data. These methods are known as data distillation methods (see c.g. Wang et al., 2020; B. Zhao, Mopuri, and Bilen, 2021; B. Zhao and Bilen, 2021) However, these methods have significant limitations, including the difficulty of interpreting the synthesized samples and the significant computational cost. The interpretability issue is particularly these approaches to use in real-world applications, particularly in high-stakes fields such as medicine and financial engincering.
7 Discussion and Limitations
7.1 Extreme Scenarios
Our framework provides insights in the case where both n and rn large. As a result, there are cases where this framework is not applicable. We call these cases extreme scenarios.
Extreme scenario 1: small n. Our asymptotic analysis can provide insights when a sufficient number of samples are available. In the scarce data regime (small n), our thcoretical results may not accurately reflect the impact of pruning on the loss function. It is worth noting, however, that this case is generally not of practical interest as there is no benefit. to data pruning when the sample size is small.
19

---

Published in Transactions on Machine Learning Research (11/2023)
Extreme scenario 2: large n with ()) In this case, the "effective" sample size after pruning is rn (1). Therefore, we cannot glean useful information from the asymptotic behavior of 4 in this case. It is also worth noting that the variance of L2-" does not vanish in the limit - oc, - with rn = y fixed, and therefore the empirical mean does not converge to the asymptotic mean.
7.2 Asymptotic Results
Theorem 1 and 2, and the subsequent corollaries are asymptotic results. They essentially reveal the limita- tions of SBPA for "large enough models'. We decided to take this direction to get results that are general as possible, showing that the discussed limitations will appear in most situations. Theorem I and 2 apply to any configuration from a large variety of classes of models, SBPAs, gencrating processes, and loss functions. The theory readily covers realistic architectures illustrated by Corollary 3, 4 and 5 (in the appendix) that cover wide NN, deep neural NN, and convolutional NN with enough filters. However, these limitations could appear for unrealisticalyy large models. We acknowledge this drawback of the proposed theory and address it in two ways. First, experimentally show that for the usual settings (ResNet on Cifar), already observe this significant drop in the performance of SBPAs compared to random pruning. This also aligns with other empirical observations (Guo, B. Zhao, and Bai, 2022). In addition, we provide Theorem 3 to cover the cases where the class of functions is potentially not rich enough; even in that case, for any SBPA, one can find datasets for which the pruning algorithm will fail for small compression ratios. Besides, to our knowledge, the lines of work that allow one to derive explicit bounds for Neural Networks usually require specific and often overly simplistic architectures (typically one hidden layer feed-forward). In our context, we additionally expect similar strong restrictions to be required for the SBPAs and generating processes. This could wrongfully lead practitioners to consider that using different SBPA class of models than the one for which one could derive quantitative results would circumvent the limitations.
7.3 Overparameterized Regime
The scenario in which both the number of parameters p and the sample size n tend to infinity (e.g. with a constant ratio ? = -p/n) holds practical significance. Our framework does not cover this case and we would like to elucidate the main point at which our proof machinery encounters challenges under this scenario. The main issue resides in understanding the asymptotic behaviour of SBPA algorithms in this context, particularly the extension of Proposition 3. While we can establish concentration with constant and n growing large, achieving this with both n and p going to infinity, especially when the underlying model is a neural network, becomes generally intractable. Nonetheless, under certain supplementary assumptions, it remains feasible to demonstrate concentration.
Recall that in Proposition in the infinite sample size limit (n + xo), while (and consequently, w) is fixed. However, in the scenario where both p and n tend to infinity, the dependency of w on p complicates matters, rendering the used variation of the LLN inapplicable. An essential condition under such circumstances becomes the convergence of w in a cortain sense as well, as p - co. For this purpose, a pertinent tool is LLN for Triangular Arrays, which takes the shape of:
essentially
variation of the law of large numbers to show the convergence
Consider a Triangular Array (Xn,))efm) of random variables such that for each n, the variables (Xn,))ieji) are ädd with meon pa- Then, under some assumptions (bounded second moments) have
12 Xn,s
n
Un 00.
However, note that our case, the terms X,,i ((yout(X, Y.)1 accepted) are not nccessarily indo- pendent, and therefore more advanced LLN for trinagular arrays should be proven and used. We leave this for future work.
20

---

Published in Transactions on Machine Learning Research (11/2023)
7.4 Pruning Time Vs Training Time
In some cases, the pruning procedure might be compule-intensive, and requires more resources than the actual training with the full dataset. This is the case when, for instance, the pruning criterion depends on socond order geometry (Hessian etc) and/or multiple perturbations of some quantity (DeepFool), or pruming is performed in multi-shot settings (dynamical pruning). In this paper, we considered pruning criteria that can be performed "one shot" and rely on criteria that involve either gradients (GraNd) or network outputs (Uncertainty) or perturbations of the network output (DeepFool). For GraNd and Uncertainty pruming, the pruning time is typically less than the time required for 1 epoch of training. For DeepFool however, the pruning time might be comparable to 10 epochs of training.
References
Agarwal, S., H. Arora, S. Anand, and C. Arora (2020). "Contextual Diversity for Active Learning". In: European Conference on Computer Vision.
Aljundi, R., M. Lin, B. Goujand, and Y. Bengio (2019). "Gradient Based Sample Selection for Online Continual Learning". In: Advances in Neural Information Processing Systems. Arkhangel'skii, A. V. (2001). "Fundamentals of General Topology: Problems and Exercises". In: pp. 123 124. Ayed, F. and S. Hayou (2022). "The Curse of (non) (nonexxny:;;y: The Case of an Optimization-Insphe Data Pruning Algorithm". Tn: I Can't Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification.
Bachem, O., M. Lucic, and A. Krause (2015). "Coresets for Nonparametric Estimation the Case of DP- Means", In: International Conference on Machine Learning.
Campbell, T. and T. Broderick (2019). "Automated Scalable Bayesian Inference via Hilbert Coresets". In: The Journal of Machine Learning Research 20.1, pp. 551-588.
Chen, Y., M. Welling, and Smola (2012). Super-Samples from Kernel Herding. arxiv: 1203.3472 [cs LG]. Coleman, C., C. Yeh, S. Mussmann, В. Mirzasoleiman, P. Bailis, P. Liang, J. Leskovee, and M. Zaharia (2020). "Selection via Proxy: Efficient Data Selection for Deep Learning". In: International Conference Learning Represendations.
Deimling, K. (2010). Nonlinear Functional Analysis. Courier Corporation.
Ducoffe, M. and F. Precioso (2018). Adversarial Active Learning for Deep Networks: a Margin Based Ap- proach. Xiv: 1802. 09841 [cs.LG].
Feldman, D., M. Faulkner, and A. Krause (2011). "Scalable Training of Mixture Models via Coresets". Tn: Advances in neural information processing systems 24.
Guo, C., B. Zhao, and Y. Bai (2022). DeepCore: Comprehensive Library for Coresel Selection in Deep Learning. arXiv: 2204. 08499 [cs.LG].
Hemaaddzz, D., J. Kaplan, T. Henighan, and S. McCandlish (2021). Scaling Laws for Transfer. arXiv: 2102.
01293 [cs. LG].
Hestness, J., S. Narang, N. Ardalani, G. Diamos, H. Jun, H. Kianinejad, M. M. A. Patwary, Y. Yang, and Y. Zhou (2017). Deep Learning Scaling is Predictable, Empirically, arXiv: 1712. 00409 (cs.LG),
Hoffmann, J., S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. de las Casas, L. A. Hen- dricks, J. Welbl, A. Clark, T. Hennigan, E. Noland, K. Millican, G. van den Driessche, B. Damoc, A. Guy, S. Osindero, K. Simonyan, E. Elsen, O. Vinyals, J. W. Rae, and L. Sifre (2022). "An Empirical Analysis of Compute-optinal Large Language Model Training". In: Advonces in Newral Information Processing Systems.
Hornik, K. (1991). " "Approximation Capabilities of Multilayer Feedforward Networks". In: Neural Networks 4.2, pp. 251 257.
Huggins, J., T. Campbell, and T. Broderick (2016). "Coresets for Scalable Bayesian Logistic Regression", In: Advances in Neural Information Processing Systems 29.
Kaplan, J., S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu,, and
D. Amodei (2020). Scaling Laws for Newral Language Models. arXiv: 2001. 08361 [Cs.LG]. Kidger, P. and T. Lyons (2020). "Universal Approximation with Deep Narrow Networks". In: Conference on learning theory, pp.
21

---

Published in Transactions on Machine Learning Research (11/2023)
Killamsetty, K., D. Sivasubramanian, G. Ramakrishnan, A. De, and R. K. Iyer (2021). "GRAD-MATCH. Gradient Matching based Data Subset Selection for Efficient Deep Model Training". In: International Conference on Machine Learning.
Killamsetty, K., D. Sivasubramanian, G. Ramakrishnan, and R. Iyer (2021). "GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning". In: Proceedings of the AAAI Conference on Artificial Intelligence.
Killamsetty, K., X. Zhao, F. Chen, and R. Iyer (2021). RETRIEVE: Coreset Selection for Efficient and Robust Semt- Supervised Learning. arXiv: 2106. 2106.07760 [cs.LG].
Kingma, D. P. and J. Ba (2017). Adam: A Method for Stochastic Optimization. arXiv: 1982 [cs LG]. Kothawade, S. N., N. A. Beck, K. Killamsetty, and R. K. lyer (2021). "SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios". In: Advances in Newral Information Processing Systems.
Margatina, K., G. Verníkos, L. Barrault, and N. Aletras (2021). Active Learning by Acquiring Contrastive Examples. arXiv: 2109. 03764 [ca.CL].
Mirzasoleiman, B., J. Bilmes, and J. Leskovee (2020). "Coresets for Data-efficient Training of Machine Learning Models". In: International Conference on Machine Learning, pp. 6950 6960.
Munteanu, A., C. Schwiegelshohn, C. Sohler, and D. P. Woodruff (2021). On Coresets for Logistic Regression.
arXiv: 1805.08577 [cs.DS]
Paul, M., S. Ganguli, and G. K. Dziugaite (2021). "Deep Learning on a Data Diet: Finding Important Examples Early in Training". In: Advances in Neural Information Processing Systems.
Robbins, H. and S. Monro (1951). "A Stochastic Approximation Method". In: The annals of mathematical statistics, pp. 400-407.
Rosenfeld, J. S., A. Rosenfeld, Y. Belinkov, and N. Shavit (2020). "A Constructive Prediction of the Gener- alization Error Across Scales". In: International Conference on Learning Representations.
Sener, O. and S. Savarese (2018). Active Learning for Convolutional Neural Networks: A Core-Set Approuch. arXiv: 1708. 00489 [stat. M.].
Sinha, S., H. Zhang, A. Goyal, Y. Bengio, H. Larochelle, and A. Odena (2020). "Small-GAN: Speeding up
GAN Training using Core-Sets", In: International Conference on Machine Learning.
Sorscher, B., R. Geirhos, S. Shekhar, S. Ganguli, and A. S. Morcos (2022). "Beyond Neural Scaling Laws:
Beating Power Law Scaling via Data Pruning". In: Advances in Neural Information Processing Systems. Toneva, M., A. Sordoni, R. T. des Combes, A. Trischler, Y. Bengio, and G. J. Gordon (2019). An Empirical Study of Example Forgetting during Deep Neural Network Learning, arviv: 1812. 05159 [cs LG]. Varadarajan, V. S. (1958). "On the Convergence of Sample Probability Distributions". In: Sankhyā: The Indian Journal of Statislies (1933-1905) 19.1/2, pp. 23 26.
Wang. T., J.-Y. Zhu, A. Torralba, and A. A. Efros (2020). Dataset Distillation. Xiv: 1811.10959 [cs LG]. Welling, M. (2009). "Herding dynamical weights to learn". In: Proceedings of the 26th Annual International Conference Machine Learning, pp. 1121-1128.
Zhai, X., A. Kolesnikov, N. Houlsby, and L. Beyer (2022). "Scaling Vision Transformers". In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
Zhao, B. and H. Bilen (2021). "Dataset. Condensation with Differentiable Siamese Augmentation". In: Inler- national Conference on Machine Learning.
Zhao, B., K. R. Mopuri, and H. Bilen (2021). "Dataset Condensation with Gradient Matching". In Inter- national Conference on Learning Representations.
Zhou, D.-X (2020). *Universality of Deep Convolutional Neural Networks". In: Applied and computational harmonic analysis 48.2, pp. 787 794.
8 Acknowledgement
We would like to thank the authors of DeopCore project (Guo, B. Zhao, and Bai, 2022) for open-sourcing their excellent ". The high flexibility and modularity of their code allowed us to quickly implement our calibration protocols on top of existing SBPA algorithms.
The code by Guo, Zhao, and Bai, 2022 is availahle at http:://ggttaaacccmm/////ttttttt
22

---

Published in Transactions on Machine Learning Research (11/2023)
A Proofs
A.1 Proofs of Section 2
Propositions and 2 are built on the following lemma.
Lemma 1 Let a be a distribution on D and (Wn)n a sequence of parameters in We satisfying
( ( min T (X; Y). wEWo
Then, comes that
d (wn W (T)) +
Proof:
Denote on the function from Wo to IR defined by
(w) R2 (Xx
Notice that under assumptions, the dominated convergence theorem gives that 4r is continuous. This lemmn is simple consequence of the continuity of Li and the compacity of Wa. Consider sequence (w.)
such that
Cx (ww)) 7 min (w)). wEWs
We can prove the lemma by contradiction. Consider e and assume that there exists infinitely many indices ne for which d( ((w.. (Tr) 6. Since Wo is compact, we can assume that Wng is convergent (by considering a subsequence of which if needed), denote woo E We its limit. The continuity of d then gives that d( Use WT(+)) 2 and in particular
we & (T) = argmin Ca Cur (w). But since o is continuous, the initial assumption on (wa) translates to
min (x(w) = lim L.g (wn)) fox (woc); wEW
concluding the proof.
Proposition 1. pruning algorithm A is valid at a compression ratio r E (0, 1] if and only if
df Ar, (o(w) - a.s.
where W2( = argmin Wi (ww) C. We and d WArr Wa(w)) denotes the euclidean distance from the point WAr to the set (z).).
Proof: This proposition is direct consequence of Lemma 1. Consider valid pruning algorithm A, compression ratio and sequence of observations (X,, Ys.) such that
[(wA")) + min L(w). wEWs
We can apply Lemma on the sequence (wA.r) with the distribution ग to get the result.
Proposition 2. Let A be a pruning algorithm and r E (0,1] a compression ratio. Assume that there exists a probability measure Vy on such that
Vw E Wo, (w) - E(yout (X:w), Y) a.s. Then, denoting W7 (v,) = argmin Ey, Eyoou (X; w)) Y) C Wo, we have that
(5)
d( ww Wo(v)) + 0 a.s.
23

---

Published in Transactions on Machine Learning Research (11/2023)
Proof: Leveraging Lemma 1, it is enough to prove that
Ev Eyoue (X; w2."", min Ey, (yyoc Y) - 0 a.s.
we
To simplify the notations, we introduce the function from Wo to defined by
f(z, w) e(your w), y).
where z (x, v). Since We is compact, we can find w" Wo such that Ev, (z), min, Ev, (2, w)]. It comes that
0 Eu,[f(z, wp(""]] ]]] Ev, [f(2,
S Eg, [f,, wx(")]]
Σ
f(z, wArr)
r
=EA(Dn.r)
Σ
[2, (.
[(z
m =EA(Dm.))
1
E
f(z,w)) Ev, (f(z,
m
=E.(Da.T)
The last term converges to zero almost surely by assumption. By definition of wa'r, the middle term is non-positive. It remains to show that the first term also converges to zero. With this, we can conclude that lim, E,, wA-")] E,, [f w²)] ())
To prove that the first term converges to zero, we use the classical result that if every subsequence of a sequence (u,) has further subsequence that converges to u, then the sequence (un) converges to u. Denote
Un [f(, wA))
f(z, (Ar) =E.(D...))
Σ
By compacity of We, from any subsequence of (un) we can extract further subsequence with indices denoted (mg) such that wh converges to some woo Wg. We will show that (mm,) converges to 0. Let >> 0, since f is continuous on the compact set D x Wo, uniformly continuous. Therefore, almost surely, for large enough,
sup suplf(z, wh,) - f(, woo) Se.
Denoting
U/ = Ev, (f Woo)]
1
Σ
rn. zEA(D...))
the triangular inoquality then gives that, almost surcly, for k large enough
|ine Unal S 2e.
By assumption, the sequence Uny converges to zero almost surely, which concludes the proof. We now prove Corollary 2, since Corollary is a straightforward application of Proposition 2. Corollary 2. Let A any pruning algorithm and r E (0, 1], and assume that (5) holds for a given probability mensure v, on D. A valid, then Wi (v,) n Wj( (μ4) # 0;; or, equivalently,
min ((w)
min C(w).
WEW; (v+)
wEW
24

---

Published in Transactions on Machine Learning Research (11/2023)
Proof: This proposition is direct consequence of Proposition 2 that states that
d(wn (V+)) + a.s.
Since the C is continuous on the compact We, it is uniformlly continuous. Hence, for any >> O, we can find 7) such that if d(w, w') S 7, then [C(w) -(w")l for any parameters w, w Wg. Hence, for n large enough, d(wrr (v,) 77, leading to
((wn))) 2
min L(w) - (rW,(r)
Since the algorithm is valid, we know that L(wz converges minmew, L(w) almost surely. Therefore, for any >> 0,
min C(w) min L(w) wEW,
(EW?(r)
which concludes the proof.
A.2 Proof of Proposition 3
Proposition 3. AAsymptotic behavior of SBPA]
Let A be a algorithm and let 9 be its corresponding score function. Assume that g adapted, and consider compression ratio E (0, 1). Denole by q' the 4th quantile of the random variable g(Z) where Z μ. Denote A, {2 E D g(2) )²). Almost surely, the empirical measure of the retained data samples converges weakly to EMM,, A,, where MIA, is the restriction of μ to the set Ar. In particular, have that
Vu E Wo, (w) - Ev, E(yout (X;w), Y) a.s.
Proof:
Consider F the set of functions f:D - [-1,]] that are continuous. We will show that
Σ f(z) 1 1 f(z))(22dz + a.ss a.s. A_
sup /EF A((D,, r)
(9)
sEA(D...))
To simplify the notations, and since [A(D..r) converges to 1, we will assume that rn is an integer. Denote o the (rn)th ordered statistic of (g(z:) ( = and q" the th quantile of the random variable g(Z) where
Z ~ p.
We can upper bound the left hand side in equation (9) by the sum two random terms A, and B, defined by
B,
sup T fEr
Σ
f())
Σ
f())
n
n 2ED.
2ED.
Σ
f(2) - f())) u(z)dz
Cn sup
r JEF
=ED
To conclude the proof, will show that both terms converge to zero almost surely.
25

---

Published in Transactions on Machine Learning Research (11/2023)
For any F, denoting Gn the empirical cumulative density function (cdf) of (g(24)) and G the edf of g we have that
I 71
Σ
f())))(=)500
1 Σ 71 SEDn
f()))
[f(2)] x (a(=)) - (o)
RED
- - (()
RED
Gn Gn(g")l
r GGn(d")
(G(g)) Gn(9")].
Therefore, Bn < suPreR G(t Gn (f) which converges to zero almost surely by the Giivenko-Caanelle theorem.
Similarly, the general Glivenko-Cantelli theorem for metric spaces (Varadarajan, 1958) gives that almost surely,
Σ f(z) - - BED,
((=)m(=)dz - 0.
sup fET
Consider & 1. Since g is continuous and D compact, the sets Ar(1-1/k) and A, D Ar are disjoint and closed subsets. Using Urysohn's lemma (Theorem 8 in the Appendix), can find fx. F such that fx(2) 1 if A/11-1/8) and fa(2) 0 if E A,. Consider F, it comes that
Σ [())o / ((s)s 2ED
Σ fx J I(X))))(())d= sED
rra 1/0)g((=)50"
zED
/ Lyro 1 M(z)dz
+
Hence, noticing that Sa E F, we find that
Σ f(z) - / F(E))())de) + +Gnn(g") Gnlg" (1 K
On S SuP
ZED
We can conclude the proof by noticing that |Gm(4") G. " (1-1//1)) converges to and laking k -
A.3 Proof of Theorem 1
In order to prove the theorem, will need a few technical results that state and prove first.
Lemma 2 Consider a set of continuous functions M from X y. Consider vo function the closure of M for the loo norm. Then for any 0, there exists vè M such that
supa.ye (lll(((((())))))) - ((vo(x)) Sc
Since the loss l continuous on the compact y V, is uniformly continuous. We can therefore find y such that for any you v.y/ E y, if bly s < n then ||E(yo. v) E()l.'')l S c. We conclude the proof using by selecting any tp M that is at distance not larger than 7 from v/n for the for norm.
Proof:
26

---

Published in Transactions on Machine Learning Research (11/2023)
Lemma 3 Consider SBPA A. Let M be set of continuous functions from X' to y. Consider (0, () and assume that A is consistent on M at level r, i.e.
V M, r()
Σ
((b()),)) Ex((v(X), a.s.
(..))E((D,r)
Let Do be any measurable function from X to y. there cvists sequence of elements of M that converges poinl-wise to Woo, then
BAMA, (X), Y) = (x)((
(10)
porticular, if M has the universal approzimation property, then (10) holds for any continuous function.
Proof: Le (th)a be sequence of functions in M that converges point-wist th Consider 0, since A is consistent and that th is continuous and bounded, Proposition gives that
E Ea l (xx(X), E (1h (X),
Since is bounded, we can apply the dominated convergence thcorem to both sides of the equation to get the final result.
O
Proposition 5 hereafter proves the final result for SBPA that do not depend the labels. The proof of Theorem that follows essentially deals with the remaining case of SBPA that depend on the labels.
Proposition 5 Let A be any SBPA with an adapted score function g satisfying
: + g(x, = ī(z) a.s.
Assume that there erists two continuous functions f1 and f2 such that
(x),( + E,
If UgMo has the universal opprozimation property, then there erist hyper-parrmeters 0 E O for which the algorithm is not consistent.
Proof: Consider a compression ratio E 1). We will prove the result by means of contradiction. Assume that the SBPA is consistent on UgMg. From the universal approximation property and Lemma 3, we get that
r E (fi()), E, (f((),))
from which deduce that
Y2 A.) r (()(())))))))))) E2 () e (\4)] (x)(())))
(11)
(12)
and similarly for f2.
Notice that since the score function g does not depend on Y, there exists X, C X such that A, X, x V. Consider the function defined by
( (2() 1(x
-AC Ex))
will show that
E x(f(X),)) (f(X),)
ii) There exists sequence of elements in Ug that converges point-wise almost everywhere to f
27

---

Published in Transactions on Machine Learning Research (11/2023)
The conjunction of these two points contradicts Lemma 3, which would conclude the proof.
The first point is obtained through simple derivations, evaluating both sides of the equation i).
1 Bma L (f(X),)) = () x3)
(E)(((()) (X &x)
= (I) EX)
= T X) e A,)
= ()),,
where we successively used the definition of and equation (11). Now, using the definition of f, we get that
(f(())))) = E) E &2) (f())), Y) 1(X E x,))
= (x(((1()) (,)+,,,((2()) ()T(Z ED) A,)
(10
These derivations lead to
1 F (F, = -1-r) ( (22())
by assumption on f1 and fz.
For point ii), we will construct a sequence (thx); of functions UgMo that converges point-wisc to almost everywhere, using the definition of the universal approximation property and Urysohn's lemma (Lemina in the Appendix). Consider &s 2 0 and denote EN - Denote q" and t the pth and (r+ (g)) quantile of the random variable g(X) where (X,Y) ~ μa. Denote X {x E X 5(x) S )"} and B, = {x E X Dr 2 g= Since is continuous and X' is compact, the two sets are closed. Besides, since the random variable g(X) is contin (g is an adapted score function), both sets are disjoint. Therefore, using Urysohn's 's lemma (Lerma in the Appendix), we can chose a continuous function dy : X' + [0, 1] such that dx(x) = 1 for x E X, and (x(x)) for E By Denote f& the function defined by
fu(x) = f(()))u(z) + fz(2) - (x(x)).
Notice that (ox)& converges point-wisst wise to Il- E Xx), and therefore (fk) converges point-wise to f. Besides, since fo is continuous, and Jg has the universal approximation property, we can chose tha E Ug such that
sup supsexlv<<z)) - [x(())) S cx.
Hence, for any input x X, we can upper-bound bound (x/x(x) f(x) by c + (fa(()) f(x)), giving that thx converges pointwise to and concluding the proof.
We ready to prove the Theorem 1 that state here for convenience.
Theorem 1.
Let A be any SBPA algorithm with an adapted score function. If Ug has the universal approzimation property, then there exist paramepssameters 0 E O for which the algorithm is not consistent.
We will use the universal approximation theorem to construct a model for which the algorithm is biased. Denote supp(μ) the support of the generating measure μ. We can assume that there exists x E such that (mo, 0) supp(u), (wo, 1) E supp())), and g( 1) * g 0), otherwise one can apply Proposition 5 get the result. Denote yo {0, 13 such that g(zo, > g yo). Since g continuous, we can find 0, ro (0, 1) such that
Proof:
Vx B(xo, () g(5, vo)
g 1 -y))
(13)
28

---

Published in Transactions on Machine Learning Research (11/2023)
where 9r is the r quantile of g(Z) where Z ~ p.
Since (Io, 1 - yo) E supp(μ), it comes that
A To P 2(1 + rr)
B(Tu, B(a,,) 1 80 - 1ly001111 1-001-10)). yo) > 0.
-
By assumption, the distribution of X is dominated by the Lebesgue measure, can therefore find positive é' < such that
P p(x x E B( c) B(xo. c'))
A
2 m
The sets K1 (r c') and K₂ = X (o( c) closed and disjoint sets, Lemma 8 in Appendix insures the existance of continuous function h such that h(x)) = yo for E K1, and h(x) = 1- for E K2. We use Lemma 2 to construct & Ug_Ma such that for any z, E D, [((b(z), ((h(z),)) < A/2. Let [1(2, y) = ((b((x)))) y) and f2(2,)) = f(1 yo- 9). Denote f f= =1 f2- Notice that if we assume that the algorithm is consistent on Ug Lemma 3 gives that Ef(X, = - EX,, gcx We will prove the non-consistency result by means of contradiction, showing that. instead we have
1 TO
E Ef(x,Y)
(14)
To do so, start by noticing three simple results that are going to be used in the following derivations
Vx E K2,y E v, f(x. v) = 0.
Vx e K1, [(x, un) = -((1 - -yo vo) and f(x, 1 - y0) = E(yo, 1 - yo)
Yx e B(zo. <) B( c)).y E V, (f v) I max
We start be upper bounding the left hand side of (14) follows:
E)(X,Y) (E(XX -xEK, (x
S P(X ToteKi,Y' Y1, yo E(yo: y0)
((XeKi, 1
E(1 - yoo Mo)
+ p(x E B(oo, c) B(E00 e')) max
< P(X ( =1- yo E(vo: yo) + A 2
Using (13), we can lower bound the right hand side of (14) as follows:
1 -Bf(X,
1 E)
AxEK, + (
ro
ro
1 _ E K1,Y =1 1100)) -vo)
7o
SP(x E B(xo,,) t) B((ra,()) max
To
T V = 1 e(00 1 y0) 2
A
To
Ef(XYY)
1 X K1, Y -1 y/ 1( yo)
+
To
1
+ 1/
2
E)(XYY).
where the last line comes from the definition of A.
29

---

Published in Transactions on Machine Learning Research (11/2023)
A.4 Proof of Theorem 2
Denole PB the set of probability distributions on X x {0, 1J, such that the marginal distribution the imput space is continuous (absolutely continuous with respect to the Lebesgue measure on X') and for which
Px x PY 1|X ===]
is upper semi-contimuous. For probability mcasure E PB: denote xx the marginal distribution the input. Denote y the function from [0, 1] [0.1] to R defined by
7(p v) pl(y. 0) (1 p)6(y,
Finally, denote F the set of continuous functions from X' to [0, 1]. We recall the two assumptions made on the loss:
(i) The loss is non-negative and that E(y, v') = 0 if and only if y =
(ii) For p E 1), + 7(p, v) pl(v. 1) + (1 - (v) 0) has unique minimizer, denoted vi E [0, 1], that is increasing with p.
Lemma& 4 Consider a loss & that satisfies (ii). Then, for any p E [0,1] and d > 0, there exists e >> 0 such that for any E y = [0, 1],
<l,y) - 7(p, 17) S = l upl s
1 Proof: Consider E [0 and 7 > 0. Assume that for any ck = k+1 l upl and
there exists yk E y such that
pl(yk: 1) + (1 p)e(y,, 0) pl(u). 1) (1 p)e(U 0) ck
Since y is compact, we can assume that the sequence (yK))s converges (taking, if needed, a sub-soquence of the original one). Denole Yoo this limit. Since l and 1. are continuous, it comes that W wí 2 and
pl(yse, 1) + (1 10-p)pa p)e((Ge, 0) - pe(u,, 1) - -p)((,, 0) = 0,
contradicting the assumption that Vn is unique.
Lemma 5 If tb is a measurable map from X to [0, then there exists a sequence of continuuus functions fn F that converges point- wise to vb (for the Lebesgue measure)
Proof: This result a direct consequence of two technical results, the Lusin's Theorem (Theorem 5 in the appendix), and the continuous extension of functions from a compact set (Theorem in the appendix). O
Lemma 6 For distribution Pn. define + the function from X to [0, 1] by
Vo X, (x(x)) = V)
is measurable. Besides,
inf E,(()) Ex((v((X),))
Proof: The function from [0, 1] to [0, defined by
p argminneeo..1700.00) yp-
is well defined and increasing from assumption (ii) on the loss. It is, therefore, mcasurable. Since Pa x + PY 1|X = æ) measurable, we get that vig is measurable as the composition of two measurable functions. For the second point, notice that by definition of di for any f F,
E, Ex(((()),))
Eny E, (((F(X), x]
> E, E, [(vx(X)) Y) |x] (x),
30

---

Published in Transactions on Machine Learning Research (11/2023)
Using Lemma 5, can take sequence of continuous functions fo F that converge point-wise to dig. We can conclude using the dominated convergence theorem, leveraging that & is bounded.
Lemma 7 Let A a SBPA with an adapted score function that depends on the labels. Then there erists compression level r > 0 and > 0 such that for any fo E F, the two following statements exclude each other
(1) ()) inf E,, (()
(ii) Exl(fo(X), Y) - -if (x)(
the labels, we can find to X in the support of nx such that Pp( Pa = 111X X = mo) E (0, 1) and g(Zp, 0) + g( 1). Without loss of generality, we can assume that g(za, 0) < g 1). Take r E (0, 1) such that
Proof: Since depends
g 0) < o" < g(zo, 1)
By continuity of 9, we can find a radius > 0 such that for any x in the ball (xx) of center and radius T we have that g(r, 0) < q" < g(z, 1). Besides, since Pn is upper semi-continuous, we can assume that v is small enough to ensure that for any x E (x0)),,
Pm(x) < 1 1 Pu( < 1.
(15)
2
Therefore, recalling that vr M
(x, E (x( (X E (xo), Y =0) 0 and Pr, 1 X E B,(xo)) 0.
Pa(X B, (2o)) > O and (Y = X (zo)) 0.
Denote A = PP E (o0)),, 1) > 0. Consider the subset V defined by
V = {x E (20))) 8.1. Pn(x) 2 2
We can derive lower-bound
μ. (V) as follows:
A
p(z)
(20)
/ JOEB,
p(z) M (2 (dx) + SSES p(=)) (dx)
(dxx)
S (20)
A
2 11
>dx)
1 1x (dr)
JZEV
< 2 + (V).
The last inequality gives that x (V) 2 A/2 >. 0. Moreover, we can lower-bound 1z vV((V) using (15) as follows:
(VV vr(V (0))
= nu( x {0))
= I (1 - (=(x))) (dx)
DEV
Pa(Xo)
11" (v(())
2r
4r
A
31

---

Published in Transactions on Machine Learning Research (11/2023)
Therefore, assumptions i) and ti) on the loss give that 1i, (x) 0 and 22)(2) 2 V/ > 0 for any E V. Using
Lemma 4, take ei > 0 such that
(ly, E1 - y - 3
(16)
In the following, we will show that there exists 62 such that for any p 2 A 2
y S
r(p.)) - (p. 2
(17)
Otherwise, leveraging the compacity of the sets at hand, find two converging sequences pt - Poo 2
and yk - You S 3
such that
1
T(ps vk) min (Pk,, 92)
k
Since y is uniformly continuous,
p min (p.15/) y¹
is continuous. Taking the limit comes that
(Poc Moo) - min min yp = =0,
and consequently V/o = Vp... Since Pro 2 4 2:
V
yoo = 1po
U4
3
reaching a contradiction.
Now, take E and 62 satisfying (16) and (17) respectively. Put together, we have that for any p A
(0, v) - (0, vt) S E1 = 7p,,) 7 u 2 E2.
Using the definition of V, it comes that for any function fo and
fo(x)) Se = ((p(()) - (1) 2
(18)
Let E = mmnn((1, 62) 2. (V) > 0. Consider fo E F satisfying 22)
E,, (,, - inf E2, () s..
feF
We will prove that
E,,((6(X)))) - inf Bx((((x)))) >E
JEF
to conclude the proof. Denote Us. is the subset of V such that for any E Uso 700. - 2.( that
2n
We get
e E,, (oo(()))))))) inf E,, e(S(X,)) JEF
/ (t),, - - 7p. (x), ,ht (x))] oz (dx)
/ f0,,)( (dx)
2e
((V u (V \UA)
32

---

Published in Transactions on Machine Learning Research (11/2023)
Hence we get that v (Uro)= 2 2
28 (n2 Since (V( S é1, the right hand side of (18) holds. other words,
Yx E Uo (2), fo(x)) - ((px()), (x))) 22.
from which successively obtain
J ((nn(()) - ((x(()) (x(+) n² (dc) ((p()))))))((()))))))))))))))))) (f)x))) p (dx)
E,P(Jo(X)))) inf (,(((())))) JEF
S.. ((pa(t)) -
4² (Uso)e2
ulUss {0})e2
r Dx (U)))
x (V)
rE2
8.
We can now ready to prove Theorem 2.
Theorem 2. Let A SBPA with adapted score function g that depends the labels. If UgMo has the universal approcimation properly and the loss salisfies assumplions (i) and (t), then there exist two hyper-parumeters 01, 02 E O such that the algorithm is not valid on Wo. U We..
Denote θ θ θ, and for Ū (21,02) E Ô, W We, U Wo, and Mg MMa U Mag- We will leverage Proposition and Lemma 7 show that there exist compression ratio (0, 1) and a hyper- parameter 0 such that
Proof:
min L(w) > min L(w) weW
weW
which would conclude the proof.
Using Lemma 7, we can find and such that for any continuous function So E F,, the two following propositions exclude each other:
(i E) inf yer E) (ii) E,, (,,()))) - jir Ey ()())
Since UMs has the universal approximation property, and that vit and vi, (defined as in Lemma 6) are measurable, we consecutively use Lemma and Lemma 2 to find 0 = (01, 02) such that
There exists v E Ma, such that E,,((v Y) E Y)) Y) < c/2 There exists ui2 E Mag such that E,, (XX),,), E,, lvv, (X), Y) E/22
Take v/, 2/2 MM two such functions. Consider any parameter w E (n By definition, it comes that
E,, E(yout (X; () Ey, ((V,
< E,, 1(12, Y) E,, llbi (X),Y)
< c/2
Therefore, since Lemma gives that En, Ey, llvt, Y), we can conclude that
(o; Y) - inf
(x)(((
FEF
33

---

Published in Transactions on Machine Learning Research (11/2023)
from which deduce that
(X; Y)
inf B (x((f(()))) +e FEF
Exl(v)()) (X), + t/22
W
min [(w') ) + e/2, w w'EWa
which gives the desired result.
A.5 Proof of the Corollaries 3 and
These two corollaries are a straightffrward application of Theorem 1 and Theorem well as the existing literature on the universal approximation properties of Neural Networks: (Hornik, 1991) and (Kidger and Lyons, 2020). We give the proof of the result for wide neural networks. Consider any number of hidden layers H 2 fixed. Denote 0 = (K, R) N x R θ. (Hornik, 1991) implies that U(K,R)Eo FFNNG H. (R) has the universal approximation property. Theorem 1 states that one can find lo = (Ko, Ro) such that the SBPA is not consistent on FFNN H.K, (Ro). Now from the definition of consistency, we get that a SBPA is not consistent on M, then is not consistent on any superset M' that contains M. Therefore, we get the non-consistency result by noticing that
FFNN (Ro) C CFFNNE,
for any K 2 Ko and R 2 Rg. Similarly, Theorem states that there exist 01 (K1, R1) and 02 (K2, R2) such that the model is not valid for any class of model such that
FFNNH, (R1) FFFNNNNK,KKK (R2) M.
We can conclude noticing that FFNNE SFNNHRKE H. (R) satisfies this condition if K 2 max(Ki, K2) and R N max Ry).
A.6 Proof of Theorem 3
For K N denote PK the set of generating processes for K-classes classification problems, for which the input X is a continuous random variable (the marginal of the input is dominated by the Lebesgue measure). and the output Y can take one of K values in y (the same for all Pτ). Similarly, denote PR, the set of generating processcs for regression problems for which both the input and output distributions are continuous. Let. P be any set of generating processes introduced previously for regression or classification (either P = PK for some K, or P = Pn).
Assume that there exist (x1, V1), (I2, U2) D such that
argmin (yout (I1: w). 91) O argmin (Bout (I2; w) y2) 0.
(H1)
For any SBPA algorithm A with adapted criterion, we will show that there exists a generating process μ P for which A is not valid. More precisely, will show that there exists ro E (0,1) such that for any compression ratio S ro, there exists generating process μ P for which A is not valid. To do so, we leverage Corollary 2 and prove that for any S ro, there exists E P, for which Wy(,)) n WF(H) + 0. i.e.
3ro E (0,1), Vr ro. Fp E P s.t. Vu, (Tr)), (,(w)) > min (w)
(19)
weW,
We bring to the reader's attention that = =MA. = =v,(H) depends on and so does the acceptance region A, = Ar()).
The rigorous proof of Thcorem requires careful manipulations of different quantitics, but the idea rather simple. Fig. 13 illustrates the main idea of the proof. We construct a distribution μ with the majority of the probability mass concentrated around point where the value of not minimal.
34

---

Published in Transactions on Machine Learning Research (11/2023)
Select 2, and such that g(4) < g(z))
Put small mass of around 2;
Put the bulk of around Zz
Figure 13: Graphical sketch of the proof of Theorem 3. The surface represents the loss function f(z, w)
E(yout (2), y) in 2D, where = (x, y).
We start by introducing further notations. For z == (I, E D, and w E Wo, we denote by I the function defined by f(z, w) = (1), We will use the generic notation E to refer to the Euclidean norm on the appropriate space. We denote B(X, the & ball with center X and radius p. If X' is a set, then argmin,
B(X, U p). For S c DD denote f w) XEX
Notice that is continuous on Wg. Besides, the set data generating processes is i) convex and ii) satisfies for all Xo D, 8 >> 0 and <1, there exists probability measure μ E E such that
(B((X, 6)) >
These conditions play a central role in the construction of generating process for which the pruning algorithm is not valid. In fact, the non-validity proof applics to any set of generating processes satisfying conditions i) and ii). To ease the reading of the proof, we break it into multiple steps that we list hereafter.
Steps of the proof:
1. For all 20 D, the set Ws, argmin,,,fao. w) is compact (and non empty).
For all 2g DD > 0, there exists Po > such that for all p S Po:
J p). w) C B(W=.:
3. Under assumption (HI), there exists 21, 22 D such that i) g(X1) g(X2) and ii) Ws, n n.z, 0
For 21, 22 as in 3, denote Wi = Wz, and W/ = Wzy- There exists 6, po > 0 such that for any / S Po and wi E B(W1, 6), and wy E W22
f(z, w1) sEB(xa.p)
inf
sup sEB(s2.0)
w(,,w))
5. For any (0, 1), there exits generating process μ P such that any minimizer of the pruned program w. W7 (v,) necessarily satisfies wi, E ((W1, 8) and such that p(B(22, p)) 2 1 - 2r for a given < po-
6. 3ro 0 such that Vr S ro, 3p P such that (y(ww)) min (w for any w (7(r))
35

---

Published in Transactions on Machine Learning Research (11/2023)
Proof: Result 1: Let Ws argmin w) C We. Since Wo is compact and functions fzo I [zo, w) is continuous, it comes that Wzo is well defined, non-empty and closed (as the inverse image of a closed set). Hence it is compact.
Result 2: Let E D and ō > O. We will prove the result by contradiction. Suppose that for any p > 0, there exists w E argmin, f(B(zo. p), w') such that d(w, Wxo) 2 6.
It is well known that since f is continuous and that Wo compact, the function
min (2,ww),
wEWe
is continuous. Therefore, for any &: >> 0, we can find Pk > 0 such that for any z E B(z0, (())
inf f(2, w) - inf f(zo, w)l < 1 k
For every l: > 0, let w 2t such that ** E ((2):Pe), w E argmin, w) and d(w Woo) 2 8. By definition, lim x 20. Since We compact, we can assume that w converges to w without loss of gencrality (taking a sub-sequence of the original onc). Now, notice that
If(= (,r'"")) - inf f(zo, w)l = lnf f(=", w) - inf f(zo, w)l < 1/k,
therefore, since f is continuous, f(zo, w inf f(20, w) and so x Wz,, which contradicts the fact that d(w*, w 2 8 for all k. Hence, we find p > such that for all argmin,, ( p)) C B(W=o:
Result 3: Let 21, 22 in (HI) such that g(21) - g(22). Since d is continuous, and W1 Wa, and W22 Way are compact, d(W, W2) is also compact. Hence, there exists 5 such that
min wi WiW,, WsEWs d(wi, W2) 2 6.
Using the previous result, let p such that argmin,, ( p). w) C B(W,, The triangular incquality yields argmin, ( p). n22 = 6. Since is adapted and B(21, p) has strictly positive Lebesgue measure, we can find z E B(21, p) such that g(=() # g(z)). Therefore, the points z 22 satisfy the requirements.
Result 4: Since Wi is compact and fz, is continuous, f(22, Wi) is compact, and since W1 n W2 0,
min f(22, Wi) > f(22, w() min f(2,,w).
weW.
for any w E Wz. Denote A = min f(22, Wi) - min f22, w) > 0.
Since f is continuous on the compact space D x Wo. it is uniformly continuous. We can hence take ô > 0 such that for 2, z' e D and w, w' E Wa such that
| 2' S 8, ||w w'll 6 - 10(z,w)-(( (('',w')) s A/3.
Using Result 2, we can find po > such that for all p S po:
argmin, (B(21, p), w) C of w) C B(W1,
We can assume without loss of generality that po 28. Let ii E B(W,, For any wi W2, we conclude that
min =EB(2200)
[zz wi) 2 min f(22, Wi) A/3 f(22, + A/3 2 sup ==
f(z, wg).
Result 5: Let Po defined previously, k> 1 and r E (0, 1). Using the uniform continuity of S, we construct
0 < Pk Po such that
Vu 22, E DD,(2,, S Pk [](z,w) s(=', $1/k.
36

---

Published in Transactions on Machine Learning Research (11/2023)
Consider 2² E P such that p² (B(21, 2 and μ² (B(22, Pk)) that u (B)) 2 1 - k- Using proof by contradiction, we will show that there exists & >> 1 such that
1 r/k. Let Dez ur (,") It comes
ar f(z, w) C B(W,
Suppose that the result doesn't hold, we can define a sequence of minimizers wy such that wp e argmin, f(2, w) and d(ww; Wi) 5. Denote M supz, [2z Take any wi W1,
E f2, wx)
Eng f(z, w[)
(20)
1
f(11, w]) +
u4: (B(1, pk)) M(1 (B(1)))
(21)
k
1
M
f(21, +
+
(22)
k)
k
t) +
M
min f(21, w)
(23)
Similarly, we have that
1
Eyg (z, wa)
f(11, wa)
(21,wa)
(B(11,
(24)
7:
1
((11wa))
(1 - 1/k)
(25)
k:
min f(1, 1 (1 1/k).
M
(26)
Putting the two inequalities together, we find
min f(z,, w) 1)) (1 - 1/k) (1-1/k) - (flEs, -110)1111 k. 1) (1 1/h:) < min f(1,, 1) M
Since Wo is compact, we can assurne that lim; w = = E We (laking a sub-sequence of the original one). And since Sa, is continuous, we can deduce that ( = min [(2,, w)) which contradict the fact that d(w", ) > for all k.
Result 6: Let r E 1) and 8, Pu, P. μ as in the previous results. Let E (V,),) From Result 5, we have that W, E B(W,, 8). For wž E W2, Result 5 implics that
min f(2, wp) sup sup f(z, w³)
min,gB((2,Po) [22 w.,) suP f(z, uz)) A
0
Therefore,
[,, w,,
2
min =EB(=2.Po)
J(2, wi) x (((((2,)'))
(27)
I A Ml
sup f(2 + +2) 11 ((B(22.p)) =EB(z2,p6)
(28)
Ez w2) A(1 2r) 2
(29)
min E, (z, w) + A(1 2r) Mr
(30)
Therefore,
(w(w) min Cu(w) 2 A(1 - 2r) 2r
WEW
which is strictly positive for 2(++)
37

---

Published in Transactions on Machine Learning Research (11/2023)
A.7 Proof of Proposition 4
Proposition 4. [Consistency of Exact Calibrattion+SBFA) Let A be a SBPA algorithm. Using the Eract Calibration protocol with signal proportion a, the calibrated algorithm A is consistent if 1 a > 0, i.c the exploration budget is not mull. Besides, under the same assumption - a > O, the calibrated loss is on unbiased estimator of the generalization loss at any finite sample size n > 0,
wW E Wo, Vr E (0, 1), E.Araa = =[w).
Consider < 1. Let f(z,, w) = (Ti, w), Wi), and Pe (Q-iir, independent Bernoulli random variables b; ~ B(pe). Notice that T-ar For i E {I, n). consider the
Proof:
CA - a Σ
by 1 InEA(D.ar)) I (.AA(D).a))) ((z w),
Ps
which gives
E.A.n()) ED, E [ [AAno(w)) Dn] ED.Cn(w) L(w).
Define the random variables
bi A. .. -1) S ((z w), Yn (1eeA(Da
ps
Let Fa,i = o(( + i)) be the o-algebra generated by the random variables {Ynj.ā & i). Let now show that the conditions of Theorem 7 hold with this choice of Yn.i.
Let n 2 and i (l....,n).
n). Similarly to the previous computation, we get that E[Y,, Fn,i] Using the compactness assumption on the space Wo and D, we trivially have that supi,n EY4, n,² < co.
Trivially, for each n 2 1, the variables (Ynihgisn are identically distributed.
Using Theorem and the standard strong law of large numbers, we have that n E' Yn,t + almost surcly, and n Em= f(z,, w) fz, w) almost surely, which concludes the proof for the consistency.
B Technical results
Theorem 4 (Universal Approximation Theorem, (Hornik, 1991)) Let C(X,Y) Y) denote the set of continuous functions from X to Y. Let ó E C(R, R). Then, à is not polynomial if and only if for ev- ery n, m E N, compact K C R", f C(K, RTT), e e> 0, there exist & E N, E R E R C m such that
sup [f(()) yout (x)l Se zek
where Yout Bout(z) (z) CT o(Ax CTAxx +).
Lemma 8 (Urysohn's lemma, (Arkhangel'skii, 2001)) For any two disjoint closed sets and of a topological space X, there exists a real-valued function f, continuous all points, taking the value at all points of A, the value 1 at all points of B. Moreover, for all X, 5 f(x) 11
Thcorem (Lusin's Thcorem) If X a topological measure space endowed with a regular measure μ. if y is second-countable and X + y is measurable, then for every > 0 there exists compact set C such that v(X) \ K) < e and the restriction of de to K is continuous.
38

---

Published in Transactions on Machine Learning Research (11/2023)
Theorem (Continuous extension of functions from a compact, (Deimling, 2010)) Let A C R be compuct and f A - R be continuous function. Then there erists continnous exlension f Rd - R such that f(x) = f(x) for all x E A.
B.1 A generalized Law of Large Numbers
There are many extensions of the strong law of large numbers to the case where the random variables have some form of dependence. We prove strong law of large numbers for specific sequences of arrays that satisfy a conditional zero-mean property.
Theorem Let (Yn,is 1 S siism,n 2 13 be a triangular array of random variables satisfying the following conditions:
For all 2 1 and i [n], E|Yn, Fn,sl O, where Fn, = o(fYngi) i)), Le. the a o-algebra generaled by all the random variables in row n. other Ihan Yn,i-
For all n 2 1, the random variables (Yna)ssinn are identically distributed (but not necessarily independent).
sup,,i EY,,, n. < 00.
Them, we have that
Y +0 0, 1=1
a.s.
The proof uses similar techniques to the standard proof of the strong law of large numbers, with some key differences, notably in the use the Chebychev inequality to upper-bound the fourth moment of the mean. Let S, Dim1 Yn,. We want to show that P(liimn-ac. S./n = 0) = 1. This is equivalent to showing that for all 0, IPS, > ne for infinitely many n) = This event is nothing but the limsup of the Borel-Cantel to conclude if we
Proof:
events An {S,, ne). Hence, Let 0. Using Chebychev inequality with degree 4, have that P(An) I (en) bound ESA to conclude. We have that ES, = E Eis.JAAsS Y,,Y m.y YY Yna. Using the first condition Izero-mean conditional distribution), all the terms of the form YY Yn, YY,,,, Yn,. and Y Y2,Yn, for # vanish and we end up with ES! nEY n.1 + 3n(n - 1)EY? n.1 n.2: where we have used the fact
show that En P(A,)
It remains to
y2
that the number of lerms of the form y2, n.j in the sum is given by (7) x ( s(n-1) 6 3n(n 1).
Using the last condition of the fourth moment, we obtain that there exists constant M > such that ES, Cn². Using Chebychev inequality, we get that I(A,)) S = and thus En P(An) co. We conclude using the Borel-Cantelli lemma.
-2
C Additional Theoretical Results
Convolutional neural networks: For an activation function a, real number R >> 0, and integers J 2 1 and s 2 denote CNNNJ,, the set of convolutional neural networks with J filters of length with all weights and biases in [- [-R, R). More precisely, for filter mask (wo..., W.-1), and vector Rd, the rosults of the convolution of and x, denoted w*z is a vector in Rd-s defined by (w+z); Σ Wi-kkk k=i-st1
A network from (N) then defined recursively for x E X:
(x) =
j E [1 J), (x)) = (w(i) (x)))())) + bb)),, where the filters and biases wl) and BD) are in [R, R
Nout (x) (x), where the vector has entries in [- R, R
39

---

Published in Transactions on Machine Learning Research (11/2023)
Corollary 5 (Convolutional Neural Networks (Zhou, 2020)) Let be the ReLU activation function. Consider fülter length E [2, dz). For any SBPA with adapled score function, there erists wumber of filters Jo and radius Ro such that the algorithm is not consistent on ON 3,, (R), for any J 2 Jo and R 2 Rg. Besides, if the algorithm depends on the labels, then it also not valid on CNN) (R), , for any J z Jg and R R
Experimental details
Dataset
CIFAR10
CIFAR100
Architecture
ResNet18
ResNet34
Methods
GraNd(10), Uncertainty, DeepFool
GraNd(10), Uncertainty,
DeepFool
Selection LR
0.1
Training IRR
0.1
0.1
Selection Epochs
1, 5
1,
Nb of exps
Training Epochs
160
160
Optimizer
SGD
SGD
Batch Size
128
128
The table above contains the different to using the GraNd method with 10 different seeds (averaging over 10 different initializations). Selection LR refers to the learning rate used for the coreset selection. The training LR follwos a cosine annealing schedule given by the following:
used to run the experiments. GraNd(10) refers
(1+ cos
Teur x
)
7 Mmin + 2 (Amaz Mmin)
Tmaz
where Tour is the current epoch, Tmaa the total number of epochs, and Amaz 0.1 and Amin 10-4 These are the same hyper-parameter choices used by Guo, B. Zhao, and Bai, 2022.
D.1 MLP for Scaling laws experiments We consider an MLP given by
V1 (x) @Wi + b1);
1/2 22(2) @(W31 (x) b2),
Yout (z) W (o) bouts
where Pin 1000 is the input, W, E R 1000 W2 R 128 W Wont E 2x188 are the weight matricos and bi, b2, bout are the bias vectors.
40


Reviews:
[{"review_id": "jEqfaZelCW", "reviewer": "Reviewer_moww", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper studies a very relevant problem. I really appreciate the proposed formalism to study this problem in the asymptotic regime.\n2. The theoretical results on SPBA are very interesting and, to my knowledge, are new in the literature, although I have some questions regarding their applications to neural networks.\n3. The new algorithm is quite straightforward but seems very effective in practice.\n4. The empirical verifications are solid.\n\nWeaknesses:\n1. I have some questions about corollaries 3 & 4 and in general, about the results of universal approximation. Note the universal approximation results are also asymptotic in nature. For example, the wide neural network requires the width to go to infinity. For fixed $\\epsilon$, there exists $R_0$ and $K_0$ in Corollary 3, but I think Corollary 3 is not for fixed $\\epsilon$ but letting $\\epsilon \\rightarrow 0$ as well. I recommend writing Corollarys 3 & 4 and their proofs in a fully rigorous form instead of just citing the universal approximation theorems.\n2. While it is definitely valuable to study the asymptotic regime (number of parameters fixed, $n \\rightarrow \\infty $), it is also worth studying both the number of parameters and $n$ going to infinity (with the same or different rates). I know this is beyond the scope of this paper, but more discussions are needed, because this is a practically relevant scenario.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. An interesting novel formalism to characterize the asymptotic properties of data pruning algorithms.\n2. Analyses of Scire-Based Pruning Algorithms (SBPA) for universal approximations and general function classes. Theoretical results show that SBPA is worse than random sampling.\n3. New algorithm that interpolates between SBPA and random sampling. Theoretical and empirical analyses show that the new method is promising.\n4. Empirical evaluations that verify the theories.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vf0pF7fCz1", "reviewer": "Reviewer_oDiF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I liked the paper, one can see that the authors put a lot of effort into the preparation of the manuscript.\n\nStrengths: \n- The paper is well written and easy to follow.\n- The claims of the paper are well supported in the manuscript. \n- The developed theory is easy to follow.\n- The review of related works looks complete.\n\n\nWeaknesses:\n- The paper is a bit long. Notation paragraph appears multiple times at different places in the manuscript.  In the Intro, in order to understand some figures, one needs to read sections that are further down the manuscript — as such the flow of the reading is affected. Spending some time in trimming the paper and improving the presentation outline would improve the paper.\n\n- Showing the results on other tasks that go beyond classification and trying to highlight the utility of the developed framework for larger scale datasets such as ImageNet, would further improve the manuscript.\n\n- The observations/conclusions are not surprising, it not an expectation from the TMLR paper to show surprising results, thus this point is  not affecting my judgement of the paper. However, I do think that papers with surprising/interesting observations, results will be more impactful in the long run. Thus, if possible I would encourage the authors to think if there is some angle on the paper presentation and results that would add a twist of surprise to the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies score-based dataset running approaches focusing on a setup where less than 30% data is kept. The paper shows that in such setup score-based approaches underperform random pruning. The paper shows how to improve score-based pruning by mixing it with random sampling in high data pruning scenarios. This paper is mostly focused on theory, however, quite broad experimental validation is also included (including CIFAR10 and CIFAR100 datasets).\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Fig 2 is a bit confusing. For the bottom plots, the legend is not always matching the plots. W, r, and n are not defined in the caption. \n\nI’m curious about the time required by pruning algorithms vs time required for training the classification model. I would assume that that in some cases the time spend on data pruning might not be worth it as it exceeds the time spend on training, the opposite is probably also the case in many scenarios. Adding some discussion about the tradeoff of the time spend on pruning vs time spend on the training of the downstream task model might be interesting.\n", "broader_impact_concerns": "The paper covers some limitations of the framework. \n\nI do not have any further suggestions to include.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bD2F2LhK9N", "reviewer": "Reviewer_TwLS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n- The paper is well-written overall and provides an excellent theoretical account of the limitations of score-based data pruning methods. It brings to attention their pitfalls and why one might need to supplement them with random sampling to remove the bias introduced by the pruning procedure.\n\n- Some of the examples and discussions in the paper, such as in Section 5.1 using logistic regression, are quite insightful and provide a strong demonstration of the limitation of SBPA algorithms, (in particular GraNd).\n\n\n*Weaknesses*\n\n- The primary concern in my opinion is in Section 5. The authors state that $r=1$ corresponds to random pruning when, in fact, $r=1$ corresponds to no pruning at all. This is a concern because many of the conclusions in that section pertain to the comparison with random pruning, but there is no comparison with random pruning as far I as understand. In Figures 6 and 7, random pruning should be included for all values of $r$.  Later in Figure 10, the authors correct this when they correctly refer to $r=1$ as “no pruning” but do not fix this in the discussion. \n\n- In many places, the statements of the theorems/propositions are not self-contained. For example, Theorem 1 does not say that it only addresses SBPA algorithms which ignore the labels $y$, even though this becomes evident from the proof and from the subsequent discussion in the paper. Also, in Proposition 5, the functions $f_1$ and $f_2$ are assumed to be in $\\mathcal{M}$ but this is not mentioned in the statement of the proposition.\n- Along similar lines, I find it surprising that there does not seem to be a smoothness assumption made on the scoring function $g$. This might be embedded within the proof; I don't know. The reason I find this surprising is because one can “approximate” random pruning with a deterministic scoring function $g$ that partitions the domain into extremely small regions, such that pruning based on $g$ is almost similar to random pruning. This is because the probability measure of isolated points is assumed to be zero. However, $g$ would not be smooth in that case, so I would expect smoothness of $g$ to show up as a condition in the results.\n- See my comment above about the limitation of some of the theoretical results.\n- Figure 12 is supposed to be the main demonstration that one can do better than random pruning by carefully selecting the parameter $\\alpha$. But, the authors do not explain how $\\alpha$ is selected in that figure and whether or not the same $\\alpha$ is used for all compression levels $r$. There are no confidence intervals and the improvement compared to random pruning, if it exists, is quite small.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on score-based data pruning algorithms (SBPA), which use a scoring function $g$ to rank the examples in the training sample and select a fraction $r$ of the examples accordingly (with the convention that lower values of $g$ point to more important examples).\n\nThe authors present some theoretical results, which establish the limitations of score-based pruning. One result (Theorem 1) states that for any SBPA that does not use the labels $y$, suppose we have a collection of function classes $W_\\theta$ parameterized by some hyperparameter $\\theta$ (e.g. $\\theta$ can be the number of layers in a neural network while $W_\\theta$ is the set of all functions realized by the neural network with depth $\\theta$). If $\\cup_\\theta W_\\theta$ enjoys the universal approximation property, as in deep neural networks, then there exists a hyperparameter $\\theta$ such that pruning is inconsistent with respect to the function class $W_\\theta$. That is, there exists a function $f\\in W_\\theta$ such that the expectation of the loss w.r.t. pruned data is different from the expectation of the loss on the original distribution. Hence, model selection based on pruned data can fail. \n\nThe intuition behind this result is quite simple. Since it's assumed that SBPA does not use the labels, score-based pruning is asymptotically a rejection sampling method on the instance space $X$ so the pruned data have limiting distribution $\\eta$. One can then construct many functions that agree on the support of $\\eta$ and disagree outside it, but the scoring rule cannot distinguish among them. \n\nThe above result is not that interesting because most score based pruning methods use the labels $y$. This brings us to the second main result in the paper (Theorem 2) , which is more interesting (but I have to admit that I could not really follow its proof). It states that for any SBPA that also uses the labels $y$, there exists a compression level $r_0$ and hyperparameters such that pruning is not \"valid\" (the paper refers to the classical notion of “consistency” as “validity”). \n\nInitially, I found this last result surprising because the claim is that this holds for any data distribution $\\mu$! However, it seems now to be less exciting than I originally thought. This is because the theorem states that there exists *some* hyperparameter $\\theta$ where failure happens. In the case of deep neural networks, for example, we do not know if that $\\theta$ corresponds to something unrealistic like 1 billion layers. \n\nGenerally, the intuition behind such arguments is that pruning changes the data distribution. So, to fix this problem, the authors propose using a mixture of two distributions: pruned data using SBPA and random sampling. Since score-based pruning can be viewed as rejection sampling, one can assign different weights to the two distributions such that we recover the original objective function. The authors show that with as little as 10% of random examples, the consistency is recovered in practice. In theory, of course, any fraction is enough as long as it is positive.\n\nOverall, this is a useful message. However, it does not mean that one can do better than random pruning, which I find to be disappointing. The authors hint that one may do better depending on the quality of SBPA, e.g. with linear datasets, but I don’t find the empirical results convincing. There is no improvement in Figure 11 while Figure 12 doesn’t include a confidence interval. In general, if there is indeed an improvement, it seems to be quite marginal at best.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please include random pruning in Section 5.1, particularly in Figures 6 and 7. Please fix the issue mentioned above about calling r=1 random pruning.\n- In Figure 12, please describe how $\\alpha$ is selected and whether or not the same $\\alpha$ is used for all compression levels $r$. Also, it would be useful to provide confidence intervals for the “best $\\alpha$” curves.  \n\nNitpicks:\n- Page 4: “euclidiean” → “Euclidean”\n- The term “validity” in Definition 2 is used to describe what is often referred to in the literature as “consistency.” This can be confusing.\n- Figure 4 does not add much value in my opinion.\n- Page 14: there are many extra spaces before the footnote.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I'm recommending acceptance based in part on the unanimous agreement among the reviewers that this paper is acceptable and that the paper's claims are well-supported by evidence (btoh empirical and theoretical) The reviewers highlighted the paper's valuable contribution to data pruning and its likely significance as a baseline for future works in the area. I agree with this second point very much. The paper is moreover on an important topic, of considerable interest to the community. Based on my own reading, it is a nice contribution to this line of work.

The authors were very responsive and diligent in revising their manuscript, and addressed a good number of concerns raised by reviewer. Specifically, they have clarified the proof of the main theorem and improved the overall readability of their paper by refining the notation and adding/clarifying key notions.
Decision: Accept (poster)