Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

1. 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.

2. The proposed algorithm construction leverages existing theoretical results; and the authors provide further theoretical analysis for RBF and Laplacian loss functions.

3. The proposed algorithm is efficient - the coreset can be computed before each epoch with negligible time by sampling according to the sensitivity distribution.

4. Extensive empirical evaluation that demonstrates the efficiency and effectiveness of the proposed algorithm.

Questions and weaknesses:

1. 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?

2. 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?

3. The standard deviation of the empirical results is not reported - I'm not fully convinced the differences are statistically significant.

Minor issue:

In definition 2 where the function $U(p)$ is defined, the $P$ should be $p$?
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and the proposed idea seems interesting and novel.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength

- 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.

- The authors also develop provable theoretical guarantees for the proposed coreset construction algorithm. 

Questions:

- In the abstract, `notoriously known' should be `well known'

- 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.

- 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.

- How does this approach compare to the clustering-based data selection as discussed in the recent work https://arxiv.org/pdf/2206.14486.pdf
clarity,_quality,_novelty_and_reproducibility: Good
summary_of_the_review: see above
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

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:

- While the paper is generally easy-to-follow, the motivations in Section 1 are unclear.
- 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. 
- The performance seems to be limited for CIFAR-100 and MNIST datasets. 
- 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.
- 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. 
clarity,_quality,_novelty_and_reproducibility: I believe that the idea of selecting the coreset with RBFNN is interesting and novel. Moreover, the paper is generally well-written although some parts of the paper are not easy-to-follow due to organization. I believe that the quality of the paper meets the standard of the ICLR. 

The authors did not provide a code or details of the experiment set-up and I believe that it would be difficult to reproduce the experiments at the current state. 

Below, I left some additional comments:
- I found the description in Section 1 - coresets to be confusing at first. A more description of the query selection before showing the equation would be useful. 
- In addition, I think that the reorganization of the materials presented in Section 1 would be helpful. At the moment, the motivation for the work is not clear when first reading the introduction. 
- While I believe that Figure 1 is extremely useful to capture the core contribution, there needs to be a detailed description. At the moment, the main text does not mention Figure 1.
- In my current understanding, the algorithm proposed in the paper could be split into two parts: RBFNNs and coreset selection. Would it be possible to set up an experiment that confirms the accuracy of each method (in step)? 

Minor comments:
- While I believe that Figure 1 is extremely useful to capture the core contribution, there needs to be 
In Section 5, “... after each gradient update to support there theoretic…” →“... after each gradient update to support their theoretic…”.
- There are several places where \citet and \citep are misused (e.g., Section 6, competing methods). 
- In Table 1, it would be helpful if the fastest model training time is bolded. The same applies to Table 2 and Table 3. 
- The resolution for figure 3 is bad. 

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 


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,

1. 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.

2. 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)$. 

3. The formula in Claim 5 is not correct since letting $R=1$ will give $e/2\leq 1$, this can not be true.

4. 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|$.
clarity,_quality,_novelty_and_reproducibility: Quality: This paper is not very technically sound.

Clarity: This paper is well organized. I find it easy to follow.

Significance: I think the results in this paper are not very significant. 
summary_of_the_review: Due to many confusions in the technical parts, as explained above, I tend not to accept this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The submission proposes a coreset selection method based on (shallow) RBF neural networks, which are similar to RKHS coreset methods but with the theoretical ability to select RBF centers, an a number of RBF functions that can be set independently from the number of data points.  With this coreset selection procedure, the authors propose to use the selected points to train networks with less data, similar to the approaches proposed in Killamsetty et al. (2021a) (GRAD-MATCH), Mirzasoleiman et al. (2020a) (CRAIG), and in Killamsetty et al. (2021b) (GLISTER), which are the competing methods.  There is some new theoretical work on the construction of RBFNN coresets, resulting in theoretical results perhaps comparable to those available for RKHS coreset methods.  The submission received reviews around the borderline threshold.  There are several concerns about the paper in its current form: motivation and comparison to the current state of the art.

Motivation: the authors argue that a key benefit of the proposed approach is that there is one coreset for all subsequent networks, as the coreset method is independent of any subsequent network architecture (Section 5).  This is equally true for RKHS coresets, which have a rich literature and are from a function class with the same universal function approximation guarantee used to motivate the current method.  It seems that any coreset method could be used in the same setting, which indicates that additional experiments would be necessary to show why the RBFNN method, which is far from standard, is a better choice.

Experiments: Comparing Table 1 with the standard deviations in the appendix is different, and it is not clear that with 5 runs statistical significance can be established.  The authors' response in the rebuttal is difficult to parse, but does not claim significance and seems to acknowledge that it is not necessarily present: "Note that while our standard deviation is larger than that of GradMatch for instance, however, in most of our results our reported mean accuracy is larger. Indeed our standard deviation is larger since we are applying a sampling technique for computing a generic coreset. In addition, the lower bound on the accuracy of our is slightly larger than that of our competing methods in most of our experiments."  The values in 1, 2 & 3 have results in bold, when in some cases the values differ only in the second decimal place compared with competing methods.

On the balance, the submission explores an interesting question of generating coresets and using them in NN training.  There are essentially two main sets of contributions: 1) theoretical work developing a coreset theory for RBFNNs, and 2) empirical results showing their effect in training NNs with fewer data compared to several existing methods.  It is not entirely clear why RBFNNs would be selected over better studied RKHS coresets, and the empirical results are inconclusive compared with the chosen methods.
justification_for_why_not_higher_score: The submission is a combination of two ideas, which have some problems in motivation, and experimental results without significance.
Decision: Reject