Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper compares the effect of interpolation and regularization on robust generalization. It shows that in the case of regression under squared loss and classification under the log loss when the ground truth is a linear model robust generalization error is smaller for regularized estimators. The robust generalization error is defined as the error under consistent adversarial perturbations. 
main_review: This paper provides important insight into the effect of regularization vs interpolation for robust generalization. It is clearly written and well-organized. 

While the results presented in this paper are useful and interesting I have some concerns about the form of adversarial perturbations considered. In particular, there is not sufficient motivation why the particular definition of adversarial perturbation is used. It seems as though considering perturbation orthogonal to the ground truth may primarily be well suited to the linear ground truth setting. It's not clear if this is a valid choice for other models or how to generalize such perturbation to different models especially one where the data is lower dimensional. It is also unclear why "adversarial" perturbations are consistent. That is a strong assumption. 

On a different axis, it is not clear why training in the regression setting does not include adversarial examples but training in the classification setting does. What structural differences in the two problems imply the use of these different settings? 

Furthermore, to provide a faithful comparison to related work some experimental evidence on real world data might be beneficial. 
limitations_and_societal_impact: Some limitations were addressed by the authors.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies how regularization affects the robust population risk in the overparameterization regime. The authors study the behavior of linear regression and logistic regression under sufficient statistical settings. In particular, even in the noiseless regime, the population robust risk benefits from the regularization, but not the population test risk. The argument is empirically verified. 
main_review: The problem studied is important and interesting. The writing is clear and the proofs look technically sound. These results help us further understand the behavior of overparameterization, especially in the adversarial environment. Here are my questions and some minor typos:

1. In theorem 3.1 (and also 4.1), how do we get $R(\hat\theta_0)$ or $R_\epsilon(\hat\theta_0)$? Do we directly take the limit of the RHS in (6) as $\lambda\to 0$? If so there should be an argument that involves monotone convergence/dominated convergence theorem that exchanges the limit and integration (which may be straightforward but worth mentioning)? Say I set $\gamma=2$, then isn't $\lim_{\lambda\to 0^+}m(-\lambda)=\infty$? I probably missed something here. 
2. In Figure 4(b), when $1/\lambda\to 0$, the ERM should start to look like an all $0$ vector right? Then shouldn't the risk be large?
3. Is there any intuition that you use $\ell_2$ regularization other than $\ell_1$ in (8) since the true $\theta^*$ is assumed to be sparse? I guess one thing is $\ell_2$ is easier to analyze, but do we at least know how $\ell_1$ regularization behaves in this setting?
4. [1] is an important reference that is missing. They also study the relation between regularization and double descent, but in the non-adversarial setting. 
5. In the description of figure 5 some typos: "the minimum margin is decreases...", "this trendis also observed..."
6. Line 257, "regularization improves regularization".

[1]: Optimal Regularization Can Mitigate Double Descent
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the benefits of non-vanishing regularization for improving generalization in overparameterized classification and regression problems. In this setting, previous works studied the implicit bias effect. Particularly, it was shown that training models *without* explicit regularization can still yield good generalization performance. In contrast, in this paper, the authors show that explicit regularization can further improve generalization, especially w.r.t. the adversarial robust risk.
main_review: The paper studies how regularization affects the adversarial robust risk for both linear and logistic regression problems.

The paper main contributions are:
-	The authors illustrate empirically the benefits of ridge regression and early stopping w.r.t. robust generalization, both for linear and logistic regression.
-	The authors state theoretical results which shed light on these empirical observations.

My main concern is the paper’s writing and clarity. I found the flow of the paper lacking and, in general, the message the authors tried to convey did not pass clearly. In addition, there are many sloppy typos throughout the draft. Doing a very thorough revision and improving the writing flow would greatly benefit the paper and make the message much clearer.

Some examples of issues that should be addressed:
-	Theorem 3.1 seems to be cut off in the middle of a sentence. The Theorem abruptly ends with the sentence “Finally,”. 
-	Lines 303-305: “While our theoretical results hold for the ridge penalty, we experimentally observe the same behavior for early stopping gradient descent. While our theoretical results apply for ridge regularization, we also observe the same behavior for early stopping.”
This seems to be just a duplication of the same sentence and is probably a typo.
-	The observations and conclusions from each of the experiments should be clearly stated.
-	The Theorems are very technical, and some explanations will help better understand the results. For example, how is the function m behaves as a function of z? What this means on B and V depends on $\lambda$? There is some discussion in the paper, but I found it insufficient.

Items such as these persist throughout the paper and make it difficult to assess the paper quality, correctness, and the significance of the results.

---

After reading the rebuttal: In their response, the authors made the paper's main contributions much clearer. Therefore, I would like to increase the score to 5. I hope that, given the reviewers’ feedback, the authors will improve the clarity of the final draft.
limitations_and_societal_impact: It is hard to properly assess the limitations of the results due to the reasons listed above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors analyze the generalization performance of regularized adversarial linear regression and classification models for standard Gaussian data in the overparameterized setting.  The analysis allows for l^2 weight decay as well as l^\infty perturbation of the inputs.  Using similar methods to Hastie, Montanari, Rosset, and Tibshirani [18] and Javanmard and Soltanolkotabi [19], they are able to develop precise formula for the generalization error in the limit as n/d -> constant as n,d -> infinity.  They demonstrate that non-zero regularization has strictly better generalization in the robust setting. 

main_review: At a high-level, the technical tools seem to be straightforward applications of theory developed in [18] (for Theorem 3.1) and in the CGMT/[19] (for Theorem 4.1) to the robust and l2 regularization setting, with the caveat that [19] was for the mixture of Gaussians setting rather than the Gaussian marginal setting which thus requires an additional extension.  (I did not check all of the details of the proof.) However, no previous work had been able to demonstrate concretely that nonzero ridge regularization will provably lead to better generalization performance even when there are noiseless observations in the robust setting, which as an interesting observation and informs our understanding of interpolating models. I particularly liked the intuitive explanations given in Sections 3.4 and 4.4. 


A few comments/questions:

(1) It is unclear to me from Figure 2 if either the standard interpolating or regularized (asymptotic) risk is supposed to be larger in the noiseless setting.  They clearly look the same, but are the theoretical predictions the same?  It is hard to parse given the complicated formula for P and B, and the possible dependence on gamma.  It would help if there were comments on this in the text.  

(2) What is the reason for requiring epsilon = O(1/sqrt(d)) in Theorem 4.1?  Can larger perturbations be tolerated, or what is the bottleneck?  Previous work [3', Corollary 2.10] has shown that adversarially trained linear classifiers over Gaussian marginals can tolerate \ell^\infty perturbations of constant order (albeit with suboptimal generalization guarantees). 

(3) Can you comment on how the results would extend to l^2 perturbations?  It seems like most of the analysis would follow through, but I don't recall a discussion about this in the text. 

(4) A discussion on a number of references [1', 2', 3'] would be helpful, especially [2'] as it directly concerns the ability of ridge regularized linear regression to generalize.  [1', 3'] concern the ability of adversarially trained linear classifiers (under logistic loss) to have small robust risk and/or the implicit bias of such algorithms; discussing these works would improve the presentation around lines 221-230 and 633-661.  Especially in footnote 2, the work [1'] is relevant. 

(5) Relatedly, it is not clear to me if the comment on lines 221-223 is true.  Has it been shown that the gradient descent on the robust empirical risk converges to the robust maximum margin direction for the l^\infty perturbation?  [1'] shows this is the case for l^2 perturbations but I am not aware of a work that shows it for l^\infty, but perhaps the authors can point out such a work or my misunderstanding. 

(6) The current main section of the text has very limited description of the proof the proof techniques involved for the results, especially Theorem 3.1 (CGMT tools seem the workhorse for Thm 4.1).  It would be helpful if more high-level proof ideas were provided in the main part of the text. 

Minor points/typos:
* Figure 4 caption: "plottet"
* Figure 5 caption: "average margin (horizontal lines) decreases" should be increases, no?
* Figure 5 caption: "trendis"
* lines 303-304 appears a sentence got repeated
* lines 666-668 check writing, appears something went wrong
* lines 829-831 put () around eqs
* display (33) "sucht"


[1'] Implicit Bias of Gradient Descent based Adversarial Training on Separable Data. Yan Li, Ethan X.Fang, Huan Xu, Tuo Zhao. ICLR 2021.

[2'] Benign overfitting in ridge regression. A. Tsigler, P. L. Bartlett. 2020 preprint

[3'] Provable Robustness of Adversarial Training for Learning Halfspaces with Noise. Difan Zou, Spencer Frei, Quanquan Gu.  ICML 2021.


** post rebuttal **

Thanks for the detailed response.  I'm happy with the paper and think they did a good job of responding to other reviewers' concerns.  I recommend acceptance for the paper. 

limitations_and_societal_impact: Yes, they adequately addressed the limitations.
review_title: null

Meta-review: This paper aims to understand the effect of ridge regularization in overparameterized settings. It is believed that overparameterized models already have implicit bias and incorporating regularization does not provide any additional benefits in terms of standard risk. However, this paper shows that, for linear models, employing ridge regularization does help improve robust generalization in both regression and classification settings, even when the training is performed with noiseless data. 

All reviewers agree that the paper studies an interesting and timely problem, and makes multiple novel theoretical contributions. There were some concerns about the writing of the paper that have been resolved via the discussion among the authors and the reviewers. Once reviewers' feedback is incorporated, this paper will be a valuable addition to NeurIPS 2021.
Decision: Accept (Poster)