Regularization properties of adversarially-trained linear regression
Authors: Antonio H. Ribeiro
Dave Zachariah
Francis Bach
Thomas B. Schön
Venue: NeurIPS 2023 spotlight (2023)
Keywords: adversarial training; regularization; linear models
TL;DR: We study the solution of adversarial training in linear regression, presenting connections with Lasso, square-root Lasso, ridge regression, and minimum-norm interpolators.

Abstract: State-of-the-art machine learning models can be vulnerable to very small input perturbations that are adversarially constructed. Adversarial training is an effective approach to defend against it. Formulated as a min-max problem, it searches for the best solution when the training data were corrupted by the worst-case attacks. Linear models are among the simple models where vulnerabilities can be observed and are the focus of our study. In this case, adversarial training leads to a convex optimization problem which can be formulated as the minimization of a finite sum. We provide a comparative analysis between the solution of adversarial training in linear regression and other regularization methods. Our main findings are that: (A) Adversarial training yields the  minimum-norm  interpolating solution in the overparameterized regime (more parameters than data), as long as the maximum disturbance radius is smaller than a threshold. And, conversely, the minimum-norm interpolator is the solution to adversarial training with a given radius. (B) Adversarial training can be equivalent to parameter shrinking methods (ridge regression and Lasso). This happens in the underparametrized region, for an appropriate choice of adversarial radius and zero-mean symmetrically distributed covariates. (C) For $\ell_\infty$-adversarial training---as in square-root Lasso---the choice of adversarial radius for optimal bounds does not depend on the additive noise variance. We confirm our theoretical findings with numerical examples.

Regularization properties of ad adversarially-trained linear regression
Antônio H. Ribeiro Uppsala University
Dave Zachariah
Uppsala University
antonio horta. uu.. se
dave. d zachariahhit..c..m su
Francis Bach
Thomas B. Schön
PSL Research University, INRIA francis, bach@inria.frr
Uppsala University
thomas schon@it uu.
Abstract
State-of-the-art machine learning models can be vulnerable to very small input perturbations that adversarially constructed. Adversarial training is effective approach to defend against it. Formulated as a min-max problem, searches for the best solution when the training data were corrupted by the worst-case attacks. Linear models are among the simple models where vulnerabilities can be observed and the focus of our study. In this case, adversarial training leads a convex optimization problem which can be formulated as the minimization of finite sum. We provide a comparative analysis between the solution of adversarial training in linear regression and other regularization methods. Our main findings are that: (A) Adversarial training yields the minimum-
interpolating solution the overparameterizee regime (more parameters than data), long the maximum disturbance radius smaller than threshold. And, conversely, the minimum- norm interpolator is the solution to adversarial training with given radius. (B) Adversarial training can be equivalent to parameter shrinking methods (ridge regression and Lasso). This happens in the underparametrized region, for an appropriate choice of adversarial radius and zero-mean symmetrically distributed covariates. (C) For adversaaall training as in square-root Lasso the choice adversarial radius for optimal bounds does not depend on the additive noise variance. We confirm theoretical findings with numerical examples.
Introduction
Adversarial attacks generated striking examples of the brittleness of modern machine learning. The framework considers inputs contaminated with disturbances deliberately chosen to maximize the model eиror and, even for small disturbances, cause a substantial performance drop in otherwise state-of-the-an models [1] [6]] Adversarial training [7] is one of the most effective approaches for deep learning models defend against adversarial attacks [7]-[9]. It considers training models samples that have been modified by an adversary, with the goal of obtaining a model that will be more robust when faced with new adversarially perturbed samples. The training procedure is formulated as a min-max problem, searching for the best solution to the worst-case attacks.
Despite its success in producing state-of-the-ard results in adversarial defense benchmarks [10], there are still major challenges in using adversarial training. The min-max problem a hard optimization problem to solve and it is still an open question how solve it efficiently. Moreover, these methods still produce large errors in new adversarially disturbed test points, often much larger than the adversarial error obtained during training.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

40-
40
coefficients
20
20
0-
0-
20
20-
-40
-40
10
5
15
11
||
(a) Lasso regression
(b) Loo adversarial training
Figure 1: Regularization paths estimated in the Diabetes dataset [18]. Regularization paths are plots showing the coefficient estimates for varying regularization parameter or, in adversarial training, perturbation radius ò. This type plot commonly used in analysing Lasso and variants, i.e. [18], [19]. On the horizontal axis, we give the l -norrm of the estimated parameter. On the vertical axis, the coefficients obtained for each method. The dataset has = 10 baseline variables (age, sex, body mass index, average blood pressure, and six blood serum measurements), which were obtained for n = 442 diabetes patients. The model output is a quantitative measure of the disease progression. See Appendix B.5 for the relationship between ||]| and and A.
To get insight into adversarial training and try tackle these challenges, a growing body of work [11]- [15] studies fundamental properties of adversarial attacks and adversarial training in linear models. Linear models allow for analytical analysis while still reproducing phenomena observed in state-of- the-art models. Consider a training dataset {( yi y;));= consisting of n data points of dimension RP x R, adversarial training in linear regression corresponds to minimizing (in (3 E RP)
a (3: -1
Σ
max 1t - (x, + Ax.) A 3 A
(I)
Restricting the analysis linear models allows for simplified analysis: the problem is convex and the next proposition allows us express Rady in terms of the dual norm, || suP||=|is1 13 |/Txl. z/|
Proposition (Dual formulation). Let || ||+ be the dual norm of || then
neady (3:8,
(lys x. T 3 - -)
m
This simple reformulation removes one of the major challenges:
it removes the inner optimization problem and yields a model that is more amenable analysis. Similar reformulations can be obtained for classification. This simplification made the analysis of adversarial attacks in linear models fruitful to get insights into the properties of adversarial training and examples. From giving counterexample to the idea that deep neural networks' vulnerabilities to adversarial attacks were caused by their nonlinearity [2], [5], [16], to help explaining how implicitly regularized overparametrized models can be robust, see [17].
In this paper, we further explore this reformulation and provide thorough characterization of adversarial training in linear regression problems. We this comparative fashion, establishing when the solution of adversarially regularization methods. For instance, a simple inspection of (2) hints at the similarities with other parameter shrinking methods. This similarity is confirmed in Figure I, which illustrates how the solutions of adverraraa training can be almost indistinguishable from Lasso. We explain the similarities and differences with other methods. Our contributions are:
linear models coincides with the solution of traditional
A. In the overparametrized region, we prove that the minimum- interpolator is the solution to adversarial training for 5 smaller than a certain threshold (Section 4).
We establish conditions under which the solution coincides with Lasso and ridge regression, respectively (Section 5).
We show that adversarial training can be framed in the robust regression framework, and use it to establish connections with the square-root Lasso. We show that adversarial training (like the square-root Lasso) can obtain bounds on the prediction error that do not require the noise variance to be known (Section 6).
D. We prove a more general version of Proposition I, valid for general lower-semicontimuous and convex loss functions (Section 8).
'Code for reproducing the figures is available in: https: htte::://gttt.uet/ http://ghhhuu...ooooooooot/t/a// linreg

---

2
Related work
Generalization minimum-norm interpolators. The study of minimum-nome interpolators played a key role in explaining why overparametrized models generalize- an important open question for which traditional theory failed to explain empirical results [20]- and for which significant progress has been made over the past few years [21]. These estimates provide simple scenario where can interpolate noisy data and still generalize well. Minimum-nome interpolators have indeed been quite fruitful setting to study the phenomenon of benign overfitting, i.e., when the model interpolates the training data but still generalizes well to new samples. In [22] the authors use these estimates to prove consistency, development that later had several extensions [23]. From another angle, in a series of insightful papers, Belkin et al. [24], [25] explore the phenomena of double-descent where double-descent curve subsumes the textbook U-shaped bias-variance trade-off curve, with second decrease in the error occurring beyond the point where the model has reached the capacity of interpolating the training data. Interestingly, minimum-norm interpolators are also basic scenarios for observing this phenomena [24]-[26]. Our research connects the research on robustness to adversarial attacks the study of generalization of minimum minimuum-norm norm interpolators.
Adversarial training in linear models. The generalization of adversarial attacks in linear models is well-studied. Tsipras al. [16] and Ilyas et al. [5] use linear models explain the conflict between robustness and nigh-performance models observed in neural networks; Ribeiro et al. [17] use these models to show how overparameterizztion affects robustness to perturbations; Taheri et al. [11] derive asymptotics for adversarial training in binary classification. Dan el al. [27] and Dobriban et al. [28] study adversarial robustness in Gaussian classification problems. Javanmard al. [12] provide asymptotics for adversarial training in linear regression, Javanmard el al. [29] in classification settings and Hassani et al. [13] for random feature regressions. Min et al. [14] investigate how the dataset size affects adversarial performance. Yin et al. [15] provide an analysis of -ataack on linear classifiers based on Rademacher complexity. These works, however, focus on the generalization properties. We provide a fresh perspective on the problem by clarifying the connection of adversarial training to other regularization methods.
Robust regression and square-root Lasso. The properties of Lasso [30] for recovering sparse parameters in noisy settings have been extensively studied, and bounds on the parameter estimation error are well-known [31]. However, these results rely on choices of regularization parameters that depend on the variance of additive noise. Square-root Lasso [32] was proposed circumvent this difficulty. We show that for aaversaaa,,,,,, similarly to the square-root Lasso, bounds can be obtained with the adversarial radius set without knowledge about the variance of the additive noise. We also show that both methods fit into the robust regression framework [33]. The work on robust classification [34] also connected our work, there they show that certain robust support vector machines are equivalent to SVM. Our results for classification in Section 8 can be viewed as a generalization of their Theorem 3.
Dual formulation. Variations of Proposition 1 are presented in [12]. [17]. [35]. Equivalent results in the context of classification are presented in [2], [15]. We use the reformulation extensively in our developments and also present a generalized statement for it.
3 Background
Different estimators will be relevant to our developments and will be compared in this paper. Adversarially-trained linear regression. Our main object of study is the minimization of
1 max 1//- (z; + Ax;)
(+)
n
Rady R, 8, 11-
(lv:
xT B + +11l))))),
n2
72
where equality (a) follows from Proposition We use || = sup [1 | x0| to denote the dual norm of || We highlight that the fz-norm, || lz = 13,12 is dual to itself. The norm, ||,81] Σ, 18,,, is the dual norm of the l norm, |||||]|]]| 00 = .max; [8,]. When the adversarial disturbances are constrained to the é, ball: (Ax: | S 6} we will call it f, adveesrraliall training. Our focus will be on lxx and aaaaverralia training.
Parameter-shrinking methods. Parameter-shrinking methods explicitly penalize large values of B.. Regression methods that involve shrinkage include Lasso [30] and ridge regression, which minimize,
3

---

respectively
Rlasso (3:
Σ U/ a. 3 1| and R. (B; (3: n
1
Σ 1 n 1: x
Square-root Lasso: Setting (with guarantees) the Lasso regularization parameters requires knowledge about the variance of the noise. Square-root Lasso [32] circumvent this difficulty by minimizing:
RV
RVlusso Jusso (B,
- -l x, 31 A||
Minimum-norm interpolator: Let X E TR= denote the matrix of stacked vectors æ; and y E Ik" the vector of stacked outputs. When matrix X has full row rank, the linear system X3 y has multiple solutions. In this case the minimum || -lo-m interpolator is the solution
min B
||||. subject to XB y.
Adversarial training in the overparametrized regime
Our first contribution is provide conditions for when the minimum- norm interpolator equivalent to adversarial training in the overparametrized case (we will assume that rank(X) = n and n < p). On the one hand, our result gives further insight into adversarial training. On the other hand, allows us to see minimum minimum-norm norm interpolators as a solution of the adversarial training problem.
Theorem 1. Assume the matrix X E RRx to have full row rank, let ā denote the solution of the dual problem max
y. and 8 denote the threshold
(nl|@(llm))
(5)
H The minimum || I--norm interpolator minimizes the adversarial risk Bad (B, 8, II I1) if and only 8 (0,8).
Remark (Bounds on 8). The theorem allows to directly compute 8, but does require solving the dual problem to the minimum-norm solution. In Appendix A.3, we provide bounds on ò that avoid solving the optimization problem. For instance, for &oo adversarial attacks, we have the following bounds depending on the singular values of X: 1 ,x I no I (X), Where and on
denote the largest and smallest positive singular values of X, respectively.
Proof of Theorem 1. Let / and & be the minimum || || -norm solution and the solution of the associated dual problem. Throughout the proof we denote Rudv (3) = R (B: 8, || II), dropping the
last two arguments. The subgradient (Pdx((3) evaluated at 3 is given by²
28
OR (B)
[pia, + 811
(6)
for any = (pI....,Pu E R that satisfies || oc I We have that any element of 0||3||| can be written as X & (we prove that in Lemma in the Appendix). Hence, we can rewrite
25
(x'++oxTa)
X n
aRadv (3)
[p + 6x T a)
26||
If 8= 100i=lnnn|@@leeee hand, i 8 > 1/(n| @l)))) then x + 6x T Tā) is not zero for || 1.
take p -nöā and the subderivative contains zero. On the other
The minimum f--or interpolator is well studied in the context of "basis pursuit' and allows the recovery of low-dimensional representations in sparse signals [39]. The interest in the minimum f--norm is more recent. It played an important role in studying the interplay between interpolation and generalization, being used in many recent papers where the double-descent [24], [26] and the benign overfitting phenomena [22] were observed.
"hhe subgradient of a function IR + R is the set: (W(),)) {w R ( w w( 2 r1 Bb), V/ E R?).
See [36]-[38] for properties. We use a ||]] denote the subgradient of w(3) || evaluated at 3

---

Theorem gives new perspective on the robust- ness of the minimum norm interpolator, allow- ing us to see it as a solution to adversarial train- ing with adversarial radius 8. Figure 2 shows that the radius 8 of the adversarial training prob- lem corresponding to the minimum-nore inter- polator increases with the ratio p/n. It is natural to expect that training with larger radius would yield more adversarially robust models test points. The next result formalizes this intu- ition by establishing
10
fy-norm
hD
10
10'
10
p/n
Figure 2:
Threshold 8 vs. number of fea-
tures. We fix n 60 and show the value of å (defined in (5)) as a function of the number of features p. The dotted lines give the reference deest = 0.01E [| for comparison.
upper bound on the bustness gap: the difference between the square- root of the expected adversarial squared error
RAa (3; Sest || []) = Eyo. ar max || Aæ.l Eórent (yo
(æo + Aoo) }) and the expected squared error (B) Eyo. mo [(yu z 3) The upper bound depends on the in-training adversarial error and the ratio buss which quantities that you can directly compute.
Proposition Assume X to have full row rank and let 33 be the minimum || ||--norm interpolator, than
Stest
Rady (3: Erest, ||- (
(3)
Rady RRdv(B; 5, II).
(7)
8
Remark The example in Figure 2 one case where adding more features makes the minimum- norm interpolator more robust. Examples showing the opposite and illustrating that adding more features to linear models can make them less adversarially robust are abound in the literature [16], [17]. Indeed, examples that consider the minimum lg fz-interpolator subject to adveesssall attacks during test-time result in this scenario, as discussed in [17]. Proposition
the Appendix the equivalent of Proposition 2 for this case (mismatched norms in train and test). There, the upper bound grows with vP, which explains the vulnerability in this scenario.
Remark 3. A pitfall of analyzing the minimum-none norm solution properties in linear models is that requires the analysis of nested problems: different choices of p require different covariates æ. The random projection model proposed by Bach [40] avoids this pitfall by considering the input æ is fixed, but only projected version of it Sa: is observed, with the number of parameters being estimated changing with the number of projections observed. Adversarially training this model consists in finding parameter & that minimizes: 1 >i max A 13; (æ, A ( T We generalize our results so that we can also study this case (See Appendix A.4).
Adversarial training and parameter-shrinking methods
Theorem stated an equivalence with the minimum-norm solution when ö is small. The next result applies to the other extreme of the spectrum, characterizing the case when ö is large.
Proposition (Zero solution of adversarial training). The zero solution 3 = 0 minimizes the
||x vl
adversarial training and only if 5 Z 17/1
In the remaining of this section, we will characterize the solution between these two extremes. We compare adversarial training to Lasso and ridge regression.
5.1 Relation to Lasso and ridge regression
Proposition makes it clear by inspection that adversarial training is similar to other well-known parameter-shrinking regularization methods. Indeed, for &oo -ddversaraaal attacks, the cost function Rndy 5, lloo) in its dual form is remarkably similar to Lasso [30] and Radv (3: 8, || ll2), to ridge regression (the cost functions were presented in Section 3). In Figures and 3, we show the regularization paths of these methods (the dataset described in [18]). We observe that 6x- adversarial training produces sparse solutions and that Lasso and adversaaali training have extremely similar regularization paths. There are also striking similarities between ridge regression and ezaavirraaiall training, with the notable difference that for large the solution of agaavveraaiaal
5

---

40
40
cnefficients
20
20
0
0
-20
20
-40
40
10
10"3
10
10"1
109
10
10
109
101
10a
10
10
10
1/A
1/6
(a) Ridge regression
(b) -z-avversarial training
Figure 3: Regularization paths in the Diabetes dataset [18] (see dataset description in Figure 1). On the horizontal axis, give the inverse of the regularization parameter (in log scale). On the vertical axis, the coefficients.
training is zero (which is explained by Proposition 3). The next proposition justifies why we can observe such similarities in part of the regularization path. It applies to data that has been normalized and for positive responses (as it is the case in our example).
Proposition Assume the output is positive and the data is normalized: y 2 and X 1 0. The solution of adversarial training B, for ||3]|. S min; lvil is also the solution sill
1 Σ
min 72 U: 22. 3 (6) l1lll1)²
The proposition proved in Appendix B. It establishes the equivalence between foe -aveersarial training and Lasso (even though there is not a closed-formula expression for the map between ó and X²). Indeed, under the assumptions of the propositions, 3 is the solution of adveessrra problem only if it is the solution of
min 1 Σ
- 3) x1133111
(1
(8)
for some X. We prove this statement using the proposition: under the appropriate assumptions, the advversaaaaaal problem solution is also solution to the problem
1 3T (811811 + 72 (ulll)
min B
y:
71
which in turn, is the Lagrangian formulation of the following constrained optimization problem
Uy xx. 3) subject to (811911 + n |1 - A,
min
1=1
for some A A 1
1y/11- The constraint can be rewritten as 8||,8|1 S V -1///11 And, the result
follows because (8) is the Lagrangian formulation of this modified problem. similar reasoning could be used to connect the result for fz-adversarial training with ridge regression.
More generally, even when the condition on 3 is not satisfied and if y is negative, we show in Ap- pendix B that for zero-mean and symmetrically distributed covariates, i.c., E [xt] and (x xx), adversarial training has approximately the same solution as
min
2 3
(81|8)) 111 1sTT)) ")²
for sign(y- X 33). This explains the similarities in the regularization paths.
5.2 Transition into the interpolation regime
The discussion above hints at the similarities between adversarial training and parimeter-shrinking methods. Interestingly, Lasso ridge regression are also connected minimum-norm interpolators. The ridge regression solution converges to the minimum-norm solution as the parameter vanishes

---

10
Train MSE
10-1
Train. MSE
10-1
10
10-11
10
10-14
10
fyyady train
fuv train
10 19
10
ridge
Jasso
10-
10
10
10
10a
10*
10
10
10
10
10'
102
102
10*
10²
1/6
1/6
Figure 4: Training mean squared error ys inverse adversarial radius. Left: for ridge and é2- adversarial training. Right: for Lasso and ad--vrrearriall training. The error bars give the median and the 0.25 and 0.75 quantiles from realizations. The vertical black lines show ō in (5). Figure S.9 (appendix) shows the test MSE. For ridge regression Lasso (see Section 3), the z-axis should be read as 1/2, rather than 1/8. We generate the data synthetically using an isotropic Gaussian feature model (see Section 7) with n 60 training data points and p 200 features.
1/2 as À - 0+. Similarly, there is a relation between the minimum & norm solution and Lasso. The relation requires additional constraints because, for the overparameterizze case, Lasso does not necessarily have a unique solution. Nonetheless, is proved in [41, Lemma 7]
ridge i... _ -+) 3
lasso (A) -
that the Lasso solution by the LARS algorithm satisfies
as À + 0+.
For a sufficiently small 6, the solution of veaavrrral training equals the minimum & -orm solution; and, the solution of adveesaaalli training equals the minimum & nnorr solution. There is notable difference though: while this happens only in the limit for ridge regression and Lasso, for adversarial training this happens for all values smaller than the threshold J. We illustrate this phenomenon next. Unlike ridge regression and Lasso which converge towards the interpolation solution, adversarial training goes through abrupt transitions and suddenly starts to interpolate the data. Figure illustrates this phenomenon in synthetically generated data (with isotropic Gaussian feature, see Section 7).
Intuitive explanation for abrupt transitions. To get insight into why the abrupt transition occurs we present the case where n 1, i.c., the dataset has a single data point (ar, y), where
8
L(ox)
1 and ||æ||| 1. We can write Radv (B; 6, || (12) (L( where
0.5
((3) ly - x 3 + 8|131122
Figure Function L(3) for B oa.
The function L is necessarily minimized along the sub- space spanned by the vector æ. Now, along this line, the function L is piecewise linear with three segments, Figure 5. One of the three segments changes the slope sign as 8 decreases and the minimum of the function changes abruptly, thus explaining why abrupt transitions occur.
6 Relation to robust regression and square-root Lasso
In this section we establish that both adversarial training and square-root Lasso can be integrated into the robust regression framework. We further investigate the similarities between the methods by analyzing the prediction error upper bounds.
Robust regression framework. Robust linear regression considers the minimization of the following cost function
probust (3: max y (X + A
AES
where the disturbance matrix A is constrained to belong to the 'disturbance set' S. We connect robust regression, square-root Lasso and adversarial training. The next proposition gives the equivalence between robust regression for row-bounder disturbance sets Rp,5 and Ep adversarali training, see the appendix for the proof.

---

Proposition 5. For disturbance set with the rows bounded by 6:
E
|| ||
5 Vi
we have that arg ming Rrobuss (B, R Ry.s) arg ming Runhy (B:d, || I1).
On the other hand, there an equivalence between square-root I Lasso and robust regression for oolunn-bounded disturbance sets C2.5. This was established by Xu al. [33, Theorem 1] and we repeat it below.
Proposition 6. [33] For a disturbance set with columns bounded by 6:
C2 = {((
Sm : 11: 2 S 6,
have that arg ming prrobuss C2,)) arg ming RVllssso (3,6).
The above discussion hints at the similarities between adversarial training and square-root Lasso, as instances of robust regression under different constraints. Square-root Lasso minimizes RVlasso (G, X) = n n-11/1|ly
x + A||/3111 (See Section 3). The main motivation for the square- root Lasso that is 'pivotal' method for sparse recovery: that is, it attains near-oracle performance without knowledge of the variance levels to set the regularization parameter [32]. As we will show in the next section, a similar property applies to adversaaiaa training.
Fixed-design analysis and similarities with square-root Lasso. In this section, we assume that the data was generated as: yi = x 3 + E; where 3" is the parameter vector used to generate the data. Under these assumptions, we can derive an upper bound for the (in-sample) prediction error:
Theorem 2. Let 8 8* X eli>, the prediction error of &oo -adversaiial training satisfies |e|l
the bound:
x (3 Br) )1 < 86|| la (Hllell2 + 1051|
(10)
For comparison, we also provide the result for Lasso: (Adapted from [31, Thm. 7.13, p. 210])
Theorem 3. [31] Let > X = 3| X e loo, the prediction error of Lasso satisfies the bound:
x 33 < 81
(11)
Without additional constraints (see Remark 5) it can be shown that for Lasso it is not possible to improve the above bound. To satisfy this bound, however, Lasso requires knowledge the magnitude of the noise e. In Theorem 3, X 2 2| X ell. Hence, if we rescale ε (i.e., é - m)) then correspondent change in magnitude follows in X" (i.e., X - v))*). Square-root Lasso [32] avoids this problem and achieves similar rate method. Our method has similar properties and allows us to set ó without estimating the variance. This can be seen in Theorem 2, where re-scaling ε does not alter the value of 8 3 x ell//ell, because it affects the numerator and denominator simultancously.
without knowing the variance: i.e., it is a 'pivotal"
For instance, if assume has i.i.d. AO, o entries and that the matrix X is fixed with max ||ær loce < M. For À Mo (log p)/n, we (with high-probability) satisfy the con- dition in Theorem 3, obtaining: +|IX - 11 S /loglop/// For adversarial training, we can set: 8 M / pi/n,, and (with high-probability) satisfy the theorem condition, obtaining the same bound. Notice that the choice of 5 is not dependent on a. We provide a full analysis in Appendix C.3.
Remark 4 (On the relation between 5 and 8*). For sufficiently large we have 5* > in the scenario above- the noise e has i.i.d. normal entries A (0, o²) and the matrix X fixed. We can prove by contradiction: if 8* < 8 then could apply the bound from Theorem 2 to the minimum & -orm
8

---

can always choose a sufficiently large value of in - = - -
interpolator (due to Theorem 1). Hence, o² ~²==0
< / f)/n and we
n for which the inequality false.
Remark 5. In the original square-root Lasso paper [32], a bound is obtained for the lg parameter distance: |3 3 12 for the case X satisfy the restricted eigenvalue condition and 3 is sparse. Under these more strict assumptions (restricted eigenvalue condition) we can also obtain faster convergence rate for the prediction error. Here we focus on the fixed-design prediction error without additional assumptions on X. For other predictors, these other proofs follow similar steps and yield similar requirements on X", see [31, Chapter 7J. However, we leave these and other analysis (such as variable selection consistency) of adversarial training for future work.
7 Numerical Experiments
We study five different examples. The main goal is to experimentally confirm our theoretical findings. For each scenario, we compute and plot: train and test MSE for different choices of p. n and 8. For comparison purposes, we also compute and plot train and test MSE for Lasso and ridge regression and minimum-norm interpolators. Finally, in line with our discussion in Section 4, we compute and plot 8 as a function of p/n. In all the numerical examples the adversarial training solution is implemented by minimizing (2) using CVXPY [42]. The scenarios under consideration are described below (see Appendix D for additional details)
1. Isotropic Gaussian feature model. The output is a linear combination of the features plus additive noise: 3/- = 2 [3 + c,, for Gaussian noise and covariates: c, ~ N/00, o²) and æ; ~ (O,0, I,). 2. Latent-space feature model [26, Section 5.4]. The features æ are noisy observations of a lower- dimensional subspace of dimension d. A vector in this latent space is represented by x E Rd.
x: = W=+ + u. The output is a linear combination of the latent space plus noise.
3. Random Fourier features model [43]. We apply random Fourier feature map inputs of the Diabetes dataset [18). Random fourier features are obtained by the transformation æ; =
v /2/m cos(cosssss Wz, z; + b) where the entries of W and b are independently sampled. It can be seen as one-layer untrained neural network and approximates the Gaussian kernel feature map [43].
4. Random projection model [40]. The data is generated as in the isotropic Gaussian fcature model, but we only observe Sæ,, i.e., projection of the inputs.
5. Phenotype prediction from genotype. We illustrate our method on the Diverse MAGIC wheat dataset [44] from the National Institute for Applied Botany. We use a subset of the genotype to predict one of the continuous phenotypes.
Results. We experimentally corroborate Theorem 1 in all scenarios: In Figures 4 and S.8 (Appendix) we show the train MSE as we change the adversarial radius 6, confirm- ing the abrupt transitions into the interpolation regime and also that 8 is the transition point. In Figures S.9 and S.10 we show the corresponding test MSE without and in the presence of an adversary, respectively. Interestingly, the adversarial radius that yields the best results is not always equal to the radius &zest the model will be evaluated on. Figures? 2 and S.5 (Appendix) display d function of the ratio p/n. We observe that 8/E [||=|| [] is growing in all examples and we would still expect improved ro- bustness in light of Proposition 2. The Random Fourier
1.4
features, P
Toe NMSE
1.2
1000
2000
features model is the only case where 8 seems to de-
4000
crease (in absolute value). However, E [||>]]]] is also decreasing (and at a faster rate). Figures S.6 and S.7 give test MSE without and in the presence of an adver- sary for the minimum- morm interpolator as a function of the ratio p/n. confirming improved adversarial ro- bustness as p grows.
0.6
S000
0.4
16000
min Ey-omm
ridge
adv. train fa min nomm
lasan
adv. train far
Figure 6: Test normalized MSE (NMSE) in the MAGIC dataset.
Figure 6 provides a comparison of the test error of the different methods under study. For Lasso, ridge and adversarial training, we use the best 5 or À available for each method (obtained via grid search). We note that while for p = 1000 optimally tuned Lasso and adverrrrsali training significantly outperform the corresponding minimum -orm interpolator. As p increases, the performance of the three different methods becomes quite similar. It is also an example where the minimum n-rorm outperforms the minimum norm interpolator (for large p). In the same setup, Figure S.12

---

study a choice of adversarial radius inspired by Theorem 2. We use d x ||XE|=// for & a vector with zero- mre- normal entries. We use random &. since we do not know the true additive noise. Even with this approximation, aadversraai training performs comparably with Lasso with the regularization parameter set using 5-fold cross-validation doing a full search in the hyperparameter space. The figure also provides a comparison with square-root Lasso under similar setting.
8 Results for general loss functions
The following theorem can used to generalize Proposition 1.
Theorem 4. Let L: R >> I be convex and lower-semicontinuous function, for every 6 2 0,
max A
L ((x + Az) 3) T)) max L ((x B +s|BB(l..) .E(-1.1)
(12)
We can find a closed-formula expression for s, arg max L(B x + 8s.[ in many cases of interest. For regression problems, given any non-decreasing function 8 RR+ - IR+,, and [(x'' (3) = E( a , - vl). If é is lower semicontinuous and convex then so will L and the result of the theorem holds (the squared loss {(z) = z² is a special case). Then s, -sign x. T (3) and
((((x: Ar) TT)T B vl) Elly IT A 81|B11.)-
max |
For classification, let E 1-,, and L(x 3) [yy(x T (3) where l is a non-increasing function. If é is lower semicontinuous and convex then so will L and the result of the theorem holds. Then S, y and we obtain:
max C(y((x + A 3)) = E(y(@ 3) -1 | 15
The above result can also be applied to unsupervised learning. In the Appendix, we illustrate how Theorem 4 can be used for dimensionality reduction. We consider the problem of finding P that minimizes the reconstruction error || + PP x (that yields PCA algorithm) and derive an adversarial version of it.
Remark 6. Over this paper we consider x, B E R2, but Theorem 4 holds generaly for x: E X' a vector in Banach space endowed with norm ||- || and B X' continuous linear map 3 : X R. Just define x: == B(x:) and take || || to be the norm of the dual space X
9 Conclusion
We study adversarial training in linear regression. Adversarial training allows us to depart from the traditional regularization setting where we can decompose the loss and the regularization terms, minimizing _ Eizo ((x)) B3 y:) + (2(3) for some penalization function Ω. We show how it provides new insights into the minimum- norm interpolator, by proving a new equivalence between the two methods (Section 4). While adversarially -traind linear regression arrives at similar solutions to parameter shrinking methods in some scenarios (Section 5), also has some advantages, for instance, the adversarial radius might be set without knowing the noise variance (Section 6). Unlike, squared- root Lasso it achieves this while still minimizing a sum of squared terms. We believe natural next step is to provide tailored solver that can allow for efficient solutions for models with many features, rendering adversarially -arraiialll-trtieedddeeaea linear regression useful, for instance, in modeling genetics data (see one minimal example of phenotype prediction from the genotype in Section 7).
Another interesting direction is generalizing adversarial training is very often used in the context of neural networks and it is natural to be interested in the behavior of this class of models. Our work allows for the analysis of simplified theoretical models commonly used to study neural networks. Random Fourier feature models can be analyzed using our theory and are they studied in the numerical examples. These models can be seen simplified neural network model (one-layer neural network where only the last layer weights are adjusted). In Appendix A.4, we provide adversarial training after linear projections, and could, for instance, be used to analyze deep linear networks, as the ones studied in [45], [46]. Finally, Section 8 provides a result for infinite spaces, and one could attempt to use it to analyze kernel methods and infinitely-wiie neural networks [47], [48]. Overall we believe that our results provide interesting set of tools also for the analysis of nonlinear models, and could provide insight into the empirically observed interplay (sce [49]) between robustness and regularization in deep neural networks.
results classification and nonlinear models. Indeed,
10

---

Acknowledgments
The authors would like to thank Carl Nettelblad for very fruitful discussions throughout the work with this research. We also thank Daniel Gedon and Dominik Baumann for their feedback the first version of the manuscript.
TBS and DZ. are financially supported by the Swedish Research Council, with the projects Deep probabilistic regression new models and learning algorithms (contract number: 2021-04301) and Counterfactual Prediction Methods for Heterogeneous Populations (contract number:201 05040) and by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation. TBS, AHR and DZ by the Kjell och Märta Beijer Foundation. FB by the Agence Nationale de la Recher-che as part of the "Investissements l'avenir" program, reference ANR-19- 19-PA00001 (PRAIRIE 3IA Institute); and by the European Research Council (grant SEQUOIA 724063).
The research was partially conducted during AHR's research visit to INRIA. The visit was financially supported by the Institute Français de Suède through the SFVE-A mobility program; and, by the European Network of AI Excellence Centres through ELISE mobility program.
References
[1] J. Bruna, C. Szegedy, I. Sutskever, Gondfellow, W. Zaremba, R. Fergus, and Frhan, "Intriguing properties of neural networks," in International Conference on Learning Representations (ICLR), 2014.
[2] I. Goodfellow, J. Shlens, and C. Szegedy. "Explaining and Harnessing Adversarial Examples," in International Conference on Learning Representations (ICLR), 2015.
[3] A. Kurakin, I. Goodfellow, S. Bengio, al., "Adversarial attacks and defences competition," in The NIPS '17 competition: Building Intelligent Systems, 2018, pp. 195-231.
[4] A. Fawzi, O. Fawzi, and Frossard, "Analysis of classifiers' robustness to adversarial perturbations," Machine Learning, vol. 107, no. 3, pp. 481-508, 2018.
[5] Ilyas, Santurkar, Tsipras, Engstrom, Tran, and Madry, "Adversarial Examples Are Not Bugs, They Are Features," Advances Neural Information Processing Systems, vol. 32, 2019.
[6] X. Yuan, P. He, Q Zhu, and X. Li, "Adversarial examples: Attacks and defenses for deep learning," IEEE Transactions on Neural Networks and Learning Systems, vol. 30, no. pp. 2805-2824, 2019.
[7] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, "Towards Deep Learning Models Resistant to Adversarial Attacks," International Conference for Learning Representations (ICLR), 2018.
[8] R. Huang, B. Xu, D. Schuurmans, and C. Szepesvari, "Learning with a Strong Adversary," X5x 1.000334 2016.
[9] T. Bai, J. Luo, J. Zhao, B. Wen, and Q. Wang, "Recent Advances in Adversarial Training for Adversarial 2021.
Robustness,"
[10] F. Croce, M. Andriushchenko, V. Schwag, E. Debenedetti, N. Flammarion, M. Chiang, P. Mittal, and
M. Hein, "RobuslBench: A standardized adversarial robustness benchmark," " in NeurlPS Datasets and
Benchmarks track, 2021.
[11] H. Taheri, R. Pedarsani, and C. Thrampoulidis, "Asymptotic Behavior of Adversarial Training in Binary Classification," IEEE International Symposium Information Theory (ISIT), vol. 127-132. 2022.
[12] A. Javammard, M. Soltanolkotabi, and H. Hassani, "Precise tradeoffss in adversarial training for linear regression." in Proceedings of the Conference on Learning Theory, vol. 125, 2020, pp. 2034-2078.
[13] H. Hassani and Javanmard, "The curse overparametrizzatoon in adversarial training: Precise analysis of robust generalization for random features regression," 220i::220000014999 2022.
[14] Y. Min. L. Chen, and A. Karbasi, "The Curious Case of Adversarially Robust Models: More Data Can Help. Double Descend. or Hurt Generalization." Proceedings of the Conference on Uncertainty in Artificial Intelligence, vol. 161, pp. 129-139, 2021.
[15] D. Yin, R. Kannan, and P. Bartlett, "Rademacher Complexity for Adversarially Robust Generalization," in Proceeding of the International Conference on Machine Learning, 2019, pp. 7085-7094,
[16] D. Tsipras, S. Santurkar, I.. Engstrom, A. Turner, and A. Ma, "Robustness May Be At Odds with Accuracy," International Conference for Learning Representations, 2019.
[17] A. H. Ribciro and T. B. Schön, "Overparameterized Linear Regression under Adversarial Attacks," IEEE Trunsactions on Signal Processing, 2023.

---

[18] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, "Least angle regression." The Annals of Statistics. vol. 32, no. 2. pp. 407-499, 2004.
[19] T. Hastie, R. Tibshirani, and J. Friedman, Elements of Statistical Learning, Second. Springer Science Business Media, 2009.
[20] C. Zhang. S. Bengio, M. Hardt, B. Recht, and O. Vinyals, "Understanding deep learning requires rethinking generalization," " in International Conference on Learning Representations, 2017.
[21] P. L.. Bartlett, A. Montanari, and A. Rakhlin, "Deep learning: A statistical viewpoint," arXiv:2103.09117,
2021.
[22] P. L.. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler, "Benign overfitting in linear regression," Proceedings
of the National Academy of Sciences, vol. 117, no. 48, pp. 30 063-300 070, 2020.
[23] F. Kochler, L. Zhou, Width, Norm Bounds and Benign Overfitting"" in NewrIPS, 2021.
Sutherland, and Srebro, "Uniform Convergence of Interpolators: Gaussian
[24] M. Belkin, D. Hsu, S. Ma, and S. Mandal, "Reconciling modern machine-learinng practice and the classical bias-variance trade-off," Proceedings of the National Academy of Sciences, vol. 116, 32,
pp. 15 849-15 854, 2019.
[25] M. Belkin, D. Hsu, and J. Xu. "Two Models of Double Descent for Weak Features," SIAM Journal on Mathematics of Data Science, vol. no. 4, pp. 1167-1180, 2020.
[26] T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani, "Surprises in high- sigh-dimensional ridgeless least squares interpolation," The Annals of Statistics, vol. 50, no. 2, pp. 949-986, 2022.
[27] C. Dan, Y. Wei, and P. Ravikumar, "Sharp statistical guaratees for adversarially robust Gaussian classifi- cation," in Proceedings of the 37th international conference on machine learning, ser. Proceedings of machine learning rescarch, vol. 119, PMLR, 2020, pp. 2345-2355.
[28] E. Dobriban, H. Hassani, D. Hong, and A. Robey, Provable tradeoffs in adversarially robust classification, 2022.
[29] A. Javanmard and M. Soltanolkotabi, "Precise statistical analysis of classification accuracies for adver- sarial training." " The Annals of Statistics, vol. 50, 4, pp. 1127-2156, 2022.
[30] R. Tibshirani, "Regression shrinkage and selection via the LASSO," Journal of the Royal Statistical Sociery. Series B (Methodological), pp. 267-288, 1996.
[31] M. J. Wainwright, fligh-Simensioal Statistics: a non-Asymptotic Viewpoint, ser. Cambridge series on statistical and probabilistic mathematics 48. Cambridge University Press, 2019.
[32] A. Belloni, V. Chernozhukov, and L. Wang. "Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming." Biometrika, vol. 98, no. 4. pp. 791-806, 2011.
[33] H. Xu, C. Caramanis, and S. Mannor, "Robust regression and lasso," Advances in Neural Information Processing Systems, vol. 21, 2008.
[34]
"Robustness and regularization of support vector machines," Journal of Machine Learning Re- search, vol. 10, no. 51, pp. 1485-1510, 2009.
[35] Y. Xing, Q. Song, and G. Cheng, "On the Generalization Properties of Adversarial Training." in Proceed- ings of the International Conference on Artificial Intelligence and Statisticx, 2021, pp. 505-513.
[36] D. Bertsekas, A. Nedi, and A. E. Ozdaglar, Convex Analysis and Optimization. 2003.
[37]
F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics. 1990.
[38]
S. Boyd, J. Duchi, M. Pilanci, and L. Vandenberghe, "Subgradients (Lecture Notes)," Tech. Rep. Notes for EE364b, Stanford University. Spring 2021-22, 2022.
[39] S. S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by hasis pursuit," SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 61, 1998.
[40] F. Bach, -Hiig--dimesiionlll analysis of double descent for linear regression with random projections." arXiv:203300337 2023.
[41] R. J. Tibshirani, "The Lasso Problem and Uniqueness." Electronic Journal of Statistics, vol. 7, pp. 1456- 1490, 2013.
[42] S. Diamond and S. Boyd, "CVXPY: A Python-embedded modeling language for convex optimization," Journal of Machine Learning Research, vol. 17, no. 83, pp. 1-5, 2016.
[43] A. Rahimi and B. Recht, "Random Features for Large-Scale Kernel Machines," in Advances in Neural Information Processing Systems 20, 2008, pp. 1177-1184.
[44] M. F. Scott, N. Fradgley. A. R. Bentley, et al., "Limited haplotype diversity underlies polygenic trait architecture across 70 years of wheat breeding." Genome Biology, vol. 22, no. 1, 137, 2021.
12

---

[45] A. M. Saxe. J. L. McClelland, and S. Canguli, "Exact solutions to the nonlinear dynamics of learning in deep linear neural networks," International Conference on Leurning Representations (ICLR), 2014.
[46] T. Laurent and J. Brecht, "Deep Linear Networks with Arbitrary Loss: All Local Minima Are Global," in Proceedings of the International Conference on Machine Learning. 2018, pp. 2902-2907.
[47] Lee, Xiao,
Pennington. "Wide neural networks of any depth evolve as linear models under gradient descent," Journal of Statistical Mechanics: Theory and Experiment, vol. 2020, no. 12, 124 002, 2020.
Schoenholz, Y. Bahri,, R. Novak,
Sohl-Dickstein,
[48] Jacot, Gabriel, and Hongler, "Neural Tangent Kernl:: Convergence and Generalization in Neural Networks," " Advances in Neural Information Processing Systems 31, 2018.
[49] D. Jakubovitz and R. Giryes, "Improving DNN robustness adversarial attacks using jacobian regular- ization," " in European conference computer vision, 2018.
13


Reviews:
[{"review_id": "OKjjw2fSJm", "reviewer": "Reviewer_CYXN", "summary": "This paper investigates adversarial training of linear regression. The authors compared the solution of adversarial training and other regularization frameworks (minimum-norm interpolating, ridge regression, Lasso and square-root Lasso), and established close relations between adversarial training and other methods under certain conditions depending on the disturbance radius and over/under-parameterization. The authors also consider extending the result to more general loss function for linear model.", "questions": "Here are some additional questions/comments:\n\n1.\t$\\sigma_1$ and $\\sigma_n$ in line 126 are undefined.\n\n2.\tThe authors claim in line 151 and Remark 2 that the model becomes robust as feature dimension $p$ grows, which seems not precise to me. The authors suggest that the threshold $\\bar{\\delta}$ increases faster, but this only guarantees that the optimal solution of adversarial training and minimum-norm interpolator agree, which does not necessarily mean more robustness. Does the risk $\\mathcal{R}^{\\text{adv}}$ decrease as feature dimension $p$ grows? \n\n3.\tThe paper investigates the situation where the sample features $x_i$’s are disturbed in linear regression. In applications, it is also very common that the target $y_i$’s are disturbed.  \n", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper provides valuable insights on the relation between adversarial training and other regularization frameworks for linear regression, which contributes to the area of robust learning. The analysis is sound.\n2.\tThe paper provides good background knowledge and details in their work. \n3.\tThe paper is well-organized and easy to follow overall.\n", "weaknesses": "1.\tIn the abstract, the authors claim that adversarial training can be equivalent to parameter shrinkage methods (like ridge regression and Lasso). However, from Proposition 4, it seems the two frameworks are not equivalent, since the regularization term in the equation of Proposition 4 equals $\\delta^2\\left\\| \\beta\\right\\|^2 + c\\delta\\left\\| \\beta\\right\\|$ for some constant $c$. I am curious about how the quadratic term can affect the solution, or how close the adversarial training solution is from the parameter shrinkage solution.\n\n2.\tIn the numerical experiment, the authors have not mentioned how the adversarial training is carried out in these datasets. From the code in the supplementary materials, it seems the adversarial samples are generated by the PGD attack. Please consider including more details in the paper. Also, does PGD generate sufficiently strong attacks for linear regression?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of our paper (including even going into the code). We answer the comments below.\n\n1.  **On the equivalence with parameter shrinking methods.** Thank you for the comment. A possible interpretation is to view \n$$\\min\\_{\\beta}\\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta)^2 + \\Big(\\delta ||\\beta||\\_1 + \\frac{1}{n}||y||\\_1\\Big)^2,$$\n(in Proposition 4) as the Lagrangian formulation of the following constrained optimization problem\n$$\\min\\_{\\beta} \\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta)^2\\text{ subject to }\\Big(\\delta ||\\beta||\\_1 + \\frac{1}{n}||y||\\_1\\Big)^2 \\le \\Delta,$$\nfor some $\\Delta$. We can then rewrite the constraint as\n$$\\delta ||\\beta||\\_1 \\le \\sqrt{\\Delta} - \\frac{1}{n}||y||\\_1.$$\nNote that we can always rescale the data such that  $\\sqrt{\\Delta} - \\frac{1}{n}||y||\\_1 > 0$ so that the problem is well-posed. In turn, the Lagrangian formulation of the modified problem is\n$$\\min\\_{\\beta}\\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta) +  \\lambda' ||\\beta||\\_1.$$\nfor some $\\lambda'$ . After this reformulation, the equivalence between $\\ell\\_\\infty$-adversarial training and lasso becomes explicit, but the value of $\\lambda'$ does not have a closed-form expression. A similar reasoning could be used to connect the results of $\\ell\\_2$-adversarial training with ridge regression. We will clarify this in the text. We also highlight that the equivalence is corroborated experimentally in Figures 1 and 3 (the regularization paths are very similar).\n2. **On the use of PGD.** We apologize that the presence of PGD implementation caused confusion. The algorithm was only used for double-checking some of the results. In the case of linear regression, we can generate the attacks exactly (we use the function `compute_adv_attack` in the supplementary file `code/adversarial_attack.py`). The function is based on the results of Theorem 4 and gives the optimal solution to the maximization problem. We will add additional comments on the code to make it clearer. We will also add an explanation in the paper to make sure the experimental setup is clear.\n\n\n**Questions:**\n1. Thank you for catching it. Here, $\\sigma\\_1\\le \\cdots \\le \\sigma\\_n$ are the eigenvalues. We will make sure that it is defined in the revised paper.\n2. Yes, it does decrease. We will add the plot in the supplementary material. The intuition behind it is that each time you add one more feature to your model the previous solution is still a valid one, so the training error would either be the same (if the weight given to the parameter that multiplies this feature is zero) or decrease (if there is a value that produces a better solution). \n3. Interesting point. We considered the possibility of $y\\_i$ being contaminated with noise. In part of the analysis in Section 6, we assume this noise would be Gaussian, but except for that, there is no assumption on the type of output noise.\n"}, {"review_id": "Q9xCJVxIqX", "reviewer": "Reviewer_6WVQ", "summary": "The paper studies adversarial training (AT) for linear regression for which the inner maximization problems has a closed form solution. They then attempt at relating the solutions to solutions of other optimization problems:\n\n- They show that the minimum norm interpolator also minimizes the adversarial loss (iff the adversarial perturbation is sufficiently small)\n- They show that adversarial training (under certain conditions) minimizes something closely related to the LASSO and ridge regression objective for $\\ell_\\infty$ and $\\ell_2$ attacks respectively.\n- They show that similarly to square-root LASSO, adversarial training does not need knowledge of the variance and they argue that this makes adversarial training a viable alternative.\n", "questions": "- Thm. 1: $\\bar \\delta$ depends on the $\\ell_\\infty$-norm regardless of the choice of norm in the adversarial training? This seems potentially loose – could you comment on it?\n- Prop. 2: Do you still rely on full row rank in Prop. 2? \n- l. 158-159: Isn't the claim in [17] about $\\ell_2$ minimum norm while your Prop. 7 is a claim about choice of norm in the adversarial training? \n- Figure 3: Could you label the plot to explain the colors? I don't understan how to interpret the plot.\n- Figure 4 / l. 179: what is \"regularization paths\"? \n- What assumption breaks in Prop. 4 since it is no longer able to predict similarly after $\\delta$ is made sufficiently small (as demonstrated in Fig. 4)?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- It seems interesting to attempt connecting AT to sparse solutions\n- The initial setup and the statements of the theorems are presented in a clean way\n- Existing literature is well-covered\n", "weaknesses": "- My main concern is that the theoretical claims are rather weak:\n    - Concerning Thm. 1, l. 122 \"minimum-norm interpolators as the outcome of adversarial training\" seems a bit of a stretch, since it is not *consistently* the outcome of adversarial training (we might be able to find a minimizer of $R^{adv}$ that is *not* a min norm interpolator). AT would imply minimum-norm interpolator if the minimizer of $R^{adv}$ was unique, but this cannot be the case since LASSO is not unique in general.\n    - Prop. 2 is concerning minimum norm interpolator (so not necessarily obtainable with AT!). What makes this statement interesting for adversarial training if we need to obtain the solution through other means?\n    - Prop. 4 seems to not directly relate AT to LASSO/ridge regression. Whats is the conclusion of Prop. 4? \n    - Thm. 2 exists to show that AT can replace sqrt-root LASSO. You are comparison with Lasso though – doesn't the bound have a bias in comparison with sqrt-root LASSO (eq. 10 of [29]). The main feature of AT seems to be the claim that $\\delta^*$ is invariant to rescaling of $\\varepsilon$. Can you explicitly make $\\delta^*$ in Thm. 2 independent of $\\varepsilon$? (currently this is not the case in theorem statement)\n\nComments:\n\n- Prop. 5 maybe pick a different variable than $p$ (already used for dimensionality)\n- l. 144 should have been $\\delta$ instead of $\\delta_{train}$?\n- Maybe write \"a solution\" in l. 144 instead of \"the\".\n- l. 179: Please describe the dataset in the appendix or provide a more direct pointer to [18].\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback. We are grateful the reviewer pointed out aspects that were unclear. We answer your comments below and will update the paper accordingly.\n\n- **Thm 1:**  Indeed, we did not establish uniqueness. We will tone down our claims and rewrite so it is not misleading.\n- **Prop 2:** Proposition 2 provides a way of analyzing the adversarial robustness of minimum-norm interpolators in test time.  Theorem 1 allows us to see minimum-norm interpolators as *a* solution to adversarial training, giving a new perspective on its robustness. The results, however,  only refer to training performance. Proposition 2 adds to that picture by giving intuition about how $\\bar \\delta$ affects the adversarial robustness in *test-time* (which is what we are ultimately interested in). \n- **Prop 4:**  Thank you for the comment, we use this opportunity to clarify it (it also generated a question from Reviewer CYXN). A possible interpretation is to view \n$$\\min\\_{\\beta}\\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta)^2 + \\Big(\\delta ||\\beta||\\_1 + \\frac{1}{n}||y||\\_1\\Big)^2,$$\n(in Proposition 4) as the Lagrangian formulation of the following constrained optimization problem\n$$\\min\\_{\\beta} \\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta)^2\\text{ subject to }\\Big(\\delta ||\\beta||\\_1 + \\frac{1}{n}||y||\\_1\\Big)^2 \\le \\Delta,$$\nfor some $\\Delta$. We can then rewrite the constraint as\n$$\\delta ||\\beta||\\_1 \\le \\sqrt{\\Delta} - \\frac{1}{n}||y||\\_1.$$\nNote that we can always rescale the data so that $\\sqrt{\\Delta} - \\frac{1}{n}||y||\\_1 > 0$ and the problem is well-posed. In turn, the Lagrangian formulation of the modified problem is\n$$\\min\\_{\\beta}\\frac{1}{n} \\sum\\_{i=1}^n (y\\_i - x\\_i^\\top \\beta) +  \\lambda' ||\\beta||\\_1.$$\nfor some $\\lambda'$ .  After this rewriting, it becomes clear that Proposition 4 establishes the equivalence between $\\ell\\_\\infty$-adversarial training and lasso (but $\\lambda'$ does not have a closed-formula expression). A similar reasoning could be used to connect the result for $\\ell\\_2$-adversarial training with ridge regression. We will make it more clear in the revised text.  The equivalence is also observed experimentally in Figs 1 and 3. \n- **Thm 2:** Theorem 2 establishes similarities between $\\ell\\_\\infty$-adversarial training and square-root lasso.  Our derivation yield the same convergence rates as would be obtained under the same assumptions for square-root lasso, any additional term that appears in the derivation vanishes faster as we set $\\delta \\propto R \\sqrt{(\\log p) / n}$.  We do not believe that the theorem implies that adversarial training replaces square-root lasso: for both methods, we can set the regularization parameter without knowledge of the variance and get the same rate of convergence.\n\n  Also, as mentioned in Remark 5, Eq. (10) in [28] is not directly comparable to ours, we bound the prediction error, while they bound the parameter estimation error under data assumptions that differ from ours.\n\n  We are not aware of any way to make $\\delta^*$ independent of $\\epsilon$, neither for $\\ell\\_\\infty$- adversarial training nor square-root lasso. The results where $\\epsilon$ does directly not appear in [28] follow from using subgaussian upper bounds (that also could be used in our case). \n\n**Comments**\n- Indeed, $p$ was a bad choice since it overrides the notation. We will change it.\n- Using $\\delta\\_{\\text{train}}$ was intentional. The reason to use it was to make the contrast with $\\delta_{\\text{test}}$ more clear. We will add a sentence to clarify the notation.\n- Good point, without proving uniqueness we cannot use \"the\". We will rewrite the sentence.\n- We will add a subsection in the appendix with a short description of the dataset and point to it.\n\n**Questions**\n- The choice of the adversarial training norm appears indirectly: it determines which dual problem $\\widehat{\\alpha}$ solves.  We highlight that the result is tight: the theorem is an \"if and only if\" statement. We also check it experimentally in Fig 4, there the model interpolates (up to numerical precision) the training data for solutions where $\\delta \\le \\bar \\delta$ with the transition happening exactly at $\\bar{\\delta}$. \n- It is necessary. We will update the text. This was implicit since without full rank there exists no interpolating solution. But, we agree that it is more clear to explicitly say it. \n- Proposition 7 is about the gap between training and testing for minimum-norm interpolators. Theorem 1 allows us to see the minimum-norm solution as *an* optimal solution during adversarial training. Proposition 7 shows that despite being optimal during training this solution can still have very large adversarial test error for mismatched evaluations. What, for instance, allow us to explain Fig 1 in [17].\n- In Fig  3, we are considering $p=10$  coefficients, corresponding to the ten variables in the problem (age, sex, body mass index, average blood pressure, and six blood serum measures). Each color corresponds to the value of one coefficient of the coefficients $\\beta_i$ in the regression problem, as we change the value of the regularization. We will include a legend.\n- We will make it more clear in the text. The regularization path is a plot of the coefficient value against varying values of the regularization parameter (for adversarial training the adversarial radius $\\delta$, for ridge and Lasso $\\lambda$). This type of analysis is used in the study of Lasso and variants, see [17] and [B1, Section 3.4].\n- The hypothesis $||\\widehat{\\beta}||\\ge \\min_i \\frac{|y_i|}{\\|x_i\\|}$ no longer holds after the transition point in Fig 4. That is because after the transition point $y_i = \\widehat{\\beta}^\\top x\\_i$ for all $i$. Hence, $|y\\_i| = |\\widehat{\\beta}^\\top x\\_i| \\ge ||\\widehat{\\beta}||_*||x\\_i||$, with the strict inequality holding for some $i$.\n\n**References**\n- [B1] J. Friedman, T. Hastie, and R. Tibshirani *\"The elements of statistical learning\"* 2001.\n"}, {"review_id": "xl2Otw0uqQ", "reviewer": "Reviewer_Zg7q", "summary": "This paper studies the connection between adversarial training and regularization methods in linear regression problem. Simulation studies are provided to justify the correctness of their theoretical observations.", "questions": "Is it possible to extend the analysis to two-layer neural networks?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors conducts a comprehensive study on the relationship between adversarial training and regularization methods in linear regression setup. The writing is clear and easy to understand.", "weaknesses": "My major concern towards this paper is the limit of its contribution. While the analysis is comprehensive, it is only restricted to linear models. Considering that the adversarial training is more commonly used in neural networks rather than linear models in reality, the contribution is limited. The authors are encouraged to add more discussions on neural networks.\n\nIn addition, the following paper considers the connection between regularization and adversarial robustness:\n\nJakubovitz, Daniel, and Raja Giryes. \"Improving dnn robustness to adversarial attacks using jacobian regularization.\" Proceedings of the European Conference on Computer Vision (ECCV). 2018.\n\nPlease cite this paper and compare it to the submission from intuition aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for useful feedback and comments.\n\n**Why restrict the analysis to linear models?** We understand your concern and believe you raise a very valid point: adversarial training is very often used in the context of neural networks and it is natural to be interested in the behavior of this class of models.\n\nWe will try to have a more extensive discussion on the consequences of our results to neural networks. While neural networks are not analyzed, we cover some of the simplified theoretical models commonly used to analyze neural networks. For instance, Random Fourier features models can be analyzed using our theory and can be seen as a simplified neural network model (one-layer neural network where only the last layer weights are adjusted), see Section 7, example 5.  Moreover, we will try to clearly highlight possible uses of our results for analyzing neural networks. For instance, in Appendix A.4., we provide adversarial training after linear projections, and could for instance be used to analyse deep linear networks, as the ones studied in [A1, A2]. Section 8 provides a result for infinite spaces, and one could attempt to use it to analyze infinitely-wide neural networks, as the ones studied in [A3, A4].\n\nWe admit that making these connections might help, but still has limited effect in addressing this limitation. Nonetheless, we believe the analysis of linear models is rich enough to justify an interest of its own and does not necessarily reduce the impact or relevance of the paper:\n1. A thorough analysis of adversarial attacks in linear models is a natural toolbox for any researchers trying to understand nonlinear models.\n2. We believe the results presented in this paper are novel and provide a hint at many interesting phenomena that can be observed in neural networks. Providing, for instance, insight into the relation between overparameterization and robustness.\n3. There are a lot of extensions and future work that can be done from this paper. We hope our group and other groups can use it as a starting point for further analysis.\n\n**On the connection with the ECCV paper.** Thank you very much for the reference. We will cite and add a comment establishing the connection. The paper is indeed relevant, it establishes a connection between adversarial robustness and regularization methods in more complex scenarios than studied by us. We establish a direct connection between regularization and adversarial training in linear models. This idea is complemented by your reference, which shows how the interplay between robustness and regularization is still relevant in deep neural networks.\n\n**References**\n- [A1] A. M. Saxe, J. L. McClelland, and S. Ganguli, “Exact solutions to the nonlinear dynamics of learning in deep linear neural networks,” ICLR, 2014. \n- [A2] T. Laurent and J. Brecht, “Deep Linear Networks with Arbitrary Loss: All Local Minima Are Global,” in ICML 2018.\n- [A3] J. Lee et al., “Wide neural networks of any depth evolve as linear models under gradient descent,” J. Stat. Mech., vol. 2020, no. 12, p. 124002, Dec. 2020, doi: 10.1088/1742-5468/abc62b.\n- [A4] A. Jacot, F. Gabriel, and C. Hongler, “Neural Tangent Kernel: Convergence and Generalization in Neural Networks,” NeurIPS, 2018\n\n"}, {"review_id": "RMbwxkROj1", "reviewer": "Reviewer_uRwm", "summary": "This paper provides an in-depth analysis of adversarial training with linear models and its relationship to regularized regression methods under the overparametrized regime.\nDepending on the value of the perturbation radius, it is revealed that there exist three modes.\nWhen the radius is small, solutions to adversarial training behave as minimum-norm interpolators (Theorem 1).\nWhen the radius is medium, the solutions behave as solutions to the parameter shrinkage regression (Proposition 4).\nWhen the radius is large, the zero solution is necessary and sufficient (Proposition 3).\nIn addition to these theoretical results, the authors observe the mode change experimentally and discuss how adversarial training is advantageous over parameter shrinkage regression.", "questions": "See the weaknesses.", "limitations": "Obviously, the analysis is entirely limited to the linear model case. Nonetheless, the analysis provides a fair amount of insights to readers, so I don't think this is a big limitation.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- A modern extension of theory on robust optimization and regularization: The relationship between robust optimization (somewhat encompassing adversarial training in this work) and regularization has been known in the literature, including Xu et al. (2009). This work contributes to studying what happens when it comes to overparametrization and nicely characterizes the relationship between the perturbation radius and the corresponding modes (as I summarized above).\n- Demonstration of the benefit of overparametrization: In the numerical simulation of Figure 2, the authors demonstrate that the robustness radius increases as the model becomes more overparametrized, namely, $p/n$ increases. This clearly indicates the benefits of overparametrization (though the analysis hinges on norm matching, as mentioned in Remark 2).\n- Clarity: Despite the thorough theory, the paper is written clearly and easy to follow.\n\nXu et al. (2009). \"Robustness and Regularization of Support Vector Machines.\" (JMLR)", "weaknesses": "One of the main weaknesses would be the restriction to linear models, which is crucial for the current analysis yet needed for further understanding adversarial training.\n\nYou may refer to Xu et al. (2009) when you show Theorem 4. Indeed, the equation right after l.322 can be regarded as a generalization of Theorem 3 in Xu et al. (2009) because $\\\\ell(y(\\\\boldsymbol{x}^\\\\top\\\\boldsymbol{\\\\beta}) - \\\\delta\\\\|\\\\beta\\_\\*\\\\|) \\\\le \\\\ell(y(\\\\boldsymbol{x}^\\\\top\\\\boldsymbol{\\\\beta})) + \\\\delta\\\\|\\\\boldsymbol{\\\\beta}\\\\|\\_\\*$ when $\\\\ell$ is the hinge loss.\n\nBelow, I have other minor comments.\n\n- In Figure 1, can you specify what $\\\\lambda$ and $\\\\delta$ are used for each line?\n- In the proof of Theorem 1, you may need $-$ (negative) sign in front of either $\\\\epsilon\\_i\\boldsymbol{x}\\_i$ in Eq. (6) or $n\\\\delta\\boldsymbol{\\\\alpha}$ in l.132. Otherwise, \"the subderivative contains zero\" (l.132) does not seem to be correct.\n- In l.150, the reason of $\\\\delta\\_{\\\\text{test}} \\\\propto \\mathbb{E}[\\\\|\\\\boldsymbol{x}\\\\|]$ is unclear to me. Can you elaborate on it?\n- In Figure 4, can you specify what $n$ and $p$ are used?\n- In Eq. (8), do you miss the exponent $2$ for the norm?\n- In Eq. (9), it might be better to change the notation $\\\\epsilon$ for the noise because $\\\\epsilon$ has already been used in the proof of Theorem 1.\n- In the equations after l.319 and l.322, should we need $+ \\\\Delta x$ on the left-hand sides?\n- In the appendix, what is referred to as Theorem 3 seems to be Proposition 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's comments and feedback. We are thankful for the overall positive assessment of our work and also believe the comments will greatly improve the paper.\n\n**About Theorem 4 and its relation to Xu et al (2009).** Thank you for the comment. We updated the manuscript including the reference and its connection with our Theorem 4.\n\n**Other minor comments.** (we answer in order)\n- Good suggestion. There is a one-to-one correspondence between the x-axis in Figure 1 (i.e., $||\\widehat \\beta||\\_1$) and the value of $\\lambda$ or $\\delta$. We will add the figure displaying the relation in the Supplementary material (and add a pointer to it in the caption of Fig.1).\n- Indeed, it should have been $\\varepsilon = - n \\delta \\widehat{\\alpha}$. Thank you for catching it.\n- Thank you for the question.  In the end, the relative size of the adversarial attacks $||\\Delta x||$ in relation to $||x||$ is what matters, not its absolute value (i.e., having a very small disturbance $\\Delta x$ will have a different meaning when all the inputs are also very small, compared to when they are normalized). In Figure, as we increase $p$ the magnitude of the inputs $||x||$ can also increase depending on how the features are added. By making $\\delta\\_{\\text{test}} \\propto E[||x||]$ we make sure this effect is taken into account.\n- We use $n=60$, $p =200$. We will add this information to the figure caption.\n- No, it is correct. Nonetheless, you have a good point: the optimization problem with the exponent 2 for the norm could also work (since it is an equivalent problem). We use without the exponent so it is the same formulation as in reference [30].\n- Good point. We will choose a different letter that does not override the notation.\n- We believe the equations are correct. These two equations are specific cases of eq. (11). And indeed, in Theorem 4 the double application of Fenchel duality allows us to get rid of $\\Delta x$ in the left-hand side of (11). \n- Yes, you are correct. Thank you for spotting it.\n"}]

Author rebuttal:
We sincerely thank all reviewers for taking the time to read and reflect on our paper. We are pleased to have received a generally positive response and that all the reviewers highlight the clarity of the paper and that it provides insight into adversarial training. We also believe the feedback provides us with useful information which will allow us to improve our paper. 

Meta-review: The paper provides a set of interesting results about the minimizers of the adversarial training objective when the underlying problem is linear regression (with using several regularization methods). As main messages, it is shown that adversarial training yields the minimum-norm interpolating solution in the overparameterized regime (more parameters than data), as long as the maximum disturbance radius is smaller than a threshold. And, conversely, the minimum-norm interpolator is the solution to adversarial training with a given radius. Also, it is shown that adversarial training can be equivalent to parameter shrinking methods (ridge regression and Lasso). 

All the reviewers (and myself) are very positive about this paper. I believe that the results will be useful for the broad robust-ML community. 

As a small note: I think the paper could also discuss the following papers as related works: (1) Dan et al on guarantees for adversarially robust gaussian classification, and (2) Dobriban et al on adversarially robust classification; Both papers have interesting results on classification which connect to linear classifiers (and also connect to some of the objectives considered in the paper).
Decision: Accept (spotlight)