Approximating any Function via Coreset for Radial Basis Functions: Towards Provable Data Subset Selection For Efficient Neural Networks training
Authors: Murad Tukan
Samson Zhou
Alaa Maalouf
Vladimir Braverman
Dan Feldman
Venue: Submitted to ICLR 2023 (2023)
Keywords: Data subset selection
Coresets
Radial basis functions neural networks
deep learning

Abstract: Radial basis function neural networks (\emph{RBFNN}) are notoriously known for their capability to approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. Coreset is a small weighted subset of an input set of items, that provably approximates their loss function for a given set of queries (models, classifiers, etc.). In this paper, we suggest the first coreset construction algorithm for \emph{RBFNNs}, i.e., a small weighted subset which approximates the loss of the input data on any radial basis function network and thus approximates any function defined by an \emph{RBFNN} on the big input data. This is done by constructing coresets for radial basis and Laplacian loss functions. We use our coreset to suggest a provable data subset selection algorithm for training deep neural networks, since our coreset approximates every function, it should approximate the gradient of each weight in a neural network as it is defined as a function on the input. Experimental results on function approximation and dataset subset selection on popular network architectures and data sets are presented, demonstrating the efficacy and accuracy of our coreset construction.

Under review as a conference paper at ICLR 2023
APPROXIMATING ANY FUNCTION VIA CORESET FOR RADIAL BASIS FUNCTIONS: TOWARDS PROVABLE DATA SUBSET SELECTION FOR EFFICIENT NEURAL NETWORKS TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Radial basis function neural networks (RBFNN) well-known for their capabil- ity to approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. Coreset is small weighted subset of an input set of items, that provably approximates their loss function for given set of queries (models, classifiers, etc.). In this paper, we suggest the first coreset con- struction algorithm for RBFNNs, i.c., a small weighted subset which approximates the loss of the input data on any radial basis function network and thus approx- imates any function defined by an RBFNN on the big input data. This is done by constructing coresets for radial basis and Laplacian loss functions. We use our coreset to suggest a provable data subset selection algorithm for training deep neu- ral networks, since our coreset approximates every function, it should approximate the gradient of each weight in neural network as it is defined a function the input. Experimental results on function approximation and dataset subset selee- tion popular network architectures and data sets are presented, demonstrating the efficacy and accuracy of our coreset construction.
INTRODUCTION
Radial basis function neural networks (RBFNNs) are artificial neural networks that generally have three layers: an input layer, a hidden layer with radial basis function (RBF) as an activation function, and linear output layer. In this paper, the input layer receives a d-dimensional vector E IRd of real numbers. The hidden layer then consists of various nodes representing RBFs, to compute (||2)) exp (- || cill) where c; E Rd is the center vector for neuron across,
say, N neurons in the hidden layer. The linear output layer then computes Σ aGp([|= - e: ll2,, where o; is the weight of neuron in the linear output neuron. Therefore, RBFNNs are feed-forward neural networks because the edges between the nodes do not form a cycle, and enjoy advantages such as simplicity of analysis, faster training time, and interpretability, compared to alternatives such as convolutional neural networks (CNNs) and even multi-layer perceptrons (MLPs) (Padmavati) 201T).
Function approximation via RBFNNs. RBFNNs are universal approximators in the sense that an RBFNN with a sufficient number of hidden neurons (large N) can approximate anv continuous function on a closed, bounded subset of Rd with arbitrary precision (Park Sandberg 1991), i.e., given a sufficiently large input set P of n points in Rd and given its corresponding label function y: P + TR. an RBFNN, can be trained to approximate the function y. Therefore, RBFNNs are com-
monly used across wide range of applications, such as function approximation (Park & Sandberg 1991 [993] Lu et al. 1997). time series prediction (Whitchead & Choate 1996] Leung et al. |000] Harpham & Dawson 2006), classification (Leonard & Kramer 1991 Wuxing al.) [004]] Babu &
Suresh 2012), and system control (Yu et al. 201 Liu 2013), due to their faster learning speed.
For given size of RBENN (number of neurons in the hidden layer) and an input set, the aim of this paper is to compute a small weighted subset that approximates the loss the input data on any radial basis function neural network of this size and thus approximates any function defined

---

Under review as a conference paper at ICLR 2023
(approximated) by such RBFNN the big input data. This small weighted subset is denoted by coreset.
Coresets. Usually, in machine/deep learning, we are given input set P S E' of n points, its corresponding weights function w : P + R. a set of queries X (a set of candidate solutions for the involved optimization problem), and loss function called query space, and it defines the optimization problem at hand - where usually, the goal is to find x² E arg min Epep [ x)). Given query space (P, w. f), coreset for it is small weighted subset of the input P that can provably approximate the cost of every query on P (Feldman 2020); see Definition [ In particular, a coreset for a RBFNN can approximate the cost of RBFNN on the original training data for every set of centers and weights that define the RBFNN (see Section 4). Hence, the coreset approximates also the centers and weights that form the optimal solution of the RBFNN (the solution that approximates the desired function). Thus coreset for a RBFNN would facilitate training data for function approximation without reading the full training data and more generally. strong coreset for an RBFNN with enough hidden neurons would give strong coreset for any function that can be approximated to some precision using the RBENN.
P x X + [0, 20). The tuple (P, w. X,
X
To this end, in this paper, we aim to provide coreset for RBFNNs, and thus provably approx- imating (providing a coreset to) any function that can be approximated by given RBFNN.
function.
Train RBFFNN on large dataset P to approximate f
Train an RBFFN on small we weighted coreset C =
(xx
P
CCP
x R
RBFNN'
RBFNN
For x R2, we have:
f(x) RBFNN" (x) RBFNN (x)
Figure 1: Our contribution in nutshell.
Furthermore, we can use this small weighted subset (coreset) to suggest provable data subset selection algorithm for training deep neural networks efficiently (on the small subset), since our coreset approximates every function that can be approximated by an RBFNN of this size, it should approximate the gradient of each weight in neural network (if it can be approximated by the RBFNN).
Training neural networks on data subset. Although deep learning has become widely success- ful with the increasing availability of data (Krizhevsky et al. 2017; Devlin et al. 2019), modern deep learning systems have correspondingly increased in their computational resources, resulting in significantly larger training times, financial costs (Sharir et al. 2020). energy costs (Strubell et al,, 2019), and carbon footprints (Strubell et al.) 2019: Schwartz et al. 2020). Data subset selection (coresets) allows for efficient learning at several levels (Wei et al. 10144/Kaushh et al., 2019 Cole- man al. 2019; Har-Peled & Mazumdar 2004 Clarkson| 2010). By employing significantly smaller subset of the big dataset, (i) we enable learning on relatively low resource computing set- tings without requiring a huge number of GPU and CPU servers. (ii) we may greatly optimize the end-to-end turnaround time, which frequently necessitates many training runs for parer-par tweaking, and (iii) because large number of deep learning trials must be done in practice, we allow for considerable reductions in deep learning energy usage and CO2 emissions (Strubell et al.) 2019)) Several efforts have recently been made to improve the efficiency of machine learning models using data subset selection (Mirzasoleiman al. 2020a Killamsetty et al. 202 lb a). However, existing techniques either (i) employ proxy functions to choose data points, (ii) are specialized to specific machine learning models, (iii) use approximations of parameters such gradient error general- ization errors, (iv) lack provable guarantees on the approximation error, or (v) require an inefficient gradient computation of the whole data. Most importantly, all of these methods are model/network
2

---

Under review as a conference paper at ICLR 2023
dependent, and thus computing the desired subset of the data after several training epochs (for the same network) takes a lot time and must be repeated each time the network changes.
To this end, in this paper, aim at suggesting provable and efficient model- model-independent subset selection algorithm for training neural networks. This will allow us to compute a subset of the training data, that is guaranteed to be coreset for training several neural network architecturess/odell.
1.1 OUR CONTRIBUTIONS
In this paper, we suggest a coreset that approximates any function can represented by an RBFNN architecture. Specifically:
(i) We provide coreset for the RBF and Laplacian cost functions; see Algorithm and Section 3.1.2
(ii) We employ (i) generate coreset for any RBFNN model, in turn, approximating any function that can represented by the RBFNN; see Figure ioor illustration, and Section for more details.
(iii We then exploit the properties of RBFNNs, to approximate the gradients of any deep neural networks (DNNs), leading towards provable subset selection for learning/training DNNs. We also show the advantages of using our coreset against previous subset selection tech- niques; see Section Jnd and Section
(iv) Finally, we provide an open source code implementation of our algorithm for reproducing our results and future research.
1.2 RELATED WORK
A long line of active work has studied efficient coreset constructions for various problems in com- putational geometry and machine learning, such as k-means and k-median clustering (Har-Peled
& Mazumdar 2004]] Chen, 2009 Braverman et al., 2016 Huang & Vishnoi 2020; Jubran et al.,
|020][Cohemn [CohnCC Addad et al. (002)). regression (Dasgupta et al.) [008]] [Chhaya et al. 2022 | Tolochin
sky et 20]2 Meyer et al. (202), low-rank approximation (Cohen al. [2017] Braverman al.
2020 Maalouf et al. 2020 2021). volume maximization (Indyk et al. [0200] Mahabadi et al. 2020
Woodruff & Yasuda 2022). projective clustering (Feldman al. 2020 Tukan et al. 2022b), , sup-
port vector machines (SVMs) (Clarkson) 2010; Tukan et al. (021). Bayesian inference (Campbell
& Broderick 2018), sine wave fitting (Maalouf et al. 2022). and decision tree (Jubran et al. 2021)
(Baykal al. 2022 suggested coreset-based algorithms for compressing the parameters of a trained fully-connected neural network by using sensitivity sampling on the weights neurons after train- ing. though without pruning full neurons. (Mussay et al. 2020 [Liebnnwei al.) [019 Tukan et al.)
2022a) sidestepped this issue by identifying the neurons that can be compressed regardless of their weights, due to the choice of the activation functions, thereby achieving coreset-based algorithms for neural pruning.
These approaches use coresets to achieve an orthogonal goal to data subset selection in the context of deep learning - they greatly reduce the number of neurons in the network while we greatly reduce the number of samples in the dataset that need to be read by the neural network. Correspondingly, we reduce the effective size of the data that needs to be stored or even measured prior to the training stage. Moreover, we remark that even if the number of inputs the input layer were greatly reduced by these neural compression approaches, the union of the inputs can still consist of the entire input dataset and so these approaches generally cannot guarantee any form of data distillation.
Toward the goal of data subset selection, (Mirzasoleiman et al.) 2020a by introduced algorithms for selecting representative subsets of the training data to accurately estimate the full gradient for tasks in both deep learning and classical machine learning models such as logistic regression and these approaches were subsequently refined by (Killamsetty et al.] 2021abb) b). Data distillation has
also received lot of attention in image classification (Bohdal al. 2020 Nguyen et al., 2021
Dosovitskiy et al., 2021). natural language processing (Devlin et al. 2019 Brown et al. 2020), and federated learning (Ozkara et al. 2021 Zhu et al. 2021).
3

---

Under review as a conference paper at ICLR 2023
2 PRELIMINARIES
For an integer n > 0, we use [n] to denote the set {1, 2.).. A weighted set of points is a pair
(P, w), where P S IRd is set of points and w P - [0, 00) is weight function.
We now formally provide the notion of e-coreset for the RBF loss. This will be later extended to a coreset for RBFNN.
Definition 1 (RBF s-coreset). Let (P, w) be a weighted of points in Rd X C He be a set of queries, E E (0, 1). For every x E X and p E P let f(p, x) == exp (- -lp x11) denote the RBF loss function between p and x. An E-coreset for (P, w) with respect to f, pair (S. where S S.P. 8 + (0, oo) is weight function, such for every x X, [ Eper w(p)/(p.z) S.
2inss "(o)((g.))
We say the RBF coreset is strong if it guarantees correctness over all E X. Otherwise, we say the coreset weak if only provides guarantees for all x only in some subset of X.
Sensitivity sampling. To compute our RBF E-coreset, we utilize the sensitivity sampling frame- work (Braverman et al. (0166). In short, the sensitivity of a point p E P corresponds to the "impor- tance" of this point with respect to the other points and the problem hand. In our context (with w(pp)f(p.))
respect to the RBF loss), the sensitivity defined as s(p) supzex Eger ((q))(qa3) where the denominator is nonzero. Once we bound the sensitivities for every p P, we can sample points from P according to their corresponding sensitivity bounds, and re-weight the sampled points to obtain an RBF E-coreset in Definition [ The size of the sample (coreset) is proportional to the sum of these bounds the tighter (smaller) these bounds, the smaller the coreset size. For formal details, refer the reader to Section A in the appendix.
Sensitivity bounding. We now present our main tool for bounding the sensitivity of each input point with respect to the RBF and Laplacian loss functions.
Definition 2 (Special case of Definition 4 (Tukan et al. 2020 Let (P, w, f be query space as in Desinition 9 where for every p E P and E R&. (p, = 10 s/|. Let D E [0, ) d be diagonal matrix of full rank and let V E Rdddd be an orthogonal matrix, such that for every x Rd.
|DVV 2|12 - Σ
w(p) xl Va vá DVT
pEP
Define U : P + I.d such that U(p) = p (DVTT) -1 for every p E P. The tuple D,) the -VD P. P.
Using the above tool, the sensitivity w.r.t. the RBF loss function can be bounded using the following.
Lemma 3 (Special case of Lemma 35, (Tukan et al. 2020)). ). Let (P, w, Rd (f) be query space as in Definition 9 where for every E P and x E IR,, f(,,z) x) 1p" x). Let (U, D,V) V) be the Il-I|
of (P, w) with respect to 1-1 (see Definition 2 Then, claims (i) - (ii) hold as follows:
(i) for every p E P, the sensitivity of with respect to the query space (P, w. Rd [.I1) is bounded by s(p) S (p)())
(ii) and the total sensitivity is bounded by Σ s(p) < d..s.
PEP
3 METHOD
In this section, we provide coresets for the Gaussian and Laplacian loss functions. We detail our coreset construction for the Gaussian loss function and Laplacian loss function in Section 3.1.2
Overview of Algorithm i
Algorithm receives as input, a set P of n points in R2., a weight function P + [0, oo), J. bound R on the radius of the ball containing query space X, and sample size m > O. If the sample size m is sufficienlly large, then Algorithm outputs pair (S, that is e-coreset for RBF cost function; see Theorem
4

---

Under review as a conference paper at ICLR 2023
First d' is set be the VC dimension of the the quadruple (P, w, X, p.)): see Definition 10 The heart of our algorithm lies formalizing the RBF loss function as a variant of regression problem, specificallly, variant of the & errrerressoon problem. The conversion requires manipulation of the input data as presented at 2ine We then compute the f-SVD of the new input data with respect to the -i-regressoon problem followed by bounded the sensitivity of such points (Lines 3 Now have all the needed ingredients to use Theorem [1 in order to obtain an E-coreset, i.c., we sample ii.d m points from P based on their sensitivity bounds (see Line 8), followed by assigning new weight for every sampled point at Line
Algorithm 1: CORESET(P, w. R, m)
Input:
S R2 of n points, weight function : P - [0, 00). bound on radius of the query space X, and sample size m 2 1.
Output: pair (S, v) that satisfies Theorem 6
Set == the VC dimension of quadruple (P, w, X. p.)) // See Definition 10 Vp p]
Set P = { {1r 4p = [IP -2p", 1]"
Set (U, D, V) to be the f-SVD of (P', w. 1-)) // See Definition 2
for every p P do
Set s(p) == e 12
(1 + 8R
w(p) प(() + w()) [1U
// bound on the sensitivity of p as in Lemma 13 in the
appendix
Set / := p spp)
Set ē > 1 to be sufficiently large constant Can be determine ned from
Theorem
Pick i.d sample of m points from P, where each p E P sampled with probability e(p)
uet u: Rd + [0, oo] to be a weight function such that for every g E S, v(q) 3(g).m
return v)
3.1 ANALYSIS
3.1.1 LOWER BOUND ON THE CORESET SIZE FOR THE GAUSSIAN LOSS FUNCTION
We first show that the lower bound on the size of coresets, to emphasize the need for assumptions on the data and the query space.
Theorem 4. There exists set of n points P C Rd such that Epep s(p) 2m)).
Proof. Let d 2 3 and let P S Rd be a set of points distributed evenly on a 2 dimensional In other words, using the law of cosines, every p E P, VInn
sphere of radius
2000 (
mingep\(P)) 1p
9 A1ا see Figure Observe that for every E P.
11p-=111
s(p) == max
rERd
Σ
1
1+
11pp-9
1+
Σ
2
gEP
PEP
QEP((p)
(1)
where the first equality holds by definition of the sensitivity, the first inequality and sec- ond equality hold trivially, the second inequality follows from the assumption that vIn minger Ip - 4/12. and finally the last inequality holds since E,EP) 4 4 1
3.1.2 REASONABLE ASSUMPTIONS LEAD TO EXISTENCE OF CORESETS
Unfortunately, it is not immediately straightforward to bound the sensitivities of either the Gaussian loss function or the Laplacian loss function. Therefore, we first require the following structural prop- erties in order relate the Gaussian and Laplacian loss functions into more manageable quantities.
5

---

Under review as a conference paper at ICLR 2023
We shall ultimately relate the function e e-Ip"al a| to both the Gaussian and Laplacian loss functions.
Thus, we first relate the function e ell=" to the function 1y² x +1
Claim 5, Let E IRd such that llpl22 S 1, and let R > 0 be positive real number. Then for every
x E E Rd | S R
R (1+R) (1+ s 1p= +1
In what follows, we provide the analysis of coreset construction for the RBF and Laplacian loss functions, considering an input set of points lying in the unit ball. We refer the reader to the supple- mentary material for generalization of our approaches towards general input set of points.
Theorem 6 (Coreset for RBF). Let R 2 be positive real number, X {Ir R [= S R),
and let E, 8 E (0, 1). Let (P, w, X, f) be query space as in Definition g such that every p E P For every x E X and p E P. let f(p, x) == ((ppp x 2 Let (S, v) be a call
satisfies lpll, S
to CORESET(P, w, R. m) where S C P and : + [0, oo). Then (S, v) e-coreset of (P,w) with
1nn a (R² + log + log !))
probability at least 8, m =0
Coreset for Laplacian loss function. In what follows, we provide coreset for the Laplacian loss function. Intuitively speaking. leveraging the properties of the Laplacian loss function, we were able to construct a coreset that holds for every vector x E IRd unlike the RBF case where the coreset holds for ball of radius R. We stress out that the reason for this is due the fact that the Laplacian loss function is less sensitive than the RBF.
Theorem (Coreset for the Laplacian loss function). Let (P, w, R) be query space as in Defi- nition such that every p E P satisfies |pll S 1. For E Rd and P, let f(p ():=))=== := e-ellll -1r-=12, Let E, E (0, 1)- Then there exists an algorithm which given P, we, e,, return a weighted set (5, where S C of size O (Sndd
(log n log d + log 1t) and weight function S - [0, oo) such that ()) is an E-coreset of (P, w) with probability at least 1 - 5.
4 RADIAL BASIS FUNCTION NETWORKS
In this section, we consider coresets for RBFNNs. Consider an RBFNN with L neurons in the hidden layer and single output neuron. First note that the hidden layer uses radial basis functions as activation functions so that the output is a scalar function of the input layer, @ RRd -> IR defined
by ((x) Σle a,p([1== c(2), where c( E R for each i [d].
For an input dataset P and a corresponding desired output function : P:P R. RBFNNs aim to optimize
2
Σ v(p) Σ age -ae-lll-- 10--60113
PEP
i=1
Expanding the above cost function, we obtain that RBFNNs aim to optimize
Σ リル())~2 Σ 09
Σ v(lee-lie 10
Σ
age
PEP
PEP
PEP
Bounding the a term in equation
2 We first define for every x E Rd:
(x)
Σ v(p)e
1p-x113
pePa)p)>
(x)
Σ
(B(p)
1p x11
Pe PEP.o(p)<0

---

Under review as a conference paper at ICLR 2023
Observe that Epep (()))((p-c)))))) o* (c - (c()). Thus the term in equation can be approximated using the following.
Theorem 8. There exists an algorithm that samples O (e Rf (R² + log d log 8) points to form weighted sets (S1, w1) and (S2, W22 such that with probability at least 28,
Σ ai Σ wi(ple (omi)e-lll-ce |||- (E
aj Σ w2(g)e 1110-
Σ x(p)(()) PEP
PEši
SELL] ay<0
9E
a.20
Σ as (ot (clil) + (c(1))
+ Σ lasl (ot (clt)) + o (c(i1)
iE a,20
KELL a2 <0
Bounding the 3 term in equation 2 By Cauchy's inequality, it holds that
are IIe-
o3e 2
2 2
L
PEP
pEP i=1
x=1
PEP
where the equality holds by simple rearrangement.
Using Theorem 6 we can approximate the upper bound on 33 with approximation of L(1 + 6). However, for every E [T.] holds that Og 2 0, then we also have the lower bound
2
Σ
Σ PEP
2
1
S
Σ a&e 1|e- 11e-od0113
--e--lle-d
PEP
Since generate multiplicative coresct for the left-hand side of the above inequality, then obtain also a multiplicative coreset in a sense for / as well.
5 BENEFIT OF OUR CORESET OVER OTHER SUBSET SELECTION METHODS
One coreset for all networks. Our coreset is a model independent, i.e., we aim at improving the running time of multiple neural networks. Contrary other method that needs compute the coreset after each gradient update to support there theoretical proofs, our method gives the advantage of computing the sensitivity (or the coreset) only once, for all of the required networks. This is since our coreset can approximate any function that can be defined (approximated) using a RBFNN model.
Efficient coreset per epoch. Practically, our competing methods for data selection are not applied before each epoch, but every R epochs. This is since the competing methods require lot of time to compute a new coreset since they compute the gradients of the network with respect to each input training data. However, seconds), since we compute the sensitivity of each point (image) the data once at the beginning, and then whenever we need create new coreset, we simply sample from the input data according to the sensitivity distribution.
coreset can be computed before each epoch in negligible time (~
EXPERIMENTAL RESULTS
In this section practically demonstrate the efficiency and stability of our RBFNN coreset approach for training deep neural networks via data subset selection. We mainly study the trade-off between accuracy and efficiency (time/subset size).
Competing methods. We compare our method against many variants of the proposed algorithms in Killammmstt al. (2021a) (denoted by, GRAD-MATCH), in Mirzasooeimm et al. (2020a) (denoted by CRAIG), and in Killamsetty et al. (2021b) (denoted by GLISTER). For each of these methods, report the results for 4 variants: (i) the "vanilla" method, denoted by its original name, (ii)

---

Under review as a conference paper at ICLR 2023
applying warm start i.e, training the whole data for 50% of the training time before train- ing the other 50% on the coreset, where such methods are denoted by adding the suffix -WARM. (ii) more efficient version of each of the competing methods denoted by adding the suffix PB (more details are given at Killamsetty et al. (2021a)), and finally, a combination of both (ii) and (iii). In other words, the competing methods are GRAD-MATCH, GRAD-MATCHPE, GRAD- CRAIG, CRAIGPB, CRAIG-WARM, CRAIGPB- WARM, and WLISTER-WARM, We also compare against randomly selecting points (denoted by RANDOM).
MATCH-WARM, BRAD-MATCHPP-WARD
Datasets and model architecture. We performed our experiments for training CIFARIO and CI- FARI00 (Krizhevsky et al. 2009) on Resnet18 (He et al.) 2016), and MNIST (LeCun et al. 1998) on LeNet.
The setting. We adapted the same setting of Killamsetty et al. (2021)) where we used SGD op- timizer for training initial learning rate equal 0.01, a momentum of 0.9, and weight decay of 5e - 4. We decay the learning rate using cosine annealing (Loshchilov & Hutter) (2016) for each epoch. For MNIST, we trained the LeNet model for 200 epochs. For CIFARIO and CIFAR 100, we trained the R for 300 epochs all on batches of size 20 for the subset selection training versions. We train the data selection methods and the entire data training with the same number of epochs; the main difference is the number of samples used for training single epoch. All exper- iments were executed on V100 GPUs. The reported test accuracy in the results is after averaging across five runs.
Subset sizes and the R parameter. For MNIST, we use sizes of (1%, 3%, 5%, 10%). while for CI- FARIO and CIFARI00, we use (5%, 10%, 20%, 30%) } on ResNet18. Since the competing methods require a lot of time to compute the gradients, we set R = 20. We note that for our coreset we can test with R- without adding run run-time since once the sensitivity vector defined, commuting a new coreset requires ~ 0 seconds. However, we test it with R = 20, to show its robustness.
Discussion. Table and 2 report the results for CIFARIO and CIFAR 100 on ResNet18, respectively. It is clear from Table that our method achieves the best accuracy (without warm start) for 20% and 30% subset selection of CIFAR1O, while for CIFARI00 and smaller subset selection on CIFARIO. 10, our method drastically outperform all of the methods that does not apply warm start (training on the whole data), and we still outperform all of the other methods in terms of accuracy vs time. The same phenomena is witnessed in the MNIST experiment (Table 4 where our coreset results are consistently placed among the top methods across all sizes. Furthermore, we note that our sensitivity sampling vector is computed once during experiments for each dataset. This vector can be used to sampled coresets of different sizes, for different networks, at different epochs of training, in a time that is close to seconds. Note that the best results are represented in bold text, while the fastest are underlined.
Table 1: Data Selection Results for CIFAR10 using ResNet-18
Top-I
Test accuracy of the Model(()
Model
Training time(in hirs
Budget (6)
5%
10%
20%
30%
5%
10%
20%
30%
FULL (skyline for test accuracy)
95.09
95.09
95.09
95.09
4.34
4.34
4.34
4.34
RANDOM (skyline for training time)
71.2
80,8
86.98
87.6
0.22
0.46
0.92
1.38
RANDOM- WARM (skyline for training time)
83.2
87.8
90.9
92.6
0.21
0.42
0.915
1.376
GLISTER
85.5
91.92
92.78
93.63
0.43
0.91
1.13
1.46
GLUSTER-WAaD WARM
86.57
91.56
92.98
94.09
0.42
0.88
1.08
1.40
CRAIG
82.74
87.49
90.79
92.53
0.81
1.08
1.45
2.399
CRAIG-WARD WARM
84.48
89.28
92.01
92.82
0.6636
0.91
1.31
2.20
CRAIGPB
83.56
88.77
92.24
93.58
0.4466
0.70
1.13
2.07
CRAIGPB WARM
86.28
90.07
93.06
93.8
0.4143
0.647
1.07
2.06
GRADMATCH
86.7
90.9
91.67
91.89
0.40
0.84
1.42
1.52
GRADMATCH- HOMATCH-WARM WARM
87.2
92.15
92.11
92.01
0.38
0.73
1.24
1.41
ATCHP
85.4
90.01
93.34
93.75
0.36
0.69
1.09
1.38
GRADMATCHPE. BAAMR
86.37
92.26
93.59
94.17
0.32
0.62
1.05
1.36
RBENN CORESET (OURS)
86.9
91.4
93.61
94,44
0.28
0.52
0.98
1.38
RBENN CORESET- WARM (OURS)
87.82
91.44
93.81
94.6
0.27
0.51
0.99
1.34
8

---

Under review as a conference paper at ICLR 2023
Table 2: Data Selection Results for CIFAR using ResNet-18
Top-I
Test accuracy of the (%)
Model
Training time(in hrs)
Budget(
5%
10%
20%
30%
5%
10%
20%
30%
FULL (skyling line for test accuracy)
75.37
75.37
75.37
75.37
4,871
4,871
4.871
4.871
RANDOM (skyline training time)
19.02
31.56
49.6
58.56
0.2475
0.4699
0.92
1.453
RANDOM-WARM (skyline for training time)
58.2
65.95
70.3
72.4
0.242
0.468
0.921
1.43
GLISTER
29.94
44.03
61.56
70.49
0.3536
0.6456
1.11
L,5255
GLISTER-WAR WARM
57.17
64.95
62.14
72.43
0,3185
0.6059
1.06
1.452
CRAIG
36.61
55.19
66.24
70.01
1.354
1.785
1.91
2.654
CRAIG- WARM
57.44
67.3
69.76
72.77
1.09
1.81
2.4112
CRAIGPB
38,95
54,59
67.12
70.61
0.4489
0.6564
1.15
1.540
CRAIGPB- WARM
57.66
67.8
70.84
73.79
0.394
0,6030
1.10
1,5567
GRADMATCH
41.01
59.88
68.25
71.5
0,5143
0.8114
1.40
2.002
GRADMATCH- WARM
57.72
68.23
71.34
74.06
0,3788
0.7165
1.30
1.985
GRADMATCHPB
40.53
60.39
70.88
72.57
0.3797
0.6115
1.09
1,56
GRADMATCHPP WARM
58.26
69.58
73,2
74.62
0,300
0.5744
1.01
1.5683
REFNN CORESET (OURS)
54.17
64.39
71.17
73.58
0.346
0,5699
1.01
1,552
RBFNN CORESET- WARM (OURS)
59.22
67.8
72.79
75.04
0.352
0,5710
1.03
1.56
Table 3: Data Selection Results for Image using ResNet-18
Top-1 Test accuracy of the Mo
Model Training time(in hrs)
Budget(5))
5%
5%
FULL (skyline for accuracy)
70,36
276.28
RANDOM (skyline for training time)
21.124
14.12
CRAIGPB
44.28
22.24
GRADMATCH
47.24
18.24
FTRADMATCHPP
45.15
16.12
RBENN CORESET (OURS)
47.26
15.24
6.1 FUNCTION APPROXIMATIONS
In this section, we compare our coreset to uniform for approximating the linear regression loss function by running RBENN on the coreset, where the results are averaged across 8 trials, while the shaded regions correspond to the median absolute deviation. It is clear from Figure 2 that our coreset outperforms uniform sampling. Furthermore learning on the coreset was x30 faster than learning the whole data. The data set is the 3D spatial networks (Dua et al. 2017
CONCLUSION AND FUTURE WORK
In this paper, we have introduced coreset that provably approximates any function that can be represented by a RBFNN architecture. Our coreset construction can be used to ap- proximate the gradients of any deep neural networks (DNNs), leading towards provable subset selection for learning/training DNNs. We also empirically demonstrate the value of our work by showing significantly better per- formances over various datasets and model architectures. As the first work on using core- sets for data subset selection with respect to RBFNNs, our results lead to a number of in- teresting possible future directions. is natu- ral to ask whether there exist smaller coreset constructions that also provably give the same worst-case approximation guarantees. Another ques- tion is whether results can be extended to more general classes of loss functions. Finally, remark that although our empirical results significantly beat state-of-the of-the-art, they nevertheless only serve proof-of-concept and have not been fully optimized with additional heuristies.
Uniform sampling
2.0
Our RBFNN coreset
Aggroximation erfor
1.0
0.5
5000
10000
15000
20000
Sample size
Figure 2: Function approximation.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Giduthuri Sateesh Babu and Sundaram Suresh. Sequential projection-based metacognitive learn- ing in a radial basis function network for classification problems. IEEE transactions on neural networks and learning systems, 24(2)194-206,, 2012.
Cenk Baykal, Lucas Liehenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Sensitivity- informed provable pruning of neural networks. SIAM J. Math. Data Sci., 4(1):26-45, 2022.
Ondrej Bohdal, Yongxin Yang. and Timothy M. Hospedales. Flexible dataset distillation: Learn labels instead of images. CoRR, abs/2006. 08572, 2020.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming 2016.
coreset constructions, arXiv preprint
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 517-528, 2020.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neu- ral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In Proceedings of the 35th International Conference on Machine Learning, ICML, pp. 697-705, 2018.
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923-99) 2009.
Rachit Chhaya, Anirban Dasgupta, and Supratim Shit. On coresets for regularized regression. In Proceedings of the 37th International Conference on Machine Learning, ICML, 2020.
Kenneth Clarkson. Coresets, sparse greedy approximation, and the frank-wold algorithm. ACM Trans. Algorithms, 6(4):63:1-63:22 2010.
Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank ap- proximation via ridge leverage score sampling. In Proceedings of the Twenty-Eight Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1758-17777 2017.
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 1038-1051, 2022.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint a9X6v: 1829, 2019.
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney. Sampling algorithms and coresets for Lp regression. Proceedings of the Nineteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 932-941, 2008
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre- mre-training of deep bidirectional transformers for language understanding. In Proceedings the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NA.CL-HI.T, pp. 4171-4186 2019.
10

---

Under review as a conference paper at ICLR 2023
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR, 2021.
Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017.
Dan Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl. Discov, 10(1), 2020.
Dan Feldman, Melanic Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3):601-66)) 657, 2020.
Sariel Har-Peled and Soham Mazumdar. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 291-300, 2004.
coresets for k-means and k-median clustering. In
C Harpham and Christian W Dawson. The effect of different basis functions radial basis function network for time series prediction: A comparative study. Neurocomputing, 69(1--8); 2161-2170, 2006.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1416-1429, 2020.
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei. Composable core-sets for determinant maximization problems via spectral spanners. In Proceedings of the 2020 ACM- SIAM Symposium on Discrete Algorithms, SODA, pp. 1675-1694, 2020.
Ibrahim Jubran, Murad Tukan, Alaa Maalouf, and Dan Feldman. Sets clustering. In International Conference on Machine Learning, pp. 4994-5005. PMLR, 2020.
Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, and Dan Feldman. Coresets for decision trees of signals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp. 30352-30364, 2021.
Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrishnan. Learning from less data: unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference Applications of Computer Vision (WACV), pp. 1289-1299, IEEE Computer Society, 2019.
KrishnaTeja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, and Rishabh K. Iyer. GRAD-MATCH: gradient matching based data subset selection for efficient deep model training. In Proceedings of the 38th International Conference on Machine Learning, ICML, pp- 5464-5474, 2021a.
KrishnaTeja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh K. Iyer. GLISTER: generalization based data subset selection for efficient and robust learning. In Thirty- Fifth AAAI Conference on Artificial Intelligence, AAAI, 2021b.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey F. Hinton. Imagenet classification with deep convo- lutional neural networks. Commun. ACM, 60(6):84-90, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2344 1998.
James A Leonard and Mark A Kramer. Radial basis function networks for classifying process faults. IEEE Control Systems Magazine, 11(3):31-88, 1991.

---

Under review as a conference paper at ICLR 2023
Henry Leung. Titus K. Y. Lo, and Sichun Wang. Prediction of noisy chaotic time series using an optimal radial basis function neural network. IEEE Trans. Neural Networks, 1235)1116--112, 2001.
Lucas Liebenwein, Cenk Baykal, Harry Lang, Dan Feldman, and Daniela Rus. Provable filter pruning for efficient neural networks. In International Conference on Learning Representations, 2019.
Jinkun Liu. Radial Basis Function (RBF) neural network control for mechanical systems: design, analysis and Matlab simulation. Springer Science & Business Media, 2013.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint urXiv:1608.03983 2016.
Yingwei Lu, Narasimhan Sundararajan, and Paramasivan Saratchandran. A sequential learning scheme for function approximation using minimal radial basis function neural networks. Neu- ral Compur., 9(2):461 478, 1997.
Alaa Maalouf, Adiel Statman, and Dan Feldman. Tight sensitivity bounds for smaller coresets. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2051-2061, 2020.
Alaa Maalouf, Ibrahim Jubran, Murad Tukan, and Dan Feldman. Coresets for the average case error for finite query sets. Sensors, 21(19):6689, 2021.
Alaa Maalouf, Murad Tukan, Eric Price, Daniel G Kane, and Dan Feldman. Coresets for data discretization and sine wave fitting. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, and Samson Zhou. Non-adaptive adap- tive sampling on turnstile streams. In Proccedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC, pp. 1251-1264, 2020.
Raphael Meyer, Cameron Musco, Christopher Musco. David P. Woodruff, and Samson Zhou Fast regression for structured inputs. In The Tenth International Conference Learning Repre- sentations, ICLR, 2022.
Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proceedings of the 37th International Conference Machine Learning, ICML, pp. 6950-6960, 2020a.
Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of deep neural networks against noisy labels. In Advances Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems, NeurIPS, 2020b.
Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman. Data- independent neural pruning via coresets. In 8th International Conference on Learning Represen- tations, ICLR, 2020.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp. 5186-5198, 2021.
Kaan Ozkara, Navjot Singh, Deepesh Data, and Suhas N. Diggavi. Quped: Quantized personaliza- tion via distillation with applications to federated learning. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, 2021.
pp.
J Padmavati. A comparative study on breast cancer prediction using rbf and mlp. International Journal of Scientific Engineering Research, 2(1):1-5, 2011.
Jooyoung Park and Irwin W. Sandberg. Universal approximation using radial- sasaal-bbii--aaa wasi-bbauctiiiooo net- works. Neural Comput., 3(2):246-257, 1991.
12

---

Under review as a conference paper at ICLR 2023
Jooyoung Park and Irwin W. Sandberg. Approximation and radial-basia functinn networks. Neural Comput., 5(2):305-316, 1993.
Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green AI. Commun. ACM, 63(12): 54-63, 2020.
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training NLP models: concise overview. CoRR, abs/2004.08900, 2020.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in NLP. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL, pp. 3645-3650, 2019.
Elad Tolochinsky, Ibrahim Jubran, and Dan Feldman. Generic coreset for scalable learning of mono- tonic kernels: Logistic regression, sigmoid and more. In International Conference Machine Learning, ICML, 2022.
Morad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. Advances in Neural Information Processing Systems, 33, 2020.
Murad Tukan, Cenk Baykal, Dan Feldman, and Daniela Rus. On coresets for support vector ma- chines. Theor. Compul. Sci., 890: 190:171-191, 2021. 2021.
Murad Tukan, Loay Mualem, and Alaa Maalouf. Pruning neural networks via coresets and convex geometry: Towards assumptions. In Proceedings of the 36th International Conference Neural Information Processing Systems, 2022a.
Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In International Conference on Artificial Intelligence and Statistics, AISTATS,, pp. 5391-5415, 2022b.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi-stage submodular maximization. In International conference on machine learning, pp. 1494-1502. PMLR, 2014.
Bruce Whitehead and Timothy D. Choate. Cooperative-competiine genetic evolution of radial basis function centers and widths for time series prediction. IEEE Trans. Neural Networks, 7(4): 869-880, 1996.
David P. Woodruff and Taisuke Yasuda. High-dimensional geometric streaming in polynomial space. CoRR, abs/2204.03790, 2022.
Lai Wuxing, W Tse Peter, Zhang Guicai, and Shi Tielin. Classification of gear faults using cumulants and the radial basis function network. mechanical systems and signal processing, 18(2):381-333) 2004.
Hao Yu, Tiantian Xie, Stanislaw Paszczyñski, and Bogdan M Wilamowski. Advantages of radial basis function networks for dynamic system design. IEEE Transactions on Industrial Electronics, 58(12):5438-55 54500, 2011.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogeneous federated learning. In Proceedings of the 38th International Conference on Machine Learning, ICML, pp. 12878-12889, 2021.
A CORESET CONSTRUCTIONS
In what follows, we provide the necessary tools to obtain coreset; Definition
I
Definition (Query space). Let P be set of points in Rdd, P - [0, oo) be non-negative weight function, and let P. dd + [0, oo) denote a loss function. The tuple (P, w, Rd f) is called a query space.
13

---

Under review as a conference paper at ICLR 2023
Definition 10 WC-dimensoon (Braverman al. 2016)). For query space (P, (,,,RR. f) and [0, oo), we define
ranges(z,)) (p (p P w(p)f(p, x) r)
for every I Ihd and
0. The dimension of (P, w. IR. (] is the size (S| of the largest subset
C. P such that
(s ranges(a, r) R. r 2 0} =
where A denotes the number of points in for every A _ R
The following theorem formally describes how to construct an E-coreset based on the sensitivity sampling framework.
Theorem 11 (Restatement of Theorem 5.5 in BBavverman et 2016)). Let (P, w, Fd ff be query =(p)f(p.a) space in Desinition 9 For every p P define the sensitivity of supzERd Eger ( (q.z))
[0. 1] be where the sup over every x Idd such that the denominator non-zero. Let 8 s(p) and d' be a function such that s(p) is an upper bound on the sensitivity of p. Let 1 = Let 2 be sufficiently large
the VC dimension the triplet (P, w. RR, f); see Definition 10
constant, e,8 (0,1). 1). and let S be random sample of
et (d' (d'log 2
|S|
+ log
i.id points from P, such that every P is sampled with probability s(p)/t. Let u(p) every p E S. Then, with probability at least 1 - 5, (S, v) an E-coreset for P with respect to f.
sp]]s| for
tw(p)
B PROOFS FOR OUR MAIN THEOREMS
B. PROOF OF CLAIM 5
Claim 5. Let p E Rd such that llpll S 1, and let 0 be positive real number. Then for every
{a E Rd |x|1| S RJ.
R (1 + R) (1+ |p"xl) se-1paa 1= +1.
Proof. Put x E f E |< < R} and note that if p² 0 then the claim is trivial. Otherwise, we observe that
1
1
1 1p x
R
(1+ R) R
B.2 PROOF THEOREM 6
Claim 12. Let a, b 2 0 be pair of nonnegative real numbers and let d > O be pair of positive real numbers. Then
b b
+ c
c d
Proof. Observe that
a+b b
a
b
a
+ c
+ c
c
c
where the inequality holds since e, > 0.
Lemma 13 (Sensitivity bound w.r.t the RBF loss function). Let R 2 1 be positive real number;
and let X = ff x E & ||0||| S R}. Let (P, F.,,..R. Rdd, .f) be query space as in Definition where for
every p E P and x E Rd,, (() = 11, Let P = = [|||||2 -2p". 21]" Vp E P) and
14

---

Under review as a conference paper at ICLR 2023
let q² E arg sup 2 (1 + 3R (1911)) Let u(p)
ax 1l<pl w(p)
(24382 and let (U.D.V)
9EPr
be the -VVD of (P", u(-)). Then for every p E P.
u(p)
s(p) S 312 3 spll2 (1+ 312 11m112)
Σ u u(/) + u(p)) 11 (4m)ll
FEP
and
Σ x(q)== S 1 (1 3R² 114111))
(1 1 (d (d+ 2)).s)
QEP
Proof. Let x= =
ER 1}, and observe that for every p P and E Rd, it holds that
||p x 11 = 10 ml
(3)
where 9p = 111p112 -2p" 1]² and y = [1, || T
Let Y = [1, |1:1 T " | [ Following the definition of Y, for every y E Y, we obtain that llvil, S 3R²h Hence, by plugging =- Se and R =- 3/2 ||pp|| for every E P into Claim 5 obtain that the for every y Y and E P.
Tepll
we
(1+ + up ul) S e - 195
S + 1 y
(4)
GR 9olla (1 + 3R² (192112)
Note that for every p E P, u(p) (1+331l2))
w(p)
Thus
wpp)f(p,2)
sup =eX 9EP
Σ w(1){(g,z)
w(p)e- 115
sup yeY Σ w(1) 1f-11
p'Em"
u(p)
1/ yl
+ u(p)
(5)
< 1977l2 (1 + 3RR² (11l11))
sup NEY
Σ a (p/)
E u (p¹) P'EP
MEP
S 344l1 (1 + 3R² (1m)
u(p)
u(p) 1 y
+ sup
Σ
u (p')
vEY
Σ (V') 4p/10
WEP
PEP
where the first inequality holds by Claim 5 and the second inequality is by Claim 12
Let f : P' Y + [0, oo) be function such that for every q E P' and Y. f(a.v) = |4 vl- Plugging in P == P", w = u. d := d 2, and f := f into Lemma 3 yields for every E P
sup w(p)f(p,x)) < aa (1 3R² (1421la)
u(p) Σ WEP
(p') + u(p) |I (ww)ll)
(6)
=eX Σ w(g)f(q.x) TEP
Note that by definition, 4"' E sug gEP"
3n (1 + 3R² (1l12)) Then the total sensitivity is
bounded by
Σ sup Σ w(g)s(g, S 312 (1 3R² 11a"1l)) (I+ (d+2)) 22) 2))
(p))((p.z)
REX QEP
15

---

Under review as a conference paper at ICLR 2023
Theorem 6 (Coreset for RBF). Let R 2 be positive real number, X = fs B [= I R). and let e, E (0.1). Let (P. w, f)) be query spuce as in Definition
9 such that every p E P
satisfies lplll2 S For every to CORESET(P, w, R. m) where S P and :S + [0, oc). Then (S, v) e-coreset of (P,w) with probability at least - 8. if = 128² R
X and p E P, let f(p, x) = p(lpp =11))- Let (S, v) a call
(R² + log + log :))
Proof. First by plugging in the query space (P, w. IR f) into Lemma 13 we obtain that bound the sensitivities s(p) for every p E P and bound the total sensitivities / := since the mäXger |lal22 < 1. Notice that the analysis done
121tt (1 + 1222) (1 (d+
Lemma
13 analogues the steps done in Algorithm |
By plugging the bounds on the sensitivities, the bound on the total sensitivity t, probability of failure
(0, 1), and approximation error ε (0, 1) into Theorem 11 we obtain a subset S' C Q and
o' S + [0, oo) such that the tuple (S", vo) is an e-coreset for (P: w) with probability at least 1-6. 6.
B.3 PROOF OF THEOREM 7
Lemma 14 (Sensitivity bound w.r.t. the Laplacian loss function). Let (P, w, Rd be query 9 where for every p E P and E R4, f()xx) e-11e-zil,, Let space in Definition
P' = 9p |1el2 22p".
T Vp E P] and let q" argsuppEP eVVllala (1+ (1+3v/lallz) Let and let (U,D,V) the I1-11, of (P", 22)). Then for every
up) 3 / (143
m(p)
P P.
u(p) Σ up)) + u(p) |IU (4x)l1 PEEP
elelllz / Vlloolll (()
s(p) @3Vilnolla (1+3
+
Σ w(1)
PEP
and
Σ5(0) s 1 + (1+3/ //3/lll (1+ v (d+
10
QEP
Proof.
Let X = fo E |= $ 1). and observe that for every p E P and x E Rd. holds that
|pp ==11== = V /99888).
(8)
where 9, =[|p|]2 -2p" TT 1] and y= [1, ||0||
Let Y [1,,,,|<<13] ||=1|]]] x x]. Hence, following Theorem the sensitivity of each point
p E P, can be rewritten as
w(p)f(p.2) < sup xEX Σ w(g)f(g,x) OEP
w(p)f(p.x)
wpp)f(p,
sup
Σ w(g)f(q,zz OEP
sup Σ w(g)f(g,x)) x dEP
(9)
ZERd
From here, we bound the sensitivity with respect to subspaces of Rdd
Handling queries from X. Following the definition of Y, for every y E Y, we obtain that ||v|| < 3.
Hence, by plugging := qp for every p P and R = 3 |1 into Claim 5 we obtain that the for every y E Y and P.
(1+Vlog))
10 S s1+ Vl0g m/-
(10)
3 lollla (1 + 3 (11
16

---

Under review as a conference paper at ICLR 2023
Note that for every P. u(p) == e eVllorlla (1+3 1-3 (1
w(p)
Combining equation 9 and equation 10.
yields that
w(p)f(p,x) Σ (1) S <eVlluolla (1=3/119g) ///lpplla PEP
2 u(p) 4 M + +u(p)
sup wE
sup NEY
Σ u (p') v [
+ Σ w (p'
MEEP
VEP
u(p) v 16 us
S <ellllll (1 3-3//1 3/11lbl)))
u(p)
sup VEY
Σ MEP
u
(F')
Σ u (1d)
F'EP
(11)
where the first incquality holds by Claim 5 and the second inequality is by Claim 12 By Cauchy-Schwards inequality,
u(p) V 15
[u(p2
105
sup DEY
sup DEY
Σ u (D') v (og-11
Σ P'Er
(0²)
PEP
u(p)
1 yl
S sup yEY
Σ u(1)²
PEP
u(p)²
1 9
< sup #ER442
(12)
Σ u(g)²
WEP
where the last inequality follows from the properties associated with the supremum operation.
Let u' P' - [0, co) be weight function such that for every p E P, u' (qp) = =pp)² . P' 4
[0, oc) be function such that for every q E P' and Y, f(g. v) = 1 v/- Plugging in P == Pl,
w = u, == d + 2, and f == I into Lemma yields for every p E P
sup w(p)s(p, #eX Σ w(1)s(q,4) S e3VVleella (1 3/ (++3/l1bbl>))
u(p) Σ u (v) #EP
u(p) u VIU (gx)
(13)
gEP
Note that by definition, q²' E arg sup ger
AVlllll (1 + 311ppl1)).. Then the total sensitivity is
bounded by
Esu sup (p)s(pp,)) pzex Σ w(g)f(g,x) S SeaVile'Ta (1+3, (1+3//101ls) (1+ vn (14)
PEP
where the v follows from Eyep VIU (gp))l I VT Eyer |IU (4 which used when using Lemma]
This inequality a result of Cauchy-Schwarte' 's inequality.
Handling queries from Rdd \ X. First, we observe that for any integer m 2 1 and a, E R
- ||||| - |lvll, < - || - vllı S || ||vll
(15)
where the first incquality holds by the triangle inequality, and the second inequality follows from the reverse triangle inequality.
17

---

Under review as a conference paper at ICLR 2023
(()))(()))) Thus, by letting Tp arg sup Σ (()) for every P. we obtain that =ER VEP
u(p)s (p, Σ w(g)s kp) GEr
w(p)ellp 1 1-11pll 1
w(p)ellplla=1lzze -1
.1llll
f1 /
Σ w(g)e llal2 lnllla
Σ
w(g)e 110"112-1lzzl)
Σ w(g)
qEP
PEP
gEP
Vll4 11 (16)
where the first inequality holds by equation 15 lllllz for every E P.
and the second inequality holds since
Combining equation
equation
13
equation
and equation 16 yields that for every p P
s() & 2 (1 (1+3// 3 [10olla)
u(p) u (p')
+ u(p)y/ |IU (q))1
Σ PEP
Σ w(q)
PEP
and
Σs(p) 5 26 Vooaollll. 11 eollll (1+ (1+3/110112) (1+ vn (d (d ((++2)2 2)2
PEP
Theorem 7 (Coreset for the Laplacian loss function). Lel (P, w. RR, be query space as in Defi- nition such that every p E P satisfies |ll|2 S 1. For Rd and p P. let x) e 1le--12, Let e, ó E (0, 1). Then there exists an algorithu which given P. v,,,,6 return a weighted set (S,z) where S C of size O
yidd 2²
(log n + log d + log ?)) and weight function v > 00)
such that (S, v) an E-coreset of (P, w) with probability at least 5
Proof. Plugging in the query space (P, w, , f) into Lemma 14 we obtain that bound on the sensitivities s(p) for every p E P and a bound on the total sensitivities t == 2 + 3e (1 ++5) (1 /n (d 2)1.5). since the max [|gllz I By plugging the bounds on the sensitivitics, the bound on the total sensitivity t, probability of failure å (0, 1). and approximation
error (0, 1) into Theorem II we obtain a subset S' C Q and v' : S² - [0, oo) such that the tuple (S', o') is an c-coreset for (P, w) with probability at least 6.
B.4 PROOF OF THEOREM S
To prove Theorem g we first prove the following theorem.
Theorem 15. There exists algorithm that samples O (
(ehe Rea (R² + log d + log 2))
points
e²
to form weighted sets (S1, w2) and (S2, w2) such that with probability at least 1 - 26,
wi (p)e 1|00-60012 (1ppec-loo-0001
w2(g)e 111o-ot01 -2(g)c-llo-o(ijp
Σ v(p)p(1pp- -l0) PEP
Σ
Σ
PESI
DES²
I E.
/ (c(i) + x (c(0)
Proof. We first construct strong coresets for both o+ and o- If [[c,]|2 22 S R for all i E [n], then by 12x" 1Pats (12² + log d + log /)
Theorem 6 it suffices to sample a weighted weight S of size O
to achieve a strong coreset S₁ with corresponding weighting function for ø with probability at least 5. Similarly, we obtain strong coreset for Φ with probability at least o by sampling 2
a set S2 with weights w2 of size O c
and2
R²a"
(R²2 + log d + log 3) 3)).
18

---

Under review as a conference paper at ICLR 2023
Hence by the definition of strong coreset, have that
Σ u c02
E
w1(p)p(1pp l2) Se Σ v(0)p(lp-cC0)
PEs,
PEP
((P)>0
v(n)30
= eΦ' (c("))
and
Σ v(p)p(llp- c(0) Σ
w2(1))((la-c (l)
S
Σ ((D)le((1p-C"
PEP v(A)<0
0ES2
PEP v(r)
= cΦ (c(t))
for any input x R
Thus by triangle inequality and a slight rearrangement of the inequality, we have that with probability least 1 - 6,
Σ v(p)p(1pp- cl))))) pEp
Σ
wi (p)e- 11 (p)e-11e-<<)1
Σ PES,
w2(g)e w2(g)e-(la-elll
PES,
S 6.
x (c(0) + x- (c(0)
To prove Theorem we split Or into the sets {ila, 0} and {i < 0} and apply Theorem 15 to each of the sets. We emphasize that this argument purely for the purposes of analysis so that the algorithm itself does not need to partition the a, quantities (and so the algorithm does not need to recompute the coreset when the values of the weights a change over time). We thus get the following guarantee:
Theorem 8. There exists an algorithm that samples O ( (MHR R2d' (R² + log d + log ) points to
2²
form weighted sets (S1, si, and (S2, w2) such that with probubility at least 25,
wi(p)e--loe-ae -1l- 110
Σ aj Σ W2(g)e (
110-c
Σ x(p)((p) PEP
Σ az Σ wi(ple
PESt
JELL a
4ES²
0,50
Σ as (ot (cli) + + (c01)) LELL]
+ Σ lail (ot (cli)) x (ct1))
RELL) a.<0
a.20
C LOWER BOUND ON THE CORESET SIZE FOR THE GAUSSIAN LOSS FUNCTION ILLUSTRATION
Here, we illustrate dataset such that for any approximation E, the e-coreset must contain least half the points to ensure the desired approximation from a theoretical point of view.
D EXPERIMENTAL RESULTS EXTENDED
D. MNIST RESULTS
In what follows, we present subset selection results the MNIST dataset at Table 4
19

---

Under review as a conference paper at ICLR 2023
P2
p3
P1
P1
P1o
P5
P9 P6
Figure 3: Evenly distributed points circle where the minimal distance between each point and any other point is at least Vin where in this example 10.
Table 4: Data Selection Results for MNIST using LeNet
Top-1
Test accuracy
Model(
Model Training time(in hrs)
(Sdget(S))
1%
3%
5%
10%
1%
3%
5%
10%
FULL Gskline lor Lest accuracy)
99.35
99.35
99.35
99.35
0.82
0.82
0.82
0.82
RANDOM (skyline for truining time)
94.55
97.14 14
97.7
98.38
0.0084
0.03
0.04
0.084
(skyline for training time)
98.8
99.1
0.03
GLISTER
93.11
98.062
99.02
99.134
0.045
0.0625
0.082
0.132
GLISTER-WARD
97.63
98.9
99.1
99.15
0.04
0.058
0.078
0.127
CRAIG
96.18
96 93
97.81
98.7
0.3758
0.4173
0.434
0.497
CRAIG- WARM
98.48
98
0.2239
0.258
0.2582
0.3416
CRAIGPB
97.72
98.47
98.79
99.05
0,08352
0.106
0.1175
0.185
CRAIGPB-WARD WARM
98.47
99.08
99.01
99.16
0.055
0.077
0.0902
0.1523
GRADMATCH
98.954
99.174
99.214
99.24
0.0607
0.097
0.138
GRADMATCH- WARM
98.86
99
99.28
0.046
0.057
0.089
0.132
GRADMATCHPE
98.7
99.1
99.25
99.27
0.04
0.051
0.07
0.11
GRADMATCHPE B--M
99.0
99.23
99.3
99.31
0.038
0.05
0.065
0.10
RBENN CORESET (OURS)
98.98
99.2
99.31
99.32
0.028
0.051
0.062
D.2 STANDARD DEVIATION AND STATISTICAL SIGNIFICANCE RESULTS
Tables 7 show the standard deviation results over five training CIFARIO, CIFARI00, and MNIST datasets, respectively.
Table 5: Data Selection Results for CIFAR10 using ResNet-188 (for 5 runs)
Standard deviation of the Model
Standard deviation of the Model(for runs)
Budget(%)
5%
10%
20%
30%
FULL (skyline for test accuracy)
0.032
0.032
0.032
0.032
RANDOM (skyline for training time)
0,483
0.518
0.524
0.538
RANDOM- WARM (skyline for training time)
0.461
0.348
0.24
0.1538
GLISTER
0,453
0.107
0.046
0.345
GLISTER- WARM
0.325
0.086
0.135
0.129
CRAIG
0,289
0.2657
0.1894
0.1647
CRAIG- CRAIG-WARM
0.123
0.1185
0.1058
0.1051
CRAIGPB
0.152
0.1021
0.086
0.064
CRAIGPB- HAIGGB--WAMM WARM
0.0681
0.061
0.0623
0.0676
GRADMATCH
0.192
0.123
0.112
0.1023
GRADMATCH-WAAL
0.1013
0.1032
0.091
0,1034
GRADMATCHPB
0.0581
0.0571
0.0542
0.0584
GRADMATCHPB-WA. WARM
0.0542
0.0512
0.0671
0.0581
RBFNN CORESET (OURS)
0.25
0.2
0.17
0.13
RBENN CORESET- WARM (OURS)
0.21
0.16
0.13
0.12
20

---

Under review as a conference paper at ICLR 2023
Table 6: Data Selection Results for CIFAR100 using ResNet-18: Standard deviation of the Model (for 5 runs)
Standard deviation of the Model(for 5 runs)
Budget(%)
5%
10%
20%
30%
FULL (skyline for test accuracy)
0.051
0.051
0.051
0.051
RANDOM (skyline for training time)
0.659
0.584
0.671
0.635
RANDOM WARM (skyline for training time)
0.359
0.242
0.187
0.175
GLISTER
0.463
0.15
0.061
0.541
GLISTER WARM
0.375
0.083
0.121
0.294
CRAIG
0.3214
0.214
0.195
0.187
CRAIG-WARM
0.18
0.132
0.125
0.115
CRAIGPB
0.12
0.134
0.123
0.115
CRAIGPB WARM
0.1176
0.1152
0.1128
0.111
GRADMATCH
0.285
0.176
0.165
0.156
GRADMATCH- -WMMMMAHH--AMMMM
0.140
0.134
0.142
0.156
GRADMATCHPB
0.104
0.111
0.105
0.097
GRADMATCHPP-WAAN WARM
0.093
0.101
0.100
0.098
RBFNN CORESET (OURS)
0.3
0.19
0.18
0.16
RBENN CORESET- WARM (OURS)
0.19
0.14
0.11
0.1
Table 7: Data Selection Results for MNIST using LeNet: Standard deviation of the Model (for runs)
Standard deviation of the Model(for 5 runs
Budget(%)
1%
3%
5%
10%
FULL (skyline for test accuracy)
0.012
0.012
0.012
0.012
RANDOM (skyline for training time)
0.215
0.265
0.224
0.213
RANDOM-WARM (skyline for training time)
0.15
0.121
0.110
0.103
GLISTER
0,256
0.218
0.145
0.128
GLISTER WARM
0.128
0.134
0.119
0.124
CRAIG
0.186
0.178
0.162
0.125
CRAIG-WAL WARM
0.0213
0.0223
0,0196
0,0198
CRAIGPB
0.021
0.0209
0.0216
0.0204
CRAIGPB- WARM
0.023
0.0192
0.0212
0.0184
GRADMATCHI
0.156
0.128
0.135
0.12
GRADMATCHI- WARM
0.087
0.084
0.0896
0.0815
GRADMATCHPP
0.0181
0.0163
0.0147
0.0129
GRADMATCHPB. WARM
0.0098
0.012
0.0096
0.0092
RBENN CORESET (OURS)
0.18
0.13
0.11
0.1
RBENN CORESET- WARM (OURS)
0.09
0.08
0.05
0.01
D.3 RBF FITTING OUR CORESET VERSUS UNIFORM SAMPLING
In this experiment, we aim to show the efficacy of our coreset against uniform sampling for the task of fitting RBFs. Specifically speaking, we have taken two datasets: (i) 3D spatial networks Dua ct al. 2017). and (ii) HTRU2 pulsar dataset (Dua et al. 2017
In the following figures, we report the averaged approximation factor over 20 trials, where the shaded area corresponds to the median absolute deviation, more robust statistical measurement that the standard deviation.
21

---

Under review as a conference paper at ICLR 2023
2-3
Uniform sampling
Our coreset
2-5
Approximation error
2-7
2-9
2-11
200
400
600
800
1000
Sample size
Figure 4: The averaged approximation error: The z-axis is the size of the chosen subset, while the y axis is the averaged approximation error. This is with respect to dataset
Uniform sampling Our coreset
23
Approximation error E
20
2-3
2-6
2-9
0
200
400
600
800
1000
Sample size
Figure S: The averaged approximation error: The æ-axis is the size of the chosen subset, while the axis is the averaged approximation enror. This is with respect to dataset (ii)
22


Reviews:
[{"review_id": "kE7Fn-vkoJd", "reviewer": "Reviewer_NHbT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes an algorithm for coreset selection with low computation time. The key idea is to approximate a function using RBFNN on a large dataset and then construct coresets for radial basis and Laplicain loss function. Empirically, the authors show that the proposed method can find a small coreset with competitive performance with the existing baseline methods on MNIST, CIFAR-10, and CIFAR-100 datasets.\n", "summary_of_the_review": "Overall, I believe that the idea presented in the paper is interesting and the paper is overall well-written. There are some concerns about the experiment analysis (e.g., the small number of baseline methods, evaluation on relatively small datasets and architectures, limited performance on CIFAR-100 and MNIST, and no ablation studies). I recommend 6. ", "strength_and_weaknesses": "As detailed below, the paper is well-written and I believe that the idea presented in this paper is novel. Note that I am not familiar with the background and did not fully understand the mathematical justification. Hence, my most concerns lie in the experiment section:\n\n- While the paper is generally easy-to-follow, the motivations in Section 1 are unclear.\n- The paper does not sufficiently describe the limitation of the proposed approach. What are additional hyperparameters that need to be tuned (e.g., $R$) and how robust are they? The paper briefly mentions that the algorithm is robust to these hyperparameters, but did not empirically verify this. \n- The performance seems to be limited for CIFAR-100 and MNIST datasets. \n- The paper does not describe the experiment details and it would be challenging to reproduce the experiment. Moreover, the details on how the hyperparameters (e.g., learning rate) are selected are missing.\n- The evaluations were done on three relatively small datasets and architectures (e.g., MNIST, CIFAR-10, and CIFAR-100) and it is unclear if the method will scale to large settings. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TSCZWR-qgv", "reviewer": "Reviewer_A6tT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose the first coreset construction algorithm for RBFNNs, i.e., a small weighted subset which approximates the loss of the input data on any radial basis function network. This is achieved by constructing coresets for radial basis and Laplacian loss functions. The coreset is then used to develop a provable data subset selection algorithm for training deep neural networks, since the coreset approximates every function. Experimental results on function approximation and dataset subset selection on popular network architectures and data sets are presented to demonstrate the effectiveness of the algorithm in certain cases.", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength\n\n- This paper develops the first coreset construction algorithm for RBFNNs and Laplacian cost function. These properties of RBFNNs are further leveraged to approximate the gradients of any deep neural networks.\n\n- The authors also develop provable theoretical guarantees for the proposed coreset construction algorithm. \n\nQuestions:\n\n- In the abstract, `notoriously known' should be `well known'\n\n- The authors study RBFNNs and use them to help data selection as they can approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. But many other neural networks are also universal approximators, I am wondering what is the advantage to use RBFNNs and bridge them with general deep neural networks.\n\n- In the experiments, the authors compare with some SOTA baselines with warm start, i.e., training on the whole data for 50% of the training time before training the other 50% on the coreset. It is shown that the proposed algorithm outperforms these SOTAs without warm start, but worse than with warm start. As warm start is a good strategy used in practice, I suggest the author also add the proposed algorithm + warm start to the comparison.\n\n- How does this approach compare to the clustering-based data selection as discussed in the recent work https://arxiv.org/pdf/2206.14486.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R3PxaVlvJ01", "reviewer": "Reviewer_zk6H", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a coreset construction algorithm for RBFNNs. The coreset corresponds to a data subset selection algorithm for training deep neural networks. Such a coreset can provably approximate any function that can be approximated by a given RBFNN. The proposed algorithm is efficient and the results are empirically verified.", "summary_of_the_review": "This paper presents an interesting coreset construction for RBFNNs, and the authors provide solid theoretical analysis and empirical evaluation for the proposed algorithm.", "strength_and_weaknesses": "Strength:\n\n1. The authors propose a coreset construction algorithm for the RBF and Laplacian cost functions, which is efficient and in theory can be used to approximate the gradients of any deep neural networks.\n\n2. The proposed algorithm construction leverages existing theoretical results; and the authors provide further theoretical analysis for RBF and Laplacian loss functions.\n\n3. The proposed algorithm is efficient - the coreset can be computed before each epoch with negligible time by sampling according to the sensitivity distribution.\n\n4. Extensive empirical evaluation that demonstrates the efficiency and effectiveness of the proposed algorithm.\n\nQuestions and weaknesses:\n\n1. I'm curious about the experiment results - from Tables 1 and 2, the proposed RBFNN Coreset seems to be inferior to some other methods (e.g., GradMatchPB-WARM) for both accuracy and training time. Is this difference mainly coming from the warm start? If so, would warm start help to improve the performance of the RBFNN Coreset?\n\n2. Why is the training time with a warm start shorter than the one without (e.g., Table 1)? Shouldn't train on the whole dataset increase the training time?\n\n3. The standard deviation of the empirical results is not reported - I'm not fully convinced the differences are statistically significant.\n\nMinor issue:\n\nIn definition 2 where the function $U(p)$ is defined, the $P$ should be $p$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ExP2PRQ0M85", "reviewer": "Reviewer_zVhj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors introduced a coreset that provably approximates any function that can be represented by an RBFNN architecture, and use the coreset to suggest a provable data subset selection algorithm for training deep neural networks. The better performances of their algorithms are verified by some experiments. \n\n", "summary_of_the_review": "Due to many confusions in the technical parts, as explained above, I tend not to accept this paper.", "strength_and_weaknesses": "Although the experiment results seem promising, the technical parts may not seem very solid, which makes me have some concerns about the correctness of the results. For example,\n\n1. In Theorems 4 and 6 (and somewhere else), the authors write something like $f(n)\\in O(n)$, this is not the standard notation, it should always be $f(n)= O(n)$ in mathematics.\n\n2. In Theorem 4, actually the author prove that $\\sum s(p) \\geq n/2$. In this case, the results should be $\\sum s(p) = \\Omega (n)$ (the big Omega notation), not $\\sum s(p) \\in O (n)$. \n\n3. The formula in Claim 5 is not correct since letting $R=1$ will give $e/2\\leq 1$, this can not be true.\n\n4. The right hand side of formula in Claim 5 could be $1$, since $e^{-|p^T \\cdot x|} \\leq 1$. I don't understand why it writes $e^{-|p^T \\cdot x|} \\leq 1 + |p^T \\cdot x|$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject