Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper studies the phenomenon of double descent for ridgeless regression. They show that when the label noise in the regression problem is lower bounded, the test error for regression must peak at the interpolation threshold (n=p) before descending again in the over-parameterized regime and that this holds with very weak assumptions making it a universal phenomenon when we consider unregularized linear regression. 
These results extend our understanding of double descent and point that under most general settings it is impossible to avoid for ridgeless linear regression. 

The paper is well-written and the analysis and comparison to prior work provided appears thorough. I have not verified all the proofs in the appendix.

-------
Thank you to the authors for their response and update. I have read the response and am keeping my current rating for the paper.
review_title: Well-written Paper on Generality of Double Descent Phenomenon for Unregularized Regression

final_score: rating: 7: Good paper, accept
review_content: This work studies the double descent phenomenon in ridgeless regression with deterministic or random features. The work provides a lower bound on the generalization error that requires weaker assumptions than bounds given in previous work and applies to many interesting learning methods.

Strengths:
-- The generalization bound presented this work requires fewer assumptions than previous such bounds while also being stronger.
-- The work is theoretically rigorous and helps to shed light on why various learning methods perform well.
-- The authors thoroughly investigate the applicability of their bound with specific discussion of each of their assumptions.

Weaknesses:
-- While the analysis applies to a class of feedforward neural networks with analytic activation functions, some common activationswith a perfectly linear component like ReLU, however are not covered by the results in this work.

The second sentence in Remark 7 says, "If (d) in Propositions 8 does not hold..." but I don't think you mean to reference Prop. 8 here.
review_title: "On the Universality of the Double Descent Peak in Ridgeless Regression" review

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

The paper focuses on the theoretical understanding of the so-called double descent phenomenon, which may offer insights into the practical success of deep learning methods and has been observed in both overparametrized neural networks and kernel machines.  In particular, the authors derive a nonasymptotic distribution-independent lower bound on the excess generalization error of the ridgeless linear regression under mild conditions on the input distributions and feature maps. More specifically, their analysis applies to the cases where the input distribution has a Lebesgue density and the features are induced by random deep neural networks with analytic activation functions,  random Fourier features, polynomial kernels, and so on. The sharpness of the lower bound has been demonstrated by some numerical experiments. The results should be of interest to the community of theoretical deep learning. Overall, I vote for accepting.


Concerns:

1. Is it possible to derive a nonasymptotic upper bound which matches the lower bound in Theorem 3?
2. In Theorem 3 and Corollary 4, which lower bound should be adopted when $p=n$, $\sigma^2n$ or $\sigma^2$?
3. In the underparameterized regime ($\gamma<1$), the derived lower bound seems to be not asymptotically sharp by looking at Theorem 2 of Hastie et al. (2019), any special reason for this?
4. The authors may consider using subsections since sections 2 and 3 are very short compared to other sections.
review_title: Official Blind Review #4

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Contributions

This work studies linear regression with feature maps (or kernel regression) without regularization in order to theoretically explore double descent phenomena seen empirically when training over-parametrized networks.

This paper provides lower bounds on the out of sample error or generalization error caused by the label noise. In the over-parametrized regime or beyond the interpolation threshold this is the primary source of error. 

While this setting has been studied before this work strictly generalizes previously provided bounds especially around the interpolation threshold. They also consider analytic feature maps including random ones and thus imply results for random deep neural networks. 

The main text of the paper is well organized. However, it could benefit from some more clarity in presentation of the technicalities especially in section  5 when comparing with prior work and in section 6 when providing examples. 

# Concerns
1. It seems that a big part of the assumptions is that the data is generated from a full dimensional distribution. Given that in the high dimensional settings where d ~ n a key problem is to characterize the behavior of estimators when true data has low intrinsic dimension can we say anything about this regime given the results in the paper? 
2. It seems that the main novelty over prior work especially Muthukumar et al. (2020) is around the interpolation threshold or slight weakening of the assumption on the noise. Since the over-parametrized regime is currently most relevant to the community is there a relevant example in this regime where the results provided in this work are strictly better (in terms of actual rates or in understand of this regime) than those from prior work? 
3. Or just as importantly are there examples of proof techniques that are used here that are substantially novel over those in the prior work that may be beneficial to the community in general in understanding these over-parametrized regimes? 
4. There is some recent work on ridgless kernel regression by [Liang et al. (2020)][1]. Since these two settings are fairly intertwined it would be nice to understand how results in current work compare to the results in this paper.

[1]:https://arxiv.org/abs/1808.00387
review_title: While this paper provides relevant theoretical insight into ridgeless linear regression there are some concerns over novelty given prior work.

Meta-review: This paper shows that the double descent phenomenon of ridgeless regression appears under considerably general settings of the input distributions by showing a lower bound of the excess risk. The analysis covers various types of input distributions including deterministic and random feature maps and its asymptotic sharpness is also shown.

One reviewer raised a concern about its novelty compared with existing work, but the authors properly clarified the novelty in the rebuttal and updated version of the manuscript. Although there were some other minor concerns, the reviewers all agree that this paper gives a valuable theoretical result supporting universality of double descent phenomenon. I also concur with this assessment. I think this paper is a solid theoretical paper giving an informative result as a piece of researches in double descent. Thus, I would recommend acceptance of this paper.
Decision: Accept (Poster)