Venue: ICLR 2021 Conference

Reviews:

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

The paper proves that the generalization curve of a linear regression problem can be designed. The paper discusses both the under-parameterized and over-parameterized case and shows that the generalization curve can be designed in either case. The paper presents only theoretical results.


##########################################################################
Reason for score:

My vote is for accepting the paper. The subject it addresses is of importance and I believe the results that are presented are of sufficient interest.

##########################################################################
Pros:

1. The generalization error is an important aspect for ML algorithms. The paper addresses the case of linear regression, one of the simplest ML algorithms. However, showing that the generalization error can be controlled even for a simple model as this is nonetheless important.

2. The paper is well written, the problem it addresses is clearly discussed and the development of the proposed method is well detailed.


##########################################################################
Cons:

1. I would have liked to have some numerical examples to illustrate the design of the generalization curve for a simple case. 

2. In the setting in the paper you draw the new elements either from a normal distribution or from a mixture distribution when you increase the dimension. In a practical settings, where I already have the data, do such hypothesis still remain true?


##########################################################################
Miscellaneous:

1. Could you please elaborate on the statement that 'the true linear model is \beta = 0 \in R^{d}'. For me it is not clear what is the purpose of the statement, do you mean that the model parameters are all zero? 

2. There are some typos present, for example 'The quantiry ...' in the paragraph after lemma 3, they should all be spotted by a spell checker. 
review_title: Generalization loss design for linear regression

final_score: rating: 6: Marginally above acceptance threshold
review_content: Previous work has shown peaks in generalization error as the capacity of the model increases (called the double-descent phenomenon). The submitted paper proposes methods for generating data that would arbitrarily change the number and positions of peaks in a generalization-vs-capacity curve for linear regression, where the number of features controls the capacity,  and shows that properties of data can play an important role in this phenomenon.

This paper tackles an important problem in a quite active area of research with clear presentation and coherent organization. Existence of this data serves as an impossibility result that shows that relating the double descent phenomenon to the properties of model and interpolation without further assumptions on the data is futile. However, there is a critical discrepancy between the generalization curves studied in this paper and previous work that I describe below and, therefore, I'm leaning towards rejection. I will raise my score if the authors can show that the effects on the number and positions of the peaks hold in the original setting, as I believe this is an important paper otherwise.

The generalization error in this paper is normalized by the square of the number of features and this can have major effects on the shape of generalization-vs-capacity curve. The number of features is what controls the capacity so, for example, if the regular (unnormalized) error is flat across different capacities, the normalized curve will be a decreasing sequence.

Neither the generalization error in a classical bias-variance curve nor the error that matters to a practitioner is normalized. I skimmed through the double descent paper by Belkin et al and they also seem to be using the typical generalization error which is not normalized.

The motivation for normalization in the paper is that the closed form error, $||(A^\top)^+x||^2$, sums over d dimensions and so the generalization error has to be normalized by d^2. This does not seem right. $(A^\top)^+$ itself has factors that sum over d dimensions and are then inverted, so the effect of d will cancel out.

Minor remarks:
- \beta and A are not clearly defined in the problem setup.

--
Update: The issue with normalization is fixed in the new version and I am increasing my score.
review_title: Important result; mismatched settings;

final_score: rating: 4: Ok but not good enough - rejection
review_content: Short summary:
The paper claims that the double descent phenomenon arises from 'specific interactions between properties of typical data and the inductive biases of algorithms' and constructs a distribution that generates an arbitrary generalization curve for linear regression, specifically building a multiple descent generalization curve both in the under and overparametrized regimes. 

The model that is used in the paper is a linear regression model over an increasing (in a revealing manner) set of coordinates or features. The authors construct the distribution that gives the peaks at custom coordinates by having features being independent  standard normal when they want the test error to decrease and to be a (independent) mixture of gaussians when they want the test to increase.
++++++
Main points:
While the math to my understanding is clean and the exposition is clear, my main concern is how the authors relate their findings to Double Descent. This worries me in two related ways. First, from the perspective of the complexity of the model.  While adding a dimension to the linear regression adds a parameter, I'm skeptical how this relates to the complexity of the model in how we view complexity in machine learning and in the research area of double descent in particular. I would be much more convinced if the authors could show a case where adding a feature in the random features sense where the features are of the whole vector (say apply a random rotation and then do the inverse transform sampling) or adding a neuron in a two layer network and still being able to decrease/increase performance arbitrarily (or close to it in some sense).  Even doing the same as in https://arxiv.org/pdf/1903.07571.pdf, where they choose a random set of indices of increasing cardinality would convince me much more. The second related issue, is the distribution of the features. I would not mind it if the classifier would use the features uniformly, but increasing/decreasing the hardness of the distribution at each coordinate feels very artificial in the following sense: Assume that the first coordinate is the label (or something close to it), but the next coordinates are pure noise. Then both our train and test will increase when we increase the number of features. In my intuition, this is very far from what is studied and claimed in the double descent literature (for example in the sense of Belkin's interpolation point or Nakkiran's Model Complexity, we expect the train error to decrease when model capacity increases). 

I do believe that the question of whether we can construct an arbitrary generalization curve is very important and that it should be studied and explored more deeply, but I'm not convinced by the set-up in this paper. I would be willing to change my opinion in the case the authors will address the above points in a satisfactory manner. 

Minor comments:
1) The related work in the body of the paper is lacking:
  (i)  One notable paper that should be present is: Advani & Saxe 17' https://arxiv.org/abs/1710.03667.  
  (ii) While Nayshabur 15' observe the double decent without realizing it and Neal 18' study the bias-variance tradeoff, Nakkiran 19' https://arxiv.org/abs/1912.02292 is the first to demonstrate it in a convincing fashion and should be cited as such. 
2) I would appreciate an explanation for why the loss is scaled by $1/d^2$, this feels rather arbitrary. 
 
review_title: The paper studies an interesting problem but gives an unsatisfactory answer to it.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the double/multiple descents of the prediction error curve for linear regression in both the under-parameterized and over-parameterized regime. 

The strength: while many papers have studied the double descent for linear regression estimate or the minimum $\ell_2$ norm solution,  this paper shows multiple descents when d=O($\sqrt{n}$) a setting is barely studied by others. Further, while multiple descents have been numerically discovered by other concurrent works, they have theoretically proved that such multiple descents exist.  

The weakness: The major weakness of the paper is the model settings. Specifically, 1) it is unclear why the prediction error is normalized by the number of features, and 2) the bias term is left out in the prediction error due to the true coefficients being zero and only the variance term is considered. First, for normalization, the authors claim that this normalization is necessary for comparison. Indeed, the entire results are hinged on this normalization, i.e., without the normalization, the proof can NOT show the existence of the multiple descents neither in under-parameterized regime nor overparameterized regime. The reasons I found this normalization is weird are the following:

i) Normal linear regression problem does not have such normalization on the prediction error. It is unclear why we want to divide a one-dimensional error by the feature size.

ii) Other double descent works mainly deliver two messages:

a) Given a fixed sample size, what is the best model gives the best estimate of the response. The answer is a larger model, i,e, adding more features, may help. (e.g. Xu's PCR paper)

b) Given a fixed feature size, what is the best sample size that gives the best estimate of the response. The answer is using a smaller sample size may help. (e.g. Hastie's double descent paper)

For both cases, I do not see any reason to normalize the prediction error of response by feature size. If this normalization is for the purpose of the model selection penalty, it is unclear why we should encourage a larger model instead of penalizing it.   

A reasonable quantity for such normalization is the MSE of the coefficient, i.e., $\|\hat{\beta}-\beta^*\|^2$. There are many applications where people are more interested in the coefficients rather than the response. Maybe the authors should consider this quantity instead of the prediction error. 

For the second weakness of the model settings, the bias term has been left out of the prediction error when the true coefficients are assumed to be all zero. Because of this setting, all features are just pure noise, irrelevant to the response. Then, we can check that 0 is the best estimate when all features are just pure noise, and it seems that there is no motivation for us to learn anything from the random noise. If the main purpose of this paper is to deliver a message that using only irrelevant features and adding more of them can help to improve the prediction error, this effect is known already in those double descent paper in the overparameterized regime. Showing multiple descents does not add much value because it never beats the trivial estimate 0 in this setting.   

Because of these major weakness, I recommend rejection for this paper. But I will possibly change my evaluation if the authors can provide a very convincing explanation of the model settings and motivation.

Besides these, another suggestion for the paper is that the proof of the Theorems and the statement of Lemmas takes a lot of places. I think they can be replaced by more detailed discussions of the model settings and messages or conclusions from the main theorems. For example, is there any intuition about what kind of multiple descents curve is more favorable? Also, despite the attractive title, I think it is still hard to design the generalization curve without taking the bias term into consideration. The room can be left for the analysis of the bias term.   

After response:
Thanks for addressing the concern about normalization. It appears that other reviewers have a concern about such normalization as well. I suggest the authors remove the results with normalization entirely from the main paper and only have it in the appendix for anyone that is interested in such normalization. 

On the other hand, without normalization, the results have changed for the under-parameterized regime (which makes more sense to me) and the proof looks quite different in the over-parameterized regime as well. I did not have time to check the proof and I believe it is better to resubmit the paper as new because of the major changes. 

Finally, I still have concerns about the fact that only variance is discussed. I suggest the authors state their results in a setting where both bias and variance exists and the features added to the model are related to the response. Otherwise, it is a weird message that it is good to add pure noise as features. It feels like although we can design multiple descents in the overparameterized regime when noise is large, it is very likely that the 0 estimate achieves the best prediction risk. So there is no point to go into overparameterization and multiple descents at all.    

In summary, I have raised the score to 5. I believe it can be 6 or 7 if all issues are addressed, but I am afraid that the paper looks basically new after these changes and thus I am not sure whether it should be still considered for this conference.  

review_title: My decision hinges on a very convincing explanation on the model settings and motivation. Currently I consider a reject.

Meta-review: While there was some interest in the analysis, the consensus view was that the original treatment was not sufficiently well-motivated, and the revision was too dissimilar from the original submission for it to be evaluated for publication in this year's ICLR.
Decision: Reject