Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the generalization error of a class of interpolator in linear regression and identifies conditions for optimality. They consider a setting where there is a true linear model generating the data, whose parameters are drawn from a Gaussian distribution with zero-mean and covariance Phi. In this setting they consider a natural class of estimators that are a function of the data, the population covariance matrix, the prior covariance matrix Phi and the signal to noise ratio. Among this class of estimators they calculate a closed-form expression for the optimal interpolator, with respect to the expected excess risk and show that there are certain settings where the expected excess risk of this estimator can be much lower than the risk of the OLS solution. They also provide an extension of their results to the random features model.
main_review: The authors study an interesting problem on a topic of much recent interest---benign overfitting of linear models. While the assumptions made on the problem are pretty stringent, the authors provide a clean exposition of their results which I appreciated as a reader. 

Here are some questions/comments about the paper:

1. The authors mention the results by Amari et al. (2021), who they mentioned studied estimators whose asymptotic bias or variance is optimal. How do the techniques and setting used in this paper differ from theirs? Can the techniques used there also be used here but instead to balance the bias and the variance optimally? A discussion regarding this would be helpful to the reader. 

2. On ln 91 the authors say an interesting question that they study here is if minimum norm interpolant is always close to optimal, and show that this is not the case. But I think this question has already partially been answered given past work of Bartlett et al. (2020). Given their results, it is easy to construct cases, for example, when population covariance matrix is isotropic, where the minimum norm interpolant is not consistent but the ridge regression solution is. So, I would urge the authors to provide some more nuanced context and discussion here.

3. Regarding the assumptions both the noise xi and the true parameter w* are assumed to be drawn from a Gaussian distribution. Can this be relaxed? Further, can the results of this paper (Proposition 1 in particular) be extended to hold in the case where w* is not mean zero?

4. In the experiments described in Section 4.1, where w_O is approximated by w_{O_e}, what is the structure of the population covariance matrix? Is it isotropic or close to it? Or does it have a heavy tailed structure similar to one that was shown to be necessary by Bartlett et al. for the minimum norm solution to be consistent? Further, empirically, was the estimate Sigma_e close to Sigma? A plot to verify this would be nice.


=================== Post rebuttal comments =================== 

Firstly, I would like to thank the authors for their very carefully response to the questions raised by all of the reviewers. I continue to support acceptance of this paper post the rebuttal period. In my view, I think it would be nice if the authors incorporate the many helpful suggestions raised in all of the reviews in a subsequent version.

limitations_and_societal_impact: The authors do a good job of describing the potential negative impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper is concerned with inducing a certain type of best possible interpolator in linear regression. It is based on the notion of best possible interpolator, defined in Muthukumar et al., 2019., which is the best estimator (i.e., with minimum risk) among the class of interpolators. Based on that, the authors define a new theoretical estimator, the best estimator among interpolators that are also linear in the response variable.  They manage to induce a closed form of this estimator and prove that it is the limit of preconditional gradient descent under a specific initialization. In addition, using approximations for quantities that are usually unknown in practice (e.g.  population covariance matrix, signal to noise ratio), they turn this theoretical estimator into a fully empirical one and compare its performance to other frequently used estimators, showing that this estimator performs arbitrarily better in certain cases. Finally, they extend this notion of best possible theoretical estimator to the random features setting, where they again induce a closed form for this estimator and prove that it is the limit of preconditioned gradient descent under a specific initialization.

main_review: The paper is interesting to read. It belongs to the long list of papers that are concerned with the overparametrized estimation, but instead of trying to explain why this type of estimation generalizes so well, it aims to find the best linear interpolator in the linear regression setting. By restricting the class of possible estimators in the definition by Muthukumar et al., 2019, they manage to turn a theoretical device into a fully observable estimator. They also define a similar notion of optimal estimator for a more complex model and induce a closed form of this estimator, something that may suggests that we could try to induce this type of optimal estimators for even more complex model like neural networks. There is also an interesting example, where we can see that a frequently used interpolator, the minimum-norm interpolator, has arbitrarily bad generalization. Finally, these examples combined with the results related to preconditional gradient descent highlight nicely the importance of initialization.

The paper could be of greater significance if
a) the construction of the fully-empirical estimator would not be restricted to the isotropic regime
b) (as they note) it included a precise guarantee on the approximation error of the estimation of the covariance matrix Σ
c) instead of performing an empirical analysis for special cases, they could manage to prove a theoretical result that bounds the generalization error of the fully-empirical estimator w.r.t. the generalization error of the theoretical optimal response-linear achievable interpolator.

In addition, I think that some points in the beginning of the proof of Proposition 1 could be written with more clarity.
limitations_and_societal_impact: In line:
-64  I don't think that Mourtada deals with interpolators in this paper.
-129 A comment regarding the subscript in the expectation may add some more clarity, as some times this means expected value given this quantity, or expected value given everything else other than this quantity
- 132 "In linear regression (when d>n), minimizing the..."
-480  Maybe you could start with a general W that belongs in this class instead of Wo, as equation (17) seems a bit strange.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper under reviews studies the problem of optimal linear interpolation. More precisely the authors derive an explicit formula for the *best* linear interpolator that can be written as a linear function of the outputs and as a function of desired quantities. From this, they show how to recover theoretically this estimator from a optimization algorithm. Finally they expose cases where the designed estimator show some good generalization properties while the miminum norm interpolator does not.  The link with kernel methods is also made.
main_review: **Overall comments and impression**

First, I would like to say that I am not an expert in statistical learning theory, so that I may have missed some insights in the results.

To begin, I would like to say that the paper is perfectly well written: the story is very clear and the mathematical writing is precise and fluid. This made the reading very pleasant and I would like to thank the authors for that.

The aim of the author is clear: provide an (under certain constraints) optimal linear predictor that may perform better than the minimum norm one naturally considered in the literature (naturally coming from GD or SGD on the empirical risk). The authors do so quite effortlessly ad give, to my opinion a nice result for those asking whether minimum norm solutions are always good estimators. **Yet**, I would have liked a lot more comments on the shape of this estimator: what intuition should the reader build when reading the paper ? A clear weakness is that the authors never really take the time of analysing why makes the estimator optimal (beyond technical considerations). In the very same manner, Proposition 2 gives that the optimal linear response is in fact the solution recovered by GD with a certain initialization: could the authors comment a bit on this ? 

The result on the divergence of the minimum norm linear interpolator (whereas the optimal one does not) is nice: however I would really need to understand further *why* and *when* we should expect this to happen. And in general cases *how close* should I expect the minimum norm interpolator to be close to the optimal one ? 


**Minor comments:**

- I guess that the part on the random matrix concepts arrive too early. As far as I understood, there is absolutely no need to put this part at the beginning, and this could be postpone in section 4.2 or even in the Appendix. 

- The part on random features model gives nothing new to the results: they are not commented (at all) and are absolutely expected once the linear model is covered. If these results are not further commented, then I recommend to put it in the Appendix as they do not give any additional insight on the paper. A nice introduction on why linear model are trendy is enough in my opinion (NTK, random features...)

- In Section 4.2, is this possible to derive a close form for the asymptotic risk of the optimal interpolator ? If not, why is this complicated ?

- Give more motivation and justification for the form of the *optimal linear interpolating estimator* you build. Why are you okay with the dependance on \Sigma, \phi, \delta. How could relax these ? I understand that these parameter will be estimated on the fly later: but once again, the comments on this are not deep precise enough to convince me. In particular there are only a few comments on the Graphiical Lasso approximation and why this is a good idea to approximate the population covariance.

- Plots commenting Proposition 2 would rely complement the result! If not, it seems not so important: a comparison with GD without preconditionning would be welcomed.


**Conclusion**

Even if I really enjoyed reading the paper, my opinion is that, under this form, the results lack from commentaries, intuition, insights and a bit of further developments.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper considers the problem of optimal interpolation in linear regression. It defines the class of response-linear achievable interpolators, and provides a closed-form expression for the optimal interpolator in this class. The paper is about an important topic in machine learning and statistics. However, it is unclear to me whether the "achievable" interpolators are really achievable, and as a result if the investigation is meaningful.
main_review: Major comments and questions:
1. The paper claims that the realization of true data-generating parameter and the realization of the noise in the training data are unknown. However, it assumes that the population covariance, the signal-to-noise ratio, and the covariance of the prior for the signal are known. The latter seems to be more unrealistic. For high dimensional data, the covariance matrix contains much more number of parameters than the regression coefficient so it is a much harder problem to estimate the covariance matrix. In a Bayesian setting, the primary goal is to find the distribution of the parameter. If the distribution of the parameter is assumed to be known, then there is no estimation problem.

2. For $\Phi$, do you mean it is the correlation matrix? Otherwise calling $r^2$ the signal is not appropriate. 
   
3. The population risk between lines 125 and 126 is not clear.It is written as the conditional expectation given $X, \xi, w^*$, but this does not make sense. A risk should not be random.

4. I think the $y$ in line 131 should be $y_i$, but what is the $y$ in line 132? The $y$ in line 117 should be $y_i$? How about the $y$ in lines 120 and 124? Each of these may be typos or poor notations, but when there are too many this type of problems and makes it hard to following the paper it becomes a major issue. 
   
5. Line 142, I believe you need $\gamma\ge1$.

6. Line 156 says "rank(X) = n with probability 1" while this becomes a condition in line 160.

7. Definition 4, do you mean there exists a known function? Otherwise, the function $f$ may depends further on other unknowns.

8. As in my first point, the $w_O$ is not realistic. The updating formula in (7) requires the inverse of $\Sigma$ which is almost impossible for high dimensional data. 

9. I don't think Hastie et al. (2019) considered the case of $\Phi=I_d$. It is probably a typo here.
   

Minor issues and typos:

Line 53, "are best" to "are the best".

In (5), use paratheses to make the definition clear.

limitations_and_societal_impact: Please see the main review.
review_title: null

Meta-review: This is a good paper and I recommend to accept it. There are plenty of points in the reviews that suggest ways to improve the paper and I recommend that the authors follow up on these.
Decision: Accept (Poster)