Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides some mathematical understanding on influence functions and datamodels via harmonic analysis including
1. reasons for existence of datamodels.
2. exact characterizations of \theta_i for datamodels without/with abbitrary regularization.
3. providing a new algorithm to estimate the degree whether a linear datamodel is well-approximated without having to train the datamodel per se.
4. studing group influence which quantifies the effect of adding or deleting a set.
strength_and_weaknesses: Strength:
1. This paper introduces harmonic analysis into the discussion of influence functions and datamodels, which is a novel idea.
2. This paper gives a new algorithm to estimate the degree whether a linear datamodel is well-approximated without having to train the datamodel per se.

Weakness:
1. To my knowledge, all the analysis in this paper is based on a fixed test point, which means that we need to repeat the algorithm proposed in this paper with $m$ times when we need to estimate $m$ test points.
2. In Section 3.1, the author claimed that normalized noise stability should be high, and perhaps close to its maximum value of $1$ when the number of training samples grows, intuitively. Then Theorem 3.2. gives a bound on the best linear approximation in terms of the magnitude of the residual error because $1- \overline{h} (\rho)$ is close to $0$. But if I understand correctly, $\overline{h} (\rho)$ is close to $1$ when $\rho$ is close to $1$ intuitively. The bound given in Theorem 3.2 is meaningless at this point. In consequence, I think this intuition lacks theoretical or experimental evidence. I am willing to raise my score if the author can explain this question theoretically or experimentally.
3. It becomes worthless to estimate the quality of the best linear datamodel when it becomes a question whether datamodel is a good approximation.
clarity,_quality,_novelty_and_reproducibility: This paper is written clearly and well organized. There are a few flaws. For example, in page 2 line 2, author used symbol ‘ith’ but ‘i-th’ in other parts to represent the same thing.
summary_of_the_review: This paper introduces harmonic analysis into the discussion of influence functions and datamodels and gain some novel results. But the main theorem proofs based on the intuition. Generally, I think harmonic analysis is a useful and relatively novel tool for machine learning.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper uses theoretical tools from harmonic analysis and noise stability to explain the effectiveness of data-models introduced by Ilyas et. al (2022). In addition, the same theoretical components are used to analyze group influence and identify conditions when first-order influence (linear in terms of training data influence) can be used to characterize group influence. 
strength_and_weaknesses: Strengths:

	- While the framework of datamodels empirically approximate training data influence, the original paper does not show any understanding of why it works in the first place. This paper, provides a starting point to analyse datamodels and further understand why it works. This is one of the major strengths of the paper. 

	- The noise stability estimator is a good contribution to bypass the expensive process of training the datamodels (though see Weakness for a follow-up question). 


While I am not an expert in harmonic analysis, there are certain questions regarding the paper:

Weakness / Questions:

	- While Ilyas et. Al (2022), show that datamodels can approximate group influence (via linearity), as shown in previous works [1], this linearity assumption is not always true, especially when a large number of points are deleted. In such cases, how does datamodels relate to higher-order variants of influence which seem to be a better approximation for group influence? 

	- The paper has a good theoretical contribution, however I would like to see some more empirical analysis on how the noise stability estimator is a good proxy for predicting the fit. One way could be to run similar experiments on datasets beyond CIFAR-10 (e.g., Imagenet derivatives) to strengthen it's effectiveness.

The paper is difficult to read for someone who has limited background on harmonic analysis; Considering influence functions is used by a mix of empirical + theoretical researchers, it would be good to provide a small background on the topic in the Appendix or in the main paper (e.g., a brief background of the theoretical tools used in your analysis). 


[1]. https://arxiv.org/abs/1911.00418




clarity,_quality,_novelty_and_reproducibility: The paper is well-written and clear. However, as mentioned in the previous section, it would be beneficial to give a more informative background about the theoretical tools used in the paper.
summary_of_the_review: Overall,  I feel that the theoretical contribution is a good initial step towards understanding data-models and finding links between influence estimation and datamodels. While the authors connect the theory to empirical findings (e.g., prediction of the fit), this section can be strengthened with more experiments on datasets beyond CIFAR-10. 

Overall, the paper can be a good addition to iclr as it provides some theoretical footing connecting datamodels to  influence functions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on a very interesting and important research topic, predicting the predictions from training data. Built on the datamodels proposed in [1], this paper seeks to provide a better theoretical understanding of why a linear regression method can predict the effect of training data. More importantly, this paper designs a new algorithm for estimating the approximated linear datamodel with much less training cost. This paper provides an exciting view to the counter-factual explanations of training data.

[1]Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data, ICML 2022
strength_and_weaknesses: Strength:
1. The research problem, analyzing the influence of data points, is very interesting and important for explainable AI.
2. The paper provides a theoretical analysis of the linear datamodel, and explained why the effects of number of points deleted is observed in practice as linear rather than exponential.
3. Experimental results verified the proposed method

Weaknesses:
1. This paper is not friendly to most beginners, and the main idea is hard to follow. The authors also need to explain more detailedly how the residual estimation can predict the performance.
clarity,_quality,_novelty_and_reproducibility: This paper is novel and interesting while hard to read.
summary_of_the_review: This paper is generally well-written and novel, and the authors focus on an interesting research problem. I'd like to accept this paper and appreciate if the author can revise the paper more clearly.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper revealed the connection of influence function and the linear datamodel using harmonic analysis.
Linear datamodel is a model fitted with an $N$-dimensional binary vector as its input and with the outcome (or loss) of a model trained on a subset of $N$ training points indicated by the binary vector as its regression target.
A recent study observed that the influence function (more formally, discrete influence function) can be approximated by this linear datamodel.
This paper provides a unified view of this observation why such an approximation is possible.
Let $f$ be a training algorithm that maps the $N$ dimensional binary vector to the target.
For the analysis, the authors considered expanding $f$ using an orthonormal basis in $N$ dimensional space.
This expansion allows us to view $f$ as a function on the $N$ dimensional grid rather than the training algorithm.
With this expansion, we can see that discrete influence function corresponds to the coefficient of the degree-1 basis. 
This finding explains why the linear datamodel can approximate discrete influence function.
If the coefficients of $f$ in the higher-degree basis are small, the basis of degree-1 can well approximate $f$.
The authors also analyzed a case when this approximation is possible by introducing the notion of noise stability.
The authors also provided an efficient algorithm for estimating the approximation error.

strength_and_weaknesses: ### Strength
The major strength of the paper is on the characterization of the connections between influence function and the linear datamodel.
This characterization successfully explained the finding of the linear datamodel.
The authors also found some counter cases when the connection fails.
The authors further provided an efficient way to estimate the fitting error so that one can assess whether the linear datamodel is valid on the dataset at hand.

### Weakness
I do not find any crucial weakness.
As a minor suggestion, I think the paper becomes much easier for the readers if there is a brief overview of the linear datamodel.
The linear datamodel is not that popular compared to influence function.
clarity,_quality,_novelty_and_reproducibility: ### Clarity
I think the paper is written clearly and the main idea and the results are easy to follow.
As a minor suggestion, I think the paper becomes much easier for the readers if there is a brief overview of the linear datamodel.
The linear datamodel is not that popular compared to influence function.

### Quality, Novelty
The problem considered in this paper, characterizing the connection between influence function and the linear data model, is an interesting problem and the finding would be novel.
The finding explains the success of the linear datamodel.

### Reproducibility
The experimental setups are provided in appendix.
The results will be reproducible.
summary_of_the_review: This paper provide the characterization of the connections between influence function and the linear data model.
This characterization successfully explained the finding of the linear datamodel.
This is an interesting problem and the finding would be novel.
The paper also provides some counter cases when the connection fails, and also an efficient way to estimate the fitting error so that one can assess whether the linear datamodel is valid on the dataset at hand.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a harmonic analysis perspective on influence functions and datamodels. Even though the reviewers agreed that the empirical performance was not necessarily groundbreaking, they all appreciated this new perspective.

In an era where models are trained on increasingly large datasets and adding and removing examples are an important way to tune them with minimum additional computation, I welcome any attempt at providing more understanding of the influence of such changes on the final model.
justification_for_why_not_higher_score: The paper focuses on harmonic analysis, a tool that might not be known to a wide audience at ICLR. Additionally, while the theoretical idea is interesting, the limitations of the empirical section (which are fully understandable given the computational cost) might limit its appeal.
justification_for_why_not_lower_score: This is one more tool to provide a functional analysis of large models and attempts to predict their behaviour in increasingly common scenarios. Accepting this paper will provide a refreshing perspective on this question.
Decision: Accept: poster