Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This article deals with excess risk guarantees, under Gaussian noise, of linear regression with interpolators: estimators with zero training error. In particular, it highlights the role played by the norm of an interpolator in the generalization bounds. The proposed analysis covers a wide range of problems since it is valid for a large class of norms. In particular, the analysis covers the case of  $\ell_1$ norm interpolator and the  $\ell_2$ norm interpolator. These upper bounds were used to prove the consistency of the respective interpolators.

main_review: Although heavily technical, the article is well written and the proven results were widely discussed and compared to the existing results in the literature. However, some aspects of this work need to be clarified: 
- the theoretical results proven in this article are relevant and single out from existing work in the regime  $n$ goes to infinity. Yet, in practice, the dimension d  is finite. Taking both n and d to infinity makes sense in the context of kernel-based interpolation: the effective dimension increases with n and goes to infinity as the regularisation parameter goes to $0$. But, it seems to be unnatural to take d to infinity in the context of linear regression. How can we conciliate the two seemingly contradictory regimes (n goes to infinity and d is finite) in the context of linear regression? 
- It would be interesting to give the intuition behind the conditions for consistency in equation (7), especially for the two quantities $\sqrt{\frac{Tr \Sigma_2}{n}}$ and $\frac{n}{R(\Sigma_2)}$. (Or at least the order of magnitude of these quantities when $\Sigma$ is a sequence of decreasing exponentially or polynomially to 0.) 
-The same goes with the conditions of Theorem 2: intuitively, what does it mean to have $R(\Sigma_2) \geq n \log(2/\delta) ...$?

Minor comments:
- Line 122: I can’t understand why the rate is only $\mathcal{O}(N^{-1/4})$ since $1+\beta^{,}$ converges to 1.
- Equation (7) is misleading: we may think that the three terms are equals...

limitations_and_societal_impact: No.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper uses (a small modification of) the CGMT for a uniform bound and the GMT for bounding the norm of the min-norm linear interpolators for general norms. Using this technique they recover generalization bounds for l2 and l1 and consistency conditions such as in Tsigler, Bartlett et al. or Zhou et al. In contrast to these works their bound does not only apply to the exact min-norm interpolator but for all linear interpolators that have a norm as small as an high probability upper bound of the min-norm interpolator. By doing this they provide a counterpoint to some recent works that question uniform convergence to explain the generalization capabilities of overparameterized interpolating models. 
main_review: Strengths:
- the authors provide a novel and (to the best of my knowledge) innovative and elegant way to use uniform bounds for low-norm linear interpolators for regression (proven separately before for the min-l1 and min-l2) by appealing to the (C)GMT. 
- the manuscript is very clearly and nicely written
- the proof sketch contains the key ideas of the proof so it’s very informative

Constructive comments:
- The proof technique is the key novelty and one certainly wonders about the impact of the exercise of unifying proof framework for l1 and l2 generalized to norms in general -> is there any gain going forward for non-Gaussian distributions, neural networks etc. - the impact of the new technique is not quite clear to me since the (C)GMT crucially rely on Gaussianity. On the other hand, the l1-discussion about w* = 0 - relatively speaking, it’s not that big of a result IMO. Hence in my view, given the limited space, it would be much more enlightening to shorten that section and instead discuss the impact of the new proof technique. Also a discussion about more insights from the proof would be very helpful / useful - what is the intuition behind why consistency for min-l1 can be achieved for spiked covariances with d = e^{omega(n)}? 
- The proof would benefit from significant modularization. Navigating through the proofs is unnecessarily cumbersome since there is a lot of nesting, lemmas are often proved along the way

On  another note: 
Regarding the story that makes a case for/in defense of uniform convergence min-norm-ball: I guess somewhat concurrently, Chinot et al. ‘21 (AdaBoost ...) have also used uniform convergence techniques for min-l1-norm classifiers although they study a different setting … 

limitations_and_societal_impact: -
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors study generalization bounds for minimum norm linear interpolants. They use techniques from uniform convergence to derive a general bound that applies to minimum norm linear interpolant, that depends on both the norm of the optimal linear predictor as well as the Gaussian width and radius of the corresponding norm ball. In the case of the Euclidean norm the authors re-derive the sufficient conditions previously obtained by Bartlett et al. (2020) by deriving an upper bound on the norm of the predictor. In the case of the l_1 norm, the authors provide a set of sufficient conditions for the minimum norm interpolant to be consistent and discuss the implications in two special cases.
main_review: This paper was a pleasure to read, and the authors provide an interesting set of results that help improve our understanding of the behavior of interpolating models. Their results also indicate that the fact that techniques from uniform convergence may indeed be useful in understanding the generalization behavior of interpolating models by skirting past recent lower bounds (e.g. Bartlett and Long).  Some questions for the authors that hopefully shall help improve this draft:

1. In ln 107 the authors say that we expect the Gaussian width to scale like sigma sqrt{n}. I dont see where the dependence on sigma comes in here if the set K is just the norm ball of radius B.

2. In equation 12 is it clear if the sufficient conditions for the l_1 minimizer to be consistent close to necessary? Is there any evidence, theoretical or otherwise to suggest this or not?

3. On ln 266 the authors say ||w^*||_1 sqrt{log(d)/n} diverges, but it is not clear to me why this is the case.

4. I would appreciate a more detailed comparison between the techniques used in this paper and the techniques employed by Ju et al. and Chinot et al. who also study the minimum ell_1 norm interpolant using uniform convergence techniques.


5. On ln 297, both equation (PO) and equation (AO) are not defined.


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

I thank the authors for their responses. I would like to continue to vote for acceptance, and would be happy to see this paper being published at NeurIPS.

limitations_and_societal_impact: The authors have addressed the limitations and potential impacts of their work.
review_title: null

Meta-review: The paper studies uniform convergence for linear predictors in the high-dimensional setting with gaussian assumptions on the data. This setting has been adopted by the learning theory community to tractably study generalization phenomena arising in deep learning. In this setting, the paper gives new bounds on the generalization error of interpolating solutions, where the bound depends on the gaussian width of the function class and the norm of the predictor. This recovers some existing bounds derived in special cases, and adds a counterpoint to recent work suggesting uniform convergence cannot explain generalization in high dimensional settings.

All reviewers agreed that the results are novel and interesting, the paper is clearly written, and the proofs are easy to follow and illuminating. As such, we believe this will make a strong contribution to the program. 
Decision: Accept (Oral)