High-dimensional (Group) Adversarial Training in Linear Regression
Authors: Yiling Xie
Xiaoming Huo
Venue: NeurIPS 2024 poster (2024)
Keywords: adversarial training
high-dimension
convergence rate
sparsity
minimax
Primary area: learning_theory

Abstract: Adversarial training can achieve robustness against adversarial perturbations and has been widely used in machine-learning models. This paper delivers a non-asymptotic consistency analysis of the adversarial training procedure under $\ell_\infty$-perturbation in high-dimensional linear regression. It will be shown that, under the restricted eigenvalue condition, the associated convergence rate of prediction error can achieve the minimax rate up to a logarithmic factor in the high-dimensional linear regression on the class of sparse parameters. Additionally, the group adversarial training procedure is analyzed. Compared with classic adversarial training, it will be proved that the group adversarial training procedure enjoys a better prediction error upper bound under certain group-sparsity patterns.

High-dimensional (Group) Adversarial Training in Linear Regression
Yiling Xie
Xiaoming Huo
School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia, USA yxie3508gatech. edu
School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia, USA huo@gatech.
Abstract
Adversarial training can achieve robustness against adversarial perturbations and has been widely used in machine-learning models. This paper delivers non- asymptotic consistency analysis of the adversarial training procedure under foo perturbation in nigh-dimensional linear regression. It will be shown that, under the restricted eigenvalue condition, the associated convergence rate of prediction error achieve the minimax rate up logarithmic factor in the high-dimensional lin- ear regression on the class of sparse parameters. Additionally, the group adversarial training procedure analyzed. Compared with classic adversarial training, it will be proved that the group adversarial training procedure enjoys a better prediction error upper bound under certain group-sparsity patterns.
Introduction
Adversarial training is proposed to hedge against adversarial perturbations and has attracted much research interest recent years. Adversarial training has been widely used Large Language Models [4 24
computer vision [13], cybersecurity 333. etc. While the empirical risk minimization procedure optimizes empirical loss, the adversarial training procedure seeks conservative solutions that optimize the worst-case loss under given magnitude of perturbation. People have actively investigated model modifications and algorithmic frameworks to improve performance and training efficiency for adversarial training under different problem settings [1 [2
22
23 27 29
We are interested in understanding the fundamental properties of adversarial training from a statistical viewpoint. A standard approach for statisticians to evaluate statistical or machine-leammin models investigate whether the estimator obtained from the model can achieve the minimax rate (25]. In this paper, we will give the non-asymptotic convergence rate of the prediction error in high- dimensional adversarial training. The associated convergence rate achieves the minimax rate under certain settings, which will be clarified in Section 2.2
In machine-learning models, adversarial training has the following mathematical formulation:
min
sup L(X; + A, ا
where (X,, Yi).... (X,, Yr) are given samples, is the perturbation, || the perturbation norm, 8 is the perturbation magnitude, |9 is the model parameter, and L(x, y, 8) is the loss function with æ being the input variable and y being the response variable.
Regarding the choice of the perturbation norm, we focus on foc pertuuuurbat,on, i.e., | Some literature has pointed out that pertuurbbbiii could help recover the model sparsity 21 28
|
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

For example, [28] has proved that the asymptotic distribution of adversarial training estimator under bx -epetturration has a positive mass when the underlying parameter is O. Since the sparsity assumption could improve the model interpretation and reduce problem complexity [1]], especially in high-dimensional regimes, fec-perturbation will be studied, and certain sparsity patterns will be assumed in this paper. In terms of the loss function, we focus on the loss in the linear regression, i.e., L(x, y, 3) = (æ: 3 - 2)². In particular, many of the existing theoretical explorations on adversarial training are based on linear models 11 16 21 28 30 31, which admits advanced analytical analysis and sheds light on the characteristics of adversarial training in more general settings and applications. In this regard, the linear regression is considered in this paper. In short, we will focus on the adversarial-traine linear regression as shown in the following:
B E arg min 3 1=1 | So
Σ
max
where ,,, RP and Y, E R. For the convenience of analysis. we write the given n samples (X,, Yi),... (Xn; Yn) in the matrix form: X = (X,,.., X,) Raxp and Y = (Yi.... Y,) e
R=x1, where we call X the design matrix.
This paper delivers the convergence analysis under the high-dimension setting, where we suppose the dimension of the model parameter /3 is larger than the sample size, i.e., p n. Further, the parameter sparsity is assumed. Specifically, we suppose that only a subset of the elements of the p-dimensional ground-truth parameter B. is nonzero. If the size of the nonzero subset is 8, it will be shown that the resulting prediction error of problem (I), i... X B.)11 n, of the order s log under the restricted eigenvalue condition. The restricted eigenvalue condition is a standard assumption in the literature of sparse high-d high-dimensional linear regression [ B 4 17]. Notably, the rate log p/ is optimal in the minimax sense, up to logarithmic factor, for all estimators over class of s-sparse p-dimensional vectors if there are n training samples (20).
Our aforementioned results have the following implications. Firstly, in addition to robustness towards perturbation, our results show that adversarial training is beneficial regarding statistical optimality. This means the resulting estimator can achieve the minimax convergence rate for prediction error. To the best of our knowledge, we are the first to prove the minimax optimality of the adversarial training estimator. Secondly, our analysis illustrates that the fx <e--perturbation is recommended if the sparsity condition, i.e., the ground truth 3. is supported on subset of {1,.... p), is known and fast theoretical error convergence rate is required.
The convergence rate of the group adversarial training is also investigated. In the literature, the group effect has been studied in (finite-type) Wasserstein distributionally robust optimization prob- lems 5 77 Since adversarial training is equivalent to xc-ype Wasserstein distributionally robust optimization problem [9]. the formulation of group Wasserstein distributionally robust optimization problem discussed in |5] can be generalized to the adversarial training problem. We give formal formulation of the group adversarial training problem based on frameworks in (5) 77. Further, we derive the -on-asymptoiic convergence rate of the prediction error for the group adversarial training problem. It will be shown that group adversarial training can achieve a faster convergence upper bound if certain group sparsity structures are satisfied. The details can be found in Section 332
1.1 Related Work
We review and compare some related work in this subsection.
The asymptotic behavior of l.x adversariall training estimator in the generalized linear model has been discussed in (28). Notably, the paper (28) studics the behavior of adversarial training estimator from an asymptotic point of view, while our paper delivers non-asymplotic analysis. More specifically, analysis in (28) is based on the asymptotic distribution of the adversarial training estimator, while our work is to give non-asymptotic upper bound of the prediction error of the adversarial training estimator. More discussions can be found in Remark 2.7
The prediction error of adverrsarll training estimator has been briefly analyzed in (21), where the proven convergence of the order 1/vn in terms of n. The results our paper are different in the following two perspectives. Firstly, faster convergence rate of the order 1/n in terms of given, and the associated rate is minimax optimal up to a logarithmic factor. Secondly, we have incorporated the sparsity setting in the model analysis, while no sparsity pattern is considered in
2

---

theoretical analysis for -adversaaal training in [2T] More discussions can be found in Remark
2.8
The paper 30 also investigates the convergence of adversarial training estimator in linear regression.
The derivations in 30 are based on the assumption that the input variable X follows p-dimensional Gaussian distribution while our analysis imposes the restricted eigenvalue condition. In addition, notice that [30] argues the superiority of incorporating the sparsity information by deriving lower bounds for the estimator error while we directly prove the rate optimality of the adversarial training estimator under the sparsity assumption. Also, 30 applies fz-perturbation while our work focuses on Lo perturbation.
In the literature, it has been proven that multiple estimators, including LASSO, Dantzig selector, and square-root LASSO, can achieve the minimax rate (up to a logarithmic factor) in high-dimensional sparse linear regression 8 4 20). However, the best of our knowledge,
literature has investigated this property for the widely used adversarial training model. We are the first to study whether the adversarial training estimator can be minimax optimal, and our theoretical analysis implies that the answer is yes, i.e. the adversarial training estimator under loo -perturbbaaonn enjoys rate optimality. In addition, the group lasso has been intensely studied to explore the parameter group structure [7 (2) while group adversarial training imposes group structure on the perturbation. It will be shown that the group adversarial training estimator shares a similar convergence rate with the group LASSO estimator. Our proof technique is developed upon and extends the technical methods the aforementioned papers
1.2 Notations and Preliminaries
We introduce some notations, which will be used in the rest of the paper. For vector z E RP, we use ||=||, to denote the l, norm of the vector z, i.e., || = ン |zy1%,1 S q < 0o, || |0x S. p. to denote the basis vectors where the jth component is I and 0 otherwise. In E Rax= denotes the identity matrix. For some set S, use S to denote the complement set of S and [S] to denote the cardinality of S. If the set S is the subset of (1, p). we use 25 E |l to denote the subvector indexed by elements of S.
maxı</<p |z,|. We use e, E 18,15
We clarify some preliminary settings that will be used in this paper. Throughout this paper, we suppose the high-dimension setting holds, the samples are generated from the Gaussian linear model, and the design matrix is normalized. We conclude these conditions with the following assumptions:
Assumption 1.1 (High-dimension). The parameter dimension p is larger than the sample size n, i.e. we have < p.
Assumption 1.2 (Gaussian linear model). The design matrix X is fixed and the response vector Y is generated by the following: Y =XB. + e, where e. has i..dd entries (10 o²).
Assumption 1.3 (Normalization). The design matrix is normalized such that [|eell S for
1 S S
1.3
Organization of this Paper
The remainder of this paper is organized as follows. Section 2 we derive the convergence rate of the adversarial training estimator in high-dimensional linear regression. In Section we derive the convergence rate of group adversarial training and compare it with the existing adversarial training. Numerical experiments are conducted in Section 4 Possible future work is discussed in Section The proofs are relegated to the Appendix whenever possible.
2 loc -e-Adversarill-Trinnnn Linear Regression
In this section, we will first introduce the problem formulation of the adversarial training in linear regression under perttururbaii and then deliver the convergence analysis of the prediction error under foc perturrbatio in the high-dimensional setting.
3

---

2.1 Problem Formulation
In this subsection, we give the problem formulation of auddersarill-traiiinnn linear regression and discuss its dual.
Recall that the aaveesrraa training problem in linear regression has the formulation shown in I The solution the optimization problem (T) is used to estimate the ground- truth data generating parameter S.. seeing Assumption 1.2 In the inner optimization problem, we compute the worst-case square loss between the response variable and the linear prediction among the perturbations, The
perturbations are added to the input variable and with the largest & -nomm& 6. In the outer optimization problem, we optimize the empirical expectation of the worst-case loss of given samples.
The optimization problem |I can be further simplified by considering its dual formulation, which is
shown as follows [2 Proposition I].
Proposition 2.1 (Dual Formulation of problem (T). If we denote the optimal value of problem by R(6). then have that
R min n Σ (x,
Y,1 +1111111
(2)
We discuss the advantages and theoretical insights we could get by considering the dual problem 2
Note that the dual formulation ( removes the inner maximization of problem (I). and the associated
objective function is convex function of 3. Thus, it will be more convenient solve the dual problem 2 than the primal problem [T. Also, the expansion of the objective function in (2) yields the following:
min 1 [X 3 12) + 811311
Σ
(2 2 Σ x 3 - Yil + 8 5811811
where the residual term 8118112 will be of high order if we let 8, for example, be proportional to the inverse of a positive power of n. Regardless of the high order residual term, the objective function in problem (2) can be viewed as the sum of the loss function in linear regression and regularization term depending on || 1- This implies that - -rriiind linear regression has regularization effect. We refer to 121 28) and references therein for more discussions about the regularization effect of adversarial training. Since the well-known LASSO is formulated by imposing the L noomm regularization term and enjoys the minimax convergence rate of the prediction error 20) the dual formulation (2) of fa adversarial training in linear regression and its expansion 33) may indicate a fast convergence of its prediction error for the adversarial training estimator.
2.2 Convergence Analysis
In this subsection, we will first introduce the restricted eigenvalue condition and then derive the convergence rate of the prediction error for the adversarial training estimator in high-dimensional linear regression under the restricted eigenvalue condition and -ertturturaation. We will also discuss the high-probability arguments upon which we prove the optimality of the associated adversarial training estimator.
Before we deliver the convergence analysis, we make the following assumption.
Assumption 2.2 (Restricted Eigenvalue Condition). The matrix X E Raxp satisfies the restricted eigenvalue condition if there exists positive number = 7 01) > 0 such that
|S] S s,s, E RP\ (0). Uss s calluslli 2%
min
V
where S is some subset of (1,....P)
In the sequel, we use the notation RE(s, (1) to denote the restricted eigenvalue condition w.r.t the cardinality of the index set S and the constant cj in the constrained cone, i.e., ||us= ll I ct /llsllli The restricted eigenvalue condition can be considered as a relaxation of the positive semidefiniteness of the gram matrix X X and is useful technique in theoretical analysis in the sparse high-
dimensional analysis 11
Equipped with Assumption 2.2 we have the following convergence result of prediction error.

---

Theorem 2.3 (Prediction Error Analysis for Adversarial Training). problem satisfies
Suppose the adversarial training
2 X clloo
S 6.
(4)
|E||]
If B. is supported on subset S of {I.... p} where [S| S 8, and the design matrix X satisfies
RE(s,3) with parameter 7(s, 3), then we have that
9
|el|| n
1x B.)1 S 35 max 2n
1644|
(s,
Theorem 2.3 shows that the upper bound of the prediction error mainly depends the sparsity cardinality s of the ground-truth parameter 3. and perturbation magnitude 6. The perturbation mag- nitude 8 assumed be equal to larger than ||| e' /|>=//||||1 We could apply the concentration inequalities to give closed-form expression of the perturbation magnitude, based on which the convergence rate of the prediction error is derived. The convergence rate holds with high probability and can be found in the following corollary.
Corollary 2.4. Consider the adversarial training problem with perturbation magnitude
4
logp
8
(5)
10
If 19 is supported on subset S of {1,....p) p} where (S) S 8, and the design matrix X satisfies
RE(s,3) with parameter (18, 3), then we have that
1 -3x3333115 192 2n
log
2 ||c||| n
max
(x,3)
1164|
(6)
n
holds with probability greater than 2 exp (Cin)) - 2/p. where C1 is positive constant.
Remark 2.5. We discuss the choice of 8. Corollary 2.4 implies that the perturbation magnitude 5 should be of the order 1/ /n in order to derive the non non-asymptotic convergence rate (6). The associated order is consistent with the asymptotic analysis in 128), where the sparsity- ability could be proven in the asymptotic sense if the sample size is of the order //.n.
In Corollary 2.4
we choose 8 shown in (5). Under this setting, it can be proven that the inequality holds with a high probability. Then, we adopt Theorem 2.3 and could have the expression of the prediction in terms of p and n as shown in (6).
The convergence rate could be further simplified in the following corollary if both the error variance 2² and the E -ormm of the ground-truth parameter 3. are bounded.
Corollary 2.6. Under the assumptions stated in Corollary 2.4 constant such that
suppose there exists finite positive
2v 2v41 s R,
σ< 6
(s,3)
then we have that
- -3 B.)13 < 192
blog P n
nt2
2n
holds with probability greater than constant.
2/p - exxp (-xpn)) where C₁ is positive
Remark 2.7. Corollary 2.6 investigates the behavior of the adversarial training estimator under lo perturbationn by computing the resulting prediction ervor while (28) studies the behavior of the adversarial training estimator under Eoc pertturbbation by deriving the associated limiting distribution. Both (28) and our results consider the sparsity condition. (28) proves that Eox -ddversarial training can help recover spursity asymptotically if the parameter spursity is known while our paper, i.e., Corollary 2.6 provides a fast non-asymptotic convergence rate for prediction error under the sparsity condition.
5

---

Remark 2.8. Corollary 2.jillustreaee that the convergence rate of prediction error &o aadvesarial training in linear regression is of the order s log p/n while the prediction error shown in 12T] has lower order 1/v/n in terms of Our paper achieves a faster rate by incorporating the sparsity information and applying the restricted eigenvalue condition.
Corollary 2.6 implies that the prediction error of high-dimensional & addersarial trainee estimator is of the order logp/n. This order is optimal up to a logarithmic factor in the minimax sense for any estimators over a class of s-sparse vectors in R' when n samples are given 20).
3 Group Adversarial Training
This section will elaborate on the formulation of group adversarial training and the associated convergence rate. Also, we compare group adversarial training under (2, peerturbatioon with classic adversarial training under &x fe--peeturbation.
Since the adversarial training forces the perturbation with uniform magnitude each component of the input variable, it may not perform well if the input variable has a group effect. The group structure exists in many real-world problems. For example, groups of genes act together in pathways in gene-expression arrays [18] and financial data can be grouped by different sectors and industries help market prediction [6]. Also, an input variable is multilevel factor and dummy variables
are introduced, then these dummy variables act in a group [32]. Group adversarial training can tackle the group effect by adding group-structured perturbation. The detailed formulation can be seen in Section 3.1
3.1 Problem Formulation
In this subsection, describe the formulation of the group adversarial training.
Suppose the input variable æ can be divided into non-overlapped groups. Then, we have the definition of the group-structured weighted norm accordingly in the following proposition, where the associated dual norm also stated.
Proposition 3.1 (Proposition 5 in [5). Theorem 2.2 in 77). Consider a vector x = (z=",..,,ar x where each x² E RPI, and Σt= Pt p. Define the weighted (r, s)-momm of x with the L-dimensional weight vector w (wi,,..,,1,) wI, ). to be:
1/8
n lire
Σ |wra'l |1
max &wlllooe
Ilwa'llrr I|r,
00,
ISISL
where W1 0, vl and 1. Then, the dual norm of (r, 8)-norm with weight is the (q, -)-rrrm with weight - = 10 (1/w1,..., 1/WL), Lee || where 1/r + 1/9 and 1/8 + 1/t 1.
To handle the group structure in the input variable, the weighted (r, -nomm is applied to add group structure in the perturbation accordingly, and the group adversarial training is formulated follows.
Σ sup
((X++)) Yx)² --),
min =
Aull..,
where w = (Wi, W.).
Recall we focus on adversarial training problems under foo perturbation, high-dimension setting, and sparsity condition. Under this consideration, we let s = oo and = 2, and then the associated group adversarial training problem under (2, pertturrbattion has the following expression:
min 3 71
sup |A 28
+ A)
To facilitate convenience for the computation and analysis, similar to our study towards classic
adversarial training in Section 2. we derive the dual formulation of problem 7 in the following proposition. One can check that the corresponding objective in the dual formulation convex.
( is also

---

Proposition 3.2 (Dual Formulation of problem 7 If we denote the optimal value of problem by R(6), then have that
R(6)) min
(I(X; + A)
Y, 511Bw-1 112.1)
(8)
where
11 ||,11
| 1//1/2 1
3.2 Convergence Analysis
In this subsection, deliver the convergence analysis of the prediction error of the estimator obtained from group adversarial training under (2, perttuubbbaatinn, i.c., problem
First, we clarify some notations for subsequent analysis. In terms of the group structure of the input variable and the perturbation, we focus on non-overlapped cases, Assume that the index set {1,... p} has the prescribed (disjoint) partition [l,...,p} = U G₁. We use to denote the cardinality of each group, i.e., G1| Pt-
Consider the group sparsity structure the ground-truth parameter 3, E RP, where sparsity is imposed at the group level instead of individual components. Specially, the set J {1,..., L} denotes a set of groups and B. is supported at these J groups, i.e., 8. is supported on the G. Ule, Gt-
We make the following assumption before we proceed to derive the convergence analysis. Assumption 3.3 (Group Restricted Eigenvalue Condition). The matrix X R satisfies the group restricted eigenvalue condition if there exists a positive number & = k(g, 02) > 0 such that
Xell
min
Vallva ll2
1 S g.Ue R (10) IEJc
RM
Σ
la
5 0
Wi
K.
IEJ
where J is some subset of (1...,,.}, L].
In the sequel, use the notation GRE(g, 02) denote the restricted eigenvalue condition w.r.t. the cardinality g of the index set J and the constant C2 in the constrained cone, i.e., Σle 1 ||l'|la s 02 Eies + || ||2. Group restricted eigenvalue condition is an extension of the restricted eigenvalue condition and can used in the theoretical analysis for the group LASSO, seeing [17].
Theorem 3.4 (Prediction Error Analysis for Group Adversarial Training). Consider the group adversarial training problem 7 satisfying
211 X
E)
ll2
8
VI.
||||]
W1
If 33 is supported on a subset G, of (1,...p} where
|J] S and the design matrix X satisfies
GRB(g, 3) with parameter nggg, 3), then we have that
|elli 2
2n - < 38
Σ LEJ
max
164 12
k. 3)
where 3 is the estimator obtained from solving problem
Theorem 3.4 shows that the upper bound of the prediction error mainly depends on the weight w and perturbation magnitude 6. We apply the arguments in concentration inequalities and obtain the convergence rate in the following corollary.
Corollary 3.5. Consider the group adversarial training problem
satisfying
5
2
3p: + 9 9log L
V1,
W1
T0
7

---

and - -,, Xa./n = Ipippo where XG, denotes the n. X pt sub-matrix of X formed by the columns indexed by Gt. If 3r is supported on a subset G. of {L, p} where |J| S 9. and the design matrix X satisfies GREig, 3) with parameter x(g.3) 3), then we have that
1 1x(3-B.11 S 432 2n
GGyl + glog max
9
2 [|e]1a
1644
n
1² (s,
n2
holds with a probability greater than 2 exp (-Cin) L/ where C1 a positive constant.
Remark 3.6. Note that we assume the gram matrix satisfies that XG, Xx. /n = ppppe This is standard assumption in the theoretical analysis in sparse high-dimensional linear regression, seeing 77
Similar to the analytic investigations in Section 2 be further simplified in the following corollary the f--norm of the ground-truth parameter B, and error variance o² are bounded.
the convergence rate of the prediction error could
Corollary 3.7. Under the assumptions stated in Corollary constant such that
3,5
suppose there exists finite positive
2 2/4T S R
k(g.3)R,
then we have that
1
GG + g log R²
X B.)11 < 432
2n
holds with probability greater than 1 2/2 - 2exp (-Cin) exp(-n)), where C₂ is positive constans.
Remark 3.8. we make the number of groups equal to p. ie., each group only has one component, then we will have that L = P.P = G, 9. The resulting error bound is g log p/n, where denotes the number of nonzero components of B.. This order matches what is derived in Corollary 2.6
indicates that the upper bound of the associated prediction error in group adversarial training under (2, sertpuruuraaio is of the order (|Gu] + g log L) Recall that L is the number of prescribed groups for the p-dimensional variable, the ground-truth parameter 3x E IR is supported by subset of the L groups, and the subset is denoted by J C {1.....I L}. The cardinality of the support subset J is g. We also use G2 C {l. p} to denote all the indexes included in J.
Corollary 3.7
It follows from Corollary2..jthat 2.6tthat the convergence rate of the prediction error for the classic adversarial training under fox Tec-perturbatin is of the order s log p/n, where denotes the cardinality the support set of 3.. Then, we can conclude that if |Grl/s s < log p and g << 8, the group adversarial training superior to the classic adversarial training. In essence, if the sparsity pattern B. has a good group structure, i.e., most of the nonzero components can be captured in J, then the group adversarial training procedure can provide an improved upper bound for the prediction error.
Numerical Experiments
In this section, we will numerical experiments to observe the empirical performances of (group) adversarial training in high-dimensional linear regression.
We consider the following models to generate synthetic data: The response variable Y is generated by the Gaussian linear model, as stated in Assumption 1.2 The standard deviation of the error e is chosen as 0.1. In Model 1, the ground truth parameter 3. is a 500-dimensional vector. The first four components are [0.1, 0.2, 0.15, 0.25]. the last four components are [0.9, 0.95, 1, 1.05), and the other components are zero. In Model 2, the ground truth parameter 3_ is a 600-dimensional vector. 0.6]. The last three components of B. correspond to
The first three components of 3, are f0.4. 0.5.0.6] dummy variables generated from four-level categorical factor. These dummy variable components are assigned values [0.2, 0.3, 0.7]. The other components are zero.
We run adversarial training under f-c-perturbation and group adversarial training under (2, oo)- perturbation to give the estimations for the ground-truth parameter 3.,, respectively. As suggested in Corollary 2.4 and Corollary 3.5 the perturbation magnitude is chosen in the order of 1/ /n in the
8

---

adversarial training: the ratio of the perturbation magnitude and the perturbation weight is chosen in the order of L the group adversarial training. For the constant, we selected for simplicity and experimental convenience. For the group adversarial training, we divide the parameter equally into 125 groups of size for Model and 200 groups of size for Model 2. The sample sizes are chosen (50, 100, 150, 200, 250, 300, 350, 400) for Model and {50, 100, 150, 200, 250. 350, 450, 550) for Model 2. In terms computation, we apply the dual formulations, i.e. problem 2 and problem (8). and solve these convex optimization problems using the CVXPY toolbox g Five random samples are generated at each sample size, and we run (group) adversarial training for each sample. The mean and standard error of the coefficient estimations and prediction emorr computed and recorded.
We first plot the coefficient estimation paths of adversarial training with error bars in Figure and Figure 2 Both adversarial training and group adversarial training can shrink the parameter estimation, while group adversarial training performs better shrinkage effect, addition, the final values that the coefficients converge to are annotated in the figures. Given the ground-truth non- zero values [0.1, 0.15, 0.2, 0.25, 0.9, 0.95, 1, 1.05) and [0.4, 0.5, 0.6, 0.2, 0.3, 0.7]. the final values of group adversarial training are closer to the ground-truth, indicating that the group adversarial training output more accurate estimations.
We also plot the curve of log10 (prediction error) versus 1og10 (sample size) with error bars in Figure 3 and Figure 4 We can observe that the slopes of two curves are approximately equal to -1, which consistent with our theoretical analysis, where we have proved that the prediction error for high- dimensional (group) adversarial training is of the order 1/'n in terms of the sample size n. Further, the curves and error bars of group adversarial training are below those of adversarial training, indicating the superiority of group adversarial training. This conclusion also consistent with our theoretical analysis that if the model has good group structure, group adversarial training has lower order of prediction error.
Adversarial Training
Group Adversarial Training
1022
0.96
Extimation
Estimatioon
0.6
0.6
0.4
0.-
0.21
0.2
813
0.06
0.6
0.0
Sample Size
Sample Size
Figure Coefficient Estimation Path in Model
Adversarial Training
Group Adversarial Training
0.7
0.7
0.56
0.57
0.5
0.5
0.48
Essmation
0.4
0.6
0.27
324
0.2
024
014
0.0
100
150
200
250
300
600
500
50
100
150
200
250
300
350
400
450
500
Sample Size
Sample Size
Figure 2: Coefficient Estimation Path in Model 2

---

Prediction Error
Prediction Error
2.0
Group Adversarbl Triniing Acversaial Trining
Group Aoversaro Traninng
-2.0
Aeversar al Traniig
-22
-24
(oglError)
(oglError)
-2.4
-2.6
-2.0
-2.8
3.0
-12
3.2
3.4
-34
log(Sample Size)
logiSample Size)
Figure 3: Prediction Error in Model
1
Figure 4: Prediction Error in Model 2
5
Discussions
This paper reveals the statistical optimality of adversarial training under for -eertuuruaiiio in high dimensional linear regression and discusses potential improvements that can be achieved by group adversarial training. In the future, we may generalize the analysis in linear regression to broader statistical models, e.g., the generalized linear model and other parametric models. Also, since the prediction errors are investigated in this paper, will consider analyzing estimation errors as next step. More advanced analytical future work may use the primal-dual witness technique for the non-asympiotic variable-selection analysis.
Acknowledgments and Disclosure of Funding
The authors would like thank the chairs and anonymous reviewers for their careful comments, which helped enhance the presentation of the manuscript. The authors are partially sponsored by subcontract of NSF grant 2229876, the A. Russell Chandler III Professorship Georgia Institute of Technology, and NIH-sponsored Georgia Clinical & Translational Science Alliance.
References
[1] M. Andriushchenko and N. Flammarion. Understanding and improving fast adversarial training. Advances in Neural Information Processing Systems, 33: 18:16644-1055 2020.
[2] C. Bellec, G. Lecué, and A. B. Tsybakov. Slope meets lasso: improved oracle bounds and optimality. The Annals of Statistics, 46(6B):3603-366) 3642, 2018.
[3] A. Belloni, V. Chernozhukov, and L. Wang Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791-806, 2011.
[4] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, pages 1705-1732, 2009.
[5] J. Blanchet and Y. Kang. Distributionally robust groupwise regularization estimator. In Asian Conference on Muchine Leurning, pages 97-112. PMLR, 2017.
[6] M. J. Chan-Lau. Lasso regressions and forecasting models in applied stress testing. Interna- tional Monetary Fund, 2017.
[7] R. Chen and I. Paschalidis. Robust grouped variable selection using distributionally robust optimization. Journal of Optimization Theory and Applications, 194(3):0422-071, 2022.
[8] S. Diamond and S. Boyd. CVXPY: A python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17, 2016.
10

---

[9] R. Gao and A. Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2):603-655, 2023.
[10] Y. Gao, L. Qin, Z. Song, and Y. Wang. A sublinear adversarial training algorithm. In The Twelfth International Conference Learning Representations, 2024.
[11] Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity. Monographs on statistics and applied probability, 143((43):8, 2015.
[12] D. Hendrycks, K. Lee, and M. Mazeika. Using pre- me--trainng can improve model robustness and uncertainty. In International conference on machine learning, pages 2712-2721. PMLR, 2019.
[13] C. Herrmann, K. Sargent, L. Jiang, R. Zabih, H. Chang, C. Liu, D. Krishnan, and D. Sun. Pyramid adversarial training improves vit performance. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13419-13422 2022.
[14] X. Hu, P.-Y. Chen, and T.-Y. Ho. Radar: Robust Al-text detection via adversarial learning. Advances in Neural Information Processing Systems, 15775-555 2023.
[15] A. Javanmard and M. Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4)22127-2556 2022.
[16] A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoff's in adversarial training for linear regression. In Conference Learning Theory, pages
PMLR, 2020.
[17] K. Lounici, M. Pontil, S. van de Geer, and A. B. Tsybakov. Oracle inequalities and optimal inference under group sparsity. The Annals of Statistics, pages 2164-2204, 2011.
[18] G. Malenová, D. Rowson, and V. Boeva. Exploring pathway-based group lasso for cancer survival analysis: a special case of multi-task learning. Frontiers in Genetics, 12:771301, 2021.
[19] Y. Nardi and A. Rinaldo. On the asymptotic properties of the group lasso estimator for linear models, Electronic Journal of Statistics, 2:605-633, 2008
[20] G. Raskutti, M. Wainwright, and B. Yu. Minimax rates of estimation for high-dimensional linear regression over ly balls. IEEE Transactions information theory, 57(10):6976-6994 2011.
[21] A. Ribeiro, D. Zachariah, F. Bach, and T. Schön. Regularization properties of adversarially- trained linear regression. Advances in Neural Information Processing Systems, 36, 2023.
[22] A. Robey, Latorre, J. Pappas, H. Hassani, and Cevher. Adversarial training should be cast as non-zero-sum game. In The Twelfth International Conference on Leurning Representations, 2024.
[23] A. Shafahi, M. Najibi, M. A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L. S. Davis, G. Taylor, and T. Goldstein. Adversarial training for free! Advances in neural information processing systems, 32, 2019.
[24] E. Shayegani, M. A. A. Mamun, Y. Fu, P. Zaree, Y. Dong, and N. Abu-Ghazaleh. Survey of vulnerabilities in large language models revealed by adversarial attacks. arXiv preprint arXiv:2310.10844 2023.
[25] V. N. Vapnik, V. Vapnik, et al. Statistical learning theory. 1998.
[26] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[27] 7. Wang, T. Pang, C. Du, M. Lin, W. Liu, and S. Yan. Better diffusion models further improve adversarial training. In International Conference on Machine Learning, pages 36246-36263. PMLR, 2023.
[28] Y. Xie and X. Huo. Asymptotic behavior adversarial training estimator under pertuuruuaaaioon. arXiv preprint arXhv:2401.1522, 2024.

---

[29] Y. Xing, Q. Song, and G. Cheng. On the algorithmic stability of adversarial training. Advances neural information processing systems, 34:26523-26533. 2021.
[30] Y. Xing, R. Zhang, and G. Cheng. Adversarially robust estimate and risk analysis linear regression. In International Conference on Artificial Intelligence and Statistics, pages 514-522. PMLR, 2021.
[31] D. Yin, R. Kannan, and P. Bartlett. Rademacher complexity for adversarially robust generaliza- tion. In International conference machine learning, pages 7085-7094. PMLR, 2019.
[32] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, (661), 2006.
[33] S. Zhou, C. Liu, D. Ye, T. Zhu, W. Zhou, and P. S. Yu. Adversarial attacks and defenses in deep learning: From perspective of cybersecurity. ACM Computing Surveys, 55(8):1-39, 2022.
12

---

Appendix
A Proof of Theorem 2.3
We first give the upper bound of the [| in terms of ||3.|11.
Lemma A.I (Upper Bound of 1111), Under conditions stated in Theorem 2.3 we have that
| S 911..111.
Proof. The proof of this lemma follows a similar approach to the proof of Theorem in 2T follows from the first-order condition of dual formulation ② of the adversarial training problem that
0
X X 3 n
Y)
+ 5 |
|| B
Y Y |1 2,
where
2; x
3
YI, w/ 01
Then, we take the dot product of both sides of equation ( with 3 3. and could have the following:
x3 - 33)11
7
(x 3.)) c- 531|3 || T(3 B.)
- -1
8
- Tlw B.)
11 -3.)) 2,
-
n
72
n2
(x 3.)) - 8 ||
31
w B.
TBB
1 Y
_
111
1
+
5
| Yll T..
n
n
8
1311 - 1 5
T
(2)
||/h11 3 - 8111 - 111331 + 8²
111113111
X 111111 + I
Y 11111.111
2n.
|3
Y -11 ||//|1/
19 5
2| - 1l11) + - = Y 1111118.111 +
8
|||11(11@11 + 11.31111)
2n
- 1311 + 1
9 8 1811 3 x - 8.)111 3 [ + -1 - 1111113.111 +
5
(11311 + 11..
2n
- 1 + 11
(4)
( B.)1 2 |1 1
+ 113.1111)
|||| 1 11812 + 2 -18.111)-52118)) + 6 1111311111..11
3
(10)
where (a) comes from the Hölder's incquality, i.c.
(x(3-B))) < |13 X c/ w TTB. B. < ||m|| || 118.111 -cT 2 ||||||||=||0 |||]]
and the condition X ell /|c//2 S 5, (b) comes from from the relationship that
- 11.11 || 11 || 1I. (c) comes
x 3 YI
| Y 2 - x +
and (d) comes from the inequality that X B1)11 + ||<||a.
X X
B+)
Vnl
X (3 B.)1l2 and || Y S
One may observe that (10) is a second-order inequality of variable | (3 -3.)12/ Tū, then the associate discriminant should be equal to larger than 0, resulting in
(-13(1 + 1811..11) 2 0. 1 8 (- | + 661| 911..1117 + 3n
9
13

---

from which we could conclude that at least one of two terms should be equal or larger than 0, implying
|| 911..111.
Then, we proceed to prove Theorem 2.3
Proof.
We write the objective function in (2 in the matrix norm and then have that
Y IY x 11 -| X |33 S 2n
|
- x
|| 11. 1
-11 X 1.11111..111
2n
(11)
It follows from Y = XB, + c, i.e., Assumption 1.2 that
Y - -33.11 = ||
Y x31 = | B.) < = Xx B.)1 + ||E| - -2ET x (3 BB),
|Y - x111 = x ( - 3.) - -c11 2 ||<|| | -B.)111-
In this way, the inequality (T) could be reformulated as
X (B 3.)1
2n
1
T Tx@ -8.))++++ + 1= - 1.)11111111 + ||el/a (118.111 -11111) +
1
18.11 101811
1
<
n
2
2
(a)
$
n
1
| c/lx01 11x113-100 - 3.111 + ||x 11)11111311 + n
n
||||| (118..11 (118.11-1133) 11.311 +
2
1
8
18.11
1
2
8
||e|l1113 -3.112 - +
5
X (3- -111111111111
+ 6 -|l||
- (11.112-11311) 2
18.1
2
1
1
2n
2
[|e],
x 33 12 - [||] (118- - (118111-111111)) + 1 8 11.1.11
1113
1
2
2n
n
(12) 8.
where (a) comes from the Hölder's inequality, (b) comes from the condition ||| <l| /|
(c) comes from X B.)1l1 S v X 32)
Then, we begin to give the upper bound of the prediction error. Two cases should be discussed.
First Case:
|1 - -8-1--11, + 2|13-111
2|13 S.
(13)
In this case, we have that
||8.111 - || = 11,3 || + 211331111 - 211 S 113 -.111 + 2113.111 211/31| S.. (14)
Then, it follows from (1) that
X (3 - 3,)12
2n
8
||<||/ 133 - -Ball1 +
8 X 3.)1221131
8 ||]|] (11.%.111 - -13111 + 2 1/.113.11
2 11131
1
$
+
2n
Vn
n
5
||||a (18--3.11 2113.111 21(1111
5
x B.)11211111 + 2 1
1
1 1
v
2n
x - 3.) 1211111
where the last incquality comes from 13 and
14
Lemma A. indicates that
X
3
B.)1l2 S
v261 s 9V22||18.11.
2n
14

---

which is equivalent to
-3 < 1628 < 1620>|S113-111 = 1626 16222>|13.18 $113.112 2n
(15)
Second Case:
-11 2 0. || 3 1 211
(16)
we let 0 = 3 - B., then we have that
|| B||1 ||0|| |60|| + |1 112.
11.111 - [|3 = 113. (11..g 0sll + [0 [11 - |ss [s Il
The inequality (16) indicates that
6|/ || 1|a
|| - B.ll1 2118.111 2113111 0,
(17)
implying
0g |1 - 8| ll1.
In this way, the RE(s,3) condition can be applied. In addition, it follows the inequality 12 that
X (3 3.)1
2n
$
8
||<||a 13
-Ball1+ +
3.)12113112 + [
8 ||c|l1 (1,8,111- - 11111) + 2 811111111 1 2
8311311
2n
vn
n
(0)
- 1 1 +
[ B.)1 + 831 + _ |||||1 (11.--11 - 11811) + 11113111
3
1
2n
4n
2
8
||||| (113 - 3.111 + 2|| - 2113111 + 4n x B.)1 + 1 011..111 - 131
2n
(
36
1
||||
|s||| |
x B.)112 + 4162 1| 12
2n
4n
where (a) comes from the inequality
5
X 3 3.)13 6 z
X 11)11111311
4n
vn
(b) comes from (17) and Lemma A.1
Further, we have that
38
x (3 -
B.)113 <
|| + 416
4n
2n
(18)
38
Vs
||||
B.)112 + 4188s|1B.13 |
2 2/ (s,3)
n
where the first inequality comes from ||0 S inequality comes from the RE(s,3) 3) condition and S...
S and || S / || 1l2. and the last
Then, we solve the inequality (8). we could have that
8/8
3 ||l|]
2 [E]l]
x - -2)122 <
+
9
+ (s)
n
which is equivalent to
6/3
|Ella n
x 3.)112 - (1+ v2)
/1647(5,3)113.
max
7 3)
15

---

indicating that
1
82s
(Ieell1) n
2 )
(3
3.)1 S
max
(19)
2n
(s. 3)
Combining
11
and
19 we have that
9 (s,
||l|]1 n
2
X B
B.)1 S
35 max
164418..11
2n
B Proof of Corollary 2.4
Proof. To give the high probability result, should analyze the bound of the term || // The associated arguments are discussed in the following two parts, respectively. (Note that assume has i.idd Gaussian entries. However, Bub-Gaussian cases, as sub-Gaussian variables share similar tail decay behavior.)
ellooo/ and
gigh-prbbbbilityy result can be extended to
Part I: We focus on the tail bound of || X e/lx//n. Since the design matrix X is normalized, the random variable æ e/n is stochastically dominated by (O, a² 22/n.. As shown in Theorem 11.1 in follows from the Gaussian tail bound and the union bound that
X
nt²
P
2
2t
2xxp
+ logp
20
In this way, with a probability greater than 2/p. the following holds
| |lcc 20
logg
n
Part II: We focus the concentration inequality of ||||| /n. It follows from general Hoeffding's inequality 26 that
|Ell
no
2
21
< 2exp
-C2
t
no
indicating
2
ntt2
P
|e]||
2t
< 2 exp
-02
o2
where C2 is some positive constant. By choosing / == a 0/10, have that
2
P
a
V
|e|l
2 1 - exx (-Cin),
10
where C₁ some positive constant. This is to say, with a probability greater than 1 - 2exp (-Cin). we have that
2
V
|lll.
10
Suppose we let
4
log
8
2
n
with probability greater than 1 - 2 exp
(- Cin) 2/p, we have that
X Elloo <.
||]||1
follows from Theorem 2.3 that
3.) 192 log
||]|]
2
.114 3.13
2n
n
max
3)(
holds with probability greater 2 exp (-Cin) - -2/p.
16

---

C Proof of Corollary 2.6
Proof. We focus on the tail bound of ||eli/n. We apply the Chernoff bound give the tail bound of ||e|], and we have that
P [[||]] 2 t) inf M (s) exp(-ts),
#20
where Ms) is the moment-generating function of ||<|/. We also could obtain that
a²s²
M,(s) Elexp(s|e,)) < 2[(exp(se,]] 2 exp
2
indicating
no=
M(s) S 2" exp
2
Then, we have that
!no2s²
P ([|E|] 2 f) s inf 2" exp
ts
830
2
indicating
|elllz 21) S exp
(-20²
nt² + n log 2
In this way, with probability greater exp( the following holds:
|E|l1 S 2og 2 + 20 S 20.
Since we have that (7(83)) 2
9
|||||
S R²
(s, 3)
n
holds with probability greater cxp(pxpp n). Due Corollary 2.4 we have the following
log R2
X
3,) 11 - 192
2n
holds with probability greater
2/p - 2 expp Cin) (xp(-n))
D Proof of Proposition 3.2
It follows from Proposition 1 in 21 that
R(6)
min
Σ
Yii 811 11))2
71
where ||- ||+ denotes the dual norm of (2, onomm of Bw. Due to Proposition 3.1 conclude that (8) holds.
E Proof of Theorem 3.4
We first give the upper bound of the [| 1|2,1 in terms of [|B. 11|2,1-
Lemma E.1 (Upper Bound of || - 1)2 Under conditions stated in Theorem 3.4 we have that
|
112,,1 -91,----111..1
Proof. The proof of this lemma follows a similar approach to the proof of Lemma A. It follows from the first-order condition of the dual formulation (8) of the group adversarial training problem that
1 X n
Y) 8
1
ll,
||x
Y 11 +
1135 2 TT T2, n
(20)
17

---

where
2, a|xe 3 Yl.
3r
t = س1 1 1112,19
wi 11
Notice we have that
B = Σ wi 13
Σ 1=1 wl
11 = 11 1112,1,
(21)
and it follows from the Hölder's inequality that
TB)
1
BT
|| = ||3- -1/2,1
(22)
1311
Also, we have the following from the Hölder's inequality:
(x(3-B.))
Σ |lx |((TTe) e)'lla113' 3.112 - 2
L
1
L Σ
113 B. -
wl
1=1
(23)
where the second inequality comes from the condition 2||
(x e) ||2/||||1 S 8/wr.
Then, we take the dot product of both sides of equation 20 with 8 - B. and could have the following:
x (B- - 33)11
(X B.)) Te E- "8-2211 -1,,tt (3- B.)
| - 1lli 3x) -
8 18 (12, -3.))))
n
(
(x -B)) c - 11,,1 + 5 1/1 12,1 T
B.
5
X3 Y Y111 11211
+ 1llitTB. B. - n
+
8
_
5
1 - ||2.11 X Y| + n
11 11,,1 TT=
n
(6)
8
||||| l| (3) - 8.) 12,1 13
11,, + + 1|,, || ||2.1 -11X3-X1111 1111 112,1
2n
2 11 |||2,1113 Y| + 8 11 Tl2,,e
+ + [ - 111113.. 1112,1-
(98 8 18 (1l2,(1|e||1 2| 111) +
_
| 3 1|11113. 112,,1
n
n1
8
|
[e]1((1]8@111 112,1 + 11,3 l12.1) 8 1/ 3 11,, + + 118.-111,,111..00 1l2.1
2n
1| - 1|2,11 3 ||[|]) _ X
18 1la1 3
X - B.)11
8
+ 2n
[<]12(1] 11,,1 + 1| (1211) 8 1,333 11, +
881 ||211111 11 11 1|2.1
(0)
(3 -B.)112( 5 1 11,,1 + |1 (1,,1)
- -|ell1
8
1
11
11
3
11 112,))
2
- 1 112, + 13, 11a.1113-w-111aa
(24)
where (a) comes from and (b) comes from 2
(c) comes from |1(30 3 5
|| + -| Il (d) comes from 2 X 3 - Y
I - Y 2 - - X (3 3,) +
à |||c|| (e) comes from the inequality that X [ {.) S /nl X B.) and X Y S
XX (3 B1) + |||||
18

---

Since the inequality (24 is a second-order inequality of variable |X --)111///// then the associate discriminant should be equal to larger than 0, resulting in
- (-11111 11-11118--111 1 66||3. 112.111/// 11,,1 + 9113.--111 1
+ 3n
|||| 1111111 12,1 + 18| (2,11) 2 0,
from which we could conclude that
||3 1,--1122 112,1 $ 9 3=| 112,1
Then, we proceed to prove Theorem 3.4
Proof. We write the objective function in in the matrix norm and then have that
X
||| + 8
11
+ lly
x 31118---111 1|2,1
2n
2
(25)
5 11 - 113.1a11...0- 112.11
$ 2n
1y
x3. + 11113-m 112,1
n
In this way, we have the following reformulation:
x (3 - 3+]13
2n
-6 TX -8.) + 11-1X X - (.)11
ll,, + [|||| (118mw-1l2) -113w- (12.1)
n
+ 1
112,1 -
1 11
1
2
8
[ella/(68
1112,1
3.)1lll) 112,1 + [|ella (118mw 1112,1 - -11 =112.1)
2n
Vn
+ 8² 1/. 112,1
521
12.1
2
(26)
where the last inequality comes from (33 and - (-)1l S Vn|xX33 (1x(3-B.)) B.)
Similar to the proof of Theorem 2.3 we begin to give the upper bound of the prediction error. Two cases should be discussed.
First Case:
(I@3 8r) 112,1 + +111 Il,,1 -211 112,1 S O.
(27)
In this case, we have that || 22.1 - 113--1112. 5 11(3 -B4) 11122.++000 + 3 - 211Bw-1 S
(28)
follow from 266 that
x (3 - 3.)11
2n
$
2n
8
||<||a 1(3 Ba)
10--1122 112,,11
Vrl
((3-3.)12211) 11,,11 + [|el/1 (118mw 11/2,1 - 11 112,11
1 82
82
1112,1
10133--1113
2
Vil
-2.) 120.112,11
+
2n
||ell1 (I(33 84)w-1/2.1 + B1 11,,,1 -21 112.1
112,
8
1
11.
2
x(3 - 12 1|2.1:
(29)
19

---

where the last inequality comes from
27 and 28
Notice have that
| 1 2,
Σ IEJ
||
Σ
ug 11B.l12-
(30)
wi
Lemma E.1
29
and
30 indicate that
X (3 3.)1 & 1625 13 1 12,1 I 1626
Σ
IEJ w/ 118.112.
(31)
2n2
Second Case:
II(3 3.) 112,,111 + -1133--- 111,,1111111 -211 11,111 2 0.
Notice we have that
L
11@3 - B.) 2.1
-11 113 - 11112 = Σ
Σ 11 - 3,) +
1
Σ -
|1 3.)
wi
IEJ wi
IEJ
110 -- 112,1
- -113w-1 11w-1112,
11,
Σ
B. ll2
Σ
13 l2
W1
wt
IEJ
1=1
Σ
11
11 + Σ 11 B.)
Wi
1EJ
NEJ
LEJ
11
3.)112
Σ
1
|1 B. 8.)2
W1
wi
NEJ
IEJc
we let T =B - then we have that
3
1
1 2 11(3 - 3.)
11,11 + 211 1 -1 112,1 2 0, (32)
[EJ
L
indicating
Σ
Σ 13
3
Σ
1: 112-
leje wi
IEJ
In this way, the GRE(g. 3) condition can be applied.
We also have the following from (6
X (8 -.)112
2n
<
X - B.)11 -1:11113---111 12,1 +
2n ||e/|2 (118aw 11/2,1 - -1380-1 12,1 + +211(3
B.)w- ll2.1
8
1113.aw 12,1
- 5
112_1
36 ||=||
1
1
1 ~
| -3.)113
+
| 1| +
1/ 112,1
11
4n
2n
Wi
2
IEJ
(b) 1
38
|||||
1
x
(8
3.113
LG ll2 +
8
11
+
8 12
4n
2n
2
2
where (a) comes from
32 and (b) comes from
Σ SL
lo. 12.
[eJ
20

---

It follows from GRE(g. 3) and Lemma E.1 that
-
1 B.)1 S
33
|ella k(g,3)
(3 Bo)1l2 + 410
Σ
11 12.
4n
2/n
w/
w/
[JJ
1EJ
Then, we could have that
8²
[|E||]] ((1llt) )
2
X (3
B.)1
max
9
1616 (g. 3)
(33)
2n
R² (g.
3)
wi
n
IE.
Combining
31
and
33 we have that
|||||1 )
2
x33 B.)1 - 38
.1641 1.
max
2n
wi
IEJ
Proof of Corollary 3.5
It follows from Lemma 3.1 in 17 that
2o
[[
E) e) S
Vn V tr(()) + 2|| v (4log + 22p, log L)
holds with a probability greater than 2/ L, tr( tr( (1) denotes the trace of v, and || |ill denotes the maximum eigenvalue of 1/,- Since 1 pi Xpo have that I |l Consequently, we have that
1 and tr( pt-
2 [ 1) S
20 Vn
20 3pr log L, Pr 2o + 2pr log L) S
Vn
holds with probability greater than L/LL. Also, it follows from the proof of Corollary 2.4 that
1 |e|l
10
holds with probability greater - 2 exp (-Cin). Suppose we let
3pp + 9 log L
W1
we have that
2| X E)² 12 8
|||/
W1
holds with probability greater than exp It follows from Theorem 3.4 that
(-Cin) - 2/ L.
1
9
||||||
( 3.)11 < 4882
1641133.1
2n
w
(g 3)
m
lej
3pr 9og
L
||||]] 2
< 48
max
n
k: (s, 3)
n
IeJ
G
g
log
9
||E||]
432
max
R (x,3))
1144|
n
n
G Proof of Corollary 3.7
Corollary 3.7
straightforward due to Corollary 3.5 and the upper bound arguments in the proof in
Corollary 2.6
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claim is that the convergence rate of the prediction error of adversarial training estimator under foc perturbation achieve the minimax rate up logarithmic factor in the nigh-dimensional linear regression on the class of sparse parameters. We also discuss the group adversarial training. These contributions, including important assumptions, are clearly stated in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have mentioned the limitations and future work Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
22

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results in this paper are written mathematically rigorous with full set of assumptions, and all associated proofs can be seen in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have mainly made theoretical contributions. However, some numerical experiments are also provided. Full experimental settings have been stated in the paper. Our results can be reproduced from the submitted code in the Supplementary Materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
23

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our numerical experiments are based on synthetic data. The code has been submitted in the Supplementary Materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://niis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 //nips. /tipsscc/ppb..... httpcccpccccccceeeeeeeeeeeeeeeee wwwlcc/guiiss//C/eee http:/guuiidee/oCoSubbbbiiii
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All settings are specified in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper has reported the error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our numerical experiments do not require any workers, and our numeri- cal experiments compare prediction errors achieved by different approaches instead of computation speed or storage.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/://euurrpp...ppppp/e/////
Answer: [Yes]
Justification:
The research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
25

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:NNa
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "HXe2AVDbx6", "reviewer": "Reviewer_CJZh", "summary": "The paper studies adversarial training in high-dimensional linear regression under $\\ell_\\infty$-perturbations and group adversarial training. The paper also provides non-asymptotic consistency analysis.", "questions": "- The proof of Corollary 2.4 uses Gaussian tail bounds. Can the proof be generalized for sub-Gaussian distribution?   \n\n- Are the bounds derived in Corollary 3.5 or 3.6 tight? Meaning, can the authors show the equivalence to the bounds derived in Corollary  2.4 or 2.5 by making the number of groups = 1 in Corollary 3.5 or 3.6?  \n\n- Line 55: what is the sparsity condition exactly? \n\n- Line 65: What is the certain group sparsity structures exactly?", "limitations": "- At the end of Section 3, the authors claim that the inferences made are similar to the differences between Lasso and group Lasso. If that is the case, what are the new insights that the proposed theoretical analysis is bringing in? It seems like a paper that rigorously verifies the expected results, which have been well explored in the literature for similar methods like Lasso and group Lasso. \n\n- The equality assumption on $\\delta$ or $\\frac{\\delta}{w_l}$ in Corollary 2.4 or Corollary 3.5, respectively, seem quite restrictive. Is the theoretical analysis not useful for any other $\\delta$? Any form of upper bound or lower bound on $\\delta$ could have been more helpful. \n\n- If I understand correctly, the paper analyzes the particular case of $r = 2$ and $s = \\infty$ only. But the problem is defined for general $r$ and $s$ in proposition 3.1 and equation after line 233. It gives the wrong impression to the reader that the problem is analyzed for general $r$ and $s$.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The associated convergence rate of prediction error achieves a minimax rate up to a logarithmic factor. The authors also claim that group adversarial training offers a better prediction error upper bound under certain group-sparsity patterns.", "weaknesses": "- Remark 2.8: The authors say that they improve the convergence rate of the prediction error from $\\frac{1}{\\sqrt{n}}$ to $\\frac{1}{n}$. Is the improvement possible only due to the additional assumption of restricted eigenvalue condition and sparsity information? If so, it should be clearly stated in the abstract and introduction. Otherwise, it gives the wrong impression or over-claims that the improvement is achieved without any additional assumptions. \n\n- Is the weight vector $\\mathbf{w}$ defined in line 234 assumed to be known in group adversarial training? If so, it should be stated clearly as an assumption. If not, does an algorithm exist to estimate it? The results are obviously heavily dependent on this parameter.  \n\n- The abstract can be improved by including more technical information about the specific contributions. For example, is the analysis improving any rates as compared to the existing literature? If so, what specific theoretical analysis or assumption helped to achieve that improvement? For example, the last line in the abstract mentions certain group sparsity patterns. It would be helpful if the authors could explain more about this particular sparsity pattern so that a reader gets an understanding of whether the requirement is restrictive or easily achievable. \n\n- Line 30: The authors could probably clarify with more technical details why existing literature thinks that $\\ell_\\infty$-perturbations can be helpful in recovering sparsity. \n\n- Line 87-97: It is repetitive.  \n\n- Line 229 has typo: $s = \\infty$  should be used in underscore.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer's careful and detailed comments on our work. We hope our responses and clarifications can address the reviewer's concerns!\n\n**Comment 1** ...improve the convergence rate......clearly stated in the abstract...\n\n**Response**\nThe reviewer is correct that the order improvement is based on the restricted eigenvalue condition, a standard assumption in the literature of sparse high-dimensional analysis. We also assume that the ground truth parameter $\\beta_\\ast\\in\\mathbb{R}^p$ is supported on a subset of {1,...,p}. We will revise the abstract and introduction to state these assumptions more clearly. \n\n**Comment 2** Is the weight vector $\\mathbf{w}$ defined in line 234 assumed to be known in group adversarial training?...\n\n**Response** $\\mathbf{w}$ is a hyperparameter and does not need to be estimated. Additionally, in the order analysis presented in Corollary 3.5, the error upper bound no longer depends on $\\mathbf{w}$.\n\n**Comment 3** The abstract can be improved by including more technical information about the specific contributions...\n\n**Response** The main contributions in this paper are:  (a) We are the first to show that adversarial training can achieve minimax optimality. We prove this under the restricted eigenvalue condition. (b) We analyze the group adversarial training and prove that it enjoys a better prediction error bound when group sparsity patterns are known.  The group sparsity pattern means that the variables act in groups, and sparsity exists at the level of groups of variables instead of individual variables. The group patterns exist in many real-world problems. For example, groups of genes act together in pathways in gene-expression arrays. Also, if an input variable is a multilevel factor and dummy variables are introduced, these dummy variables act in a group. We will make all these assumptions and contributions clearer in the abstract.\n\n**Comment 4** The authors...why existing literature thinks that $\\ell_{\\infty}$-perturbations can be helpful in recovering sparsity.\n\n**Response** [26] has proved that the asymptotic distribution of adversarial training estimator under $\\ell_\\infty$-perturbation has a positive mass at $0$ when the underlying parameter is $0$. Other types of perturbation do not have this property. We will state these technical details carefully in our revision.\n\n**Comment 5 and 6** Line 87-97: It is repetitive. Line 229 has typo...\n\n**Response:**\nWe will revise these lines.\n\n\n**Comment 7**  ...Can the proof be generalized for sub-Gaussian distribution?\n\n**Response**  Corollary 2.4 can be generalized to sub-Gaussian distributions since sub-Gaussian distributions share similar tail behavior with Gaussian distributions. We will revise the proof to include the generalization for sub-Gaussian distributions.\n\n**Comment 8** Are the bounds derived in Corollary 3.5 or 3.6 tight?..\n\n**Response:** Thanks for pointing this out. The bounds derived in Corollary 3.5 or 3.6 are tight. If we make the number of groups equal to $p$, i.e., each group only has one component, then we will have that $L=p,p_l=1, \\vert G_J\\vert=g$. The resulting error bound is $g\\log p/n$, where $g$ denotes the number of nonzero components of $\\beta_\\ast$. This order matches what is derived in Corollary 2.4 or 2.5. We will conclude these as a remark under Corollary 3.5 and 3.6. \n\n**Comment 9** what is the sparsity condition exactly?\n\n**Response** The sparsity condition means that the number of non-zero coefficients is less than the total number of coefficients, i.e., the ground truth $\\beta_\\ast\\in\\mathbb{R}^p$ is supported on a subset of {1,...,p}. We will clarify this definition in the revision.\n\n**Comment 10** What is the certain group sparsity structures exactly?\n\n**Response** The group sparsity structure means that sparsity is enforced at the group rather than at the individual level. \nSpecifically, suppose the index set {1,...,p} has the prescribed (disjoint) partition {1,...,p}$=\\bigcup_{l=1}^L G_l$. \n$J\\subset$ {1,..., L} denotes a set of groups and $\\beta_\\ast\\in\\mathbb{R}^p$ is supported at these J groups, i.e., $\\beta_\\ast$ is supported on the  $G_J=\\bigcup _{l\\in J}G_l$.\n\n**Comment 11** ...the inferences made are similar to the differences between Lasso and group Lasso..what are the new insights that...\n\n**Response** Our work focuses on the adversarial training problem, which is inherently different from the Lasso problem, and our contributions are (1) the adversarial training is minimax optimal, and (2) group adversarial training can improve the error bound. These conclusions have never been explored in the literature. We mention and correlate adversarial training with LASSO because both LASSO and $\\ell_\\infty$-perturbed adversarial training could recover sparsity and achieve the minimax convergence rate. In this way, it is not surprising that the theoretical error bounds of (group) adversarial training are consistent with (group) LASSO. We will add these discussions to avoid confusion.\n\n**Comment 12** The equality assumption on $\\delta$ or $\\frac{\\delta}{w_l}$ in Corollary 2.4 or Corollary 3.5, respectively, seem quite restrictive...\n\n**Response** $\\delta$ should be in the order of $1/\\sqrt{n}$ to make the corollaries hold due to the structure of the concentration inequality of Gaussian distribution. We admit that this setting seems to be restrictive. But we would like to interpret this result as a recommendation of order choice. That is to say, the order of $1/\\sqrt{n}$ is recommended in order to achieve the fast convergence rate. This order choice is also recommended in the literature [26] to achieve sparsity, seeing Remark 2.5 in our paper. \n\n\n**Comment 13** If I understand correctly, the paper analyzes ... gives the wrong impression to the reader that the problem is analyzed for general $r$ and $s$.\n\n**Response** The reviewer is correct. Thanks for pointing this out. We will clarify the scope of our analysis more clearly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CETVPPHGxM", "reviewer": "Reviewer_6XeH", "summary": "This paper provided an theoretical analysis for the optimality of adversarial training methods on linear regression, and further explored the advantages of the group adversarial training method, comparing with general adversarial training method. There are also experiments supporting their points.", "questions": "See weakness.", "limitations": "No negative social impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The paper is well-organized with clear statement. The contributions are stated clearly, and it is easy to follow the logic and flow of the paper.\n\n2.The theoretical results are discussed detailedly, which helps to understand the theorems.", "weaknesses": "1.As the paper is mainly focused on empirical errors, the contributions seem to be not enough. It is better to extend the results on test error analysis, which may be more interesting.\n\n2.The tightness of such upper bounds in main theorems has not been proved.\n\n3.The linear model seems to be quite constrained, it is recommended to extend to random feature models or other neural network models, such as two-layer NTK or diagonal network.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer's insightful comments. We hope our response and clarifications can address the reviewer's concerns!\n\n**Comment 1:** As the paper is mainly focused on empirical errors, the contributions seem to be not enough. It is better to extend the results on test error analysis, which may be more interesting.\n\n**Response to Comment 1:**\nThanks for the reviewer for pointing out this. We clarify the error framework used in this paper as follows.\n\n\n1.\nWe are using the prediction error, $\\frac{1}{n}\\Vert \\mathbf{X}(\\hat{\\beta}-\\beta^\\ast) \\Vert_2^2$ ,instead of the empirical error. \nIn the framework of the non-asymptotic high-dimensional statistical analysis, the prediction error is typically used, seeing [1-4]. The prediction error can help us directly quantify the derivation in $\\hat{\\beta}$ from $\\beta^\\ast$.\n\n\n2. The prediction error, $\\frac{1}{n}\\Vert \\mathbf{X}(\\hat{\\beta}-\\beta^\\ast) \\Vert_2^2$, is also called 'in-sample' prediction error. The 'test error' mentioned by the reviewer may be referred to as the 'out-of-sample' prediction error. We provide explanations for why the in-sample prediction error is usually preferred in high-dimensional analysis as follows.\nFirstly, high-dimensional settings typically involve situations where the number of input variables is much larger than the number of observations. In such cases, splitting the data into training and test sets can result in very few observations in the test set, making out-of-sample prediction errors unreliable.\nSecondly, the in-sample prediction error will enable the application of the concentration inequality, resulting in explicit probabilistic bounds analysis. Thus, in-sample prediction error can admit advanced theoretical analysis.\n\n\n[1] Wainwright, Martin J. High-dimensional statistics: A non-asymptotic viewpoint. Vol. 48. Cambridge university press, 20\n\n[2] G. Raskutti, M. J. Wainwright, and B. Yu. Minimax rates of estimation for high-dimensional linear regression over lq-balls. IEEE Transactions on information theory, 57(10):6976–6994,\n373 2011.\n\n[3] P. C. Bellec, G. Lecué, and A. B. Tsybakov. Slope meets lasso: improved oracle bounds and optimality. The Annals of Statistics, 46(6B):3603–3642, 2018.\n\n[4] K. Lounici, M. Pontil, S. van de Geer, and A. B. Tsybakov. Oracle inequalities and optimal inference under group sparsity. The Annals of Statistics, pages 2164–2204, 2011.\n\n**Comment 2:** The tightness of such upper bounds in main theorems has not been proved.\n\n**Response to Comment 2:**  Thank you for your comment regarding the tightness of the upper bounds in our main theorems. We appreciate the opportunity to clarify this point.\nThe upper bounds in our main theorems are indeed tight, as we have demonstrated that the error of the adversarial training can achieve the minimax rate. Specifically, the error order in our paper is $s\\log p/n$, which matches the minimax lower bound given in [2,19] (the references in our paper), seeing Line 206-208. We hope this explanation addresses your concern.\n\n\n\n\n**Comment 3:** The linear model seems to be quite constrained, it is recommended to extend to random feature models or other neural network models, such as two-layer NTK or diagonal network.\n\n**Response to Comment 3:**\nThanks for the reviewer's valuable suggestions on possible extensions.\nThe reason we focus on the linear model is that it will allow advanced analytical analysis.\nIt will make the problem mathematically tractable and provide clear insights.\nFor example, this paper proves the minimax optimality for adversarial training under $\\ell_\\infty$-perturbation, conveying the direct message that adversarial training is statistically optimal.\nMoreover, the linear model could serve as an essential starting point for understanding more complex models. For example, it is well-known that training dynamics of wide neural network can be approximated by the linear model through neural tangent kernel. \nWe appreciate your suggestions for the extensions.\nThe extensions to the more complex models are very promising but may require intensive additional proof work, so we will consider the extensions seriously in our future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jYI5MS8r0F", "reviewer": "Reviewer_J4Ez", "summary": "The paper provides a high-dimensional analysis of Linear Regression in Adversarial training. It has two contributions:\n\n1. it proves an improved convergence rate of prediction error of $1/n$  (previous work show $1/\\sqrt{n}$). \n2. It extends adversarial training for the group setting and extend the convergence results for it", "questions": "It is unclear to me why in the numerical experiments what constant is used when setting the perturbation proportional to $1/\\sqrt{n}$? How is it chosen, because I imagine is hard to guarantee in practice that the conditions of Theorem 2.3 are being satisfied.", "limitations": "The paper has no clear societal impact. See weaknesses.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and clear. \n\nThe mathematical results seem to be consistent, and to the best of my knowledge are correct. \n\nThe author authors are very explicit about their contribution and present clear distinction from related work. Particularly, it is well contextualized and compared with [20], [26] and [28].", "weaknesses": "The numerical experiments are the main weakness. Not so many different configurations are tested. Still, since this is mostly a theoretical paper, I don't see this as a major problem. But I believe studying it for different settings could strength the paper\n\nI think the presentation of the numerical results could be somehow improved,\n1. Figure 1 could be interesting to have confidence intervals and also have in the plot the final values that the coefficients converge to.\n2. Figure 2 it would be better to have log 10 base, it is a bit hard to read with ln.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Great thanks for the reviewer's appreciation of our work! Regarding the numerical experimental improvement, please see our response below and the revised figures in the pdf file attached in the global response.\n\n\n**Comment 1**:\nThe numerical experiments are the main weakness. Not so many different configurations are tested. Still, since this is mostly a theoretical paper, I don't see this as a major problem. But I believe studying it for different settings could strength the paper.\n\n**Response to Comment 1**: \nWe appreciate your recognition of the theoretical contributions of the paper. We acknowledge that the numerical experiments could benefit from a wider variety of configurations. \nDue to the page limit of the rebuttal attachments,\nwe will include the results of additional settings in future revisions.\n\n\n**Comment 2**:\nI think the presentation of the numerical results could be somehow improved,\nFigure 1 could be interesting to have confidence intervals and also have in the plot the final values that the coefficients converge to.\nFigure 2 it would be better to have log 10 base, it is a bit hard to read with ln.\n\n**Response to Comment 2**:\nThanks for the suggestions for improving the presentations of our numerical results. We have added the confidence interval, indicated the values of the coefficient converging, and changed to $\\log 10$ base in the figures. Please see the pdf file with the revised figures attached in the global response.\n\nWe have some explanations of the figures as follows.\n\n\nWe plot the curve of $log_{10}$(prediction error) versus $log_{10}$(sample size)  with error bars. We can observe that the slopes of two curves are\n approximately equal to $-1$, which is consistent with our theoretical analysis, where we have proved that the prediction error for high-dimensional (group) adversarial training is of the order $1/n$. Further,\nthe curve and error bar of group adversarial training are below those of adversarial training, indicating the superiority of group adversarial training.\n\nWe also plot the coefficient estimation paths of (group) adversarial training with error bars. Both adversarial training and group adversarial training can shrink the parameter estimation, while group adversarial training performs a better shrinkage effect,\nIn addition, the final values that the coefficients converge to are annotated in the figures. Given the ground-truth non-zero values [0.1, 0.15, 0.2, 0.25, 0.9, 0.95, 1, 1.05], the final values of group adversarial training are closer to the ground-truth, indicating that the group adversarial training output a more accurate estimation.\n\n**Comment 3**:\nIt is unclear to me why in the numerical experiments what constant is used when setting the perturbation proportional to $1/\\sqrt{n}$\n? How is it chosen, because I imagine is hard to guarantee in practice that the conditions of Theorem 2.3 are being satisfied.\n\n**Response to Comment 3**:\nThe reviewer is correct that it is hard to guarantee the conditions in Theorem 2.3 in practice. \nAs noted, we choose the order $1/\\sqrt{n}$ because Corollary 2.4 shows that the minimax convergence rate can be achieved if the perturbation magnitude $\\delta$ is of this order. This order is also recommended in the literature [26] (reference in the paper). For the constant, we selected $1$ for simplicity and experimental convenience. This constant allows us to illustrate the theoretical results effectively without complicating the numerical setup. We will clarify this setting clearly in our future revisions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IaEyDzqScv", "reviewer": "Reviewer_fdf4", "summary": "This paper presents a non-asymptotic consistency analysis of prediction error for the adversarial training procedure under $l_\\infty$ perturbation. It demonstrates that the convergence rate of the prediction error is up to a logarithmic factor. Additionally, the authors prove that the group adversarial training procedure achieves a superior upper bound on prediction error compared to classic adversarial training.", "questions": "See Weaknesses", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper applies the restricted eigenvalue condition and sparsity to deliver a convergence analysis, resulting in a better convergence rate.\n\n2. The authors investigate the convergence rate of group adversarial training and achieve a faster upper bound for convergence.", "weaknesses": "1. The authors aim to connect their conclusions about a linear model to adversarial training, but adversarial training is a defense strategy commonly used in deep neural networks (DNN). The linear model is too simple and specific to accurately represent the behavior of adversarial training. The authors would benefit from studying adversarial training on a simple two-layer neural network or a convex function, not just the linear model.\n\n2. The convergence rate for a linear model, as presented, is insufficient to illustrate the behavior of adversarial training effectively.\n\n\n3. The points in Lines 142-145 lack supporting literature.\n\n4. From Theorem 2.3 and Corollary 2.4, the authors derive a convergence rate of order $\\frac{1}{n}$. Moreover, in Remark 2.8, the authors claim that the prediction error in [20] has a lower order $\\frac{1}{\\sqrt{n}}$. However, from Theorem 2 in [20], the convergence rate is also $\\frac{1}{n}$ if $\\delta\\propto \\frac{1}{\\sqrt{n}}$ as your setting. The conclusion in this paper is very similar to that of [20]. While the restricted eigenvalue condition and sparsity might accelerate the convergence rate, I don’t see an improvement in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer's comments on our work. We hope the following responses and clarifications can address the reviewer's concerns!\n\n**Comment 1**  \nThe authors aim to connect their conclusions about a linear model to adversarial training, but adversarial training is a defense strategy commonly used in deep neural networks (DNN). The linear model is too simple .... network or a convex function, not just the linear model.\n\n**Comment 2**  \nThe convergence rate for a linear model, as presented, is insufficient to illustrate the behavior of adversarial training effectively.\n\n**Response to Comment 1 and 2**  \nAlthough the linear model seems simple, exploring the linear model is still common and crucial in the development of machine learning theories. Many existing works, e.g., [1-5], and our paper focus on the linear model for the adversarial training procedure. We explain the reasons as follows: Firstly, the linear model admits advanced analytical analysis. It will make the problem mathematically tractable and provide clear insights. For example, the minimax optimality for adversarial training under $\\ell_\\infty$-perturbation is proved in this paper, conveying the direct message that adversarial training under $\\ell_\\infty$-perturbation is statistically optimal. Moreover, the linear model could serve as an essential starting point for understanding more complex models. For example, it is well-known that the training dynamics of the wide neural network can be approximated by the linear model through the neural tangent kernel. Also, we want to emphasize that we are the first to prove the minimax optimality of the adversarial training in the linear model. We believe that this contribution has pushed the frontier of adversarial training theoretical exploration.  \nWe appreciate the reviewer’s consideration of this perspective and hope our clarifications underscore the rationale behind our focus on linear models and the significance of our contribution to the statistical theory of adversarial training.\n\n[1] A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pages 2034–2078. PMLR, 2020\n\n[2] A. Ribeiro, D. Zachariah, F. Bach, and T. Schön. Regularization properties of adversarially-trained linear regression. Advances in Neural Information Processing Systems, 36, 2023\n\n[3] H. Taheri, R. Pedarsani, and C. Thrampoulidis. Asymptotic behavior of adversarial training in binary linear classification. IEEE Transactions on Neural Networks and Learning Systems, 2023\n\n[4] A. H. Ribeiro and T. B. Schön. Overparameterized linear regression under adversarial attacks. IEEE Transactions on Signal Processing, 71:601–614, 2023\n\n[5] E. Dobriban, H. Hassani, D. Hong, and A. Robey. Provable tradeoffs in adversarially robust classification. IEEE Transactions on Information Theory, 2023\n\n\n\n**Comment 3**  \nThe points in Lines 142-145 lack supporting literature.\n\n**Response to Comment 3**  \nLine 142 - Line 145 are the analysis of Equation (3), which is a direct expansion of Equation (2). In the literature, this phenomenon has been referred to as the \"regularization effect.\" We have mentioned the relevant literature in Line 146.\n\n\n**Comment 4**  \nFrom Theorem 2.3 and Corollary 2.4, the authors derive a convergence rate of order $\\frac{1}{n}$. Moreover, in Remark 2.8, the authors claim that the prediction error in [20] has a lower order $\\frac{1}{\\sqrt{n}}$. However, from Theorem 2 in [20], the convergence rate is also $\\frac{1}{n}$ if $\\delta \\propto \\frac{1}{\\sqrt{n}}$ as your setting. The conclusion in this paper is very similar to that of [20]. While the restricted eigenvalue condition and sparsity might accelerate the convergence rate, I don't see an improvement in this paper.\n\n**Response to Comment 4**  \nThe rate derived in [20] is $\\frac{1}{\\sqrt{n}}$ rather than $\\frac{1}{n}$. We would like to provide the following explanation: The upper bound of the error in [20] is given by  $8\\delta\\Vert\\beta^\\ast\\Vert_1\\left(\\frac{1}{n}\\Vert\\varepsilon\\Vert_1 + 10\\delta \\Vert\\beta^\\ast\\Vert_1\\right), $\nwhich can be written as:  \n$$ 8\\delta\\Vert\\beta^\\ast\\Vert_1\\frac{1}{n}\\Vert\\varepsilon\\Vert_1 + 80\\delta^2\\Vert\\beta^\\ast\\Vert_1^2. \\quad \\quad \\quad \\quad \\quad (1)$$ By choosing $\\delta \\propto \\frac{1}{\\sqrt{n}}$, the order of the first term in (1) is $\\frac{1}{\\sqrt{n}}$. A common misunderstanding regarding the order of $8\\delta\\Vert\\beta^\\ast\\Vert_1\\frac{1}{n}\\Vert\\varepsilon\\Vert_1$ may come from the term $\\frac{1}{n}\\Vert\\varepsilon\\Vert_1$. At first glance, $\\frac{1}{n}\\Vert\\varepsilon\\Vert_1$seems to have the order $\\frac{1}{n}$. However, since $\\varepsilon$ is an $n$-dimensional vector, the resulting order of $ \\Vert\\varepsilon\\Vert_1$ should be $n$, indicating the order of $\\frac{1}{n}\\Vert\\varepsilon\\Vert_1$ is $O(1)$ instead of $\\frac{1}{n}$. Therefore, the order of the first term in (1) is $\\frac{1}{\\sqrt{n}}$. Consequently, the overall order of the error bound should be $\\frac{1}{\\sqrt{n}}$.  \nFor further clarification, please refer to the last paragraph on Page 8 in [20], where the authors claim that their order is $\\frac{1}{\\sqrt{n}}$:  \n> \"For $ \\lambda \\propto M \\sigma \\sqrt{(\\log p) / n}$, we (with high probability) satisfy the condition in Theorem 3, obtaining: $\\frac{1}{n}\\Vert X(\\widehat{\\beta} -\\beta^*)\\Vert_2^2 \\lesssim M \\sigma \\sqrt{(\\log p) / n}$. For adversarial training, we can set: $\\delta \\propto M \\sqrt{(\\log p) / n}$, and (with high probability) satisfy the theorem condition, obtaining the same bound,\"  \n\nwhere the same bound denotes $M \\sigma \\sqrt{(\\log p) / n}$, which has the order of $\\frac{1}{\\sqrt{n}}$.  \n\nGiven that our proved order is $ \\frac{1}{n}$, **we believe our paper demonstrates an order improvement.**  We hope our explanations address the reviewer's concern and clarify the contribution of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We have revised the figures for the numerical experiments as requested by Reviewer J4Ez. Please see the attached pdf file.

Meta-review: This paper mathematically studies sparse linear regression under adversarial training.  I am happy to recommend acceptance, however I request that the authors pay close attention to the many comments and criticisms stated by the reviewers; for example, as a purely presentation issue discussed heavily by the reviewers, it is very odd to give the rate as $1/n$ rather than $s \ln p / n$ which is the hallmark of sparse linear regression.  Thank you!
Decision: Accept (poster)