High-dimensional (Group) Adversarial Training in Linear Regression

Authors: yiling  xie
xiaoming  huo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 03:49:01

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.

Main paper: 
 introduction: 
 Adversarial training is proposed to hedge against adversarial perturbations and has attracted much research interest in recent years. Adversarial training has been widely used in Large Language Models [14, 24] , computer vision [13] , cybersecurity [33] , etc. While the empirical risk minimization procedure optimizes the empirical loss, the adversarial training procedure seeks conservative solutions that optimize the worst-case loss under a 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, 10, 12, 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-learning models is to 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 highdimensional 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 β 1 n n i=1 sup ∥∆∥≤δ L (X i + ∆, Y i , β) ,where (X 1 , Y 1 ), ..., (X n , Y n ) are given samples, ∆ is the perturbation, ∥ • ∥ is the perturbation norm, δ is the perturbation magnitude, β is the model parameter, and L(x, y, β) is the loss function with x being the input variable and y being the response variable.Regarding the choice of the perturbation norm, we focus on ℓ ∞ -perturbation, i.e., ∥∆∥ = ∥∆∥ ∞ . Some literature has pointed out that ℓ ∞ -perturbation could help recover the model sparsity [21, 28] .For example, [28] has proved that the asymptotic distribution of adversarial training estimator under ℓ ∞ -perturbation has a positive mass at 0 when the underlying parameter is 0. Since the sparsity assumption could improve the model interpretation and reduce problem complexity [11] , especially in high-dimensional regimes, ℓ ∞ -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, β) = (x ⊤ β -y) 2 . In particular, many of the existing theoretical explorations on adversarial training are based on linear models [15, 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-trained linear regression as shown in the following:EQUATIONwhere X i , β ∈ R p and Y i ∈ R. For the convenience of analysis, we write the given n samples (X 1 , Y 1 ), ..., (X n , Y n ) in the matrix form: X = (X 1 , ...,X n ) ⊤ ∈ R n×p and Y = (Y 1 , ..., Y n ) ⊤ ∈ R n×1, 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 β 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 β * is nonzero. If the size of the nonzero subset is s, it will be shown that the resulting prediction error of problem (1), i.e., ∥X( β -β * )∥ 2 2 /n, is of the order s log p/n under the restricted eigenvalue condition. The restricted eigenvalue condition is a standard assumption in the literature of sparse high-dimensional linear regression [2, 3, 4, 17] . Notably, the rate s log p/n is optimal in the minimax sense, up to a logarithmic factor, for all estimators over a 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 ℓ ∞ -perturbation is recommended if the sparsity condition, i.e., the ground truth β * is supported on a subset of {1, ..., p}, is known and a 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 problems [5, 7] . Since adversarial training is equivalent to ∞-type Wasserstein distributionally robust optimization problem [9] , the formulation of group Wasserstein distributionally robust optimization problem discussed in [5, 7] can be generalized to the adversarial training problem. We give a formal formulation of the group adversarial training problem based on frameworks in [5, 7] . Further, we derive the non-asymptotic 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 3.2.We review and compare some related work in this subsection.The asymptotic behavior of ℓ ∞ -adversarial training estimator in the generalized linear model has been discussed in [28] . Notably, the paper [28] studies the behavior of adversarial training estimator from an asymptotic point of view, while our paper delivers a non-asymptotic analysis. More specifically, analysis in [28] is based on the asymptotic distribution of the adversarial training estimator, while our work is to give a 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 ℓ ∞ -adversarial training estimator has been briefly analyzed in [21] , where the proven convergence is of the order 1/ √ n in terms of n. The results in our paper are different in the following two perspectives. Firstly, a faster convergence rate of the order 1/n in terms of n is 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 theoretical analysis for ℓ ∞ -adversarial training in [21] . 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 ℓ 2 -perturbation while our work focuses on ℓ ∞ -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 [3, 4, 11, 20] . However, to the best of our knowledge, no 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 ℓ ∞ -perturbation enjoys rate optimality. In addition, the group lasso has been intensely studied to explore the parameter group structure [17, 32] 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 in the aforementioned papers [3, 4, 11, 17] .We introduce some notations, which will be used in the rest of the paper. For vector z ∈ R p , we use ∥z∥ q to denote the ℓ q norm of the vector z, i.e., ∥z∥q q = p j=1 |z j | q , 1 ≤ q < ∞, ∥z∥ ∞ = max 1≤j≤p |z j |.We use e j ∈ R p , 1 ≤ j ≤ p, to denote the basis vectors where the jth component is 1 and 0 otherwise. I n ∈ R n×n denotes the identity matrix. For some set S, we use S c 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 z S ∈ R |S| to denote the subvector indexed by elements of S.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 n < p. Assumption 1.2 (Gaussian linear model). The design matrix X is fixed and the response vector Y is generated by the following: Y = Xβ * + ϵ, where ϵ has i.i.d. entries N (0, σ2 ).Assumption 1.3 (Normalization). The design matrix X is normalized such that ∥Xe j ∥ 2 ≤ √ n, for 1 ≤ j ≤ p.The remainder of this paper is organized as follows. In Section 2, we derive the convergence rate of the adversarial training estimator in high-dimensional linear regression. In Section 3, 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 5. The proofs are relegated to the Appendix whenever possible.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 ℓ ∞ -perturbation can achieve the minimax rate up to a logarithmic factor in the high-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 be 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 as long as it is clear that these goals are not attained by the paper. 
problem formulation: 
 In this subsection, we give the problem formulation of ℓ ∞ -adversarial-trained linear regression and discuss its dual.Recall that the ℓ ∞ -adversarial training problem in linear regression has the formulation shown in (1) . The solution β to the optimization problem (1) is used to estimate the ground-truth data generating parameter β * , 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 ℓ ∞ -norm δ. In the outer optimization problem, we optimize the empirical expectation of the worst-case loss of given samples.The optimization problem (1) can be further simplified by considering its dual formulation, which is shown as follows [21, Proposition 1]. Proposition 2.1 (Dual Formulation of problem (1) ). If we denote the optimal value of problem (1) by R(δ), then we have thatEQUATION)We discuss the advantages and theoretical insights we could get by considering the dual problem (2) . Note that the dual formulation (2) removes the inner maximization of problem (1), and the associated objective function is a convex function of β. Thus, it will be more convenient to solve the dual problem (2) than the primal problem (1) . Also, the expansion of the objective function in (2) yields the following:EQUATIONwhere the residual term δ 2 ∥β∥ 2 1 will be of high order if we let δ, 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 a regularization term depending on ∥β∥ 1 . This implies that ℓ ∞ -adversarial-trained linear regression has a regularization effect. We refer to [21, 28] and references therein for more discussions about the regularization effect of adversarial training. Since the well-known LASSO is formulated by imposing the ℓ 1 -norm regularization term and enjoys the minimax convergence rate of the prediction error [20] , the dual formulation (2) of ℓ ∞ -adversarial training in linear regression and its expansion (3) may indicate a fast convergence of its prediction error for the adversarial training estimator.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 ℓ ∞ -perturbation. 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 ∈ R n×p satisfies the restricted eigenvalue condition if there exists a positive number γ = γ(s, c 1 ) > 0 such thatmin ∥Xv∥ 2 √ n∥v∥ 2 : |S| ≤ s, v ∈ R p \{0}, ∥v S c ∥ 1 ≤ c 1 ∥v S ∥ 1 ≥ γ,where S is some subset of {1, ..., p}.In the sequel, we use the notation RE(s, c 1 ) to denote the restricted eigenvalue condition w.r.t. the cardinality s of the index set S and the constant c 1 in the constrained cone, i.e., ∥vS c ∥ 1 ≤ c 1 ∥v S ∥ 1 .The restricted eigenvalue condition can be considered as a relaxation of the positive semidefiniteness of the gram matrix X ⊤ X and is a useful technique in theoretical analysis in the sparse highdimensional analysis [11] .Equipped with Assumption 2.2, we have the following convergence result of prediction error. If β * is supported on a subset S of {1, ..., p} where |S| ≤ s, and the design matrix X satisfies RE(s, 3) with parameter γ(s, 3), then we have that1 2n ∥X( β -β * )∥ 2 2 ≤ 3δ 2 s max 9 γ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2Theorem 2.3 shows that the upper bound of the prediction error mainly depends on the sparsity cardinality s of the ground-truth parameter β * and perturbation magnitude δ. The perturbation magnitude δ is assumed to be equal to or larger than 2∥X ⊤ ϵ∥ ∞ /∥ϵ∥ 1 . We could apply the concentration inequalities to give a closed-form expression of the perturbation magnitude, based on which the convergence rate of the prediction error is derived. The convergence rate holds with a high probability and can be found in the following corollary. If β * is supported on a subset S of {1, ..., p} where |S| ≤ s, and the design matrix X satisfies RE(s, 3) with parameter γ(s, 3), then we have thatEQUATIONholds with a probability greater than 1 -2 exp (-C 1 n) -2/p, where C 1 is a positive constant.Remark 2.5. We discuss the choice of δ. Corollary 2.4 implies that the perturbation magnitude δ should be of the order 1/ √ n in order to derive the non-asymptotic convergence rate (6). The associated order is consistent with the asymptotic analysis in [28] , where the sparsity-recovery ability could be proven in the asymptotic sense if the sample size is of the order 1/ √ n.In Corollary 2.4, we choose δ as is shown in (5) . Under this setting, it can be proven that the inequality (4) holds with a high probability. Then, we adopt Theorem 2.3 and could have the expression of the prediction error 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 ℓ 2 -norm of the ground-truth parameter β * are bounded.Corollary 2.6. Under the assumptions stated in Corollary 2.4, suppose there exists a finite positive constant R such that2 √ 41∥β * ∥ 2 ≤ R, σ < 1 6 γ(s, 3)R, then we have that 1 2n ∥X( β -β * )∥ 2 2 ≤ 192 s log p n R 2holds with a probability greater than1 -2/p -2 exp (-C 1 n) -exp(-n), where C 1 is a positive constant.Remark 2.7. Corollary 2.6 investigates the behavior of the adversarial training estimator under ℓ ∞ -perturbation by computing the resulting prediction error while [28] studies the behavior of the adversarial training estimator under ℓ ∞ -perturbation by deriving the associated limiting distribution. Both [28] and our results consider the sparsity condition. [28] proves that ℓ ∞ -adversarial training can help recover sparsity asymptotically if the parameter sparsity is known while our paper, i.e., Corollary 2.6, provides a fast non-asymptotic convergence rate for prediction error under the sparsity condition.Remark 2.8. Corollary 2.6 illustrates that the convergence rate of prediction error for ℓ ∞ -adversarial training in linear regression is of the order s log p/n while the prediction error shown in [21] has a lower order 1/ √ n in terms of n. 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 ℓ ∞ -adversarial-trained estimator is of the order s log p/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 p when n samples are given [2, 20] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We have mentioned the limitations and future work in Section 5.Guidelines:• The answer NA means that the paper has no 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 a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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, ∞)-perturbation with classic adversarial training under ℓ ∞ -perturbation.Since the adversarial training forces the perturbation with uniform magnitude to 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 to help market prediction [6] . Also, if an input variable is a 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.In this subsection, we describe the formulation of the group adversarial training.Suppose the input variable x can be divided into L non-overlapped groups. Then, we have the definition of the group-structured weighted norm accordingly in the following proposition, where the associated dual norm is also stated. Proposition 3.1 (Proposition 5 in [5] , Theorem 2.2 in [7] ). Consider a vector x = (x 1 , ..., x L ), where each x l ∈ R p l , and L l=1 p l = p. Define the weighted (r, s)-norm of x with the L-dimensional weight vector ω = (ω 1 , ..., ω L ) to be:∥x ω ∥ r,s = L l=1 ∥ω l x l ∥ s r 1/s , 1 ≤ s < ∞, ∥x ω ∥ r,∞ = max 1≤l≤L ∥ω l x l ∥ r , s = ∞,where ω l > 0, ∀l and r ≥ 1. Then, the dual norm of (r, s)-norm with weight ω is the (q, t)-norm with weight ω -1 = (1/ω 1 , ..., 1/ω L ), i.e. ∥x ω -1 ∥ q,t , where 1/r + 1/q = 1 and 1/s + 1/t = 1.To handle the group structure in the input variable, the weighted (r, s)-norm is applied to add group structure in the perturbation accordingly, and the group adversarial training is formulated as follows,min β 1 n n i=1 sup ∥∆ω∥ r,s ≤δ (X i + ∆) ⊤ β -Y i 2 ,where ω = (ω 1 , ..., ω L ).Recall we focus on adversarial training problems under ℓ ∞ -perturbation, high-dimension setting, and sparsity condition. Under this consideration, we let s = ∞ and r = 2, and then the associated group adversarial training problem under (2, ∞)-perturbation has the following expression:EQUATION)To facilitate convenience for the computation and analysis, similar to our study towards classic adversarial training in Section 2.1, we derive the dual formulation of problem (7) in the following proposition. One can check that the corresponding objective in the dual formulation ( 8) is also convex.Proposition 3.2 (Dual Formulation of problem ( 7)). If we denote the optimal value of problem (7) by R(δ), then we have thatEQUATIONwhere∥β ω -1 ∥ 2,1 = L l=1 1 ω l ∥β l ∥ 2 .In this subsection, we deliver the convergence analysis of the prediction error of the estimator obtained from group adversarial training under (2, ∞)-perturbation, i.e., problem (7) .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 {1, ..., p} = L l=1 G l . We use p l to denote the cardinality of each group, i.e., |G l | = p l .Consider the group sparsity structure in the ground-truth parameter β * ∈ R p , where sparsity is imposed at the group level instead of on individual components. Specially, the set J ⊂ {1, ..., L} denotes a set of groups and β * is supported at these J groups, i.e., β * is supported on the G J = l∈J G l . We make the following assumption before we proceed to derive the convergence analysis. Assumption 3.3 (Group Restricted Eigenvalue Condition). The matrix X ∈ R n×p satisfies the group restricted eigenvalue condition if there exists a positive number κ = κ(g, c 2 ) > 0 such thatmin ∥Xv∥ 2 √ n∥v G J ∥ 2 : |J| ≤ g, v ∈ R p \{0}, l∈J c 1 ω l ∥v l ∥ 2 ≤ c 2 l∈J 1 ω l ∥v l ∥ 2 ≥ κ,where J is some subset of {1, ..., L}.In the sequel, we use the notation GRE(g, c 2 ) to denote the restricted eigenvalue condition w.r.t. the cardinality g of the index set J and the constant c 2 in the constrained cone, i.e., l∈J c 1ω l ∥v l ∥ 2 ≤ c 2 l∈J 1 ω l ∥v l ∥ 2 .Group restricted eigenvalue condition is an extension of the restricted eigenvalue condition and can be 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) satisfying2∥ X ⊤ ϵ l ∥ 2 ∥ϵ∥ 1 ≤ δ ω l , ∀l.If β * is supported on a subset G J of {1, ..., p} where |J| ≤ g, and the design matrix X satisfies GRE(g, 3) with parameter κ(g, 3), then we have that1 2n ∥X( β -β * )∥ 2 2 ≤ 3δ 2 l∈J 1 ω 2 l max 9 κ 2 (g, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 ,where β is the estimator obtained from solving problem (7) .Theorem 3.4 shows that the upper bound of the prediction error mainly depends on the weight ω and perturbation magnitude δ. 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 (7) satisfyingδ ω l = 2 2 π -1 10 3p l + 9 log L n , ∀l,andΨ l = X ⊤ G l X G l /n = I p l ×p l, where X G l denotes the n × p l sub-matrix of X formed by the columns indexed by G l . If β * is supported on a subset G J of {1, ..., p} where |J| ≤ g, and the design matrix X satisfies GRE(g, 3) with parameter κ(g, 3), then we have that1 2n ∥X( β -β * )∥ 2 2 ≤ 432 |G J | + g log L n max 9 κ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2holds with a probability greater than 1 -2 exp (-C 1 n) -2/L, where C 1 is a positive constant.Remark 3.6. Note that we assume the gram matrix satisfies that X ⊤ G l X G l /n = I p l ×p l . This is a standard assumption in the theoretical analysis in sparse high-dimensional linear regression, seeing [17, 19] .Similar to the analytic investigations in Section 2, the convergence rate of the prediction error could be further simplified in the following corollary if the ℓ 2 -norm of the ground-truth parameter β * and error variance σ 2 are bounded. Corollary 3.7. Under the assumptions stated in Corollary 3.5, suppose there exists a finite positive constant R such that2 √ 41∥β * ∥ 2 ≤ R, σ < 1 6 κ(g, 3)R, then we have that 1 2n ∥X( β -β * )∥ 2 2 ≤ 432 |G J | + g log L n R 2holds with a probability greater than 1 -2/L -2 exp (-C 1 n) -exp(-n),some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
numerical experiments: 
 In this section, we will run 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 ϵ is chosen as 0. (8) , and solve these convex optimization problems using the CVXPY toolbox [8] . 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 errors are computed and recorded.We first plot the coefficient estimation paths of adversarial training with error bars in Figure 1 and We also plot the curve of log 10 (prediction error) versus log 10 (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 is consistent with our theoretical analysis, where we have proved that the prediction error for highdimensional (group) adversarial training is of the order  
discussions: 
 This paper reveals the statistical optimality of adversarial training under ℓ ∞ -perturbation 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, we will consider analyzing estimation errors as our next step. More advanced analytical future work may use the primal-dual witness technique for the non-asymptotic variable-selection analysis.EQUATIONwhere (a) comes from the Hölder's inequality, i.e.,(X( β-β * )) ⊤ ϵ ≤ ∥ β-β * ∥ 1 ∥X ⊤ ϵ∥ ∞ , w ⊤ β * ≤ ∥w∥ ∞ ∥β * ∥ 1 = ∥β * ∥ 1 , -ϵ ⊤ z ≤ ∥ϵ∥ 1 ∥z∥ ∞ = ∥ϵ∥ 1 ,and the condition 2∥X ⊤ ϵ∥ ∞ /∥ϵ∥ 1 ≤ δ, (b) comes from ∥ β -β * ∥ 1 ≤ ∥ β∥ 1 + ∥β * ∥ 1 , (c) comes from the relationship that 2∥X β -Y ∥ 1 ≥ 5 3 ∥X β -Y ∥ 1 ≥ - 5 3 ∥X( β -β * )∥ 1 + 5 3 ∥ϵ∥ 1 ,and (d) comes from the inequality that ∥X(β -β * )∥ 1 ≤ √ n∥X( β -β * )∥ 2 and ∥X β -Y ∥ 1 ≤ ∥X( β -β * )∥ 1 + ∥ϵ∥ 1 .One may observe that ( 10) is a second-order inequality of variable ∥X( β -β * )∥ 2 / √ n, then the associate discriminant should be equal to or larger than 0, resulting in1 9 δ 2 (-11∥ β∥ 2 1 + 66∥β * ∥ 1 ∥ β∥ 1 + 9∥β * ∥ 2 1 ) + δ 3n ∥ϵ∥ 1 (-2∥ β∥ 1 + 18∥β * ∥ 1 ) ≥ 0,from which we could conclude that at least one of two terms should be equal or larger than 0, implying∥ β∥ 1 ≤ 9∥β * ∥ 1 .Then, we proceed to prove Theorem 2.3.Proof. We write the objective function in (2) in the matrix norm and then have that1 2n ∥Y -X β∥ 2 2 + 1 2 δ 2 ∥ β∥ 2 1 + δ n ∥Y -X β∥ 1 ∥ β∥ 1 ≤ 1 2n ∥Y -Xβ * ∥ 2 2 + 1 2 δ 2 ∥β * ∥ 2 1 + δ n ∥Y -Xβ * ∥ 1 ∥β * ∥ 1 . (11) It follows from Y = Xβ * + ϵ, i.e., Assumption 1.2, that ∥Y -Xβ * ∥ 2 2 = ∥ϵ∥ 2 2 , ∥Y -X β∥ 2 2 = ∥X( β -β * ) -ϵ∥ 2 2 = ∥X( β -β * )∥ 2 2 + ∥ϵ∥ 2 2 -2ϵ ⊤ X( β -β * ), ∥Y -X β∥ 1 = ∥X( β -β * ) -ϵ∥ 1 ≥ ∥ϵ∥ 1 -∥X( β -β * )∥ 1 .In this way, the inequality (11) could be reformulated asEQUATIONwhere (a) comes from the Hölder's inequality, (b) comes from the condition2∥X ⊤ ϵ∥ ∞ /∥ϵ∥ 1 ≤ δ, (c) comes from ∥X( β -β * )∥ 1 ≤ √ n∥X( β -β * )∥ 2 .Then, we begin to give the upper bound of the prediction error. Two cases should be discussed.EQUATIONIn this case, we have thatEQUATION)Then, it follows from ( 12) that1 2n ∥X( β -β * )∥ 2 2 ≤ δ 2n ∥ϵ∥ 1 ∥ β -β * ∥ 1 + δ √ n ∥X( β -β * )∥ 2 ∥ β∥ 1 + δ n ∥ϵ∥ 1 ∥β * ∥ 1 -∥ β∥ 1 + 1 2 δ 2 ∥β * ∥ 2 1 - 1 2 δ 2 ∥ β∥ 2 1 = δ 2n ∥ϵ∥ 1 ∥ β -β * ∥ 1 + 2∥β * ∥ 1 -2∥ β∥ 1 + δ √ n ∥X( β -β * )∥ 2 ∥ β∥ 1 + 1 2 δ 2 ∥β * ∥ 2 1 - 1 2 δ 2 ∥ β∥ 2 1 ≤ δ √ n ∥X( β -β * )∥ 2 ∥ β∥ 1 ,where the last inequality comes from ( 13) and (14) .Lemma A.1 indicates that 1 √ 2n ∥X( β -β * )∥ 2 ≤ √ 2δ∥ β∥ 1 ≤ 9 √ 2δ∥β * ∥ 1 ,which is equivalent toEQUATION)Second Case:EQUATIONIf we let v = β -β * , then we have that∥β * -β∥ 1 = ∥ v∥ 1 = ∥ v S ∥ 1 + ∥ v S c ∥ 1 , ∥β * ∥ 1 -∥ β∥ 1 = ∥β * S ∥ 1 -(∥β * S + v S ∥ 1 + ∥ v S c ∥ 1 ) ≤ ∥ v S ∥ 1 -∥ v S c ∥ 1 .The inequality (16) indicates thatEQUATIONimplying∥ v S c ∥ 1 ≤ 3∥ v S ∥ 1 .In this way, the RE(s, 3) condition can be applied.In addition, it follows the inequality ( 12) that1 2n ∥X( β -β * )∥ 2 2 ≤ δ 2n ∥ϵ∥ 1 ∥ β -β * ∥ 1 + δ √ n ∥X( β -β * )∥ 2 ∥ β∥ 1 + δ n ∥ϵ∥ 1 ∥β * ∥ 1 -∥ β∥ 1 + 1 2 δ 2 ∥β * ∥ 2 1 - 1 2 δ 2 ∥ β∥ 2 1 (a) ≤ δ 2n ∥ϵ∥ 1 ∥ β -β * ∥ 1 + 1 4n ∥X( β -β * )∥ 2 2 + δ 2 ∥ β∥ 2 1 + δ n ∥ϵ∥ 1 ∥β * ∥ 1 -∥ β∥ 1 + 1 2 δ 2 ∥β * ∥ 2 1 - 1 2 δ 2 ∥ β∥ 2 1 = δ 2n ∥ϵ∥ 1 ∥ β -β * ∥ 1 + 2∥β * ∥ 1 -2∥ β∥ 1 + 1 4n ∥X( β -β * )∥ 2 2 + 1 2 δ 2 ∥β * ∥ 2 1 + 1 2 δ 2 ∥ β∥ 2 1 (b) ≤ 3δ 2n ∥ϵ∥ 1 ∥ v S ∥ 1 + 1 4n ∥X( β -β * )∥ 2 2 + 41δ 2 ∥β * ∥ 2 1 ,where (a) comes from the inequalityEQUATIONcomes from (17) and Lemma A.1.Further, we have thatEQUATIONwhere the first inequality comes from ∥ v S ∥ 1 ≤ |S|∥ v∥ 2 and ∥β * ∥ 1 ≤ |S|∥β * ∥ 2 , and the last inequality comes from the RE(s, 3) condition and |S| ≤ s.Then, if we solve the inequality (18), we could have that1 √ n ∥X( β -β * )∥ 2 ≤ δ √ s γ(s, 3)   3 ∥ϵ∥ 1 n + 9 ∥ϵ∥ 1 n 2 + 164γ 2 (s, 3)∥β * ∥ 2 2   ,which is equivalent to1 √ n ∥X( β -β * )∥ 2 ≤ (1 + √ 2) δ √ s γ(s, 3) max 3 ∥ϵ∥ 1 n , √ 164γ(s, 3)∥β * ∥ 2 ,indicating thatEQUATIONCombining ( 15) and ( 19), we have that1 2n ∥X( β -β * )∥ 2 2 ≤ 3δ 2 s max 9 γ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 .Proof. To give the high probability result, we should analyze the bound of the term ∥X ⊤ ϵ∥ ∞ /n and ∥ϵ∥ 1 /n. The associated arguments are discussed in the following two parts, respectively. (Note that we assume ϵ has i.i.d. Gaussian entries. However, our high-probability result can be extended to sub-Gaussian cases, as sub-Gaussian variables share similar tail decay behavior.)Part I: We focus on the tail bound of ∥X ⊤ ϵ∥ ∞ /n. Since the design matrix X is normalized, the random variable x ⊤ j ϵ/n is stochastically dominated by N (0, σ 2 /n). As shown in Theorem 11.1 in [11] , it follows from the Gaussian tail bound and the union bound thatP ∥X ⊤ ϵ∥ ∞ n ≥ t ≤ 2 exp - nt 2 2σ 2 + log p .In this way, with a probability greater than 1 -2/p, the following holds∥X ⊤ ϵ∥ ∞ n ≤ 2σ log p n .Part II: We focus on the concentration inequality of ∥ϵ∥ 1 /n. It follows from general Hoeffding's inequality [26] thatP ∥ϵ∥ 1 -nσ 2 π ≥ t ≤ 2 exp -C 2 t 2 nσ 2 , indicating P 1 n ∥ϵ∥ 1 -σ 2 π ≥ t ≤ 2 exp -C 2 nt 2 σ 2 ,where C 2 is some positive constant. By choosing t = σ/10, we have thatP σ 2 π - 1 10 ≤ 1 n ∥ϵ∥ 1 ≥ 1 -2 exp (-C 1 n) ,where C 1 is some positive constant. This is to say, with a probability greater than 1 -2 exp (-C 1 n), we have thatσ 2 π - 1 10 ≤ 1 n ∥ϵ∥ 1 .Suppose we letδ = 4 2 π -1 10 log p n ,with a probability greater than 1 -2 exp (-C 1 n) -2/p, we have that2∥X ⊤ ϵ∥ ∞ ∥ϵ∥ 1 ≤ δ.It follows from Theorem 2.3 that1 2n 2 ∥X( β -β * )∥ 2 2 ≤ 192 s log p n max 9 γ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2holds with a probability greater 1 -2 exp (-C 1 n) -2/p.Proof. We focus on the tail bound of ∥ϵ∥ 1 /n. We apply the Chernoff bound to give the tail bound of ∥ϵ∥ 1 , and we have thatP (∥ϵ∥ 1 ≥ t) ≤ inf s>0 M (s) exp(-ts),where M (s) is the moment-generating function of ∥ϵ∥ 1 . We also could obtain thatM i (s) = E[exp(s|ϵ i |)] ≤ 2E[exp(sϵ i )] = 2 exp σ 2 s 2 2 , indicating M (s) ≤ 2 n exp nσ 2 s 2 2 .Then, we have thatP (∥ϵ∥ 1 ≥ t) ≤ inf s>0 2 n exp nσ 2 s 2 2 -ts , indicating P 1 n ∥ϵ∥ 1 ≥ t ≤ exp - nt 2 2σ 2 + n log 2 .In this way, with a probability greater 1 -exp(-n), the following holds:1 n ∥ϵ∥ 1 ≤ 2 log 2 + 2σ ≤ 2σ.Since we have that 1 6 γ(s, 3)R ≥ σ, 9 γ 2 (s, 3)∥ϵ∥ 1 n 2 ≤ R 2 ,holds with a probability greater 1 -exp(-n). Due to Corollary 2.4, we have the following1 2n 2 ∥X( β -β * )∥ 2 2 ≤ 192 s log p n R 2holds with a probability greater 1 -2/p -2 exp(-C 1 n) -exp(-n).It follows from Proposition 1 in [21] thatR(δ) = min β 1 n n i=1 |(X i + ∆) ⊤ β -Y i | + δ∥β ω -1 ∥ * 2 ,where ∥ • ∥ * denotes the dual norm of (2, ∞)-norm of β ω . Due to Proposition 3.1, we conclude that (8) holds.We first give the upper bound of the∥ β ω -1 ∥ 2,1 in terms of ∥β * ω -1 ∥ 2,1 . Lemma E.1 (Upper Bound of ∥ β ω -1 ∥ 2,1). Under conditions stated in Theorem 3.4, we have that∥ β ω -1 ∥ 2,1 ≤ 9∥β * ω -1 ∥ 2,1 .Proof. The proof of this lemma follows a similar approach to the proof of Lemma A.1. It follows from the first-order condition of the dual formulation (8) of the group adversarial training problem thatEQUATIONwherez i = ∂|X ⊤ i β -Y |, t = ∂∥ β ω -1 ∥ 2,1 , t l = 1 ω l β l ∥ β l ∥ 2 .Notice we have thatEQUATIONand it follows from the Hölder's inequality thatEQUATIONAlso, we have the following from the Hölder's inequality:EQUATIONwhere the second inequality comes from the condition 2∥ X ⊤ ϵ l ∥ 2 /∥ϵ∥ 1 ≤ δ/ω l .Then, we take the dot product of both sides of equation ( 20) with β -β * and could have the following:EQUATIONwhere (a) comes from ( 21) and ( 22), (b) comes from ( 23), (c) comes from ∥(β l -β l * ) ω -1 ∥ 2,1 ≤ ∥ β ω -1 ∥ 2,1 + ∥β * ω -1 ∥ 2,1 , (d) comes from 2∥X β -Y ∥ 1 ≥ 5 3 ∥X β -Y ∥ 1 ≥ -5 3 ∥X( β -β * )∥ 1 +Since the inequality ( 24) is a second-order inequality of variable ∥X( β -β * )∥ 2 / √ n, then the associate discriminant should be equal to or larger than 0, resulting in1 9 δ 2 (-11∥ β ω -1 ∥ 2 2,1 + 66∥β * ω -1 ∥ 2,1 ∥ β ω -1 ∥ 2,1 + 9∥β * ω -1 ∥ 2 2,1 ) + δ 3n ∥ϵ∥ 1 (-2∥ β ω -1 ∥ 2,1 + 18∥β * ω -1 ∥ 2,1 ) ≥ 0, from which we could conclude that ∥ β ω -1 ∥ 2,1 ≤ 9∥β * ω -1 ∥ 2,1 .Then, we proceed to prove Theorem 3.4.Proof. We write the objective function in (8) in the matrix norm and then have thatEQUATIONIn this way, we have the following reformulation:EQUATIONwhere the last inequality comes from (23) and∥X( β -β * )∥ 1 ≤ √ n∥X( β -β * )∥ 2 .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:EQUATIONIn this case, we have thatEQUATIONEQUATIONwhere the last inequality comes from ( 27) and ( 28).Notice we have thatEQUATIONLemma E.1, ( 29) and ( 30) indicate thatEQUATIONSecond Case:∥( β -β * ) ω -1 ∥ 2,1 + 2∥β * ω -1 ∥ 2,1 -2∥ β ω -1 ∥ 2,1 ≥ 0.Notice we have that∥( β -β * ) ω -1 ∥ 2,1 = L l=1 1 ω l ∥ β l -β l * ∥ 2 = l∈J c 1 ω l ∥( β -β * ) l ∥ 2 + l∈J 1 ω l ∥( β -β * ) l ∥ 2 , ∥β * ω -1 ∥ 2,1 -∥ β ω -1 ∥ 2,1 = l∈J 1 ω l ∥β l * ∥ 2 - L l=1 1 ω l ∥ β l ∥ 2 = l∈J 1 ω l ∥β l * ∥ 2 - l∈J 1 ω l ∥ β l ∥ 2 + l∈J c 1 ω l ∥( β -β * ) l ∥ 2 ≤ l∈J 1 ω l ∥( β -β * ) l ∥ 2 - l∈J c 1 ω l ∥( β -β * ) l ∥ 2 .If we let v = β -β * ,then we have thatEQUATIONindicatingl∈J c 1 ω l ∥ v l ∥ 2 ≤ 3 l∈J 1 ω l ∥ v l ∥ 2 .In this way, the GRE(g, 3) condition can be applied.We also have the following from ( 26)EQUATIONEQUATION≤ 1 4n ∥X( β -β * )∥ 2 2 + 3δ 2n ∥ϵ∥ 1 n l∈J 1 ω 2 l ∥ v G J ∥ 2 + 1 2 δ 2 ∥β * ω -1 ∥ 2 2,1 + 1 2 δ 2 ∥ β ω -1 ∥ 2 2,1where (a) comes from (32) , and (b) comes froml∈J 1 ω l ∥ v l ∥ 2 ≤ l∈J 1 ω 2 l ∥ v G J ∥ 2 .It follows from GRE(g, 3) and Lemma E.1 that1 4n ∥X( β -β * )∥ 2 2 ≤ 3δ 2 √ n l∈J 1 ω 2 l 1 κ(g, 3) ∥ϵ∥ 1 n ∥X( β -β * )∥ 2 + 41δ 2 l∈J 1 ω 2 l ∥β * ∥ 2 2 .Then, we could have thatEQUATIONCombining ( 31) and ( 33), we have that1 2n ∥X( β -β * )∥ 2 2 ≤ 3δ 2 l∈J 1 ω 2 l max 9 κ 2 (g, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 .F Proof of Corollary 3.5It follows from Lemma 3.1 in [17] that 2 n ∥(X ⊤ ϵ) l ∥ 2 ≤ 2σ √ n tr(Ψ l ) + 2|||Ψ l |||(4 log L + 2p l log L)holds with a probability greater than 1 -2/L, tr(Ψ l ) denotes the trace of Ψ l , and |||Ψ l ||| denotes the maximum eigenvalue of Ψ l . Since Ψ l = I p l ×p l , we have that |||Ψ l ||| = 1 and tr(Ψ l ) = p l . Consequently, we have that2 n ∥(X ⊤ ϵ) l ∥ 2 ≤ 2σ √ n p l + 2(4 log L + 2p l log L) ≤ 2σ √ n 3p l + 9 log L,holds with a probability greater than 1 -2/L.Also, it follows from the proof of Corollary 2.4 thatσ 2 π - 1 10 ≤ 1 n ∥ϵ∥ 1holds with a probability greater 1 -2 exp (-C 1 n). Suppose we letδ ω l = 2 2 π -1 10 3p l + 9 log L n , we have that 2∥(X ⊤ ϵ) l ∥ 2 ∥ϵ∥ 1 ≤ δ ω l .holds with a probability greater than1 -2 exp (-C 1 n) -2/L.It follows from Theorem 3.4 that1 2n ∥X( β -β * )∥ 2 2 ≤ 48δ 2 l∈J 1 ω 2 l max 9 κ 2 (g, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 ≤ 48 l∈J 3p l + 9 log L n max 9 κ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 = 432 |G J | + g log L n max 9 κ 2 (s, 3) ∥ϵ∥ 1 n 2 , 164∥β * ∥ 2 2 .G Proof of Corollary 3.7Corollary 3.7 is straightforward due to Corollary 3.5 and the upper bound arguments in the proof in Corollary 2.6. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]Justification: [NA] 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as details about compensation (if any)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.ℓ ∞ -Adversarial-Trained Linear RegressionIn this section, we will first introduce the problem formulation of the adversarial training in linear regression under ℓ ∞ -perturbation and then deliver the convergence analysis of the prediction error under ℓ ∞ -perturbation in the high-dimensional setting.3 ∥ϵ∥ 1 , (e) comes from the inequality that ∥X(β -β * )∥ 1 ≤ √ n∥X( β -β * )∥ 2 and ∥X β -Y ∥ 1 ≤ ∥X( β -β * )∥ 1 + ∥ϵ∥ 1 . 
 
 Appendix:  


Decision: 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!

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 

- 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.  

- 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. 

- 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. 

- Line 87-97: It is repetitive.  

- Line 229 has typo: $s = \infty$  should be used in underscore.
questions: questions: - The proof of Corollary 2.4 uses Gaussian tail bounds. Can the proof be generalized for sub-Gaussian distribution?   

- 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?  

- Line 55: what is the sparsity condition exactly? 

- Line 65: What is the certain group sparsity structures exactly?
limitations: 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. 

- 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. 

- 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$.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2.The tightness of such upper bounds in main theorems has not been proved.

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.
questions: questions: See weakness.
limitations: limitations: No negative social impact.
paper_summary: paper_summary: The paper provides a high-dimensional analysis of Linear Regression in Adversarial training. It has two contributions:

1. it proves an improved convergence rate of prediction error of $1/n$  (previous work show $1/\sqrt{n}$). 
2. It extends adversarial training for the group setting and extend the convergence results for it
strength_weakness: strength_weakness: 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

I think the presentation of the numerical results could be somehow improved,
1. Figure 1 could be interesting to have confidence intervals and also have in the plot the final values that the coefficients converge to.
2. Figure 2 it would be better to have log 10 base, it is a bit hard to read with ln.
questions: 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: limitations: The paper has no clear societal impact. See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. The convergence rate for a linear model, as presented, is insufficient to illustrate the behavior of adversarial training effectively.


3. The points in Lines 142-145 lack supporting literature.

4. 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.
questions: questions: See Weaknesses
limitations: limitations: None

Comments: title: Response to the rebuttal
Gentle Reminder
Gentle Reminder
Gentle Reminder
comment: Many thanks for the authors' response. This paper has an interesting story, but maybe it need to be polished from my side. I will maintain my score.
I thank the authors for their detailed response. I will maintain my original score.
Dear Reviewer,

We hope this message finds you well. We are writing to kindly follow up on the rebuttal. We appreciate the effort you made to provide feedback on our paper. We would be grateful if you could let us know if our response has addressed your concerns.

Thank you,

Authors
Dear Reviewer,

We hope this message finds you well. We are writing to kindly follow up on the rebuttal. We appreciate the effort you made to provide feedback on our paper. We would be grateful if you could let us know if our response has addressed your concerns.

Thank you,

Authors
Dear Reviewer,

We hope this message finds you well. We are writing to kindly follow up on the rebuttal. We appreciate the effort you made to provide feedback on our paper. We would be grateful if you could let us know if our response has addressed your concerns.



Thank you,

Authors
Thank you for recognizing our contributions and the value of our focus on linear models! We truly appreciate your positive evaluations and are greatly encouraged by your decision to raise your score to a strong accept.
I read the other reviews and comments. I believe the focus on linear models is interesting and well-justified and I don't think other scores should penalize the paper for it.  The paper is good in what it does and has a clear contribution.

I thank the reviewer for addressing my concerns and I raise my score to strong accept.