Interpolation can hurt robust generalization even when there is no noise
Authors: Konstantin Donhauser
Alexandru Tifrea
Michael Aerni
Reinhard Heckel
Fanny Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: regularization
high dimensional statistics
learning theory
robustness

Abstract: Numerous recent works show that overparameterization implicitly reduces variance for min-norm interpolators and max-margin classifiers. These findings suggest that ridge regularization has vanishing benefits in high dimensions.  We challenge this narrative by showing that, even in the absence of noise, avoiding interpolation through ridge regularization can significantly improve generalization.  We prove this phenomenon for the robust risk of both linear regression and classification, and hence provide the first theoretical result on \emph{robust overfitting}.

Interpolation can hurt robust generalization even when there is no noise
Konstantin Donhauser'; Alexandru Tifrea'; Michael Aerni',
Reinhard Heckel Fanny Yang'
EET Zurich Rice University Technical University of Munich
konstantin, donhauserdai. ethz. ch tifreaadinf ethz. ch aernimeethz.ch reinhard. Backel@gmail.. com fan. yangyinf..f.... www.iiin..ehhe..cmmmm .ethz.ch
Abstract
Numerous recent works show that overparameterization implicitly reduces variance for min-norm interpolators and max- mar-ma classifiers. These findings suggest that ridge regularization has vanishing benefits in high dimensions. We challenge this narrative by showing that, even in the absence of noise, avoiding interpolation through ridge regularization can significantly improve generalization. We prove this phenomenon for the robust risk of both linear regression and classification, and hence provide the first theoretical result on robust overfitting.
1 Introduction
Conventional statistical wisdom cautions the user who trains a model by minimizing a loss L(0): global minimizer achieves overfitting (i.e., high variance) and thus suboptimal prediction performance. Instead, regularization is commonly used reduce the effect of noise and obtain estimator with better generalization. Specifically, regularization limits model complexity and induces worse data fit, for example via an explicit penalty term R(O). The resulting penalized loss L(0) + AR(O) explicitly imposes certain structural properties on the minimizer. This classical rationale, however, does seemingly not apply to overparameterized models: for example, large neural networks in practice exhibit good generalization performance on i.i.d. samples even if L(I) vanishes and label noise is present [36].
near-zero training loss (i.e., it interpolates),
the risk of
Since interpolators not unique in the overparameterized regime, it is crucial to study the specific implicit biases interpolating estimators. In particular, for common losses, a large body of recent work analyzes the properties of the solutions found via gradient descent convergence (see e.g. [44]
12 13
22
26
27
31) For example, for linear and logistic regression, it is well-known that
gradient descent converges the min-(2-norm and max-E2-margin solutions, respectively [22 27
32 49). These interpolating estimators also minimize the respective penalized loss C()) + X| in
the limit of +
44
plethora recent papers explicitly study generalization properties on min-&y-nome interpolators [5
18 23 33 34 355 and max-Ey max-ly-marge margin solutions [14 34 46), and show that the variance decreases as the overparameterizztion ratio increases beyond the interpolation threshold. While regularization with À 0 is commonly known reduce the risk the interpolation threshold [3 37 many of these works are motivated by the second descent of the double descent phenomenon which suggests that regularization becomes redundant with sufficient overparamettrrization. Hence, previous papers focus on highly overparameterized settings where the optimal regularization parameter satisfies Aopt [29]] 54 43), implying that for large d/n,, explicit regularization with is redundant or even detrimental for generalization.
Equul contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Pruned data
Original
Without
With
0.05
Risk(A (A + 0) Risk Risk(Aopt)) (oopt)
0.5
Risk(A A + 0) Risk(Aopt))
Robust accuracy gain
0.4
0.04
0.4
0.03
0.3
0.3
0.02
0.2
0.2
0.01
0.1
0.1
0.00
0.0
0.0
0
2k
4k
6k
10k
0
2
4
6
8
10
0
4
6
10
Number of hidden units
d/n
d/n
(a) Neural networks
(b) Linear regression
(c) Linear classification
Avoiding interpolation can benefit robustness even in the overparameterized (d >> n) regime and for noiseless training data. We plot the robust accuracy gain of (a) early-stopped neural networks compared models at convergence, fit on sanitized (binary 1-3) MNIST that arguably has minimal noise; and & regularized estimators compared to interpolators with À - 0 for (b) linear regression with n 10 and (c) robust logistic regression with n 10 See Appendix for experimental details and Sections and 4 for the precise settings of (b) and (c).
Figure I:
Taking a step back, this narrative originated from theoretical and experimental findings that consider the standard risk with identically distributed training and test data. However, this measure cannot reflect the robust risk of models when the test data has shifted distribution, is attacked by adversaries, contains many samples from minority groups [19 21 40 [55) In fact, mounting empirical evidence suggests that regularization is indeed helpful for robust generalization, even in highly overparameterized regimes where the benefits for the standard risk are negligible [42]. This
phenomenon is sometimes referred to as robust overfitting.
In the presence of noise, the following intuition holds true: since the robust risk amplifies estimation errors, its variance is larger and hence regularization such as early stopping can be beneficial for generalization 47. However, we observe that even when estimating entirely noiseless signals, robust overfitting persists! We observe this phenomenon in experiments with shallow neural networks on sanitized image data depicted Figure and, in fact, even for linear models trained on high- dimensional synthetic noiseless data. In particular, Figures Ib Ic show that min-2--nore and robust max-(2 -arrgnn interpolators (minimizers of the training loss for À 0), achieve higher robust risk than the corresponding regularized estimators that do not interpolate noiseless observations (minimizers for > 0).
To date, our observations in the noiseless case cannot be explained by prior work. On the contrary, they seem to contradict a simple intuition: if the min-l2-norm and robust max-(2-margin interpolators exhibit large risks as - 0, the induced bias for small f2-norm is potentially suboptimal and a larger penalty weight À > should only degrade performance. In this paper, we provide possible explanations that debunk this intuition in the nigh-dimensional overparameterized regime. We prove for isotropic Gaussian covariates that a strictly positive regularization parameter À systematically improves robust generalization for linear and robust logistic regression. Empirically, we show that non-interpolating estimator achieve a similar effect.
early stopping and other factors that lead Our results provide the first rigorous explanation of robust overfitting even in the absence of noise.
In Section 2
formally define the setting that present precise asymptotic expressions for the robust risk for linear regression in Section 3 that explicitly explain robust overfitting. Furthermore, in Section 4 logistic regression and derive asymptotic results.
throughout
analysis. We then first
we consider classification with
2
Risk minimization framework
In this section, we introduce the data generating process that we assume throughout our analysis, and define the standard and robust risks that we use evaluation metrics.

---

2.1 Problem setting
This paper considers the supervised learning problem of estimating a mapping from d-dimensional real-valued features E RR to target y E y C R given training set of labeled samples 'D (()))))))== We assume that the feature vectors H; are drawn i.i.d. from the marginal distribution that we assume to be an isotropic Gaussian. We further focus on noiseless observations y; (0", ,,;) for regression tasks and y/ = sgu( (000 (x))) for classification tasks, respectively. However, the main results more general and apply to noisy observations well. For regression, assume additive Gaussian noise with zero mean and o² variance, while for classification we flip a certain percentage of the training labels.
This paper studies the high- -igh-dimensional asymptotic regime where d/n Y as both the dimensionality d and the number of samples n tend to infinity. This high- diteemmmeniinnl setting is widely studied as it can often as our experiments yield precise predictions for the risk of the estimator when both the input dimension and the data set size are large (9 [2) It is also the predominant setting considered in previous theoretical works that discuss overparameterized linear models
15
25
24
2.2 Standard and robust risk
We now introduce the standard and robust evaluation metrics for regression and classification. Given pointwise test loss liea R x R R, define the standard (population) risk of estimator 0 as
R Exee (1,,)), (0", x))
where the expectation is taken over the marginal feature distribution P. Note that for any data- dependent estimator 0 this risk is fixed if conditioned on the training data. Our asymptotic bounds hold almost surely over draws of the training set. As standard in the literature, we choose the square loss Gest (u, v) = (u - u)² for regression and the 0-1 loss Gestt (u, v) = [sgn(a))sgu(()) for classification.
The broad application of ML models in real-world Decision-making processes increases requirements on their generalization abilities beyond i.i.d. test sets. For example, in the image domain, classifiers should be robust and output the same prediction for perturbations of an image that not change the ground truth label (e.g., imperceptible fp o--eetuurbaionn [19). In this case, we say the perturbations are consistent and the estimator that achieves zero robust population risk also has zero standard population risk. For linear models in particular, one way to enforce consistency is to restrict perturbations to the space orthogonal to the ground truth, as proposed in [41].
Motivated by the imperceptibility assumption and fy-adversarial attacks widely studied in the image domain, we consider the adversarially robust risk of parameter with respect consistent ép- perturbations
R_ (Ø) = Ex~P max lees (ueu(10, + 8), (x)))) 5El(p(E)
with the perturbation set (e)()) 18 E Rd: ||8|p S and (0), 55 03.
In many scientific applications. security against adversarial attacks may not be the dominating concern; one may instead require estimators to be robust against small distribution shifts. Earlier work 48] has pointed out that distribution shift robustness and adversarial robustness are equivalent for losses that are convex in the parameter 6. Similarly, in our setting, adversarial robustness against consistent l fy-petuurbation implies distributional robustness against bo-noddded mean shifts in the covariate distribution P (see Appendix A.3
3 Min-Cz-norm interpolation in robust linear regression
In the context of regression, we illustrate overfitting of the robust risk in Equation (2) with the set of consistent fg-perturbations U2(e). More precisely, we show that preventing min-l2-norm interpolation on noiseless samples via ridge regularization improves the robust risk. We refer the reader to Appendix C.T for an intuitive explanation. Lastly, we note that due to the rotational invariance of the problem, our results hold for sparse and dense ground truths 0* alike.
3

---

3.1 Interpolating and regularized estimator
We study linear ridge regression estimates defined as
1 (v (0, +
Λ arg min -
(3)
n ==
The min-l2-norm interpolator is the limit of the linear ridge regression estimate with À - 0 and is given by
0g arg min |00| such that (0, y/ for all i.
Note that the min-f2-norm interpolator is also the estimator that gradient descent on the unregularized loss converges to, while ridge regression with À >> 0 corresponds early-stopped estimators 2 Therefore, by proving that a ridge regularized estimator with min-Cz-norm interpolator with À + also show that early stopping benefits robust generalization.
significantly outperforms the
Whenever the goal to achieve low robust risk, popular alternative using the standard linear regression estimate in Equations (3 is to consider adversarially trained estimators [19 25
usual form (i.e., with inconsistent perturbations) prevents regression estimators from interpolating, and hence, has similar effect to éz-regularization discuss in more detail in Appendix C.2 On the other hand, training with consistent perturbations as defined in the robust risk is equivalent to full knowledge of the direction of (* and hence simply recovers the ground truth the noiseless case. Since our goal is to reveal the shortcomings of interpolators compared to regularized estimators, we only analyze ridge estimators trained without perturbations.
However, fz-adversarial training
we
3.2 Robust overfitting in noiseless linear regression
The following theorem provides precise asymptotic expression of the robust risk under consistent fz-perturbations for the ridge regression estimate Equation (3). The proof extends techniques from
previous works [23] 15 based on results from random matrix theory [3] (28) and can be found in
Appendix E Without loss of generality, we can assume that ||0*
Theorem 3.1. Assuming the marginal imput distribution (0, La), the robust risk 2 of the esti-
mator 0x for A (defined (3) with respect to consistent ex-perturbations U2(Et) asymptotically
converges to
82 R. (0x) as, RA - 2 + PARA = Re,A
(5)
% where PA= X2 {mm(->)) and RA = X2m'(-X) + (22(m(())) >-)(-))) is the asymptotic standard risk, i.e., R(0,) at, Rr, The function m(z) is the Stieltjes transform of the Sauchenko-Pasttre law and is given by m(2) 111---11-1-00--1
d,n
with d/n
Further. the limit limx Re,x exists for all e 2 and corresponds to the asymptotic standard (e 0) and robust risks 0) of the 22-oom interpolator 0g (4)
2yz
We plot the precise asymptotic risks of the ridge estimate with optimal regularization parameter Asp and of the min-Ey-norm interpolator for - O in Figure 2 For the robust risk, we use = 0.4. We first observe in Figure 2a that ridge regularization reduces the robust risk even for d/n >> 1 well beyond the interpolation threshold - the regime where previous works show that the variance is negligible, and hence, regularization does not improve generalization.
Moreover, Figure 2b illustrates that the beneficial effect of ridge regularization persists even for noiseless data. This supports statement that regularization not only helps reduce variance, but also reduces the part of the robust risk that is unaffected by noise in the overparameterized regime. Furthermore, we show that experiments run with finite values of d and (depicted by the markers in Figure 2 closely match the predictions obtained from Theorem 3.1 for d, n + oc and d/n + y. This
'Here we choose À using the population risk oracle. In practice, one would resort to standard tools such as cross-validation techniques that also enjoy theoretical guarantees (see e.g. (38).

---

Standard, interpolating Standard, regularized (opt.)
Robust, interpolating Robust, regularized (opt.)
Population risk
Population risk
1.0
1.0
0.5
0.5
0.0
0.0
0
6
0
2
3
4
5
6
d/n
d/n
(a) Noisy observations
(b) Noiseless observations
Figure Asymptotic theoretical predictions for d, + 0o (curves) and experimental results with finite d and π 10s (markers) for the robust (e 0.4) and standard risk of the min-62- norm interpolator (solid, interpolating) and the ridge regression estimate with optimal À (dashed, regularized) for (a) noisy data with o² = 0.2 and (b) noiseless data. We observe that the gap between the robust risk of the interpolating and optimally regularized estimators persists even for noiseless observations.
indicates that the high-dimensional asymptotic regime does indeed correctly predict and characterize the high-dimensional con-asymptotic regime. Finally, even though Theorem assumes isotropic Gaussian covariates, we can extend to more general covariance matrices following the same argument in [23] based on results from random matrix theory (2
Max-(2-mary interpolation in robust linear classification
Unlike linear regression, adversarially trained binary logistic regression classifiers may still inter- polate the training data, resulting in robust max-(2-margin interpolators as À + 0. Hence, in this section train and evaluate classifiers with -ee-ttruuraaiion sets (e). standard choice in the experimental and theoretical classification literature [19] 24, 42, 47). but also discuss fz-perturbations in Appendix D.3 for completeness. Our theoretical results show that the robust max-62 -margnn
interpolator with À + has a worse robust risk than regularized predictor with À > 0.
4.1 Interpolating and regularized estimator
As discussed in Section 3 a common method to obtain robust estimators is to use adversarial training. However, for linear regression, adversarial training either renders interpolating estimators infeasible, or requires oracle knowledge of the ground truth. contrast, for linear classification, interpolation easier achieve it only requires the sign of (I; 0) be the same the label yi for all In particular, when the data is sufficiently high dimensional, it is possible to find an interpolator of the adversarially perturbed training set.
We study the robust ridge-regus regularize logistic regression estimator with penalty weight À > 0,
0x arg min 8 7
max log(1 + -0,,0t + 211011 self (c)
In the limit + 0 the results in imply that the robust ridge-regularized logistic regression estimator from Equation (6) directionally aligns with the robust max-(2-margin interpolator
0 = arg min | such that min (0 x, + 8) 2 for all i. 6ell..
While 44 only proves the result for 0, straightforward to extend to the general case where 0.
5

---

Standard risk
Robust risk
Normalized robust margin
0.2
0.0
0.0
0.2
0.2
10
10a
10a
10a
10a
10
10
1/X
Iteration
Benefit of ridge regularization
(b) Benefit of carly stopping
Figure 3: Normalized robust margins and risks of empirical simulations using 0.1 and d/n 8. with respect to (a) increasing 1/İ and (b) gradient descent iterations when minimizing Equation (6) using À O. Both ridge regularization and early stopping yield superior robust and standard risks. Each experiment uses 10 and inconsistent &o perturrbaatin for training. See Appendix for more details.
We say that the data is robustly separable if the robust
interpolator exists.
The robust max-éy-mann margin solution is interpolating estimator of particular importance since it directionally aligns with the estimator found by gradient descent [31]. Since the robust accuracy (i.e., the robust risk defined using the 0-1 loss) is independent of the norm of the estimator, simply refer to the robust max-ez-margin solution as the normalized vector ||all22
In this paper, we study two choices for the of training perturbations Uso (e):
inconsistent perturbations consistent perturbations
(c) (5 Rd ||0| c} (oo (6 Rd [10] S c, (5,0*) 0*) 0}
(8)
(9)
Adversarial training with respect to inconsistent perturbations (8) is a popular choice in the literature improve the robust risk (e.g. [19 24)). However, perturbed samples may cross the true decision boundary, and hence, inconsistent perturbations effectively introduce noise during the training procedure. In particular, in the data model with noiseless observations that introduce in Section the ground truth function misclassifies approximately 8% of the labels when perturbing the training data with inconsistent perturbations of size 0.1.
As mentioned in the introduction, this paper we are interested in verifying whether regularization can be beneficial in high dimensions even in the absence of noise. Therefore, in the sequel we study the impact of both inconsistent (8) and consistent (9) perturbations on robust overfitting.
4.2 Robust overfitting in noiseless linear classification
We now show empirically that regularization helps to improve the robust and standard risks when training with noiseless data and derive precise asymptotic predictions for both risks. Throughout this subsection we assume deterministic, and hence, noiseless training labels, i.c., 3/4 = sgn(x;, 0*). Furthermore, as we discuss in Section 4.3 the inductive bias of the -obust logistic loss encourages sparse solutions. Since we are primarily interested in learning ground truth functions that match the implicit bias of the estimator, assume the sparse ground truth 0* (1,0, 0, O1.,O...,.)) 0)".
We first show robust overfitting experimentally on noiseless data when training with inconsistent perturbations and subsequently demonstrate that overfitting persists even if the training procedure is completely noiseless (i.e., using consistent training perturbations). Finally, we provide theoretical evidence for observations in the high-dimensional asymptotic limit.

---

Training with inconsistent adversarial perturbations Figure 3a illustrates the robust margin min; minseus (+) [Ø] (0, + 5) as well as the standard and robust risks of the estimator 0, trained using inconsistent adversarial perturbations
synthetic data with fixed overparameterization ratio d//n = 8. We observe that decreasing the ridge coefficient well beyond the point where the minimizer of the robust logistic loss (6) reaches 100% robust training accuracy (i.e., the robust margin becomes positive) substantially hurts generalization.
In addition to varying the ridge coefficient X, notice that the same trends for À 0 also occur for the gradient descent optimization path as the number of iterations t goes to infinity. Figure 3b indicates that, similarly to ridge regularization, early stopping also avoids the robust max-ly-margin solution that is obtained for + oo and yields an estimator with significantly lower standard and robust risks.
Training with consistent adversarial perturbations As discussed in Section|4.1] even for noiseless training data, inconsistent perturbations induce noise during the training procedure. Hence, one could hypothesize that the noise induced by the inconsistent perturbations causes the overfitting observed in Figure 3] To contradict this hypothesis, we also study adversarial training with consistent perturbations. By definition, consistent perturbations do not cross the true decision boundary and hence leave the training data entirely noiseless.
Figure 4a shows that the adversarially trained estimators 6 with consistent and inconsistent perturbations yield comparable robust risks. Morcover, robust overfitting occurs in both situations, as the risk is higher for the interpolating estimator À + 0 compared to an optimal > 0. Hence, our observations demonstrate that robust overfitting persists even if training with consistent perturbations in an entirely noiseless setting. This observation is counter intuitive since, according to classical wisdom, would expect ridge regularization only benefit in noisy settings where the estimator suffers from a high variance.
We now prove this phenomenon using the next theorem. In particular, similar to Theorem 3.1 for linear regression, we show that robust overfitting occurs the high-dimensional asymptotic regime where d/n 7 as d, n -> co. We state an informal version of the theorem in the main text and refer to Appendix [F for the precise statement. The proof is inspired by the works [24 46) and uses the Convex Gaussian Minimax Theorem (CGMT) (20 51).
Theorem 4.1 (Informal). Assume that e e Vd for some constant Eo and 0- (1, O)T
Then, the robust and standard risks of the regularized estimator 0x (6) (A > 0) and of the robust adversurial tox
max-t2-margin interpolator (7) (X + 0) with inconsistent (8) or consistent
perturbations converge in probability as d, n + xc, d/n + to:
V and R. (+,) + R(Os) + 2 crf
EgO V1 2
R R(Oa)
arccos
+ I
22
1/
We denote by erf(.) the error function,
T(I, w) = L
1 1 exp (-2) erf
x²2
dx,
V2T
/2(1 u²)
and use the notation o' = v(11)2 + (u))2 where vi, V/ 8* are the unique solution of scalar optimization problem specified in Appendix that depends on 6", . eo and X.
Since the theoretical expressions are hard to interpret, we visualize the asymptotic values of the standard and robust risks from Theorem 4.1 in Figure/4bbby solving the scalar optimization problem specified in Appendix[] F We observe that Theorem (4. indded predicts the benefits of regularization for robust logistic regression and that simulations using finite values of d and follow the asymptotic trend. We describe the full empirical setup in Appendix
4.3 Intuitive explanation and discussion
Even though we explicitly derive the precise asymptotic expressions of the standard and robust risks in Theorem 4.T that predict the benefits of regularization for generalization, difficult extract intuitive explanations for this phenomenon directly from the proof. We conjecture that non-zero
7

---

Consistent, À - 0 Consistent, Aop
Inconsistent, À Inconsistent, Aopt
Std.,
Robust,
Std.,
Robust,
Population risk
0.6
Robust risk
0.2
0.4
0.1
0.2
0.0
2
d/n
d/n
(a) Fixed é 0.1 for increasing
(b) Fixed n, and asymptotic predictions
Figure 4: Comparison of consistent and inconsistent (ee-perruraatioos for adversarial logistic regression with respect to the degree of overparamettrivation d/ n, using = 0.1 for both training and evaluation. Note that both estimators behave very similarly, implying that the effect of inconsistency is negligible for small e. (b) Robust and standard risks of the robust max-Ez-margin interpolator (A+00 0) and robust ridge estimate (A 1) with consistent perturbations (9) using e 0.05 function of the overparameterrizaton ratio d/n for simulations (markers) and asymptotic theoretical predictions from Theorem 4.1 (lines). We note that, for small values of 7, solving the optimization problem that gives the theoretical predictions becomes numerically unstable. All simulations use
n 103 samples from our data model; see Appendix B for further experimental details.
ridge penalty induces a more sparse 0x (i.e., with smaller 6//62-norm ratio) than the robust max- 22-margin solution 0g and use simulations to support our claim. Since the -a--avversrrialyy robust risk penalizes dense solutions with large ratio of the & f2-mmsss (see Lemma A.2 in Appendix AA.)) expect more sparse estimators have lower robust risk. Indeed, Figure shows that the f2/E2-norm ratio strongly correlates with the robust risk of the estimator.
We begin by noting that, due to Lagrangian duality, minimizing the addee-pnaaizzen loss O corre- sponds to minimizing the unregularized loss constrained the set of estimators with bounded f2-norm. This norm decreases the ridge coefficient À increases. In what follows, we provide intuition on the effect of the ridge penalty À on the sparsity of the estimator 02-
Large inducing a small 22-norm We first analyze the regularized estimator 0x for large À that constrains solutions to have small mn-nrmm We can therefore use Taylor's 's theorem and the closed- form expression of adversarial perturbations (see Lemma A.2 in Appendix approximate the unregularized robust loss from Equation (6) as follows:
log( + t t0 (0
1 11 Σ
(x +
(10)
As consequence, the minimizer 0x should result in a large robust average margin solution, that is, solution with large Σ" | (y (2, f) || fl Indeed, we observe this using simulations for finite d, n in Figures 5b and Sc In particular, the objective in Equation (10) leads to trade-ofi between the sparsity of the estimator (via its convex surrogate, the m-rmm) and average of the
sample-wise margins y (I,, f). We note that such estimators have been well studied in the literature
and are known to achieve good performance in recovering sparse ground truths [5] [7 39].
Small À inducing large 22-norm In contrast, a small ridge coefficient À leads to estimators 0n with large fo-nosms. In this case, the estimator approaches large robust (minimum) margin solution, i.e., a solution with large min; [o]a (z,, 8) E [[[[_ @ll1) which is maximized by the robust max-(2-margin interpolator (7). As consequence, this leads to a trade-off between estimator sparsity and the robust minimum margin min; Tolla M1 (x,, 0). Due the high dimensionality of the input data, the training samples x; are approximately orthogonal. Thus, to achieve non-vanishing robust margin, estimators are forced to trade-off sparsity with all sample-wise margins instead of just

---

Robust margin
fi-norm
Robust avg. margin (#*)
Regularized (A 5)
Rescaled robust risk
Robust margin
Interpolating (A
100% training accuracy
Robust margin (0*)
Robust margin
2
4
0.5
2
0
0
10
100
1k
10k
10
100
1k
10k
500 1000
1/A
1/1
Training sample index
(a) Sparsity of 0x
(b) Robust margin of 0,
(c) Robust margin decay of 0g
Figure 5: (a) The -noormm and the rescaled (by factor of 10) robust risk of the estimator with respect to 1/x. (b) The robust average margin contrasted to the robust margin as a function of 1/X. The horizontal lines denote the corresponding values for 0* (c) The ordered sample-wise robust margins z (2,, 0) <l [ f/]1 when interpolating and regularizing. For larger X, the robust (minimum) margin decreases while the robust average margin (horizontal lines) increases. We normalize the estimators, i.e. ||0 1, for all curves presented in the plots; see Appendix for further experimental details.
the average. We reveal this trade-off in Figures 5a and 5b where the increase in E f1/22-non formormm ratios corresponds to a decrease the robust average margin and an increase the robust margin.
Finally, we observe that the sparse ground truth is characterized by a large robust average margin (horizontal dotted line in Figure 5b) and small (minimum) robust margin (horizontal dashed line). Therefore, we expect that the solution that is sparser and which satisfies the same properties for the robust margin as the ground truth 8*, will achieve lower robust and standard risks. Indeed, our findings indicate that the regularized estimator fg for large À aligns better with 0*, compared to the solution obtained for small X, and hence justify the better performance of ridge-regularized predictors.
4.4 Benefits of an unorthodox way avoid the robust max-lz-margin interpolator
In the previous subsections we focused on robustly separable data and studied the generalization performance of regularized estimators that do not maximize the robust margin. Another way to avoid the robust max- max-&2-mare -arrgin solution to introduce enough label noise in the training data. We now show that, unexpectedly, this unorthodox way avoid the robust max-margin solution can also yield an estimator with better robust generalization than the robust max-l2-margin solution of the corresponding noiseless problem.
Specifically, in our experiments we introduce noise by flipping the labels of a fixed fraction of the training data. Figure 6 shows the robust and standard risks together with the training loss of the estimator 0, from Equation (6) trained with consistent perturbations for - 0 with varying fractions of flipped labels. For low noise levels, the data is robustly separable and the training loss vanishes convergence, yielding the robust max-f2-margin solution in Equation 77). For high enough noise levels, the constraints in Equation (7) become infeasible and the training loss of the resulting estimator starts increase. As discussed in Subsection 4.3 this estimator has a better implicit bias than the robust
interpolator and hence achieves lower robust risk.
Even though it is well known that introducing covariate noise induce implicit regularization [8) our observations show that in contrast to common intuition, the robust risk also decreases when introducing wrong labels in the training loss. In parallel to work, the paper 30] shows that training with corrupted labels can be beneficial for the standard risk.
However, we emphasize here that we do not advocate in favor of artificial label noise means to obtain more robust classifiers. particular, even if the data not robustly separable, the estimator with optimal ridge parameter Aog in Figure 6 still always outperforms the unregularized solution.

---

provide precise Robust risk (A - 0)
Robust (Aopt)
Train. + 0)
0.50
0.25
0.00
0%
1.5%
4%
10%
30%
50%
Label noise
Figure 6: Training loss and robust risks with respect to increasing training label noise for e 0.1, d = 8 x 10 and n = 10 We observe for unregularized estimators (A - 0) that, counterintuitieely, moderate amounts of label noise decrease the robust risk by avoiding the robust max-l2-margin solution. While this might spuriously imply that injecting label noise increases robustness, estimators with optimal ridge parameter Aopt still outperform their unregularized counterparts in terms of robust risk. Since the setting is noisy, we average the risks over five independent dataset draws and indicate standard deviations via error bars.
Finally, we remark that a similar effect can also observed when training with inconsistent perturba- tions with large perturbation norm We refer to Appendix D.I for further discussion.
5 Related work
Understanding robust overfitting The current literature attempting to explain robust overfit- ting [42] primarily focuses on the effect of noise and on the smoothness of decision boundaries learned by neural networks trained to convergence [16] 47 [53. A slightly different line of work [45] shows that overparameterized models require regularization order achieve good classification accuracy on all subpopulations. However, theoretical understanding of the role of regularization is still missing.
Theory for adversarial robustness of linear models Recent works (25] [4
description of the robust risks for logistic and linear regression when trained with adversarial attacks based the Convex Gaussian Minimax Theorem 200 [I]] The analysis focuses on inconsistent attacks for both training and evaluation. For linear regression, the authors observe that adversarial training with f2-perturbations mitigates the peak in the double descent curve around d = and hence acts similarly to ridge regularization as explicitly studied (23). Several other works focus on the role of gradient descent robust logistic regression. In particular, [56] proves that early stopping yields robust adversarially-traine
linear classifiers even in the presence noise. Furthermore, the results of [3I] show that gradient descent robustly separable data converges to the robust max-(2 -argin estimator
Conclusion and future work
In this work, show that overparameterized linear models overfit with respect to the robust risk even when there is no noise the training data. Our results challenge the modern narrative that interpolating overparameterized models yield good performance without explicit regularization and motivate the use of ridge regularization and early stopping for improved robust generalization. Perhaps surprisingly,
further observe that ridge regularization enhances the bias of logistic regression trained with adversarial lo -attacks towards sparser solutions, indicating that the impact of explicit regularization may go well beyond variance reduction.
Future work Our simulations indicate that early stopping yields similar benefits as ridge regu- larization in noiseless settings. However, we leave formal proof for future work. Furthermore, the double descent phenomenon has been proven for the standard risk on a broad variety of data distributions and even for non-linear models such as random feature regression. It still unclear how our results translate to these settings. In particular, our theoretical analysis heavily makes use of the closed-forn solution of the adversarial attacks, and hence, cannot be applied to non-linear models in straightforward way.
10

---

Acknowledgments
K. D. is supported by the ETH AI Center and the ETH Foundations of Data Science. R. H. is supported by the IAS at TUM, the DFG (German Research Foundation), and by the NSF under award I1S-1816986.
References
[1] A. Ali, J. Z. Kolter, and R. J. Tibshirani. A continuous-time view of early stopping for least squares regression. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89, pages 1370-1378, 2019.
[2] A. Ali, E. Dobriban, and R. Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In Proceedings of the International Conference Machine Learning (ICML), volume 119, pages 233-244, 2020.
[3] Z. Bai and J. W. Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
[4] Z. D. Bai and Y. Q. Yin. Limit of the smallest cigenvalue of a large dimensional sample covariance matrix. The Annals of Probability, 21:1275-1294, 1993.
[5] P. Bartlett, Y. Freund, W. S. Lee, and R. E. Schapire. Boosting the margin: A new explanation for the effectiveness voting methods. The Annals of Statistics, 26:1651 1686, 1998.
[6] P. L.. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. In Proceedings of the National Academy of Sciences, volume 117, pages 30063-30070, 2020.
[7] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learinng practice and the classical bias-variance trade-off. In Proceedings of the National Academy of Sciences, volume 116, pages 15849-15854 2019.
[8] C. Bishop. Training with noise is equivalent to Tikhonov regularization. Neural Computation, 7:108-116, 1995.
[9] P. Bühlmann and S. Van De Geer. Statistics for high-dinensional data: Methods, theory and applications. Springer Science & Business Media, 2011.
[10] Bühlmann et al. Invariance, causality and robustness. Statistical Science, 35:404 426, 2020.
[11] Y. Chen and P. Bühlmann. Domain adaptation under structural causal models. arXiv preprint arXiv:2010. 15764, 2020.
[12] L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterizee models using optimal transport. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
[13] L. Chizat and F. Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Proceedings of the Conference on Learning Theory (COLT), volume 125, pages 1305-1338, 2020.
[14] Z. Deng, A. Kammoun, and C. Thrampoulidis. model of double descent for high-dimensional binary linear classification. In Information and Inference: Journal of the IMA, volume 2021.
[15] E. Dobriban and Wager. High-dimensional asymttoiies of prediction: Ridge regression and classification. The Annals of Statistics, 46:247 - -279, 2018.
[16] C. Dong, L. Liu, and J. Shang. Data profiling for adversarial training: On the ruin of problematic data. arXiv preprint 102i::2002.074::
2021.
[17] W. Gao and Z.-H. Zhou On the doubt about margin explanation of boosting. Artificial Intelligence, 203:1-18. 2013.
[18] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49:1029 1054, 2021.
[19] Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In Proceedings of the International Conference on Learning Representations (ICLR), 2015,
[20] Y. Gordon. On Milman's inequality and random subspaces which escape through a mesh in R".
In Geometric aspects of functional analysis, pages 84-106. 1988.

---

[21] P. Grother, G. Quinn, and P. Phillips. Report on the evaluation of 2D still till-imaae face recognition algorithms, 2010.
[22] S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS),
volume 31, 2018.
[23] T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv: (oxXiv:/900..0 /903,08560, 2019.
[24] A. Javanmard and M. Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. arXiv preprint arXiv:20I0. 12213, 2020.
[25] A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoff's in adversarial training for linear regression. In Proceedings of the Conference on Learning Theory (COLT), volume 125, pages 2078, 2020.
[26] Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. In Proceed- ings of the International Conference on Learning Representations (ICLR), 2019.
[27] Z. Ji and M. Telgarsky. The implicit bias of gradient descent nonseparable data. In Proceedings of the Conference on Learning Theory (COLT), volume 99, pages 1772-1798, 2019.
[28] A. Knowles and J. Yin. Anisotropic local laws for random matrices. Probability Theory and Related Fields, 169:257-352, 2014.
[29] D. Kobak, J. Lomond, and B. Sanchez. The optimal ridge penalty for real-world high- dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21:1-16, 2020.
[30] Y. Lee and R. F. Barber. Binary classification with corrupted labels. arXiv preprint arXiv:2106.091
2021.
[31] Y. Li, E. X.Fang, H. Xu, and Zhao. Implicit bias of gradient descent based adversarial training on separable data. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
[32] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
[33] S. Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint
/908. 2019.
[34] V. Muthukumar, A. Narang, V. Subramanian, M. Belkin, D. Hsu, and A. Sahai. Classification
vs regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005.08054 2020.
[35] V. Muthukumar, K. Vodrahalli, V. Subramanian, and A. Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1:67-83, 2020.
[36] Nakkiran, G. Kaplun, Y. Bansal, Yang, B. Barak, and Sutskever. Deep double descent: Where bigger models and more data hurt. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
[37] Nakkiran, P. Venkat, S. M. Kakade, and T. Ma. Optimal regularization can mitigate double descent. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[38] Patil, Wei, A. Rinaldo, and R. Tibshirani. Uniform consistency of cross-validation estimators for high nigh-dimensional ridge regression. In Proceedings of the International Conference on Artificial Intelligence and Statisties (AISTATS), volume 130, pages 3178-3186. 2021.
[39] Y. Plan and R. Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. In JEEE Transactions on Information Theory, volume 59, 2012.
[40] J. Quionero-Camne Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset Shift in Machine Learning. The MIT Press, 2009.
[41] A. Raghunathan, S. M. Xie, F. Yang, J. Duchi, and P. Liang. Understanding and mitigating the tradeoff between robustness and accuracy. Proceedings of the International Conference on Machine Learning (ICML), volume 119, pages 11146-11156, 2020.
12

---

[42] L. Rice, E. Wong, and Z. Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the International Conference on Machine Learning (ICML), volume 119, pages 8093-8104, 2020.
[43] D. Richards, J. Mourtada, and L.. Rosasco. Asymptotics of ridge (less) regression under general source condition. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130, pages 3889-3897, 2021.
[44] S. Rosset, J. Zhu, and T. Hastie. Margin maximizing loss functions. In Advances in Neural Information Processing Systems (NeurIPS), volume 16, 2004.
[45] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
[46] F. Salehi, E. Abbasi, and B. Hassibi. The impact of regularization high-dimensional logistic regression. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, 2019.
[47] A. Sanyal, P. K. Dokania, V. Kanade, and P. Torr. How benign is benign overfitting? In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[48] A. Sinha, H. Namkoong, J. Duchi. Certifying some distributional robustness with principled adversarial training. In Proceedings of the International Conference on Learning Representa- tions (ICLR), 2018.
[49] D. Soudry. E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro, The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19:1-57, 2018.
[50] P. Sur and E. J. Candès. A modern maximum- likellhod theory for high-dimensional logistic regression. In Proceedings of the National Academy of Sciences, volume 1 116, pages 14516- 14525, 2019.
[51] C. Thrampoulidis, S. Oymak, and B. Hassibi. Regularized linear regression: A precise anal- ysis of the estimation error. In Proceedings of the Conference on Learning Theory (COLT), volume 40, pages 1683-1709, 2015.
[52] M. Wainwright. High- Digh-DDimesiooal Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[53] B. Wu, J. Chen, D. Cai, X. He, and Q. Gu. Do wider neural networks really help adversarial robustness? arXiv preprint arXiv:2010.0/279 2020.
[54] D. Wu and J. Xu. On the optimal weighted le regularization in overparameterized lincar regression. arXiv preprint vrXiv:2006.05800 2020.
[55] B. Zadrozny. Learning and evaluating classifiers under sample selection bias. In Proceedings of the International Conference on Machine Learning (ICML), 2004.
[56] D. Zou, S. Frei, and Q- Gu. Provable robustness of adversarial training for learning halfspaces with noise. In Proceedings of the International Conference on Machine Learning (ICML), volume 139, pages 13002-13011, 20211.
13


Reviews:
[{"review_id": "yyTFb7rFl4z", "reviewer": "Reviewer_kE4t", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides important insight into the effect of regularization vs interpolation for robust generalization. It is clearly written and well-organized. \n\nWhile 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. \n\nOn 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? \n\nFurthermore, to provide a faithful comparison to related work some experimental evidence on real world data might be beneficial. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations were addressed by the authors. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "qNXPWsoQmWm", "reviewer": "Reviewer_U2TN", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1. 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. \n2. 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?\n3. 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?\n4. [1] is an important reference that is missing. They also study the relation between regularization and double descent, but in the non-adversarial setting. \n5. In the description of figure 5 some typos: \"the minimum margin is decreases...\", \"this trendis also observed...\"\n6. Line 257, \"regularization improves regularization\".\n\n[1]: Optimal Regularization Can Mitigate Double Descent", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Skd7jRDSO3q", "reviewer": "Reviewer_g2yR", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n\nA few comments/questions:\n\n(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.  \n\n(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). \n\n(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. \n\n(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. \n\n(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. \n\n(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. \n\nMinor points/typos:\n* Figure 4 caption: \"plottet\"\n* Figure 5 caption: \"average margin (horizontal lines) decreases\" should be increases, no?\n* Figure 5 caption: \"trendis\"\n* lines 303-304 appears a sentence got repeated\n* lines 666-668 check writing, appears something went wrong\n* lines 829-831 put () around eqs\n* display (33) \"sucht\"\n\n\n[1'] Implicit Bias of Gradient Descent based Adversarial Training on Separable Data. Yan Li, Ethan X.Fang, Huan Xu, Tuo Zhao. ICLR 2021.\n\n[2'] Benign overfitting in ridge regression. A. Tsigler, P. L. Bartlett. 2020 preprint\n\n[3'] Provable Robustness of Adversarial Training for Learning Halfspaces with Noise. Difan Zou, Spencer Frei, Quanquan Gu.  ICML 2021.\n\n\n** post rebuttal **\n\nThanks 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they adequately addressed the limitations. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "L1pNPiQqIp", "reviewer": "Reviewer_yfXT", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies how regularization affects the adversarial robust risk for both linear and logistic regression problems.\n\nThe paper main contributions are:\n-\tThe authors illustrate empirically the benefits of ridge regression and early stopping w.r.t. robust generalization, both for linear and logistic regression.\n-\tThe authors state theoretical results which shed light on these empirical observations.\n\nMy 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.\n\nSome examples of issues that should be addressed:\n-\tTheorem 3.1 seems to be cut off in the middle of a sentence. The Theorem abruptly ends with the sentence “Finally,”. \n-\tLines 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.”\nThis seems to be just a duplication of the same sentence and is probably a typo.\n-\tThe observations and conclusions from each of the experiments should be clearly stated.\n-\tThe 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.\n\nItems such as these persist throughout the paper and make it difficult to assess the paper quality, correctness, and the significance of the results.\n\n---\n\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is hard to properly assess the limitations of the results due to the reasons listed above.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)