Provable Data Subset Selection For Efficient Neural Network Training
Radial basis function neural networks (\emph{RBFNN}) are {well-known} for
their capability to approximate any continuous function on a closed bounded set
with arbitrary precision given enough hidden neurons. In this paper, we
introduce the first algorithm to construct coresets for \emph{RBFNNs}, i.e.,
small weighted subsets that approximate the loss of the input data on any
radial basis function network and thus approximate any function defined by an
\emph{RBFNN} on the larger input data. In particular, we construct coresets for
radial basis and Laplacian loss functions. We then use our coresets to obtain a
provable data subset selection algorithm for training deep neural networks.
Since our coresets approximate every function, they also approximate the
gradient of each weight in a neural network, which is a particular function on
the input. We then perform empirical evaluations on function approximation and
dataset subset selection on popular network architectures and data sets,
demonstrating the efficacy and accuracy of our coreset construction.
Murad Tukan, Samson Zhou, Alaa Maalouf, Daniela Rus, Vladimir Braverman, Dan Feldman
# Provable Data Subset Selection For Efficient Neural Network Training

###### Abstract

Radial basis function neural networks (_RBFNN_) are well-known for their capability to approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. In this paper, we introduce the first algorithm to construct coresets for _RBFNNs_, i.e., small weighted subsets that approximate the loss of the input data on any radial basis function network and thus approximate any function defined by an _RBFNN_ on the larger input data. In particular, we construct coresets for radial basis and Laplacian loss functions. We then use our coresets to obtain a provable data subset selection algorithm for training deep neural networks. Since our coresets approximate every function, they also approximate the gradient of each weight in a neural network, which is a particular function on the input. We then perform empirical evaluations on function approximation and dataset subset selection on popular network architectures and data sets, demonstrating the efficacy and accuracy of our coreset construction.

Machine Learning, ICML

## 1 Introduction

Radial basis function neural networks (_RBFNNs_) are artificial neural networks that generally have three layers: an input layer, a hidden layer with a radial basis function (RBF) as an activation function, and a linear output layer. In this paper, the input layer receives a \(d\)-dimensional vector \(x\in\mathbb{R}^{d}\) of real numbers. The hidden layer then consists of various nodes representing _RBFs_, to compute \(\rho(\|x-c_{i}\|_{2}):=\exp\left(-\left\|x-c_{i}\right\|_{2}^{2}\right)\), where \(c_{i}\in\mathbb{R}^{d}\) is the center vector for neuron \(i\) across, say, \(N\) neurons in the hidden layer. The linear output layer then computes \(\sum_{i=1}^{N}\alpha_{i}\rho(\|x-c_{i}\|_{2})\), where \(\alpha_{i}\) is the weight of neuron \(i\) 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, 2011).

**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 any continuous function on a closed, bounded subset of \(\mathbb{R}^{d}\) with arbitrary precision (Park & Sandberg, 1991), i.e., given a sufficiently large input set \(P\) of \(n\) points in \(\mathbb{R}^{d}\) and given its corresponding label function \(y:P\to\mathbb{R}\), an _RBFNN_, can be trained to approximate the function \(y\). Therefore, _RBFNNs_ are commonly used across a wide range of applications, such as function approximation (Park & Sandberg, 1991; 1993; Lu et al., 1997), time series prediction (Whitehead & Choate, 1996; Leung et al., 2001; Harpham & Dawson, 2006), classification (Leonard & Kramer, 1991; Wuxing et al., 2004; Babu & Suresh, 2012), and system control (Yu et al., 2011; Liu, 2013), due to their faster learning speed.

For a given RBFNN size, i.e., the 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 of the input data on any radial basis function neural network of this size and thus approximates any function defined (approximated) by such an _RBFNN_ on the big input data. This small weighted subset is called a coreset.

**Coresets.** Consider a prototypical machine/deep learning problem in which we are given an input set \(P\subseteq\mathbb{R}^{d}\) of \(n\) points, its corresponding weights function \(w:P\to\mathbb{R}\), a set of queries \(X\) (a set of candidate solutions for the involved optimization problem), and a loss function \(f:P\times X\to[0,\infty)\). The tuple \((P,w,X,f)\) is called the _query space_, and it defines the optimization problem at hand -- where usually, the goal is to find \(x^{*}\in\operatorname*{arg\,min}_{x\in X}\sum_{p\in P}w(p)f(p,x)\). Given a query space \((P,w,X,f)\), a coreset is a small weighted subset of the input \(P\) that can provably approximate the cost of every query \(x\in X\) on \(P\)(Feldman, 2020; Jubran et al., 2021); see Definition 2.1. In particular, a coreset for a _RBFNN_ can approximate the cost of an _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 a coreset for a _RBFNN_ would facilitate training data for function approximation without reading the full training data and more generally, a strong coreset for an RBFNN with enough hidden neurons would give a strong coreset for any function that can be approximated to some precision using the RBFNN.

**To this end, in this paper, we aim to provide a coreset for _RBFNN_s, and thus provably approximating (providing a coreset to) any function that can be approximated by a given _RBFNN_.**

Furthermore, we can use this small weighted subset (coreset) to suggest a 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 also approximates the gradient of each weight in a neural network (if it can be approximated by the RBFNN).

**Training neural networks on data subset.** Although deep learning has become widely successful 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., 2014; Kaushal et al., 2019; Coleman et al., 2019; Har-Peled & Mazumdar, 2004; Clarkson, 2010). By employing a significantly smaller subset of the big dataset, (i) we enable learning on relatively low resource computing settings 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 hyper-parameter tweaking, and (iii) because a large number of deep learning trials must be done in practice, we allow for considerable reductions in deep learning energy usage and CO\({}_{2}\) emissions (Strubell et al., 2019). Multiple efforts have recently been made to improve the efficiency of machine learning models using data subset selection (Mirzasoleiman et al., 2020; Killamsetty et al., 2021;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 as gradient error or generalization 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 dependent, and thus computing the desired subset of the data after several training epochs (for the same network) takes a lot of time and must be repeated each time the network changes.

**To this end, in this paper, we introduce a provable and efficient 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 a coreset for training multiple neural network architectures/models.**

### Our Contributions

In this paper, we introduce a coreset that approximates any function can be represented by an _RBFNN_ architecture. Specifically:

1. We provide a coreset for the _RBF_ and Laplacian cost functions; see Algorithm 1, and Section 3.1.2.
2. We generate a coreset for any _RBFNN_ model, in turn, approximating any function that can be represented by the _RBFNN_; see Figure 1 for illustration, and Section 4 for more details.
3. 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 techniques; see Section 5 and Section 6.
4. Finally, we provide an open-source code implementation of our algorithm for reproducing our results and future research (ope, 2023).

### Related Work

A long line of active work has studied efficient coreset constructions for various problems in computational 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., 2020; Cohen-Addad et al., 2022), regression (Dasgupta et al., 2008; Chhaya et al., 2020; Tolochinsky et al., 2022; Meyer et al., 2022; Maalouf et al., 2019, 2022), low-rank approximation (Cohen et al., 2017; Braverman et al., 2020; Maalouf et al., 2020, 2021), volume maximization (Indyk et al., 2020; Mahabadi et al., 2020; Woodruff & Yasuda, 2022), projective clustering (Feldman et al., 2020; Tukan et al., 2022), support vector machines (SVMs) (Clarkson, 2010; Tukan et al., 2021; Maalouf et al., 2022), Bayesian inference (Campbell & Broderick, 2018), and sine wave fitting (Maalouf et al., 2022).(Baykal et al., 2022) suggested coreset-based algorithms for compressing the parameters of a trained fully-connected neural network by using sensitivity sampling on the weights of neurons after training, though without pruning full neurons. (Mussay et al., 2020;
Liebenwein et al., 2019; 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 to the input layer was 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;b) 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., 2021a;b). Data distillation has also received a lot of attention in image classification (Bohdal et 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).

**On coresets for any function.** To the best of our knowledge, the only other coresets eligible for handling a wide family of functions without the need to devise a problem-dependent sensitivity are (Claici & Solomon, 2018; Claici et al., 2018). While such coresets are interesting and related, (i) both works provide coreset constructions resulting in an additive approximation, (ii) the coresets' theoretical applications seem quite a bit restrictive as they intend to handle mainly a family of functions that are either \(k\)-Lipschitz (functions with bounded gradient, usually \(k\)), having a bounded Dual-Sobolev distance, or functions satisfying the properties of reproducing kernel Hilbert space (RKHS). In addition, the running time in the worst-case scenario is not practical, i.e., exponential in the dimension of the points.

On the other hand, our coreset under mild assumptions can satisfy any function approximated by RBFNN (Wu et al., 2012), in time that is polynomial in the dimension of the points and linear in the number of nonzero entries of the points (Clarkson & Woodruff, 2017).

## 2 Preliminaries

For an integer \(n>0\), we use \([n]\) to denote the set \(\{1,2,\ldots,n\}\). A weighted set of points is a pair \((P,w)\), where \(P\subseteq\mathbb{R}^{d}\) is a set of points and \(w:P\rightarrow[0,\infty)\) is a weight function.

We now formally provide the notion of \(\varepsilon\)-coreset for the _RBF_ loss. This will be later extended to a coreset for _RBFNN_.

**Definition 2.1** (_RBF_\(\varepsilon\)-coreset).: Let \((P,w)\) be a weighted of \(n\) points in \(\mathbb{R}^{d}\), \(X\subseteq\mathbb{R}^{d}\) be a set of queries, \(\varepsilon\in(0,1)\). For every \(x\in X\) and \(p\in P\) let \(f(p,x):=\exp\left(-\left\|p-x\right\|_{2}^{2}\right)\) denote the _RBF_ loss function between \(p\) and \(x\). An \(\varepsilon\)-coreset for \((P,w)\) with respect to \(f\), is a pair \((S,v)\) where \(S\subseteq P\), \(v:S\rightarrow(0,\infty)\) is a weight function, such that for every \(x\in X\), \(\left|1-\frac{\sum_{q\in S}v(q)f(q,x)}{\sum_{p\in P}w(p)f(p,x)}\right|\leq\varepsilon\).

We say the _RBF_ coreset is _strong_ if it guarantees correctness over all \(x\in X\). Otherwise, we say the coreset is _weak_ if it only provides guarantees for all \(x\) only in some subset of \(X\).

**Sensitivity sampling.** To compute our _RBF_\(\varepsilon\)-coreset, we utilize the sensitivity sampling framework (Braverman et al., 2016). In short, the sensitivity of a point \(p\in P\) corre

Figure 1: Our contribution in a nutshell.
sponds to the "importance" of this point with respect to the other points and the problem at hand. In our context (with respect to the _RBF_ loss), the sensitivity is defined as \(s(p)=\sup_{x\in X}\frac{w(p)f(p,x)}{\sum\nolimits_{c\in P}w(q)f(q,x)}\), where the denominator is nonzero. Once we bound the sensitivities for every \(p\in P\), we can sample points from \(P\) according to their corresponding sensitivity bounds, and re-weight the sampled points to obtain an RBF \(\varepsilon\)-coreset as in Definition 2.1. The size of the sample (coreset) is proportional to the sum of these bounds - the tighter (smaller) these bounds, the smaller the coreset size; we 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.2** (Special case of Definition 4 (Tukan et al., 2020)).: Let \(\left(P,w,\mathbb{R}^{d},f\right)\) be a query space (see Definition A.1) where for every \(p\in P\) and \(x\in\mathbb{R}^{d}\), \(f(p,x)=\left|p^{T}x\right|\). Let \(D\in[0,\infty)^{d\times d}\) be a diagonal matrix of full rank and let \(V\in\mathbb{R}^{d\times d}\) be an orthogonal matrix, such that for every \(x\in\mathbb{R}^{d}\), \(\left\|DV^{T}x\right\|_{2}\leq\sum\limits_{p\in P}w(p)\left|p^{T}x\right|\leq \sqrt{d}\left\|DV^{T}x\right\|_{2}.\) Define \(U:P\rightarrow\mathbb{R}^{d}\) such that \(U(p)=p\left(DV^{T}\right)^{-1}\) for every \(p\in P\). The tuple \((U,D,V)\) is the \(\left\|\cdot\right\|_{1}\)-SVD of \(P\).

Using the above tool, the sensitivity with respect to the RBF loss function can be bounded using the following.

**Lemma 2.3** (Special case of Lemma 35, (Tukan et al., 2020)).: _Let \(\left(P,w,\mathbb{R}^{d},f\right)\) be query space as in Definition A.1 where for every \(p\in P\) and \(x\in\mathbb{R}^{d}\), \(f(p,x)=\left|p^{T}x\right|\). Let \((U,D,V)\) be the \(\left\|\cdot\right\|_{1}\)-SVD of \((P,w)\) with respect to \(\left|\cdot\right|\) (see Definition 2.2). Then: (i) for every \(p\in P\), the sensitivity of \(p\) with respect to the query space \((P,w,\mathbb{R}^{d},\left|\cdot\right|)\) is bounded by \(s(p)\leq\left\|U(p)\right\|_{1}\), and (ii) the total sensitivity is bounded by \(\sum\limits_{p\in P}s(p)\leq d^{1.5}\)._

## 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 1.** Algorithm 1 receives as input, a set \(P\) of \(n\) points in \(\mathbb{R}^{d}\), a weight function \(w:P\rightarrow[0,\infty)\), a bound \(R\) on the radius of the ball containing query space \(X\), and a sample size \(m>0\). If the sample size \(m\) is sufficiently large, then Algorithm 1 outputs a pair \((S,v)\) that is an \(\varepsilon\)-coreset for RBF cost function; see Theorem 3.2.

First, \(d^{\prime}\) is set to be the VC dimension of the quadruple \((P,w,X,\rho\left(\cdot\right))\); see Definition A.2. The heart of our algorithm lies in formalizing the RBF loss function as a variant of the regression problem, specifically, a variant of the \(\ell_{1}\)-regression problem. The conversion requires manipulation of the input data as presented at Line 2. We then compute the \(f\)-SVD of the new input data with respect to the \(\ell_{1}\)-regression problem followed by bounded the sensitivity of such points (Lines 3-5). Now we have all the needed ingredients to obtain an \(\varepsilon\)-coreset (see Theorem A.3), i.e., we sample i.i.d m points from P based on their sensitivity bounds (see Line 9), followed by assigning a new weight for every sampled point at Line 10.

```
0: A set \(P\subseteq\mathbb{R}^{d}\) of \(n\) points, a weight function \(w:P\rightarrow[0,\infty)\), a bound on radius of the query space \(X\), and a sample size \(m\geq 1\)
0: A pair \((S,v)\) that satisfies Theorem 3.2
1: Set \(d^{\prime}:=\) the VC dimension of quadruple \((P,w,X,\rho\left(\cdot\right))\) {See Definition A.2}
2:\(P^{\prime}:=\left\{q_{p}=\left[\left\|p\right\|_{2}^{2},-2p^{T},1\right]^{T} \left|\forall p\in P\right\}\right.\)
3:\((U,D,V):=\) the \(f\)-SVD of \((P^{\prime},w,\left|\cdot\right|)\) {See Definition 2.2}
4:for every \(p\in P\)do
5:\(s(p):=e^{12R^{2}}\left(1+8R^{2}\right)\left(\frac{w(p)}{\sum\limits_{q\in P}w( q)}+w(p)\left\|U(q_{p})\right\|_{1}\right)\) {bound on the sensitivity of \(p\) as in Lemma B.1 in the appendix}
6:endfor
7:\(t:=\sum_{p\in P}s(p)\)
8: Set \(\tilde{c}\geq 1\) to be a sufficiently large constant {Can be determined from Theorem 3.2}
9: Pick an i.i.d sample \(S\) of \(m\) points from \(P\), where each \(p\in P\) is sampled with probability \(\frac{s(p)}{t}\)
10: set \(v:\mathbb{R}^{d}\rightarrow[0,\infty]\) to be a weight function such that for every \(q\in S\), \(v(q)=\frac{t}{s(q)\cdot m}\). return\((S,v)\)
```

**Algorithm 1**Coreset\((P,w,R,m)\)

### Analysis

#### 3.1.1 Lower bound on the coreset size for the Gaussian loss function

We first show the lower bound on the size of coresets, to emphasize the need for assumptions on the data and the query space.

**Theorem 3.1**.: _There exists a set of \(n\) points \(P\subseteq\mathbb{R}^{d}\) such that \(\sum_{p\in P}s(p)=\Omega(n)\)._

Proof.: Let \(d\geq 3\) and let \(P\subseteq\mathbb{R}^{d}\) be a set of \(n\) points distributed evenly on a \(2\) dimensional sphere of radius \(\sqrt{\frac{\ln n}{2\cos\left(\frac{n}{\pi}\right)}}\). In other words, using the law of cosines, every \(p\in P\), \(\sqrt{\ln n}=\min_{q\in P\setminus\left\{p\right\}}\left\|p-q\right\|_{2}\); see Figure C.
Observe that for every \(p\in P\),

\[\begin{split}& s(p):=\max_{x\in\mathbb{R}^{d}}\frac{e^{-\left\|p-x \right\|_{2}^{2}}}{\sum\limits_{q\in P}e^{-\left\|q-x\right\|_{2}^{2}}}\geq \frac{e^{-\left\|p-p\right\|_{2}^{2}}}{\sum\limits_{q\in P}e^{-\left\|p-q \right\|_{2}^{2}}}\\ &=\frac{1}{1+\sum\limits_{q\in P\setminus\{p\}}e^{-\left\|p-q \right\|_{2}^{2}}}\geq\frac{1}{1+\sum\limits_{q\in P\setminus\{p\}}\frac{1}{n} }\geq\frac{1}{2},\end{split} \tag{1}\]

where the first equality holds by definition of the sensitivity, the first inequality and second equality hold trivially, the second inequality follows from the assumption that \(\sqrt{\ln n}\leq\min_{q\in P\setminus\{p\}}\left\|p-q\right\|_{2}\), and finally the last inequality holds since \(\sum_{q\in P\setminus\{p\}}\frac{1}{n}\leq 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 properties in order to relate the Gaussian and Laplacian loss functions into more manageable quantities. We shall ultimately relate the function \(e^{-\left\|p^{T}x\right\|}\) to both the Gaussian and Laplacian loss functions. Thus, we first relate the function \(e^{-\left\|p^{T}x\right\|}\) to the function \(\left|p^{T}x\right|+1\).

Let \(p\in\mathbb{R}^{d}\) such that \(\left\|p\right\|_{2}\leq 1\), and let \(R>0\) be positive real number. Then for every \(x\in\left\{x\in\mathbb{R}^{d}\big{|}\|x\|_{2}\leq R\right\}\), \(\frac{1}{e^{R}(1+R)}\left(1+\left|p^{T}x\right|\right)\leq e^{-\left\|p^{T}x \right\|}\leq\left|p^{T}x\right|+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 supplementary material for generalization of our approaches towards general input set of points.

**Theorem 3.2** (Coreset for _RBF_).: _Let \(R\geq 1\) be a positive real number, \(X=\left\{x\in\mathbb{R}^{d}\big{|}\|x\|_{2}\leq R\right\}\), and let \(\varepsilon,\delta\in(0,1)\). Let \((P,w,X,f)\) be query space as in Definition A.1 such that every \(p\in P\) satisfies \(\left\|p\right\|_{2}\leq 1\). For every \(x\in X\) and \(p\in P\), let \(f(p,x):=\rho\left(\left\|p-x\right\|_{2}\right)\). Let \((S,v)\) be a call to \(\textsc{Coreset}(P,w,R,m)\) where \(S\subseteq P\) and \(v:S\to[0,\infty)\). Then \((S,v)\)\(\varepsilon\)-coreset of \((P,w)\) with probability at least \(1-\delta\), if \(m=O\left(\frac{e^{12R^{2}}R^{2}d^{1.5}}{e^{2}}\left(R^{2}+\log d+\log\frac{1}{ \delta}\right)\right)\)._

Coreset for Laplacian loss function.In what follows, we provide a 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\in\mathbb{R}^{d}\) unlike the _RBF_ case where the coreset holds for a ball of radius \(R\). We emphasize that the reason for this is due to the fact that the Laplacian loss function is less sensitive than the _RBF_.

**Theorem 3.3** (Coreset for the Laplacian loss function).: _Let \(\left(P,w,\mathbb{R}^{d},f\right)\) be query space as in Definition A.1 such that every \(p\in P\) satisfies \(\left\|p\right\|_{2}\leq 1\). For \(x\in\mathbb{R}^{d}\) and \(p\in P\), let \(f(p,x):=e^{-\left\|p-x\right\|_{2}}\). Let \(\varepsilon,\delta\in(0,1)\). Then there exists an algorithm which given \(P,w,\varepsilon,\delta\) return a weighted set \((S,v)\) where \(S\subseteq P\) of size \(O\left(\frac{\sqrt{\ln d+1.5}}{\varepsilon^{2}}\left(\log n+\log d+\log\frac{ 1}{\delta}\right)\right)\) and a weight function \(v:S\rightarrow[0,\infty)\) such that \((S,v)\) is an \(\varepsilon\)-coreset of \((P,w)\) with probability at least \(1-\delta\)._

## 4 Radial Basis Function Networks

In this section, we consider coresets for _RBFNNs_. Consider an _RBFNN_ with \(L\) neurons in the hidden layer and a 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, \(\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}\) defined by \(\phi(x)=\sum_{i=1}^{L}\alpha_{i}\rho(\|x-c^{(i)}\|_{2})\), where \(c^{(i)}\in\mathbb{R}^{n}\) for each \(i\in[d]\).

For an input dataset \(P\) and a corresponding desired output function \(y:P\rightarrow\mathbb{R}\), RBFNNs aim to optimize \(\sum\limits_{p\in P}\left(y(p)-\sum_{i=1}^{L}\alpha_{i}e^{-\left\|p-c^{(i)} \right\|_{2}^{2}}\right)^{2}.\) Expanding the cost function, we obtain that RBFNNs aim to optimize

\[\begin{split}\sum\limits_{p\in P}y(p)^{2}&-2\sum \limits_{i=1}^{L}\alpha_{i}\overbrace{\left(\sum\limits_{p\in P}y(p)e^{- \left\|p-c^{(i)}\right\|_{2}^{2}}\right)}^{\alpha}\\ &+\underbrace{\sum\limits_{p\in P}\left(\sum\limits_{i=1}^{L} \alpha_{i}e^{-\left\|p-c^{(i)}\right\|_{2}^{2}}\right)^{2}}_{\beta}.\end{split} \tag{2}\]

Bounding the \(\alpha\) term in equation 2.We first define for every \(x\in\mathbb{R}^{d}\):

\[\begin{split}\phi^{+}(x)&=\sum\limits_{p\in P,y(p)> 0}y(p)e^{-\left\|p-x\right\|_{2}^{2}}\\ \phi^{-}(x)&=\sum\limits_{p\in P,y(p)<0}\left|y(p) \right|e^{-\left\|p-x\right\|_{2}^{2}}.\end{split}\]

Observe that \(\sum_{p\in P}y(p)\rho(\|p-c^{(i)}\|_{2})=\phi^{+}\left(c^{(i)}\right)-\phi^{-} \left(c^{(i)}\right)\). Thus the \(\alpha\) term in equation 2 can be approximated using the following.

**Theorem 4.1**.: _There exists an algorithm that samples \(O\left(\frac{e^{8R^{2}}R^{2}d^{1.5}}{\varepsilon^{2}}\left(R^{2}+\log d+\log \frac{2}{\delta}\right)\right)\) points to form weighted sets \((S_{1},w_{1})\) and \((S_{2},w_{2})\) such that with probability at least \(1-2\delta\),_

\[\frac{\left|\sum\limits_{p\in P}y(p)\phi(p)-\left(\sum\limits_{ \begin{subarray}{c}i\in[L]\\ \alpha_{i}>0\end{subarray}}\alpha_{i}\gamma_{S_{1}}+\sum\limits_{\begin{subarray}{ c}j\in[L]\\ \alpha_{j}<0\end{subarray}}\alpha_{j}\gamma_{S_{2}}\right)\right|}{\sum\limits_{i\in[L]} \left|\alpha_{i}\right|\left(\phi^{+}\left(c^{(i)}\right)+\phi^{-}\left(c^{(i) }\right)\right)\right)}\leq\varepsilon,\]
_where \(\gamma_{S_{1}}:=\sum\limits_{p\in S_{1}}w_{1}(p)e^{-\left\|p-c^{(i)}\right\|_{2}^{2}}\) and \(\gamma_{S_{2}}:=\sum\limits_{q\in S_{2}}w_{2}(q)e^{-\left\|q-c^{(i)}\right\|_{2}^{ 2}}\)._

**Bounding the \(\beta\) term in equation 2.** By Cauchy's inequality, it holds that

\[\sum\limits_{p\in P}\left(\sum\limits_{i=1}^{L}\alpha_{i}e^{- \left\|p-c^{(i)}\right\|_{2}^{2}}\right)^{2} \leq L\sum\limits_{p\in P}\sum\limits_{i=1}^{L}\alpha_{i}^{2}e^{- 2\left\|p-c^{(i)}\right\|_{2}^{2}}\] \[=L\sum\limits_{i=1}^{L}\alpha_{i}^{2}\sum\limits_{p\in P}e^{-2 \left\|p-c^{(i)}\right\|_{2}^{2}},\]

where the equality holds by simple rearrangement.

Using Theorem 3.2, we can approximate the upper bound on \(\beta\) with an approximation of \(L(1+\varepsilon)\). However, if for every \(i\in[L]\) it holds that \(\alpha_{i}\geq 0\), then we also have the lower bound \(\sum\limits_{i=1}^{L}\alpha_{i}^{2}\sum\limits_{p\in P}e^{-2\left\|p-c^{(i)} \right\|_{2}^{2}}\leq\sum\limits_{p\in P}\left(\sum\nolimits_{i=1}^{L}\alpha_ {i}e^{-\left\|p-c^{(i)}\right\|_{2}^{2}}\right)^{2}\).

Since we can generate a multiplicative coreset for the left-hand side of the above inequality, then we obtain also a multiplicative coreset in a sense for \(\beta\) as well.

## 5 Advantages of our Methods

**One coreset for all networks.** Our coreset is model-independent, i.e., we aim at improving the running time of multiple neural networks. Contrary to other methods that need to compute the coreset after each gradient update to support their theoretical proofs, our method gives the advantage of computing the sensitivity (or the coreset) only once, for all of the required networks. This is because 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 a lot of time to compute a new coreset since they compute the gradients of the network with respect to each input training data. However, our coreset can be computed before each epoch in a negligible time (\(\sim 0\) seconds), since we compute the sensitivity of each point (image) in the data once at the beginning, and then whenever we need to create a new coreset, we simply sample from the input data according to the sensitivity distribution.

## 6 Experimental Results

In this section, we 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.

**Competing methods.** We compare our method against many variants of the proposed algorithms in (Killamsetty et al., 2021) (denoted by, _GRAD-MATCH_), in (Mirzasoleiman et al., 2020) (denoted by _CRAIG_), and in (Killamsetty et al., 2021) (denoted by _GLISTER_). For each of these methods, we report the results for \(4\) variants: (i) the "vanilla" method, denoted by its original name, (ii) applying a warm start i.e., training on the whole data for \(50\%\) of the training time before training the other \(50\%\) on the coreset, where such methods are denoted by adding the suffix -WARM. (iii) a more efficient version of each of the competing methods denoted by adding the suffix PB (more details are given at (Killamsetty et al., 2021)), and finally, a combination of both (ii) and (iii). In other words, the competing methods are GRAD-MATCH, GRAD-MATCHPB, GRAD-MATCH-WARM, GRAD-MATCHPB-WARM, CRAIG, CRAIGPB, CRAIG-WARM, CRAIGPB-WARM, and GLISTER-WARM. We also compare against randomly selecting points (denoted by RANDOM).

**Datasets and model architecture.** We performed our experiments for training CIFAR10 and CIFAR100 (Krizhevsky et al., 2009) on ResNet18 (He et al., 2016), MNIST (LeCun et al., 1998) on LeNet, and ImageNet-2012 (Deng et al., 2009) on Resnet18 (He et al., 2016).

**The setting.** We adapted the same setting of (Killamsetty et al., 2021), where we used SGD optimizer for training initial learning rate equal to \(0.01\), a momentum of \(0.9\), and a weight decay of \(5e-4\). We decay the learning rate using cosine annealing (Loshchilov and Hutter, 2016) for each epoch. For MNIST, we trained the LeNet model for \(200\) epochs. For CIFAR10 and CIFAR100, we trained the ResNet18 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 a single epoch. All experiments 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 CIFAR10 and CIFAR100, we use \(\{5\%,10\%,20\%,30\%\}\), and for ImageNet we use \(5\%\).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 it with \(R=1\) without adding run-time since once the sensitivity vector is defined, commuting a new coreset requires \(\sim 0\) seconds. However, we test it with \(R=20\), to show its robustness.

**Discussion.** Tables 1-4 report the results for CIFAR10 and CIFAR100. It is clear from Tables 1 and 2 that our method
achieves the best accuracy, with and without warm start, for \(5\%\), \(20\%\), and \(30\%\) subset selection on CIFAR10. For CIFAR100, our method drastically outperforms all of the methods that do not apply a warm start. When applying a warm start, we can achieve the best accuracy, with and without warm start, for \(5\%\), \(20\%\), and \(30\%\) subset selection on CIFAR10. For CIFAR100, our method drastically outperforms all of the methods that do not apply a warm start. When applying a warm start, we can achieve the best accuracy, with and without warm start, for \(5\%\), \(20\%\), and \(30\%\) subset selection on CIFAR10.
warm start, we still win in half of the cases. Note that, we outperform all of the other methods in terms of accuracy vs time. The same phenomenon is witnessed in the ImageNet experiment (Table 5) as our coreset achieves the highest accuracy. We refer the reader to the MNIST experiment (Table 6 in the appendix). We note that our sensitivity sampling vector is computed once during our experiments for each dataset. This vector can be used to sample coresets of different sizes, for different networks, at different epochs of training, in a time that is close to zero seconds. In all tables, the best results are highlighted in bold.

**Function Approximations.** We now compare our coreset to uniform for function approximation. Specifically, we generate around \(10,000\) points in \(3D\), while setting the third entry of each point to be a function of the first \(2\) entries, \(f(x)=e^{-\left\|x\right\|_{2}^{2}}+0.2\cos\left(4\left\|x\right\|_{2}\right)\). We train an RBFNN to reproduce the function using only \(400\) points, where we saw that our coreset (Figure 2(c)) is closer visually to the true function (Figure 2(a)) using uniform sampling for reproducing the image (Figure 2(b)). Furthermore, we show for the \(RBF\) fitting task on CovType dataset (Dua et al., 2017), where, our coreset is better than uniform sampling by a multiplicative factor of \(1.5\) at max (Figure 2(d)).

## 7 Conclusion and Future Work

In this paper, we have introduced a coreset that provably approximates any function that can be represented by RBFNN architectures. Our coreset construction can be used to approximate 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 performances over various datasets and model architectures. As the first work on using coresets for data subset selection with respect to _RBFNNs_, our results lead to a number of interesting possible future directions. It is natural to ask whether there exist smaller coreset constructions that also provably give the same worst-case approximation guarantees. Furthermore, RKHS methods (Claici and Solomon, 2018; Claici et al., 2018) may be investigated in this context either by boosting their implementation or by merging ideas with this work. In addition, can our results be extended to more general classes of loss functions? Finally, we remark that although our empirical results significantly beat state-of-the-art, they nevertheless only serve as a proof-of-concept and have not been fully optimized with additional heuristics.

\begin{table}
\begin{tabular}{c|c|c} \hline \hline  & Top-1 Test accuracy of the Model(\%) & Model Training time(in hrs) \\ Budget(\%) & 5\% & 5\% \\ \hline Full (skyline for test accuracy) & 70.36 & 276.28 \\ Random (skyline for training time) & 21.124 & 14.12 \\ \hline CraigPB & 44.28 & 22.24 \\ GradMatch & 47.24 & 18.24 \\ GradMatchPB & 45.15 & 16.12 \\ \hline RBFNN Coreset (OURS) & **47.26** & **15.24** \\ \hline \end{tabular}
\end{table}
Table 5: Data Selection Results for ImageNet2012 using ResNet-18

Figure 2: **(a) is the function we wish to approximate by training an RBFNN on: (b) a uniformly sampled subset, and (c) our coreset.**