Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: =================================
FINAL UPDATE AFTER DISCUSSION PHASE

As the authors addressed the points that came up during the discussion phase (which made me initially lower the score), I revert back to my initial scoring of accept.


===================================
UPDATE AFTER INITIAL DISCUSSION PHASE

The authors addressed my own points, but following the discussion with the other reviewers I decided to lower my score. It was pointed out that the data generation process depends on the model-dimension, and thus the resulting investigation is not about 'generalization curves' as claimed by the authors, but rather about the generalization behavior of different interpolation regimes. While I believe the contribution is still valuable, some explanations and need be changed (which may be possible in a camera ready version).

( For example I don't believe anymore that the paper indeed answers the question: 'Can the existence of a multiple descent generalization curve be rigorously proven?'.)

==================================

The paper analyses the behavior of generalization curves of linear regression wrt an increasing feature dimensionality. The paper constructs specific examples that can generate any ascending/ descending behavior of the curve, for both the under and overparametrized case. Their construction highlights that ascending/ descending behavior of the generalization curve is not inherent to the model family, but rather a result of the data distribution in combination with the model.
main_review: Summary review:

Strength:
+ Fairly polished
+ Main story is easy enough to follow, despite some parts being rather technical
+ Original
+ Technically sound (checked some proofs of Section 3, not from 4) 

Weaknesses:
- Some remarks are missed on me 
- No discussion

Detailed review:

The paper considers learning curves, a topic that recently gained traction again. Previous works report various types of multiple descending behaviors, either empirical or theoretical, but this works provides, to the best of my knowledge, the most rigorous and general example that highlights this behavior. As I don't see any major flaws, I will thus vote to accept the paper. 

There are some remarks in the paper that got missed on me: 

Remark 2: In particular the part 'For the second part ... we can change the order of the features'. 
At this stage of the paper it is pretty unclear how the product relates to C. But more importantly: We can change the order of the features, but what is the consequence of that/ why is that an interesting observation?

Remark 3: I missed a bit the point of the remark. Is it just to demonstrate that sampling from $N^{mix}_{\sigma,1}$ is not difficult, or is there more to it?

Line 181: $x_1$ is not the best choice for the additional feature of the test vector as $x_1$ is also a training sample. For me sticking to the $b$ notation, e.g. $b^0$ or $b^{test}$, would be better to follow. 

The Gaussian $\beta$ setting:

It is a bit curious to me that we have now a distribution of $\beta$. I did not check the proof of Theorem 10, but from the statements it seems like it also works for a single $\beta$, by looking at the statements for $\rho \to 0$. It would be good if you could comment on that. Do we need it? Is it there to be more general? What do we lose/maintain if we assume a single $\beta$. 

I personally find the conclusion a bit weak. I would like to see more of a discussion. You conjecture that multiple descents also occur for NN, is that based on any observation or intuition? In the beginning you state that those curves are rarely seen in practice. Does your work now shed a new light on that observation? Or at least point into a new direction to tackle it?



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors systematically study a simple linear regression setup where an arbitrary number of ascents and descents can be obtained in the risk. 
main_review: Originality: Multiple-descent curves are studied in several works as cited in the paper. As far as I know, this one is unique in proposing an algorithmic construction of input data distribution. 

Significance: It is an interesting example setup that anyone who works on this subject should keep in mind. 

Clarity: The paper is written very clearly and has a good structure. 

Quality: Although I could not check the appendix due to time constraints, I did not detect any issues in theorems neither proofs. 

I have two comments:
- line 68: "for any learning model". The authors consider a very constrained setup of linear regression, not any general learning model. 
- line 311: Conjecture for neural networks. In my opinion, a conjecture needs some level of motivation. This sentence seems very off. In the paper, the model size grows as the input data dimensionality grows. In neural networks, the model size is totally independent of the data. The more obvious difference is non-linearity. Please remove this conjecture, or justify it with regards to your setup. 
limitations_and_societal_impact: Theory work without a clear societal impact.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper studies the generalization error of the min-l2 norm solutions of linear regression. Authors claim that their analytical results can explain the multiple peaks in the generalization curve with respect to the number of features. However, the system model and some fundamental steps of the analysis are problematic, which makes me doubt the correctness of the paper.
main_review: The problem setup in this paper seems not correct. Generally speaking, the output of the training data y is given beforehand and shouldn’t depend on the number of features d (or any other manually chosen parameters) used in the linear regression. However, the problem setup on page 3 states that y=\tilde{x}^T\beta+noise, where \tilde{x}=x[1:d] depends on d, and thus y depends on d. That makes the generalization error curve with respect to d in this paper useless because the error curve is not for one specific ground-truth function but for different ground-truth functions when d changes. In order to study the effect of the number of features on the generalization error, a more correct setup should be y=x^T\beta+noise instead of y=\tilde{x}^T\beta+noise. Authors can take the following paper as an example: “M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.07571, 2019.”

In Eq.(1) (the generalization error), it is unclear what random variable (e.g., training input, test input, noise in the training input) in each step the expectation is based on. Besides, the second step of Eq.(1) seems incorrect, i.e. E[(y-x^T\hat{beta})^2-(y-x^T\beta)^2] is not equal to E[(x^T(\hat{beta}-\beta))^2].

Remark 1 is incorrect. Authors claim that A^+A=I, which is wrong. I think the correct one should be E[A^+A]=I where the expectation is on the design matrix A (i.e., the training input x).

Remark 1 implies that the bias term is always zero in the under-parameterized region and authors completely discard the bias term in Eq.(2). This contradicts the well-known bias-variance tradeoff curve (the U-shape curve) in the under-parameterized region of linear regression. Similarly, Theorem 1 says that L_d is always increasing with respect to d, which also contradicts the known U-shape curve. The authors explain on page 5 that a "U-shaped curve does not always occur" and use the Prop.2 of [28] as evidence. However, Prop.2 of [28] describes the situation that the number of features and the number of training input go to infinity at a constant ratio, which is not relevant to the situation in this paper where both the number of features and the number of training inputs are finite. Besides, I haven't seen any literature (including [28]) that says "U-shape curve does not occur in the under-parameterized region". Indeed, "U-shape curve does not occur" is a very strong statement and should deserve more careful justification. For example, authors should clearly point out why the classical derivation of bias-variance tradeoff does not hold here. Is it because this paper uses a different setup? Or is it because the classical derivation of the bias-variance tradeoff is totally wrong?

Overall, the setup and some fundamental steps of the derivation seems problematic and the main result contradicts the well-known bias-variance tradeoff result in the under-parameterized region, which jeopardizes the credibility and the contribution of this paper.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: I have read other reviewers' comments and the author response.
I lower my score due to the following reasons: 1) changing the feature dimension $d$ doesn't change the groundtruth function, which makes the problem setting questionable. 2) the response to the issue "\sigma should be taken far smaller than O(1/5^n)" is unsatisfactory, which makes the result unattainable. 
=============================================
This paper studies the multiple descent of the excess risk for linear regression in under/over-parameterized regimes. In the under-parameterized regime, Theorem 3.1 includes two parts: one is showing that the loss $L_d$ non-decreases with $d$ independent of the data distribution; the other is $L_{d+1} - L_d > C$. In the over-parameterized regime, the authors provide the multiple descents in Theorem 5 under $\beta = 0$ and Theorem 11 with $\beta$ being Gaussian.
main_review: The quality of this paper is good but there are several points that I concern:

**Problem settings:**

The target function is assumed to be linear, low-dimensional ($d<D$), which is fair and standard in interpolation learning. 
However, it appears a little strange to me when the authors consider a linear regression over its partial features (i.e., $d<D$) so as to tune $d$. I do understand that, in linear regression, adding one dimension to features is equivalent to increasing the model complexity (strictly speaking, at least non-decreasing). This operation/setting can be also found in [51]. However, a learning problem often corresponds to a given/fixed d. A common way is to tune the number of samples n instead of d, which is more reasonable in practice. So is it possible to transform the results via tuning $d$ in this paper to the standard tuning $n$ setting, e.g., [Liu, Liao, and Suykens AISTATS2021] on kernel regression in high dimensions?


**Technical details:**

The proof in this paper largely depends on taking $\sigma  \rightarrow 0_+$. This might be unattainable in some cases. Here I take one example to illustrate this.
I’m questionable the second part in Theorem 3.1, i.e., the proof of Theorem 4. 
First, the constant $C$ in fact depends on $\sigma$?
Second, the employed strategy in the proof is to derive the lower bound in line 600 such that the second term in line 595 is sufficiently large. To this end, the authors derive this lower bound as the exponential decreasing order of n. In this case, \sigma should be taken far smaller than $O(1/5^{n})$ if we want to ensure the non-negativity of line 599. However, this might be unattainable in practice. For example, if we only consider n=100 samples, sigma should be taken as 1e-70 order. Accordingly, this condition should be better re-organized. In theory, it could be possible to derive a polynomial order (at most) of $n$ in line 599? In experiment, Theorem 4 can be experimentally validated on some synthetic datasets: obtaining A and x, and seeking for potential solutions of $C$ and $\sigma$.   


**Minor issues:**

1．	The authors claim that “To our best knowledge, this is the first work proving a multiple descent phenomenon for any learning model.” In line 67. I suggest the authors polish this sentence if [34] is taken into consideration.

limitations_and_societal_impact: yes
review_title: null

Meta-review: We thank the authors for this submission. Overall, the paper presents an interesting perspective on the fact that the generalization curve can have multiple descents, and that the locations can be explicitly controlled. 

The paper well-motivates the approach. The authors have provided extensive responses to the concerns raised and the AC + reviewers really thank them for their effort. Overall, the new results obtained during the rebuttal definitely improve the quality of the paper. We all believe that the inclusion of these results during the rebuttal period is something that does not heavily change the message of this paper.

There was discussion and consensus that this work is interesting. However, there are definitely points that need to be handled, based on the discussion so far. Having in mind issues/concerns raised by the reviewers, the main points of reviewers during further discussion were that this paper deserves publication, given the promised fixes by the authors during the discussion period.
Decision: Accept (Poster)