Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Paper presents theoretical and experimental analysis of a machine teaching algorithm for data subset selection. 
strength_and_weaknesses: Strengths
- Proves upper and lower bounds for performance of subset selection algorithm
- Good evaluation with 6 baselines tested alongside the introduced algorithm, tested on 6 datasets and ablated on 3 NN architectures.
- Provides theoretical analysis of error squashing which was missing from Cicalese et al 2020, when they introduced error squashing.

Weaknesses
- Seems to be a minor improvement on Cicalese et al. (2020); and the experimental results suggest the same-- with roughly the same performance (sometimes slightly worse and sometimes slightly better) as Cicalese's and Dasgupta's work.

Minor comments & questions
- Notation: 
-- In section 2/3: use of '[m]' describe set of all pool points is non-standard and would be nice to keep to the nomenclature in the subfield (e.g. notation used in Cicalese 2020, SVP by Coleman 2020 or Kilmasetty 2020).
-- Switching of notation of error on hypothesis classes from err[h] to E interchangebly.
-- Is E_{t} just shorthand for E_{h_t}
- More clarity on improvements as compared to Cicalese
- Add standard deviation bounds to experimental results based on multiple runs.

clarity,_quality,_novelty_and_reproducibility: Somewhat clear, primarily builds on Cicalese with some novel contributions and should be reproducible.

I should note the primary contribution is the theoretical justification for error squashing. I'm not sure about the other contribution stated in the introduction ("introduce algorithm").
summary_of_the_review: Somewhat minor improvement, but some good theoretical and empirical analysis. Improvements to exposition would assist. I think this is below the threshold for acceptance due to the lack of significant novelty here.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the author(s) considered the problem of data subset selection. The author(s) proposed a machine teaching subset selection algorithm with theoretical guarantees. Through empirical experiments, the author(s) showed the advantage of the proposed algorithm.

---
strength_and_weaknesses: ### Strength:

1. Selecting an informative subset from a dataset is significant in practice. An obvious advantage is that the training/computation time of algorithms based on such data can be largely reduced.

2. Theoretical analysis and empirical experiments are both performed for validating the proposed algorithm.

---

### Weaknesses:

1. Maybe some technique assumptions in this paper are not so reasonable.

2. Some descriptions (including experimental details) in this paper are not clear.

For more details, please see the section of "Clarity, Quality, Novelty And Reproducibility".


---


clarity,_quality,_novelty_and_reproducibility: I think the topic in this paper is interesting and this paper is generally well-written.

I have the following comments/questions. I look forward to the response/clarification from the author(s). Thanks.


Clarity:

1. At several places in this paper, it mentioned "zero error", I am not sure that it is reasonable. Generally speaking, in machine learning, "zero training error" may possibly cause "overfitting". Why use such a condition? Could you please explain that? 

2. Some experimental details are not clearly given; for example, it mentioned that "the standard train/test splits" (On Page 7, Section 5, Line 2 in the 2nd Paragraph), could you please detail it?

3. For the results in Figures 1 and 2 (also, including the Supplementary results), from the description, I understood that error bars were from training with 10 replications on a subset. I checked them, especially the results from CFLM, DHPZ, and the proposed algorithm, and I found almost no error fluctuations (except a little fluctuation on FMNIST), I wonder if this indicated that the learning results of these three algorithms are very stable? And I'm curious about the design of 10 replications, the 10 replications is a 10 random train/test splits, right? Also, for these three algorithms might consider the performance with the changing of subset sizes?

4. For the results in Table 1 (also in Supplementary Tables 3 and 4), could you please explain them further?

5. If the input data matrix is transposed, does the method in this paper, i.e., data subset selection, become feature selection?

In addition, some other tiny issues/typos

(1) The format of the references is quite inconsistent (such as, sometimes the author's name is abbreviated, sometimes it is not; sometimes the first letter of every word of journal/conference names is capitalized, sometimes it is not; and so onThere are times when the first letter of each word is capitalized, sometimes not, and so on). Please check carefully and correct it.

(2) In Table 2, there is no punctuation at the end of the caption.

(3) It may not be necessary to number each mathematical formula in the text. In general, we only need to number the mathematical formula that will be used/cited later.

---


summary_of_the_review: The work in this paper is interesting; However, there are some unclear aspects in the description (including experiments) of this paper. Maybe it needs the author(s) to clarify them.

In addition, in this paper, the author(s) performed empirical experiments, but I am not sure the empirical description/experiments would be enough to reproduce because no code of this paper seems to be provided. Thanks.

---
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper identifies theoretical gaps in the existing literature on data subset selection in machine teaching, and analysis the justification of the error-squashing heuristics adopted in the previous works. With that, the authors propose a data subset selection algorithm with near-optical guarantees on the query complexity and the size of the returned subset. The paper also shows empirical experiments on 6 datasets, 6 baseline methods and 3 model architectures to demonstrate the effectiveness of the proposed algorithm.
strength_and_weaknesses: Strengths:
1. A solid theoretical analysis of the algorithm is given, alongside a detailed theoretical section for justifying the use of error squashing.
2. Theorems and propositions are explained well with interpretations. 
3. Rather extensive experiments are conducted across multiple baseline methods, datasets and model architectures.

Weaknesses:
1. The novelty of the paper needs further justification.
clarity,_quality,_novelty_and_reproducibility: 1. The main algorithm proposed employs techniques such as doubling, clipping of the probabilities and error squashing. They have all been used or studied in prior works. Hence, I feel the novelty is lacking: The contribution mainly comes from the theoretical understanding of error squashing, which was previously used as a heuristic. The practical significance is small since the technique has been used for non-interpolating learners before. Then, how significant is that towards machine teaching design theoretically? Does it inspire other improvements or does it unify frameworks? The theoretical significance needs further justification.

2. Additionally to the previous point, the authors point out that the guarantee improvement in the size of the returned subset likely comes from the relaxation of the existing assumption on nested query sequence to an arbitrary subset. Could you elaborate more on why it is essential to allow data point removal, for example on applications like curriculum learning and continual learning, etc?

3. What kind of learners are “invariant to consistent additions”? It seems like a pretty strong requirement since the outputted function (or hypothesis) has to be exactly the same as that before the addition? Is the interpretation of “does not change the learner’s prediction” (first sentence of 4.4.1) misleading? Are the convolutional neural networks considered in the experimental sections invariance to consistent additions?

4. For the definition of the “fully intersect” (Sec. 3.2), should it be “if for all $E_h$ …”?

5. Missing bracket “)” at the second last line of Section 4.4.2 paragraph 1.

6. Is there any explanation for why the coreset selection methods often have worse performance than random selection especially when the subset size is small?

7. What hyperparameter did you use for your method and the machine teaching approaches in the experiments? Can you adjust the parameters to obtain a subset of different sizes?

8. Explanation for “I a few cases (SVHN and FMNIST), achieving near-zero pool error is insufficient to achieve minimal test error with the data” is not given. Is it because the learner is non-interpolating?

9. Even when multiple trainings on the data subset are required in continual learning, needing to train hundreds of models (Table 1) is still a very big overhead that is hard to justify. Any comments to justify it further?
summary_of_the_review: I am majorly concerned with the novelty of the paper. As discussed above, the algorithm mainly adopts existing techniques with an addition of a probability halving phase that allows drops in selection probability. The improvement in the theoretical guarantee of the algorithm is also likely due to this trick which essentially relaxes the problem setting. The second part on the theoretical understanding of error squashing is nice to have, but I wonder how much theoretical and empirical insights it could have to impact the community to move forward. The practicability of the method is also largely limited by its time and computational overhead. The authors could probably explain more about the significance of the theoretical understandings presented.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: There is a consensus among the expert reviewers that this paper provides interesting theoretical and experimental analyses of a machine teaching algorithm for data subset selection. The paper provides novel lower bounds and extensive empirical studies that demonstrate the effectiveness of machine teaching methods for data subset selection. 

Despite praise for the quality of theoretical and empirical results, a majority of reviewers still have reservations about the novelty of this work, pointing out that the contribution is incremental with respect to that of Dasgupta et al. and Cicalese et al. In particular, one of the reviewers highlighted that the novelty of this work has not been framed appropriately with respect to previous work. 

As a result, I cannot recommend the paper in its current form for publication at ICLR 2023 as it does not meet the acceptance bar of the conference.
justification_for_why_not_higher_score: The paper requires a major revision and thereby another round of peer review.
Decision: Reject