Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper establishes generalization bounds for a broad class of losses over linear predictors by utilizing Moreau envelope theory. The authors show that particular quantities that depend on a localized Gaussian width can control the prediction error under Moreau envelopes of the loss, which can then translate to generalization bounds on the original loss as well. The setting is fairly broad, as it allows for models misspecification and more general loss functions. A number of previous results in the literature were extended.
strengths_and_weaknesses: Originality: There has been significant interest in better understanding generalization properties, especially of interpolating solutions. To the reviewer's knowledge, the application of the Moreau envelope framework to tackling generalization appears novel.

Quality: The general theory provided here seems to give a number of improvements to previous results, including classical and recent ones. While the Gaussian data assumption is fairly restrictive, obtaining a complete understanding of this regime is still important.

Clarity: The paper is very well-written and easy to follow, even though it is quite technical. Here are some small comments:
- need a space between sentences in line 163
- the footnote at the top of page 8 takes you to page 1 instead of the bottom of the page

Significance: The work appears quite significant.
questions: What is the intuition behind the use of the surrogate distribution in the main theorem (Theorem 1)? Does this aid in analyzing the interaction between the noise and the low-dimensionality of the data? Also, is the main hurdle in extending the Gaussian data assumption the use of the GMT framework for the analysis? I would also suggest a short discussion after the introduction of the Moreau envelope about why analyzing the Moreau envelope of the loss is useful. The results showcase the utility of the framework, but it could be good to provide some intuition beforehand.
limitations: Yes. No societal impacts need to be discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the generalization properties of high-dimensional generalized linear models (GLM). Assuming that the inputs are Gaussian and the underlying data distribution follows a multi-index model, the authors obtained upper bounds for the population Moreau envelope risk in terms of the training loss and the Rademacher complexity of the function class in a variety of overparameterized settings. Specializing their results to several applications, they show connections to existing results in the literature such as the optimistic rates for linear regression and the benign overfitting.
strengths_and_weaknesses: Strengths:
The main results in the paper are novel due to their generality -- they holds for GLMs with possible model misspecification. The results in the main text are clearly stated and intuitions are given to parse them. The proofs of these results I checked seem to be technically solid. Finally, the connections to existing literature are very interesting and show the generality of their results.

Weaknesses:
The main issue I have with this paper is that some of the assumptions are not transparent and seem to be difficult to verify. This is the case in the main theorem in Sec. 4 as well as in the results derived in Secs. 5 and 6. One important question the authors did not answer is that whether these assumptions hold in a specific setting, e.g., well-specified linear regression. This, together with the Gaussian input assumption, question the applicability of their results. See the Questions section for more details.
questions: Major questions/comments:
1. The Gaussian input assumption is quite restrictive. If a well-specified model is assumed, can you relax this assumption?
2. How easy is it to verify Eq (6)? Can you give some examples?
3. One line 198, there is a claim "in many settings of interest, this can be directly checked using the fact that $x$ is Gaussian". I would like to see concrete results to support this claim. What can you say when $x$ is not Gaussian?
4. In Cor. 3, it is required that the inputs are Gaussian and Eq. (9) holds for all $\mathcal{D}_n$. However, Bartlett et al. (2020) do not have these assumptions when the model is well-specified. In the well-specified setting, can you verify or relax these assumptions?

Minor questions/comments:
1. The sentence "the first term is negligible since the dimension is small" on line 158 is confusing. Isn't the main focus here the high-dimensional setting?
2. What are $x_i$s in Eq. (5)? Are they the coordinates of $\tilde x$? If so, what happens to the $(k+1)$-th coordinate?
3. Should the term $\epsilon_{\lambda, \delta}$ in Eq. (6) also depend on $n$?
4. Should the term $C_\delta(w)$ in Eq. (7) depend on $k$, $d$, and $\Sigma$?
5. Why is the claim on line 245 true? Isn't $f_\lambda \rightarrow 0$ as $\lambda \rightarrow 0$?
6. On line 260, is $\tilde f$ convex? If not, how did you get $\hat L_{\tilde f}(w) = 0$?
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: analysis of (one-sided) generalization error using Moreau envelopes. 

theorem 1: if the empirical Moreau loss is unformly not much smaller than the expected Moreau loss whp then the expected Moreau loss is less than the empirical loss plus a complexity term, so ERM leads to small expected Moreau loss.

this is applied to develop 
1. vc bounds for the expected Moreau loss
2. bounds linear regression with square loss and classification with sq-hinge loss (for the expected loss instead of expected Moreau loss, by exploiting properties of Moreau envelope of square/sq-hinge resp.)
3.  discussion of l1 and hinge loss implications, and relationship to huber loss
4. general Lipschitz losses (improves existing results by a constant factor)
5. general smooth losses given interpolation (generalizes existing work)
6. recover results on benign overfitting


strengths_and_weaknesses: Strengths:
- clear writing
- easily interpreted results
- results appear to be sound
- the approach to studying generalization via Moreau envelope analysis is an interesting, and the present work initiates a nice connection between recent work in high dimensional statistics with generalization bounds.
- the literature review is quite thorough

Weaknesses:
- the consequences of the main result are not really novel. better or essentially the same (up to constants) results have been obtained using other techniques before.
- the present work would be stronger and more compelling if there was an example where these methods provided a strictly better rate than existing work.
- some of the results only bound the expected Moreau loss, not the expected Loss
- limited to linear multi-index models and gaussian covariates

questions: - The matrix Q in Eq (4): I verified that Q is idempotent, but it is not clear that it is symmetric. are you sure this is the correct definition?
limitations: - limited to linear multi-index models and gaussian covariates
review_title: null

Meta-review: metareview: The manuscript proves a new (finite-sample) generalization bound for generalized linear models, using Moreau envelope theory. The paper also provides experimental validation.

While the results only hold for Gaussian data, I believe there is some interesting novel results which might inspire some future work in the learning theory community. (In comparison, several novel frameworks have been created in the past for other problems, in which the initial versions assumed Gaussianity, e.g., the work on support recovery on sparse linear regression, for instance.)

Several technical clarifications regarding the assumptions (e.g., surrogate distribution, comparison to prior results) were asked by the reviewers, which the authors thoroughly and successfully addressed during the rebuttal phase. I recommend adding this to the camera-ready version of the paper, as well as other discussions and clarifications raised by all the reviewers.
confidence: Certain
Decision: Accept