Summary
The paper explores the problem of most influential subset selection, that is, selecting a subset of training data points whose removal would change a machine learning model the most. The paper develops further on previous works (most notably of Chatterjee and Hadi, and Kuschnig et al) and shows why the greedy heuristics do not work well in practice. Greedy heuristics operate by computing the influence (e.g., following Koh and Liang) and simply selecting the data points with highest individual influence. The paper shows how indirect interactions can lead to under- and over-estimation of influence. The paper then shows why a specific adaptive method works well in practice. The analysis of the paper is limited to OLS. While the paper does not propose a new influential subset selection algorithm, the analysis conducted in the paper adds important theoretical insights that are likely to be helpful to the research community.
Strengths
1. The paper does a very good job of setting up the problem and explaining the main results. The formalism is clean and easy to understand and the results are accompanied by intuitive explanations, e.g., in Figure 1.
2. The key limitation of greedy heuristic methods (considering the full training dataset) is explained quite well in Section 4.
3. While the paper does not quite add an algorithmic improvement, the theoretical analysis provided is an important building block in developing our understanding of the underlying mechanisms.
Weaknesses
1. Some of the analysis is limited to simpler models like OLS and takes assumptions like the inevitability of the $N=X^TX$ matrix (which may not be the case in real world datasets). This per se is not a big weakness. However, some discussion here on how we expect these results to behave on real world datasets where $N$ is non-invertible, or on models beyond OLS would be greatly helpful.
2. The result of theorem 4.2 seems a bit limited and too tailored to the adaptive greedy algorithm. Specifically, given the steps described in line 251, (remove most influential sample, retrain the model, repeat), and the proposition 4.1 (order preservation between two points), it is not immediately clear if/how much the Theorem 4.2 would extend to 3-MISS and beyond.
3. The title of the paper seems to be quite general and a bit mismatched with the content. While the content shows the weaknesses of existing influence estimation approaches (that too with a OLS model, in a 2-MISS settings and a very specific adaptive algorithm), reading the title feels as if the paper would address a much broader range of models and algorithms.
Questions
1. Section 3.1: To what extent is the finding in Section 3.1 limited to the specific target function used here, that is, the prediction on $x_{test}$? After all, reading the legend in Figure 1, there is not a huge difference on the target function value between points 1 and 8 (0.120 vs. 0.117). More broadly, do we expect the effect of high leverage points to be this large when we take “less noisy” functions like the sign of the prediction on $x_{test}$ or accuracy on the whole test set?
2. Line 171: About correcting the influence with its corresponding leverage score, how does that process look like precisely?
3. If the reviewer understood correctly, $\bar{A_{-S}}$ in Figure 3 shows the actual influence of the two approaches considered. Why not baseline this comparison with the “ground truth influence”, that is, the influence of the actual most influential data points? Clearly, this will ground truth will be very difficult to compute as $k$ increases, but some understanding over smaller values of $k$ might be very helpful for the reader.
4. The results in Figure 4 are mostly as one would expect. However, in the case of MLP, the gap in $\bar{A_{-S}}$ and winning rate starts shrinking around $k=50$. Any reason why that might be happening? How robust are the results to different choices of training data random seed?
Limitations
The paper is generally quite open about the limitations. However, please see the point 3 in weaknesses about the generality of the title.