summaries: 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.  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.   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. 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. 
abstractText: 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 robust overfitting.
authors.name: Konstantin Donhauser
authors.name: Alexandru T
authors.name: ifrea
authors.name: Michael Aerni
authors.name: Reinhard Heckel
authors.name: Fanny Yang
references.authors: A. Ali J.Z. Kolter R.J. Tibshirani
references.title: A continuous-time view of early stopping for least squares regression
references.venue: In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: A. Ali E. Dobriban R. Tibshirani
references.title: The implicit regularization of stochastic gradient flow for least squares
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
references.authors: Z. Bai J.W. Silverstein
references.title: Spectral analysis of large dimensional random matrices, volume 20
references.authors: Z.D. Bai Y.Q. Yin
references.title: Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
references.venue: The Annals of Probability,
references.authors: P. Bartlett Y. Freund W.S. Lee R.E. Schapire
references.title: Boosting the margin: A new explanation for the effectiveness of voting methods
references.venue: The Annals of Statistics,
references.authors: P.L. Bartlett P.M. Long G. Lugosi A. Tsigler
references.title: Benign overfitting in linear regression
references.venue: In Proceedings of the National Academy of Sciences,
references.authors: M. Belkin D. Hsu S. Ma S. Mandal
references.title: Reconciling modern machine-learning practice and the classical bias–variance trade-off
references.venue: In Proceedings of the National Academy of Sciences,
references.authors: C. Bishop
references.title: Training with noise is equivalent to Tikhonov regularization
references.venue: Neural Computation,
references.authors: P. Bühlmann S. Van De Geer
references.title: Statistics for high-dimensional data: Methods, theory and applications
references.venue: Springer Science & Business Media,
references.authors: P. Bühlmann
references.title: Invariance, causality and robustness
references.venue: Statistical Science,
references.authors: Y. Chen P. Bühlmann
references.title: Domain adaptation under structural causal models
references.venue: arXiv preprint arXiv:2010.15764,
references.authors: L. Chizat F. Bach
references.title: On the global convergence of gradient descent for over-parameterized models using optimal transport
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: L. Chizat F. Bach
references.title: Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss
references.venue: In Proceedings of the Conference on Learning Theory (COLT),
references.authors: Z. Deng A. Kammoun C. Thrampoulidis
references.title: A model of double descent for high-dimensional binary linear classification
references.venue: In Information and Inference: A Journal of the IMA,
references.authors: E. Dobriban S. Wager
references.title: High-dimensional asymptotics of prediction: Ridge regression and classification
references.venue: The Annals of Statistics,
references.authors: C. Dong L. Liu J. Shang
references.title: Data profiling for adversarial training: On the ruin of problematic data
references.venue: arXiv preprint arXiv:2102.07437,
references.authors: W. Gao Z.-H. Zhou
references.title: On the doubt about margin explanation of boosting
references.venue: Artificial Intelligence,
references.authors: B. Ghorbani S. Mei T. Misiakiewicz A. Montanari
references.title: Linearized two-layers neural networks in high dimension
references.venue: The Annals of Statistics,
references.authors: I. Goodfellow J. Shlens C. Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: Y. Gordon
references.title: On Milman’s inequality and random subspaces which escape through a mesh in R
references.venue: In Geometric aspects of functional analysis,
references.authors: P. Grother G. Quinn P. Phillips
references.title: Report on the evaluation of 2D still-image face recognition
references.authors: S. Gunasekar J.D. Lee D. Soudry N. Srebro
references.title: Implicit bias of gradient descent on linear convolutional networks
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: T. Hastie A. Montanari S. Rosset R.J. Tibshirani
references.title: Surprises in high-dimensional ridgeless least squares interpolation
references.venue: arXiv preprint arXiv:1903.08560,
references.authors: A. Javanmard M. Soltanolkotabi
references.title: Precise statistical analysis of classification accuracies for adversarial training
references.venue: arXiv preprint arXiv:2010.11213,
references.authors: A. Javanmard M. Soltanolkotabi H. Hassani
references.title: Precise tradeoffs in adversarial training for linear regression
references.venue: In Proceedings of the Conference on Learning Theory (COLT),
references.authors: Z. Ji M. Telgarsky
references.title: Gradient descent aligns the layers of deep linear networks
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: Z. Ji M. Telgarsky
references.title: The implicit bias of gradient descent on nonseparable data
references.venue: In Proceedings of the Conference on Learning Theory (COLT),
references.authors: A. Knowles J. Yin
references.title: Anisotropic local laws for random matrices
references.venue: Probability Theory and Related Fields,
references.authors: D. Kobak J. Lomond B. Sanchez
references.title: The optimal ridge penalty for real-world highdimensional data can be zero or negative due to the implicit ridge regularization
references.venue: Journal of Machine Learning Research,
references.authors: Y. Lee R.F. Barber
references.title: Binary classification with corrupted labels
references.venue: arXiv preprint arXiv:2106.09136,
references.authors: Y. Li E.X.Fang H. Xu T. Zhao
references.title: Implicit bias of gradient descent based adversarial training on separable data
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: K. Lyu J. Li
references.title: Gradient descent maximizes the margin of homogeneous neural networks
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: S. Mei A. Montanari
references.title: The generalization error of random features regression: Precise asymptotics and double descent curve
references.authors: V. Muthukumar A. Narang V. Subramanian M. Belkin D. Hsu A. Sahai
references.title: Classification vs regression in overparameterized regimes: Does the loss function matter
references.authors: V. Muthukumar K. Vodrahalli V. Subramanian A. Sahai
references.title: Harmless interpolation of noisy data in regression
references.venue: IEEE Journal on Selected Areas in Information Theory,
references.authors: P. Nakkiran G. Kaplun Y. Bansal T. Yang B. Barak I. Sutskever
references.title: Deep double descent: Where bigger models and more data hurt
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: P. Nakkiran P. Venkat S.M. Kakade T. Ma
references.title: Optimal regularization can mitigate double descent
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: P. Patil Y. Wei A. Rinaldo R. Tibshirani
references.title: Uniform consistency of cross-validation estimators for high-dimensional ridge regression
references.venue: In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: Y. Plan R. Vershynin
references.title: Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach
references.venue: In IEEE Transactions on Information Theory,
references.authors: J. Quionero-Candela M. Sugiyama A. Schwaighofer N.D. Lawrence
references.title: Dataset Shift in Machine Learning
references.authors: A. Raghunathan S.M. Xie F. Yang J. Duchi P. Liang
references.title: Understanding and mitigating the tradeoff between robustness and accuracy
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
references.authors: L. Rice E. Wong Z. Kolter
references.title: Overfitting in adversarially robust deep learning
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
references.authors: D. Richards J. Mourtada L. Rosasco
references.title: Asymptotics of ridge (less) regression under general source condition
references.venue: In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: S. Rosset J. Zhu T. Hastie
references.title: Margin maximizing loss functions
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: S. Sagawa P.W. Koh T.B. Hashimoto P. Liang
references.title: Distributionally robust neural networks
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: F. Salehi E. Abbasi B. Hassibi
references.title: The impact of regularization on high-dimensional logistic regression
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: A. Sanyal P.K. Dokania V. Kanade P. Torr
references.title: How benign is benign overfitting
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: A. Sinha H. Namkoong J. Duchi
references.title: Certifying some distributional robustness with principled adversarial training
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: D. Soudry E. Hoffer M.S. Nacson S. Gunasekar N. Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: Journal of Machine Learning Research,
references.authors: P. Sur E.J. Candès
references.title: A modern maximum-likelihood theory for high-dimensional logistic regression
references.venue: In Proceedings of the National Academy of Sciences,
references.authors: C. Thrampoulidis S. Oymak B. Hassibi
references.title: Regularized linear regression: A precise analysis of the estimation error
references.venue: In Proceedings of the Conference on Learning Theory (COLT),
references.authors: M. Wainwright
references.title: High-Dimensional Statistics: A Non-Asymptotic Viewpoint
references.authors: B. Wu J. Chen D. Cai X. He Q. Gu
references.title: Do wider neural networks really help adversarial robustness
references.venue: arXiv preprint arXiv:2010.01279,
references.authors: D. Wu J. Xu
references.title: On the optimal weighted `2 regularization in overparameterized linear regression
references.venue: arXiv preprint arXiv:2006.05800,
references.authors: B. Zadrozny
references.title: Learning and evaluating classifiers under sample selection bias
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
references.authors: D. Zou S. Frei Q. Gu
references.title: Provable robustness of adversarial training for learning halfspaces with noise
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
sections.heading: 1 Introduction
sections.text: Conventional statistical wisdom cautions the user who trains a model by minimizing a loss L(θ): if a global minimizer achieves zero or near-zero training loss (i.e., it interpolates), we run the risk of overfitting (i.e., high variance) and thus suboptimal prediction performance. Instead, regularization is commonly used to reduce the effect of noise and to obtain an estimator with better generalization. Specifically, regularization limits model complexity and induces worse data fit, for example via an explicit penalty term R(θ). The resulting penalized loss L(θ) + λR(θ) 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(θ) vanishes and label noise is present [36]. Since interpolators are not unique in the overparameterized regime, it is crucial to study the specific implicit biases of interpolating estimators. In particular, for common losses, a large body of recent work analyzes the properties of the solutions found via gradient descent at convergence (see e.g. [44, 12, 13, 22, 26, 27, 49, 31]). For example, for linear and logistic regression, it is well-known that gradient descent converges to the min-`2-norm and max-`2-margin solutions, respectively [22, 27, 32, 49]. These interpolating estimators also minimize the respective penalized loss L(θ) + λ‖θ‖22 in the limit of λ→ 0 [44]. A plethora of recent papers explicitly study generalization properties on min-`2-norm interpolators [15, 18, 23, 6, 33, 34, 35] and max-`2-margin solutions [14, 34, 46], and show that the variance decreases as the overparameterization ratio increases beyond the interpolation threshold. While regularization with λ > 0 is commonly known to reduce the risk at the interpolation threshold [23, 37], many of these works are motivated by the second descent of the double descent phenomenon [7] which suggests that regularization becomes redundant with sufficient overparameterization. Hence, previous papers focus on highly overparameterized settings where the optimal regularization parameter satisfies λopt ≤ 0 [29, 54, 43], implying that for large d/n, explicit regularization with λ > 0 is redundant or even detrimental for generalization.
  ∗Equal contribution.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Taking a step back, this narrative originated from theoretical and experimental findings that consider the standard test risk with identically distributed training and test data. However, this measure cannot reflect the robust risk of models when the test data has a shifted distribution, is attacked by adversaries, or 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 in Figure 1a and, in fact, even for linear models trained on highdimensional synthetic noiseless data. In particular, Figures 1b,1c show that min-`2-norm and robust max-`2-margin interpolators (minimizers of the training loss for λ → 0), achieve a 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-`2-norm and robust max-`2-margin interpolators exhibit large risks as λ → 0, the induced bias for a small `2-norm is potentially suboptimal and a larger penalty weight λ > 0 should only degrade performance. In this paper, we provide possible explanations that debunk this intuition in the high-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 early stopping and other factors that lead to a non-interpolating estimator achieve a similar effect. Our results provide the first rigorous explanation of robust overfitting even in the absence of noise.
  In Section 2, we formally define the setting that we use throughout our analysis. We then first present precise asymptotic expressions for the robust risk for linear regression in Section 3 that explicitly explain robust overfitting. Furthermore, in Section 4, we consider classification with logistic regression and derive asymptotic results.
sections.heading: 2 Risk minimization framework
sections.text: 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 as evaluation metrics.
sections.heading: 2.1 Problem setting
sections.text: This paper considers the supervised learning problem of estimating a mapping from d-dimensional real-valued features x ∈ Rd to a target y ∈ Y ⊆ R given a training set of labeled samples D = {(xi, yi)}ni=1. We assume that the feature vectors xi are drawn i.i.d. from the marginal distribution P that we assume to be an isotropic Gaussian. We further focus on noiseless observations yi = 〈θ?, xi〉 for regression tasks and yi = sgn(〈θ?, xi〉) for classification tasks, respectively. However, the main results are more general and apply to noisy observations as well. For regression, we assume additive Gaussian noise with zero mean and σ2 variance, while for classification we flip a certain percentage of the training labels.
  This paper studies the high-dimensional asymptotic regime where d/n→ γ as both the dimensionality d and the number of samples n tend to infinity. This high-dimensional setting is widely studied as it can often – as in our experiments – yield precise predictions for the risk of the estimator when both the input dimension and the data set size are large [9, 52]. It is also the predominant setting considered in previous theoretical works that discuss overparameterized linear models [2, 14, 15, 23, 25, 24, 50].
sections.heading: 2.2 Standard and robust risk
sections.text: We now introduce the standard and robust evaluation metrics for regression and classification. Given a pointwise test loss `test : R× R→ R, we define the standard (population) risk of an estimator θ̂ as
  R(θ̂) := EX∼P`test ( 〈θ̂, X〉, 〈θ?, X〉 ) , (1)
  where the expectation is taken over the marginal feature distribution P. Note that for any datadependent estimator θ̂, 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 `test(u, v) = (u − v)2 for regression and the 0-1 loss `test(u, v) = 1sgn(u) 6=sgn(v) 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 do not change the ground truth label (e.g., imperceptible `p-perturbations [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 `p-adversarial attacks widely studied in the image domain, we consider the adversarially robust risk of a parameter θ with respect to consistent `pperturbations
  R (θ̂) := EX∼P max δ∈Up( ) `test(〈θ̂, X + δ〉, 〈θ?, X〉) , (2)
  with the perturbation set Up( ) := {δ ∈ Rd : ‖δ‖p ≤ and 〈θ?, δ〉 = 0}. 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 θ. Similarly, in our setting, adversarial robustness against consistent `p-perturbations implies distributional robustness against `p-bounded mean shifts in the covariate distribution P (see Appendix A.3).
  3 Min-`2-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 `2-perturbations U2( ). More precisely, we show that preventing min-`2-norm interpolation on noiseless samples via ridge regularization improves the robust risk. We refer the reader to Appendix C.1 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 θ? alike.
sections.heading: 3.1 Interpolating and regularized estimator
sections.text: We study linear ridge regression estimates defined as
  θ̂λ = arg min θ
  1
  n n∑ i=0 (yi − 〈θ, xi〉)2 + λ‖θ‖22. (3)
  The min-`2-norm interpolator is the limit of the linear ridge regression estimate with λ→ 0 and is given by
  θ̂0 = arg min θ ‖θ‖2 such that 〈θ, xi〉 = yi for all i. (4)
  Note that the min-`2-norm interpolator is also the estimator that gradient descent on the unregularized loss converges to, while ridge regression with λ > 0 corresponds to early-stopped estimators [1, 2]. Therefore, by proving that a ridge regularized estimator with λ > 0 significantly outperforms the min-`2-norm interpolator with λ→ 0, we also show that early stopping benefits robust generalization. Whenever the goal is to achieve a low robust risk, a popular alternative to using the standard linear regression estimate in Equations (3),(4) is to consider adversarially trained estimators [19, 25]. However, `2-adversarial training in its usual form (i.e., with inconsistent perturbations) prevents regression estimators from interpolating, and hence, has a similar effect to `2-regularization as we 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 in 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.
sections.heading: 3.2 Robust overfitting in noiseless linear regression
sections.text: The following theorem provides a precise asymptotic expression of the robust risk under consistent `2-perturbations for the ridge regression estimate in 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 ‖θ?‖2 = 1. Theorem 3.1. Assuming the marginal input distribution P = N (0, Id), the robust risk (2) of the estimator θ̂λ for λ > 0 (defined in (3)) with respect to consistent `2-perturbations U2( ) asymptotically converges to
  R (θ̂λ) a.s.−→ Rλ + 2Pλ +
  √ 8 2
  π PλRλ =: R ,λ (5)
  as d, n → ∞ with d/n → γ, where Pλ = Rλ − λ2(m(−λ))2 and Rλ = λ2m′(−λ) + σ2γ(m(−λ)− λm′(−λ)) is the asymptotic standard risk, i.e., R(θ̂λ) a.s.−→ Rλ. The function m(z) is the Stieltjes transform of the Marchenko-Pastur law and is given by
  m(z) = 1−γ−z− √ (1−γ−z)2−4γz 2γz . Further, the limit limλ→0R ,λ exists for all ≥ 0 and corresponds to the asymptotic standard ( = 0) and robust risks ( > 0) of the min-`2-norm interpolator θ̂0 (4).
  We plot the precise asymptotic risks of the ridge estimate with optimal regularization parameter λopt2 and of the min-`2-norm interpolator for λ→ 0 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 our statement that regularization not only helps to 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 n (depicted by the markers in Figure 2) closely match the predictions obtained from Theorem 3.1 for d, n→∞ and d/n→ γ. This
  2Here 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]).
  indicates that the high-dimensional asymptotic regime does indeed correctly predict and characterize the high-dimensional non-asymptotic regime. Finally, even though Theorem 3.1 assumes isotropic Gaussian covariates, we can extend it to more general covariance matrices following the same argument as in [23], based on results from random matrix theory [28].
  4 Max-`2-margin interpolation in robust linear classification
  Unlike linear regression, adversarially trained binary logistic regression classifiers may still interpolate the training data, resulting in robust max-`2-margin interpolators as λ → 0. Hence, in this section we train and evaluate classifiers with `∞-perturbation sets U∞( ), a standard choice in the experimental and theoretical classification literature [19, 24, 42, 47], but also discuss `2-perturbations in Appendix D.3 for completeness. Our theoretical results show that the robust max-`2-margin interpolator with λ→ 0 has a worse robust risk than a regularized predictor with λ > 0.
sections.heading: 4.1 Interpolating and regularized estimator
sections.text: 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. In contrast, for linear classification, interpolation is easier to achieve – it only requires the sign of 〈xi, θ〉 to be the same as the label yi for all i. 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-regularized logistic regression estimator with penalty weight λ > 0,
  θ̂λ := arg min θ
  1
  n n∑ i=1 max δ∈U∞( ) log(1 + e−〈θ,xi+δ〉yi) + λ‖θ‖22. (6)
  In the limit λ → 0 the results in [44] imply that the robust ridge-regularized logistic regression estimator from Equation (6) directionally aligns with the robust max-`2-margin interpolator:3
  θ̂0 := arg min θ ‖θ‖2 such that min δ∈U∞( ) yi〈θ, xi + δ〉 ≥ 1 for all i. (7)
  3While [44] only proves the result for = 0, it is straightforward to extend it to the general case where ≥ 0.
  Standard risk Robust risk Normalized robust margin
  We say that the data is robustly separable if the robust max-`2-margin interpolator exists.
  The robust max-`2-margin solution is an 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, we simply refer to the robust max-`2-margin solution as the normalized vector θ̂0‖θ̂0‖2 .
  In this paper, we study two choices for the set of training perturbations U∞( ):
  inconsistent perturbations U∞( ) = {δ ∈ Rd : ‖δ‖∞ ≤ } (8) consistent perturbations U∞( ) = {δ ∈ Rd : ‖δ‖∞ ≤ , 〈δ, θ?〉 = 0} (9)
  Adversarial training with respect to inconsistent perturbations (8) is a popular choice in the literature to 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 we introduce in Section 4.2, 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, in 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.
sections.heading: 4.2 Robust overfitting in noiseless linear classification
sections.text: 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.e., yi = sgn〈xi, θ?〉. Furthermore, as we discuss in Section 4.3, the inductive bias of the `∞-robust logistic loss encourages sparse solutions. Since we are primarily interested in learning ground truth functions that match the implicit bias of the estimator, we assume the sparse ground truth θ? = (1, 0, . . . , 0)T .
  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 our observations in the high-dimensional asymptotic limit.
  Training with inconsistent adversarial perturbations Figure 3a illustrates the robust margin mini minδ∈U∞( ) 1 ‖θ‖2 yi〈θ, xi + δ〉 as well as the standard and robust risks of the estimator θ̂λ trained using inconsistent adversarial perturbations on a synthetic data set 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 λ, we notice that the same trends as 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-`2-margin solution that is obtained for t → ∞ 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 can 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),(7) with consistent and inconsistent perturbations yield comparable robust risks. Moreover, 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, we would expect ridge regularization to 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 in the high-dimensional asymptotic regime where d/n→ γ as d, n→∞. 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 = 0/ √ d for some constant 0 and θ? = (1, 0, · · · , 0)T .
  Then, the robust and standard risks of the regularized estimator θ̂λ (6) (λ > 0) and of the robust max-`2-margin interpolator (7) (λ → 0) with inconsistent (8) or consistent (9) adversarial `∞- perturbations converge in probability as d, n→∞, d/n→ γ to:
  R(θ̂λ)→ 1
  π arccos ( ν?‖ ν? ) and R (θ̂λ)→ R(θ̂λ) + 1 2 erf ( 0δ ? √ 2ν? ) + I ( 0δ ? ν? , ν?‖ ν? ) We denote by erf(.) the error function,
  I(t, u) := ∫ t 0 1√ 2π exp ( −x 2 2 ) erf ( xu√ 2(1− u2) ) dx,
  and use the notation ν? = √
  (ν?⊥) 2 + (ν?‖) 2, where ν?⊥, ν ? ‖ , δ ? are the unique solution of a scalar
  optimization problem specified in Appendix F that depends on θ?, γ, 0 and λ.
  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 4b by solving the scalar optimization problem specified in Appendix F. We observe that Theorem 4.1 indeed predicts the benefits of regularization for robust logistic regression and that simulations using finite values of d and n follow the asymptotic trend. We describe the full empirical setup in Appendix B.
sections.heading: 4.3 Intuitive explanation and discussion
sections.text: Even though we explicitly derive the precise asymptotic expressions of the standard and robust risks in Theorem 4.1 that predict the benefits of regularization for generalization, it is difficult to extract intuitive explanations for this phenomenon directly from the proof. We conjecture that a non-zero
  ridge penalty induces a more sparse θ̂λ (i.e., with a smaller `1/`2-norm ratio) than the robust max`2-margin solution θ̂0 and use simulations to support our claim. Since the `∞-adversarially robust risk penalizes dense solutions with large ratio of the `1/`2-norms (see Lemma A.2 in Appendix A.2), we expect more sparse estimators to have a lower robust risk. Indeed, Figure 5a shows that the `1/`2-norm ratio strongly correlates with the robust risk of the estimator.
  We begin by noting that, due to Lagrangian duality, minimizing the ridge-penalized loss (6) corresponds to minimizing the unregularized loss constrained to the set of estimators θ with a bounded `2-norm. This norm decreases as the ridge coefficient λ increases. In what follows, we provide intuition on the effect of the ridge penalty λ on the sparsity of the estimator θ̂λ.
  Large λ inducing a small `2-norm We first analyze the regularized estimator θ̂λ for large λ that constrains solutions to have small `2-norm. We can therefore use Taylor’s theorem and the closedform expression of adversarial perturbations (see Lemma A.2 in Appendix A.2) to approximate the unregularized robust loss from Equation (6) as follows:
  1
  n n∑ i=1 log(1 + e−yi〈θ,xi〉+ ‖Π⊥θ‖1) ≈ 1 n n∑ i=1 −yi〈xi, θ〉+ ‖Π⊥θ‖1. (10)
  As a consequence, the minimizer θ̂λ should result in a large robust average margin solution, that is, a solution with large 1n ∑n i=1 1 ‖θ‖2 (yi〈xi, θ〉 − ‖Π⊥θ‖1). Indeed, we observe this using simulations for finite d, n in Figures 5b and 5c. In particular, the objective in Equation (10) leads to a trade-off between the sparsity of the estimator (via its convex surrogate, the `1-norm) and an average of the sample-wise margins yi〈xi, θ〉. 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, 17, 39].
  Small λ inducing a large `2-norm In contrast, a small ridge coefficient λ leads to estimators θ̂λ with large `2-norms. In this case, the estimator approaches a large robust (minimum) margin solution, i.e., a solution with large mini 1‖θ‖2 (yi〈xi, θ〉 − ‖Π⊥θ‖1) which is maximized by the robust max-`2-margin interpolator (7). As a consequence, this leads to a trade-off between estimator sparsity and the robust minimum margin mini 1‖θ‖2 yi〈xi, θ〉. Due to the high dimensionality of the input data, the training samples xi are approximately orthogonal. Thus, to achieve a non-vanishing robust margin, estimators are forced to trade-off sparsity with all sample-wise margins instead of just
  the average. We reveal this trade-off in Figures 5a and 5b where the increase in `1/`2-norm ratios corresponds to a decrease in the robust average margin and an increase in 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 a 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 θ?, will achieve lower robust and standard risks. Indeed, our findings indicate that the regularized estimator θ̂λ for large λ aligns better with θ?, compared to the solution obtained for a small λ, and hence justify the better performance of ridge-regularized predictors.
  4.4 Benefits of an unorthodox way to avoid the robust max-`2-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-`2-margin solution is to introduce enough label noise in the training data. We now show that, unexpectedly, this unorthodox way to avoid the robust max-margin solution can also yield an estimator with better robust generalization than the robust max-`2-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 θ̂λ 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 at convergence, yielding the robust max-`2-margin solution in Equation (7). For high enough noise levels, the constraints in Equation (7) become infeasible and the training loss of the resulting estimator starts to increase. As discussed in Subsection 4.3, this estimator has a better implicit bias than the robust max-`2-margin interpolator and hence achieves a lower robust risk.
  Even though it is well known that introducing covariate noise can 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 our 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 as a means to obtain more robust classifiers. In particular, even if the data is not robustly separable, the estimator with optimal ridge parameter λopt in Figure 6 still always outperforms the unregularized solution.
  Finally, we remark that a similar effect can also be observed when training with inconsistent perturbations with large perturbation norm . We refer to Appendix D.1 for further discussion.
sections.heading: 5 Related work
sections.text: Understanding robust overfitting The current literature attempting to explain robust overfitting [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 in order to achieve good classification accuracy on all subpopulations. However, a theoretical understanding of the role of regularization is still missing.
  Theory for adversarial robustness of linear models Recent works [25, 24] provide a precise description of the robust risks for logistic and linear regression when trained with adversarial attacks based on the Convex Gaussian Minimax Theorem [20, 51]. The analysis focuses on inconsistent attacks for both training and evaluation. For linear regression, the authors observe that adversarial training with `2-perturbations mitigates the peak in the double descent curve around d = n and hence acts similarly to ridge regularization as explicitly studied in [23]. Several other works focus on the role of gradient descent in robust logistic regression. In particular, [56] proves that early stopping yields robust adversarially-trained linear classifiers even in the presence of noise. Furthermore, the results of [31] show that gradient descent on robustly separable data converges to the robust max-`2-margin estimator (7).
sections.heading: 6 Conclusion and future work
sections.text: In this work, we show that overparameterized linear models can overfit with respect to the robust risk even when there is no noise in 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, we further observe that ridge regularization enhances the bias of logistic regression trained with adversarial `∞-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 regularization in noiseless settings. However, we leave a 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 is still unclear how our results translate to these settings. In particular, our theoretical analysis heavily makes use of the closed-form solution of the adversarial attacks, and hence, cannot be applied to non-linear models in a straightforward way.
sections.heading: Acknowledgments
sections.text: 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 IIS-1816986.
title: Interpolation can hurt robust generalization even when there is no noise