Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies how the strength of inductive biases affect harmless interpolation or benign overfitting, where models can generalize well despite interpolating a (possibly noisy) test set. To study this question, the authors adjust the filter size in convolutional kernels. Smaller filter sizes encode for functions that depend nonlinearly only on local neighborhoods of the input features, whereas this bias is weakened for larger filter sizes. The paper shows theoretically that for high-dimensional kernel regression with convolutional kernels, there is a phase transition between harmless and harmful interpolation in filter size (Theorem 1). The authors show that interpolation is harmless for weak inductive biases, and that for strong inductive biases, they show interpolation can be harmful. Further, they show fitting noise is necessary for strong inductive biases to achieve optimal performance. These theoretical results are supported by experiments in neural networks, where the same phenomenology is observed.
strength_and_weaknesses: **Strengths**
- The paper studies an important problem of benign overfitting and finds a new condition (strength of inductive bias) that it is predicated on.
- The paper is easy to follow and well written. It states the main claims clearly and provides evidence for them.

**Weaknesses**
- The difference between the strength of inductive biases and parameter count is not fully resolved in the neural network experiments. Is it possible to just control the number of parameters by adjusting the width to compensate for change in filter size?
clarity,_quality,_novelty_and_reproducibility: - How is the optimal regularization strength found in the estimator of Thm 2? Is this an optimization that is performed exactly? 
- There are no results on the bias and variance of the neural network trained in Sec 4. It should be possible to estimate this from experiments. Do the authors expect to see similar multiple descent curve?
summary_of_the_review: The paper makes a nice contribution and is of interest to the ICLR community. It is clearly written with nice figures. From my read of the paper's main text, the theorems seem correct.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the harmless interpolation in the setting of high-dimensional kernel regression with convolutional kernels. Here, harmless interpolation means that the performance (measured by test error) gap between the interpolated models and optimal-regularized model is small. The authors gave the non-asymptotic bounds of test error (in terms of bias-variance decomposition) for both regularized and interpolated models. The authors further showed the impact of filter size of convolutional kernels: harmless interpolation will not happen for small filter size (strong inductive bias), but will occur for large filter size. Also, it is shown that for large filter size, the optimal-regularized models have to fit part of the noise, i.e., training error smaller than noise level. Experiments are provided to justify the theoretical results.
strength_and_weaknesses: Strength:
- The paper is overall clearly written and easy-to-follow.
- Understanding the generalization properties of interpolated models is an important and interesting direction of the theoretical machine learning, and this paper gives interesting results towards this direction.
- The results are interesting and novel to my knowledge, which show the relation between filter size and the performance of optimal-regularized and interpolated models.
- The results are clearly stated with assumptions. Proof sketch is provided in the main text with full proof in the appendix.  

Weaknesses:
- The proof techniques may not be easy to generalize to other settings beyond kernel and linear settings.
- It would be great if authors could provide a formula (or the order) of some quantities in the main text or appendix, such as $\beta^*$ and $\lambda_{opt}$.

Minor:
- line 208: missing a space between descent and predicts

clarity,_quality,_novelty_and_reproducibility: Clarity:
- Overall the paper is well-written and easy-to-follow.

Quality:
- The quality of this paper is overall good. Theorems and assumptions are clearly stated. Proof sketch is provided in the main text with full proof in the appendix. (I didn’t check the full proof).

Novelty:
- The harmless interpolation/benign overfitting is an active research direction and studying the impact of such biases is an important problem.
- The results are novel to my knowledge, which shows the impact of implicit bias on the performance in the noisy setting.

Reproducibility:
- This is a theoretical work with several experiments. Full proofs are provided in the appendix and codes are provided in the supplement material, but I didn’t check/run them.

summary_of_the_review: In summary, the paper studied the generalization error of optimal-regularized and interpolated models in high-dimensional kernel regression setting. The results showed impact of filter size to the test error, which appears to be new and interesting. Therefore, I’m leaning towards accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the impact of the strength of inductive bias on the generalization performance of the trained model. First, the authors prove that in kernel learning with convolutional kernels, a phase transition occurs in the noisy data setting. Specifically, when the level of inductive bias exceeds a particular threshold, interpolation is harmful. But, it is harmless when the inductive bias is sufficiently weak. For the noiseless data setting, no similar transition occurs and interpolation is provably harmless. In addition, the authors prove that in the noisy data setting, the model with the weak inductive bias fits some of the noise (variance on the training sample is below the data variance). However, the latter statement does not really prove that interpolating noise is necessary since nothing is mentioned about the optimal inductive bias. Finally, the authors present two experiments, which suggest that such conclusions seem to hold in deep neural networks as well. 

strength_and_weaknesses: This is a well-polished paper that studies the important topic of generalization in modern neural networks. The authors present an interesting insight in terms of inductive bias that is quite novel and is supported both theoretically and experimentally. The experiments are also well-executed. 

The primary weakness is that the settings studied theoretically and experimentally are contrived but I don’t think this is a major issue given the insight this paper provides. It would have been valuable to figure out how to quantify inductive bias in typical training settings, e.g. in standard benchmark image datasets with convolutional neural networks, but this is quite challenging given the lack of knowledge about the ground truth. 

Another weakness is already acknowledged by the authors. The main theoretical results make strong assumptions about the distribution of the data that cannot be easily relaxed. 

Finally, while the authors prove that models with weak inductive bias interpolate some of the noise, this does not mean that interpolating noise is necessary since it is not clear whether the optimal bias is below or above the threshold $\beta^\star$. Please correct me if I have miss-interpreted this part.

I have two minor suggestions:

- Please clarify the meaning of the $\Theta$ notation for quantities that are bounded from below by zero and go to zero such as writing $\sigma^2 = \Theta(d^{-\ell_\sigma})$. I personally read this as $O$ notation but if there is more than that, please clarify in the paper. 
- The statement of the theorems should be self-contained. Currently, there are hidden assumptions on the ground truth and eigenfunctions in the proof that are not stated in the main theorems. Please mention them explicitly. 

Two typos:

- Line 32: “interpolators interpolators”
- Line 208: “double descentpredicts”

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and is of a high quality. Both the theoretical and experimental results are insightful and novel in my opinion. Also, the authors describe the experimental settings in sufficient length for reproducibility. 
summary_of_the_review: This is a nice, insightful paper that is well-executed. However, I haven't verified the correctness of the proofs.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper investigates the interplay between the strength of algorithm's inductive bias and the benign overfitting phenomenon. The "benign overfitting", "harmless interpolation", and "overparametrization" phenomena have recently gained a lot of attention in the field of theoretical machine learning, including the research focused on understanding generalization of deep neural networks. I believe that advances in these directions are very interesting and important for the field.

The authors approach the question by studying a very clear and controlled setup of high-dimensional (regularized) kernel regression, where the ground truth function is known and the inductive bias of the algorithm (the filter size of the convolutional kernel) has a clear interpretation. The paper provides (Theorem 1) exact rates for the bias and variance of two algorithms --- the min-norm (un-regularized) and ridge-regularized RKHS regressions. Comparing the rates, the authors clearly demonstrate that there is a critical size of the filter (or "critical strength of the inductive bias) that separates the benign and harmful overfitting: for the stronger inductive bias, the unregularized model that is allowed to interpolate the training data performs worse than the (optimally) regularized model; for the weaker inductive bias, both models have the same performance. 

Even though the formal analytical argument holds only for the particular (and artificial) setup studied by the authors, all the reviewers agree that this does not diminish the significance of the contribution. More realistic general setups would be too difficult to deal with and by considering a simple, clear, controlled setup the authors managed to make their claim very accessible. Moreover, the authors provide experimental evidence (Section 4) suggesting that similar effects may take place in more realistic scenarios involving convolutional neural networks. Overall the reviewers agree that it is a very interesting contribution that has a potential to help future research in this direction.

All the reviewers highlighted that "the paper is easy to follow and well written" and that "it states the main claims clearly and provides evidence for them." They agreed that "both the theoretical and experimental results are insightful and novel". 

I recommend the acceptance. However, I would ask the authors to carefully account for the feedback, provided by the reviewers. Doing so will further improve the readability of the paper.
justification_for_why_not_higher_score: The topic stated in the paper is very important and popular in the field of theoretical machine learning (including "overparametrization phenomenon" and  understanding of deep neural network generalisation). The results obtained in the paper (formal for a narrow setup and empirical for more realistic scenarios) are certainly significant and interesting, particularly to the aforementioned subfields. However, given the formal argument of the paper focuses on a rather artificial and narrow setup, I don't feel confident that at the moment the consequences of these results are broad enough to interest a wider audience.
justification_for_why_not_lower_score: All the reviewers (and myself) agree that the paper provides a significant contribution to the field of theoretical machine learning, particularly to the research around overparametrization and benign overfitting.
Decision: Accept: poster