A Theoretical Study of The Effects of Adversarial Attacks on Sparse Regression
Authors: Deepak Maurya
Jean Honorio
Venue: Accepted by TMLR ()

Abstract: This paper analyzes $\ell_1$ regularized linear regression under the challenging scenario of having only adversarially corrupted data for training. Firstly, we prove existing deterministic adversarial attacks (e.g., FGSM and variants) focusing on maximizing the loss function can be easily handled with a few samples for support recovery. Hence, we consider a more general, challenging stochastic adversary which can be conditionally dependent on uncorrupted data and show existing models attacking support (Goodfellow et al., 2014; Madry et al., 2017) or Huber model (Prasad et al. 2018) are particular cases of our adversarial model. This enables us to show the counter-intuitive result that an adversary can influence sample complexity by corrupting the ``irrelevant features'', i.e., non-support. Secondly, as any adversarially robust algorithm has limitations, our theoretical analysis identifies that the dependence (covariance) between adversarial perturbations and uncorrupted data plays a critical role in defining the regimes under which this challenging adversary or Lasso can dominate over each other. Thirdly, we derive a necessary condition for support recovery for any algorithm (not restrictive to Lasso), which corroborates our theoretical findings for Lasso. Fourthly, we identify the fundamental limits and address critical scientific questions of which parameters (i.e., mutual incoherence, the maximum and minimum eigenvalue of the covariance matrix, and the budget of adversarial perturbations) play a role in the high or low probability of success of the Lasso algorithm. Also, the derived sample complexity is logarithmic with respect to the size of the regression parameter vector. Our theoretical claims are validated by empirical analysis.

Published in Transactions on Machine Learning Research (12/2024)
A Theoretical Study of The Effects of Adversarial Attacks on Sparse Regression
Deepak Maurya
dmaurya
Deportment of Computer Science, Purdue University
Jean Honorio
School of Computing and Information Systems, The Universiby of Melbourne, and @honorio@unimmll.ccoo edw.
ARC Training Centre in Oplinisation Technologies, Integrated Methodologies, and Applications (OPTIMA)
Reviewed on OpenReview: https: openreview. net/ per/forun? id- (d-DaDBtnWey9
Abstract
This paper analyzes & regularized linear regression under the challenging scenario of having only adversarially corrupted data for training. Firstly, we prove existing deterministic adversarial attacks (e.g., FGSM and variants) focusing on maximizing the loss function can be casily handled with a few samples for support recovery. Hence, we consider a more general, challenging stochastic adversary which can be conditionally dependent on uncorrupted data and show existing models attacking support (Goodfellow et al., 2015; Madry et al., 2018) or Huber model (Prasad et al., 2020) particular cases of our adversarial model. This enables us to show the counter-intuitive result that adversary can influence sample complexity by corrupling the "irrelevant features", i.e., non-support. Secondly, any adversarially robust algorithm has limitations, our theoretical analysis identifies that the dependence (covariance) between adversarial perturbations and uncorrupted data plays a critical role in defining the regimes under which this challenging adversary or Lasso can dominate over each other. Thirdly, we derive necessary condition for support recovery for any algorithm (not restrictive to Lasso), which corroborates our theoretical findings for Lasso. Fourthly, we identify the fundamental limits and address critical scientific questions of which parameters (i.e., mutual incoherence, the maximum and minimum eigenvalue of the covariance matrix, and the budget of adversarial perturbations) play a role in the high or low probability of success of the Lasso algorithm. Also, the derived sample complexity is logarithmic with respect to the size the regression parameter vector. Our theoretical claims are validated by empirical analysis.
1 Introduction
A well-known instance of the failure of machine learning (ML) models is when they are confronted with adversarial attacks. The vulnerability ML models to possibly small perturbations imperceptible to the human eye such as one-pixel attacks (Su al., 2019) may produce inaccurate predictions with high confidence (Szegody et al., 2014; Goodfellow et al., 2015; Madry et al., 2018). Hence, demystifying empirical failure with theoretical analysis to design certifiable learning algorithms has been an active area of research recently. In this work, consider the support recovery problem under adversarial attacks and theoretically analyze the behavior of the widely accepted Lasso algorithm.
We begin by providing theoretical evidence of the limitations of existing adversarial attack models in the context of the support recovery problem. We propose a more comprehensive and demanding adversarial model that addresses these limitations. Existing gradient descent-based methods, such as FGSM (Goodfellow et al., 2015) and various others (Madry al., 2018; Szegedy al., 2014; Xing al., 2021; Yin al., 2019; Awasthi et al., 2020; Qin et al., 2021) target the support (the entries corresponding non-zero coefficients)

---

Published in Transactions on Machine Learning Research (12/2024)
a per-sample basis. These methods primarily focus on maximizing the loss function rather than making parameter estimation more challenging. Attacks that exclusively target the support can be easily countered by inspecting the mean with just (log(p)) samples, as demonstrated in Section 2.1 and 2.2. To ensure a non-trivial and intriguing problem, we introduce a more general and challenging adversary.
In this work, we consider a zero-mean sub-Gaussian adversary that can be conditionalll dependent on the uncorrupted data, aiming to maximize the complexity of the learning process (for Lasso). Our adversary is more challenging as compared to existing attacks (Goodfellow al., 2015; Szegedy et al., 2014; Xing et al., 2021; Yin et al., 2019; Awasthi et al., 2020; Qin et al., 2021), as it demands larger number of samples for support recovery. Specifically, as proved in Theorem 10, our adversary demands Ω log(p)) samples, whereas existing attacks only need ((log(p)) samples (in Section 2.2). Here, k denotes the number of elements in the support. Furthermore, it is worth noting that under a specific condition, our adversary can be so powerful that achieving successful support recovery becomes impossible, even with infinite samples.
The atlack in existing methods is just one possible attack model that fits our assumptions; hence, our adversarial model is more general. For instance, approaches by Goodfellow et al. (2015); Madry et al. (2018); Szegedy et al. (2014); Xing et al. (2021); Yin et al. (2019); Schmidt et al. (2018); Awasthi et al. (2020); Qin et al. (2021) consider deterministic attacks within an e-ball, which is sub- Gaussian since any bounded random variable is known to be sub-Gaussian. Also, note that stochastic attacks are more general as any deterministic value is a random variable with a Dirac delta probability density function. Furthermore, it is worth noting that the a-Huber model (Prasad et al., 2020; Diakonikolas et al., 2019) corrupting only a < fraction of samples is particular case of our adversarial model.
In the presence of more challenging adversary, our analysis (as demonstrated in Lemma 12) reveals an intriguing aspect: the adversary can impact the sample complexity by manipulating not only the "relevant features" or support (i.e., entries corresponding to non-zero coefficients of the regression parameter vector) but also the "irrelevant features" or non-support (i.c., entrics corresponding to zero coefficients). This is a counter-intuitive result as the existing methods (Madry et al., 2018; Szegedy et al., 2014; Xing et al., 2021; Yin et al., 2019; Awasthi et al., 2020; Qin et al., 2021) attack only the support. (Temma 6). We also address critical scientific questions of which parameters (i.e., mutual incoherence (after Eq (8)), the maximum and minimum cigenvalue (Lemma 19) of the covariance matrix, and the budget of adversarial perturbations (Eq (15))) play a role in the high or low probability of success of Lasso. The adversary can also increase the sample complexity by designing the covariance matrix of perturbations in the support such that its eigenvector corresponding to the maximum eigenvalue is parallel to the regression parameter vector (discussed after Eq (15)).
We derive a necessary condition for support recovery that applies to any algorithm, extending beyond the scope of Lasso. Notably, we observe that this condition aligus with our separate analysis of the Lasso algorithm, strengthening our findings in that context. With slight abuse of terminology, both conditions essentially indicate that support recovery is impossible when the absolute value of the coefficient in the parameter vector (for an entry in the support) is not large enough as compared to the entries in the covariance mairix between the adversarial perturbation and the uncorrupted data. This aspect of our main result in Theorem 10 is discussed in Section 3.2 and verified empirically. Please refer to Figure/ for a demonstration of possible and impossible support recovery scenarios in the cases of 0 and b A 0 respectively. For more detailed experiments on the three cases of the regularization parameter, À in Theorem 10, characterizing possible and impossible support recovery, please refer to Appendix F.4.
Some initial attempts have been made in the sparse regression literature (Herman & Strohmer, 2010), but we believe that the particular theoretical framework did not allow prior work to make important findings such as noting that when adversarial perturbations correlate with uncorrupted data, then support recovery is impossible. In addition, there is prior literature in robust optimization (Bertsimas & Den Hertog, 2020), where there is uncertainty in the input coefficients of an optimization problem. Their goal is to provide guarantees that the unperturbed optimal solution is still feasible (although not optimal) in the problem with perturbed inputs. Bertsimas & Den Hertog (2020) treats canonical problems such as linear programming, for instance. While we also focus on an optimization problem, Bertsimas & Den Hertog (2020) provides a
2

---

Published in Transactions on Machine Learning Research (12/2024)
general treatment and lacks the focus machine learning aspects, e.g., support recovery and adversarial perturbations.
Our Contributions. Our key contributions are summarized below:
A challenging adversary: We show the limitations of existing adversarial models and use more general and challenging adversary (in Section 2.1 and 2.2). In this regard, our work offers theoretical insights into the reasons behind the failure of existing adversarial training approaches, even for seemingly simple problems such as sparse regression.
We derive the necessary condition (in Section 2.4) for the support recovery problem, which is applicable to any method and not limited to Lasso. Further, our independent analysis for Lasso derives similar requirements (in Section 3).
Necessary condition:
Identifying fundamental limitations: While adversarially robust algorithms have their limitations, our theoretical analysis (in Section 3.2) reveals that the dependence (covariance) between adversarial perturbations and uncorrupted data relative to the magnitude of coefficients in the parameter vector plays a crucial role in determining the regimes in which either the challenging adversary or the Lasso algorithm can outperform each other.
We derive sample complexity of order Q (k22 log(p)) (Theorem 10) for support recovery under adversarial attacks, which is known to be S2(k log(p) for the non-adversarial regime (Wainwright, 2009). If we assume the adversarial perturbation to be Gaussian, the sample complexity improves to Ω (A: log(p)) (Appendix D.10). This improved complexity is proven to be minimax optimal, indicating that further improvement is not possible.
Sample complexity:
Empirical validation: We verify our theoretical findings via experiments synthetic and real-world data where the adversarial perturbation can be dependent on the uncoruuptdd data. This identifies the regimes when Lasso (Fig. 1(a)) or the adversary (Fig. 1(b) can dominate over each other (Appendix E.4). Thcorctical tools: Our contribution can be seen as a first step towards the study of learning from adversarial training data. As byproduct, we also obtain several technical results related to new concentration inequality (Theorem 14), necessary condition (Lemma 9) which could be useful for other problems.
While we focus on sub-Gaussian data, our proofs can be extended to heavy-tailed data. Before proceeding further, we introduce the notations used in this paper.
Notation. We use lowercase letter, e.g., a to denote scalar, lowercase bold letter such to denote vector, and an uppercase bold letter such A to denote matrix. A vector 1m O, represents a vector of ones or zeros respectively, of size m. We denote a set with a calligraphic letter, c.g., P. Also, [n] denotes the set (1,2,...,n)) n2). For a vector, a; denoles the zth entry of the vector a. For a matrix A E IRPxq, we represent. the sub-matrix with rows P E [p] and columns Q E [q] as ApQ E ||11x12
For a vector vector a E R" we denote the l, norm as ||ll| = ET (P) Similarly ||A denotes the entrywise lo norm of matrix A and ||A||2 denotes the spectral norm. We denote the induced tx norm using || = max+e[m] ||a/||| for a matrix A E Rm where a, denotes its 7th row. Minimum and maximum eigenvalues of a matrix A are denoted by Amin (A), Amax (A). A function f(m) = R(g(m)) implies that there exists a constant e₁ such that f(m) 2 cig(m), Vm 2 mp- Similarly, f(m) (g(mm) denotes that there exists a constant 02 such that f(m) < (m)) Vm 2 mg. For a vector w E R,, S(w) = (i E (p). w, + 0} denotes the support of w and similarly (*(w) = [p] \ SW) denotes the non-support.
2 A Novel Generative Model For Adversarial Training Data
In this section, we propose a novel generative model for adversarial training. Let (x+(), (0-,),,(00) (() denote the jth noise-free sample. In our model, we assume the adversary has attacked the system and disturbed the noise-free free features (i) as shown below:
yd (1), yb) y(() + tel), x(0 - =000 + ((x
(1)
3

---

Published in Transactions on Machine Learning Research (12/2024)
where gr6و R, x- R", w" E R", and A(x+()) is the adversarial perturbation which can be any sub-Gaussian random variable possibly dependent on x1)) (See Appendix E.3 for an example). Let S = S(w*) denote the support of w", i.e. the set of indices corresponding to non-zero entries of w*. Let k = ||] denote the cardinality of the support, and hence p- - k = |. We argue that our proposed model is more general than other existing models the literature, including the Huber model in Lemma 3. Our theoretical and empirical analysis (Appendix E.4) draws interesting inferences using this model. We assume only adversarially corrupted data, that is, n independent samples of {y(9), x( for j E [n] are available for training, which makes the problem challenging
compared to existing works which assume availability of uncorrupted features x+) Let X E Raax be the collection of n samples xli) for j E [n]. For brevity, we may drop the superscript (i) later. Let the population covariance matrix of X* be denoted by Σx We assume that x is a zero-mean sub-Gaussian random variable with variance proxy parameter o² for i E [p]. We assume that e is a zero-mean sub-Gaussing random variable with variance proxy o².
Adversarial perturbations are typically bounded by some budget for each sample (Zhai et al., 2019; Balda et al., 2019; Yin et al., 2019; Cohen et al., 2019) so that the underlying model is learnable. We model this fixed budget a parameter in our analysis, and hence, we provide performance guarantees as a function of this parameter. We choose adversarial perturbations to be sub-Gaussian random variables, which generalizes the regime of bounded perturbations. Adversarial perturbations can also be dependent on the uncorrupted regressors, x* for each sample. To clarify, A ((x*()) can be dependent on x*(),, where denotes the 7th sample, but A (1) is independent of x+), if i j j, where j denotes another sample. Note that the adversary does not have control over the uncorrupted regressors x", but has access to x", which can be used design A(x*) in an arbitrary manner (that may make the support recovery problem more challenging).
Assumption 1. (Adversarial Perturbation) (xx) is a zero-mean sub- Goussian random vector with pa- rameters (E),)"), which can be conditionally dependent on uncorrupted data. Here Σ is the population covoriance matriz of the adversarial perturbation (A(x*)) and y2 is the variance prozy parameter for some I
In the above definition, we require that E (exp (xTA(x*))) S exp (aT)*r")/)) for all a E Rp which is akin to the classical definition (Hsu et al., 2012) as discussed briefly in Appendix A.1.
2.1 Existing attacks are special cases of our adversarial model
Note that a random variable is more general than deterministic one, i.c., a deterministic quantity is a random variable with a Dirac delta probability density function. Hence, existing deterministic adversarial attacks (Goodfellow et al., 2015; Madry et al., 2018; Szegedy et al., 2014; Xing et al., 2021; Yin et al., 2019; Awasthi et al., 2020; Qin et al., 2021) are a special case of our adversarial model specified in Assumption 1.
Lemma 2. Existing adversarial ottacks (Goodfellow et al., 2015; Madry et al., 2018; Szegedy et al., 2014; Xing et al., 2021; Yin et al, 2019; Awasthi et al., 2020; Qin et al., 2021) are a special case of our adversarial model specified in Assumption 1.
The proof of the above lemma uses the fact that the aforementioned attacks use a vector A(x*) with bounded norm, and then shows that any vector with a bounded norm is sub-Gaussian random vector.
The a- -oueer-model (Prasod et al., 2020; Diakovikolas et al., 2019) corrupting only fraction of samples is special case of our adversarial model specified in Assumption 1.
Lemma 3.
The proof of the above lemma designs an adversarial attack A(x*) that returns 0 with probability 1- a and a carefully defined perturbation that depends on x* with probability a.
Remark 4. The class of sub- Gaussian variates includes for instance some unbounded random variables (e.g., Gaussian variables), any bounded random variable (e.g. Bernoulli, maltinomial, uniform), any random variable with strictly log- concove density, and any finâte mixture of sub- Sabb-Gussian variables. Hence, our adversorial model is more general.
4

---

Published in Transactions on Machine Learning Research (12/2024)
2.2 Our adversarial attack is more challenging than existing attacks
It may look obvious for an adversary to spend its fixed budget for a sample to disturb the support entries (xs) only, since y²(i) = w = 1
X Vj. We assume the adversary attacks the non-support entries (Xs=) as well, to make the learning lask of estimating S and S lougher, which is formalized in the following lemma.
Lemma 5. If the adversary attacks only the support entries (xs) or the non-support entries (xS=) with non-zero-mean adversarial perturbalion, then the learner can guess the support trivially with probability al least 1 - O (%/) if n = Q (log(p)).
The proof of the above lemma relies the fact that the sample mean of feature vector x6) for E [n] will be close to the population mean. If only the support is attacked, the sample mean is away from zero for entries in the support, and is zero for entries in the non-support. Hence, the learner can guess the support by just computing the sample mcan.
Lemma 6. The support can be trivially estimated in S2 (log(p)) samples with high probability under eristing adversarial atlacks (Goodfellow et al,, 2015; Modry et al., 2018; Szegedy et al., 2014; Xing et al, 2021; Yin et al., 2019; Awasthi et al., 2020; Qin et al., 2021) aiming to mazimize per-sample loss function.
The proof of the above lemma first shows that the aforementioned methods atlack only the support, and then uses Lemma to make the final claim.
In order to avoid such a trivial case, we consider the pero-mean in Assumption 1.
2.3 Other assumptions for support recovery
In this section, define few quantities used in analysis later. Let the sample covariance matrix of X be denoted by Ex = X and the population covariance matrix be denoted by Σ* For the uniqueness of the solution to the problem stated in Eq. (2), we need submatrix of the sample covariance matrix to be positive definite. But as X is assumed to be random, we assume the population covariance matrix of X* to be positive definite as done in prior literature (Wainwright, 2009; Ravikumar et al., 2011; 2010; 2009; Daneshmand et al., 2014).
Assumption 7. (Positive Definiteness) The méndmuu eigenvalue of the population covariance matrix of x* fulfills Amin (EX') Cmii > 0.
Let the population covariance matrix between adversarial perturbations A (xx) and measurements x* be denoted by A Similarly, the minimum eigenvalue of the population covariance matrix of adversarial per- turbations in the support S, denoted by E is Diin 2 0. The minimum eigenvalue of [Σ + Σ* A > lss//2 is denoted by Fmin; which influences the sample complexity as discussed in Lemma 13. Similarly, the maximum eigenvalues of matrices { EA, ΣAx' } are denoted by {Cmax. Dmax. Fmax), whose influence on sample complexity can be seen in Lemma 15. Further, we make the assumption of mutual incoherence, which implics that the regressors in the non-support St do not have a strong correlation with regressors in the support S.
Assumption 8. (Mulual Incoherence) For some 7 E (0,1), X (E%)) 1||| -1-7.
This assumption is not restrictive (see Lemma 18) and has been used in various works related to sup- port recovery (Wainwright, 2009; Ravikumar et al., 2011; 2010; 2009; Daneshmand et al., 2014). In and || Hmax I co. We refer to (r,7, Fmin, Fmax: Dminy Dmax Gmax, Hmax) as the budget given to the adversary for corrupting each sample.
addition, we also assume [|([5s)] 00 Gmax
2.4 Necessary condition for support recovery
We derive the following necessary condition for support recovery relating the adversarial budget to the model parameters. Note that the following requirement is for all methods and is not limited to Lasso.
5

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma 9.
The condition 16b (1+ }) 2 < min /w]), where b == .ES
Ex a fols
w is necessary for support
15y
recovery, even in the population regime, where (intuitively speaking) the learner has access to an infinite number of samples.
In the above lemma, we prove the necessary condition by considering a case where support recovery is impossible if the required condition is disobeyed. The proof carefully constructs a specific case where the uncorrupted data as well as the adversarial perturbations are both Gaussian, and then uses the fact that Gaussian distributions are fully identifiable from its first and second order moments to argue for impossibility.
With slight abuse of terminology, the above lemma. implies that the coefficients in the parameter vector must. be sufficiently large compared to the adversarial budget for successful detection. With brief discussion of our assumptions in this section, we present our main theoretical result in the next section.
3 Our Main Result
In this section, present and discuss our main theorem that implies sample complexity of n = S2 (k² log(p)) for correct support recovery with high probability (except when there is correlation between the adversarial perturbations and uncorrupted data). We provide formal and intuitive implications the proposed theorom first and further present its proof.
The Lasso problem under the adversarial setting can be stated as:
W = arg miggm)))(w) + A//w//2 = arg min Ily Xw + A//w// wEBP 2n
(2)
WEBP
Our main theoretical result for the above problem as follows. Theorem 10. If = 22122 log(p)), Assumplion 1, 7, and 8 hold, and
16b
qıoe
2 2lo((p)
16g
(pg((p)
2 max
n
where = r w's max
oV E tr Σ b
=
Sp
w
qî = 3 (Cmax + 2Fmax + D Dmax)),
(E
then with probability of at least - 1 (1/2), we have:
1. The true support is recovered, i.e., S(w) C S(w") equivalently w, 0, Vi $ S(w*)
2. Ws is the unique solution for the Lasso problem stated in Eq. (2).
3. The estimated parameter vector satisfies
Iws - w'lloo & A11+ 7/1) 3Gmas/2 f(A)
(3)
4. w, # 0 and furthermore (w;; = sign (W7) Vi S(w*) if min |w > 2f (A). FES
Opxk, and therefore b b= 0, then A > O (vTn(tl//m) hold true and statement 3 is modified to
Additionally if p S
statement 1, 2, and 4 still
Iws - w'lloo =())= (Viig(r))
The first two claims of the Theorem 10 imply that we can uniquely recover the true support with high probability, assuming we have sufficient number of samples if we choose a regularization parameter À greater than a certain threshold. Note that choosing a very large value of X is not desirable as it would also increase the upper bound for || w'llloe as per the above theorem (Eq. (3)). The fourth claim of the thcorem states that the minimum magnitude among the support entries of the regression parameter vector should be greater than certain function of À for correct sign recovery.

---

Published in Transactions on Machine Learning Research (12/2024)
Intuition. Note that the adversary can increase the lower bound of X. For example, if b O, then À = 16// even for n + oo, resulting in a higher value of f()) in Eq. (3). This may lead to the violation of the requirement in statement 4, minge |wł] 2 2f (A); if the smallest entry in w is not large enough. Support recovery may not be possible in such a case due to a low probability of non-support recovery P|vi & S, úē; = 0] (See Appendix E.4).
We have formally proved a similar requirement in Lemma 9 for all methods not limited Lasso. But it is worth noting that substituting À 16b in Eq. (3) leads to the requirement stated in Lemma 9. The term min |w]| can be seen in statement 4 of Theorem 10. Hence, our analysis for Lasso relates to the necessary iES
condition for all methods.
In statement with b 0, the situation mentioned above can be avoided by increasing the value of n appropriately despite any efforts from the adversary. This helps to identify different regimes under which we can provide theoretical guarantees of Lasso for successful support recovery under adversarial attacks and also the case which may be lavorable to the adversary (See Section 3.2).
Proof Sketch. We use a constructive proof technique: primal-dual witness (PDW) method (Wainwright, 2009; Ravikumar et al., 2011; 2010; 2009; Daneshmand et al., 2014) to prove Theorem 10. The proof outline is summarized below:
The PDW framework starts by allowing us to find sufficient conditions to estimate the elements of the non-support (89) first by ensuring strict dual feasibility (Section 3.1). This step ensures that we correctly recover the zeroes, i.., w; 0 for all i & S(w*). This establishes the first claim of exact support recovery in Theorem 10.
We then derive the sufficient conditions for uniqueness of ws (Section C.1), which proves the second claim of Theorem 10.
The goodness of the estimated paramcter vector is proved in Section C.2 by deriving an upper bound on -oss-wsllla
|ws - wssllo to justify the third claim of Theorem 10.
Armed with the second and third claim, we prove the fourth claim of Theorem 10 for correctly recovering the non-zeros, i.c., W; + 0 for all i E S(w*).
Remark 11. For clarity of exposition, we focus on sub- nob-Gaussian data. Our proofs can be extended to heavy-tailed data by using m-order moment concentration instead of sub- Gaussinnsn concentration, as done in (Ravikumar et ol., 2011) for another machine learning problem. This will lead to sample complerity polymomial in p, instead of logarithmic in p.
3.1 Exact Support Recovery
In this subsection, we verify the stationarity, complementary slackness, and strict dual feasibility conditions for the optimal solution wg. The stationarity condition is (See Appendix D.1):
vi((ws, 0)) + \² = 0px1
(4)
where à E Ø [[W]], belongs to the sub-differential set of the & norm at w. In the context of the primal-dual witness framework (Ravikumar et al., 2010; 2011; 2009; Daneshmand et al., 2014), ws and á are referred as the primal and dual variables respectively. As à belongs to the sub-differential set of the & norm, we can claim that || < 1 by norm duality but for strict dual feasibility we need ||25=11oo < 1 as stated in Lemma of (Wainwright, 2009). In order to ensure this condition, we need to first derive åg. from the first order stationary condition in Fq. (4) which is a p-dimensional vector equation and can be written for elements in S and 8 separately to derive ag.. The final expression is (See Appendix D.1 for more details):
20: = 2S. + +2 is XI Xs (XIXs) -è2
2s
(5)
2s: =X]. (P/Xn) (e- A A(X))'s), where P= [I, -X (XIXs) -xx)
(6)
7

---

Published in Transactions on Machine Learning Research (12/2024)
where In represents identity matrix of dimension n, ( is x p matrix containing n samples of adversarial perturbation. We have decomposed 2ge in two terms 2,5 and As to bound them separately in next two sub-sections.
3.1.1 Analyzing adversarial attack on support (S) and nun-support (S*)
Let R = X and Q = - obtained after simplification for 2 in Eq. (5) is (See Appendix D.2):
s, and hence E [ S' E E = Sss- The simplified expression
X Xs (XIXs)
|11
S m. + m2 + ma + m4
(7)
where m1, m2, ma, and m4 are defined as:
m1 RR
m2 = || (Q-1 -0 R (E(Q)) E
E
R.) (E
"Il m4 =
m3 RR
This carefully constructed decomposition of ăs* has given us the freedom to study the effect of the adversarial perturbation on the non-support entries and the support entries by analyzing my and my respectively. The term my in Eq. (7) can be bounded using the mutual incoherence Assumption 8. We propose Lemma 12 and Lemma 13 to bound the terms m1, m2, and my discussed below.
The variable my in Eq. (7) is function of the adversarial perturbation in 8 for a fixed value of E [[] E> To bound my, we use the mutiipliilee property of norms:
mi S
Es
(2ss)
Lemma 12. n 1 12 (f"e log())/6=) and 0 < 8 32Ek, then x Xs E Ilae Só with probability at least 1 - O (1)), where & = max iES
0 D
try
E A
max JES
-5 + +r Σ
The proof of the above lemma relics on properties norms and sub- Gaussian distributions, union bound, and sub-exponential tail bounds. We can claim the following by substituting 8 = 1/1))) 'Ill. Lemma 12:
mi |||
E (E (E QQ) 7/116
if n = O O log(pl/72).
Intuition. It should be noted that the value of chosen to analyze the adversarial perturbation in S is a function of the adversarial perturbation in S as E/s- = ES's + [ Σx Iss + Egs- Hence the increases, then the learner is forced to choose a smaller value of in Lemma 12 for the adversarial perturbation in S which increases the sample complexity. This also demonstrates the counterintuitive point that an adversary can influence the sample complexity by an attack on the non-support (See Lemma 6). The next step is bound the term m2 in Eq. (7) using the following lemma.
adversarial perturbation in S is designed such that Ginxx = (>)))
Lemma 13. If n Ω (I² log(t)/8 (Cmm 2mmnn)D))))))) then with probubilily of at least 1 O (1/p) we have (1xxxxx)
(E%))
8..
The proof of the above lemma relies on properties of norms, sub-Gaussian tail bounds, and also the bound for [ (X*)= Σgr ||2 derived in the following theorem.
Theorem 14. For < < 32roaba
X
E Raxk a² = max Ejj, 03 k Σ (IA)
we have:
jES
SES
n < 4e 2bet
P
TT X
A
(X3)
AAX
>
(9)
2
8

---

Published in Transactions on Machine Learning Research (12/2024)
The proof of this theorem is interesting as X A (X3) is non-symmetric matrix, which makes the problem slightly challenging compared to symmetric matrices. Hence we use Lemma 20 to transform a non- symmetric matrix to a symmetric matrix without changing its spectral norm. Further, we use Lemma 6.12 from (Wainwright, 2019), which states for a random symmetric matrix M
2 2 6) S 2tr (VM(A)) e ->
(10)
where 8 8>00 O, (A) denotes the moment generating function (MGF) and represents the trace. Thus, derive the bound of |M]lp we bound the trace of the MGF of M. Using the properties of aub-Gaussian and sub-cxponential distributions, derive matrix V E 2 such that
A²v
(M & SET
Hence, in order to bound the trace of (A), we focus on the cigenvalues of V. We observe that V is a matrix with only two non-zero eigenvalues. This helps us to derive improved bounds as compared to the case of all 2k eigenvalues being non-zero. More details can be seen in Appendix D.5.
Returning deriving bound of m2 Eq. (7), we substitute 8 = [ ll Lemma 13:
m2 =
R Q-11- - (E (E 1 S 2/88
(11)
if n Q (1² log(p) H 2 (Cmin +2F Dmmn) )
Intuition.
This analysis provides insight into the nature of the dependence of the sample complexity on the dimensions (k and p), and also other parameters such as mutual incoherence (7), minimum eigenvalues {Cmiu: Dmin: } and other constants like Hmax-
Further, we proceed to bound the term ma in Eq. (7) by using the sub-multiplicative property of norms and substituting v in Lemma 12 and Lemma 13 to claim:
m3 [R ER)iI ||| (Q- (Q--1op-(000000
(B (Q)
S 2//16
if n = Ω (As2 log(p)). We substitute Eq. (8), Eq. (11), and the above equation in Eq. (7) to arrive at:
||as Il.o < - y 7/16 + 7/8 + 7/16 = 1 1 33/4
(12)
In this sub-section, we derived an upper bound for the infinity norm of ês-,, which will be used later to bound the infinity norm of 25== defined in Eq. (5) to ensure strict dual feasibility. More importantly, our analysis also sheds light on the dependence of the sample complexity on parameters such as mutual incoherence, minimum eigenvalue, and other constants like Gmax and Hmax, which helps to study critical scientific limitations behavior of the Lasso algorithm under adversarial attacks.
3.1.2 Choosing regularization parameter (A)
In this subsoction, we continue the discussion on strict dual fcasibility and focus on how the adversary affects the regularization parameter. We start from &s=,, in Eq. (6), which is (p k) dimensional random vector. Using properties of norms, whose details mentioned in Appendix D.6 and using the bound derived in Eq. (12), we arrive at:
1 A
+ (
2 5/ 1l.o
I x
Pe
(13)
This decomposition enables us to analyze the effect the adversarial perturbation on various model parameters. For example, the first term on the RHS of the above equation is concerned with the interaction of adversarial perturbations in S with e. This term can be bounded by choosing an appropriate value of X, as shown in the following lemma.
Intuition.
9

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma 15. x 2 2 / (log(e) where constant oî = 3 (Cmax + 2Fmax + D Dmax), then 1x Po/pPo/ 7/8 with probabilily of at least (1/))
Similarly, the second term on the RHS of Eq. (13) signifies the interaction of adversarial perturbations with X It can be bounded by choosing suitable value of X, shown in the following lemma.
Lemma 16. If A2 16 max
Alogbpl/n then |x | ((3) S 7/8 with probabilily of al w and Q2 = rv w's ESS pls
b2 Q2
least O (1/), where b2
x
W
max EES
0V b +
E
Similarly, the third term in RHS of Eq. (13) is concerned with the interaction of adversarial perturbations in X It can be bounded by selecting suitable value of X, presented in Lemuna 24 in Appendix D. Substituting the bounds derived in Lemma 15, Lemma 16, and Lemma 24 in Eq. (13), we obtain:
j al. S 7//8+ 7/8 7/8- 31/8
(14)
It should be noted that this bound is derived under some lower bound constraint on the regularization parameter. The lower bound can be obtained by taking the maximum of X1, A2, and X presented in Lemma 15, Lemma 16, and Lemma 24 respectively in Appendix D:
16b Q1oe 7
log(p) 16g
(l)g(p)
A 2 max (11, )2, = max
(15)
where q = TV W's SS w's max iElp] proof of X used in Theorem 10.
+ r
DA
and b b=
Σx' D
w
This completes the lower bound
Intuition. Note that for a fixed budget, the adversary can increase the lower bound of À by designing Σgs such that the eigenvector corresponding to the maximum eigenvalue of E is parallel to w to increase in Eq. (15). A higher value of the lower bound of À implics more penalization on the regression parameter vector, which might make the learning algorithm to incorrectly estimate the small non-zero parameters S as zero.
Returning to the strict dual feasibility condition, the bound for 2s. defined in Eq. (5) is derived by using the bound for 2 in Fq. (14) and the bound for 2s- in Eq. (12) as follows:
37 +
37
37
|Rselloo S
<1
(16)
8
8
In this sub-section, we have verified the strict dual feasibility condition by proving that ||gs= 1lo in the above equation. This ensures that KKT conditions are met, which proves the first claim of Theorem 10, i..., S(w) S S(w"). It should be noted that we derive the lower bound constraint on À in order to provide theoretical guarantees. For practical purposes, we choose À = O (Vor(ml//) as done in the sparse regression literature (Wainwright, 2009; Ravikumar et al., 2009; 2010; 2011; Daneshmand al., 2014).
< as 7 > 0
The remaining claims on uniqueness and upper bound of |sw - w3s loc are discussed in Appendix C.1 and Appendix C.2 respectively. In the next section, discuss the interesting implications of Theorem 10 regarding the regimes when the adversary and Lasso can dominate over each other.
3.2 Adversary Lasso Territory
If X max (di, d2, = 166/7, then need the following condition per Theorem 10:
min | 2 2f(A) = 12Gmax (1 + 4/7) EE
(17)
This requirement on the lower bound of the absolute value of parameters in the support basically states that these coefficients should have significant values for detection. If the adversary is given more budget and
10

---

Published in Transactions on Machine Learning Research (12/2024)
designs a large value S A w to break the above requirement (Eq. (17)), then we may not be p
able to provide theoretical guarantees for successful support recovery as proved in Lemma 9. Our theoretical analysis has identified the critical condition under which the adversary can design malicious attacks such that the Lasso algorithm may not have high probability of successful support recovery (See Fig. 1(b)).
Consider the case with piss = Opxk: and hence b = 0. Therefore X = max (A1, 22, As} max (A2, As} =
O (( ( (lostel/s). then the previous requirement becomes:
min w 2 2f(A) =O (0 iES
(18)
This condition can be easily fulfilled by increasing the value n sufficiently high depending on the value of minges |w;,, and hence, theoretical guarantees can be established. The adversary can still try to break the above condition by increasing the value of 91 or q in X2 or X3 respectively, but the user can increase the sample size (n) accordingly as derived in various lemmas to ensure a high probability of success. Note that. the condition min |w]l
EX P
= 0 specified in Lemma 9 holds true for this case.
In this subsection, completed the proof of Theorem 10 and discussed the critical regimes which may be favorable to the adversary or the learning algorithm. We also discussed the counter-intuitive result of how the adversarial perturbation in S can affect the guarantees for ws indirectly by influencing the lower bound on the regularization parameter.
4 Experiments
In this section, we validate our proposed theoretical claims with empirical analysis on synthetic data and real-world data. Please refer to Appendix E for more details.
Prob. of success
Prob. of success
0.8
0.8
0.6
0.6
0.4
0.4
128
128
0.2
p 256
0.2
== 256
p 512
p 512
0
0
27
104
207
413 619 1237 2474 3710 4947
27
646
1264 1882 2500 3119 3737 4355 4974 Rescaled Sample size (n/log(p))
Rescaled Sample size (n\loy(p))
(a) b=0
(b) o
Figure 1: Probability of support recovery vs rescaled sample size.
Synthetic data. To verify the sample complexity result of n ((log(p) for fixed k, we repeat the support recovery experiment 200 times for a particular value of (n, p). We report the empirical probability of successful support recovery. We perform this experiment for p E {128, 256, 512} and vary n such that n Tog(o] E (25, 1250). The results presented Figure 1(a) for constant), as the plots are overlapping (See Appendix E.1 for details regarding the data and adversarial perturbation generation.). For of 0, Figure 1(b) shows that perfect support recovery is not achievable due lo the dependence between adversarial perturbations and uncorrupted data (See Appendix E.4 for more details).
show that [ogíø] is not a function of p (hence
Real-world data. We used the BlogFeedback dataset (Buza, 2014) which contains 52397 samples and 276 features. We first recover the "true" support with the given data and further estimate the support from
11

---

Published in Transactions on Machine Learning Research (12/2024)
adversarially corrupted data, which is generated by adding adversarial perturbations to all the features. The Lasso algorithm recovers the support with F1-score of 0.94.
5 Concluding Remarks
Sparsity, support recovery and weight rocovery are tightly related concepts. In our paper, support relates the eero/nonzero weights in the sparse regression vector (nonzero entries corresponding relevant features for prediction) and weight recovery relates to estimating vector that is close (in for distance) to the true regression vector (See e.g. Theorem 10, Eq. (3)).
Our initial analysis for sparse regression already highlights some fundamental issues that not only pertain to sample complexity, e.g,, impossibility. Our initial results could be later extended to other machine learning problems where sparsity as well as support and weight recovery is relevant. This includes for instance, Gaussian graphical models (Ravikumar al., 2011), Ising models (Ravikumar et al., 2010), non-parametric regression (Ravikumar et al., 2009) and diffusion networks (Daneshmand et al., 2014).
Besides the aforementioned models, we believe our results could potentially motivate future work neural networks. Indeed, there has been a recent interest on sparse neural networks (Liu & Wang, 2023) as well as weight recovery for two-layer neural networks (Bakshi et al., 2019).
References
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431-441. PMLR, 2020.
Ainesh Bakshi, Rajesh Jayaram, and David P. Woodruff. Learning two layer rectified neural networks in polynomial time. Conference. on Learning Theory, pp. 1-73, 2019.
Emilio Rafael Balda, Arash Behboodi, and Rudolf Mathar. Perturbation analysis of learning algorithms: generation of adversarial examples from classification to regression. IEEE Transactions on Signal Processing, 67(23):6078 6091, 2019.
Adarsh Barik and Jean Honorio. Provable computational and statistical guarantees for efficient learning of continuous-action graphical games. IEEE International Conference on Acoustics, Speech and Signal Processing, 2023.
Dimitris Bertsimas and Dick Den Hertog. Robust and Adaplive Oplimization. Dynamic Ideas, 2020.
Krisztian Buza. Feedback prediction for blogs. In Data analysis, machine learning and knowledge discovery, pp. 145-152. Springer, 2014.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310 1320. PMLR, 2019.
Hadi Daneshmand, Manuel Gomez- Rodeez-odrrgguzz Le Song, and Bernhard Schoelkopf. Estimating diffusion
network structures: Recovery conditions, sample complexity & soft-thresholding algorithm. Tn International conference machine learning, pp. 793 801. PMLR, 2014.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, pp. 1696-1606. PMLR, 2019.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015.
Matthew Herman and Thomas Strohmer. General deviants: An analysis of perturbations in compressed sensing. IEFE Journal of Selected Topics in Signal Processing, 4(2):342 349442299,,40 2010.
12

---

Published in Transactions on Machine Learning Research (12/2024)
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail incquality for quadratic forms of subgaussian random vectors. Electronic Communications in Probubilily, 17:1-6,4 2012.
Shiwei Liu and Zhangyang Wang. Ten lessons we have learned in the new "sparscland"; " A short handbook for sparse neural network researcher. International Conference on Learning Representations, Workshop Sparsity in Neural Networks, 2023.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(3): 601-627, 2020.
Zeyu Qin, Yanbo Fan, Hongyuan Zha, and Baoyuan Wu. Random noise defense against query-based black-box attacks. Advances in Neural Information Processing Systems, 34, 2021.
Pradcep Ravikumar, John Lafferty, Han Liu, and Larry Wasserman. Sparse additive models. Journal of the Royal Slalistical Sociely: Series B (Slatistical Methodology), (1(5:00009 1030, 2009.
Pradeep Ravikumar, Martin Wainwright, and John D Lafferty. High-dimensional ising model selection using fi-regularized logistic regression. The Annals of Statistics, 38(3):1287-133) 2010.
Pradeep Ravikumar, Martin J Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing l--penalized log-determinant divergence. Electronic Journal of Statistics, 5: 935 980, 2011.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. Advances in Neural Information Processing Systems, 31:5019 5031, 2018.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks IEEE Transactions on Evolutionary Compulation, 23(5):828 841, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
James Victor Uspensky et al. Introduction to mathematical probobility, McGraw- Hill Book Co., Inc., 1937.
Roman Vershynin. How close is the sample covariance matrix to the actual covariance matrix? Journal of Theoretical Probability, 25(3):655-686, 2012.
Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using Il-constrained quadratic programming (lasso). IEEE transactions information theory, 55(5):2183-22000 2009.
Martin J Wainwright. Higgh-dieensional stotistics: non-asymptotic viewpoint, volume 48. Cambridge
University Press, 2019.
Yue Xing, Ruizhi Zhang, and Guang Cheng. Adversarially robust estimate and risk analysis in lincar PMLR, 2021.
regression. In International Conference on Artificial Intelligence and Statislics, pp.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust. generalization. In International conference on machine learning, pp.
PMLR, 2019.
Runtian Zhai, Tianle Cai, He, Chen Dan, Kun He, John Hoperoft, and Liwei Wang. Adversarially robust. generalization just requires more unlabeled data. Xr preprint Xrxio: 00555, 2019.
13


Reviews:
[{"review_id": "QL6ofoS2na", "reviewer": "Reviewer_xbhc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* Studying concrete toy cases is a useful way to gain theoretical insights into adversarial learning. Such insights can subsequently inform practice.\n* The results and techniques are nice (provided they are correct --- see comments below on this point).\n\n### Weaknesses\n\n* The paper treads a lot of familiar ground that was explored in earlier results. While novelty is not a criterion for TMLR, the paper probably needs to engage with the literature better before it can be published. In particular, it misses discussion/connections with at least two major lines of work that I am aware of. \n\n    The first line of work is from the robust sparse recovery literature. (I am aware of the distinction between generic robustness and adversarial perturbations, but in the authors' model of stochastic perturbations the two settings seem tightly connected.) I would start with discussing Herman/Strohmer's 2010 paper, \"General Deviants: Analysis of Perturbations in Compressed Sensing\", and also revisit any relevant follow-up papers. \n\n    The second line of work is from the (theoretical) adversarial learning literature. I would start with discussing Schmidt et al (2018), \"Adversarial learning requires more data\", which shows an analogous gap between standard and adversarial sample complexity in the classification setting, and revisit any relevant follow-up papers. \n\n* The paper is not mathematically precise. I would encourage the authors to do a thorough review of the manuscript with a critical eye in order to ensure mathematical correctness.\n\n* The paper can benefit from intuition surrounding the main results, proof techniques, and implications. I see that there is a good amount of discussion in the appendix, but found the main paper somewhat lacking in this aspect. Eg. Lemmas 2,3,6,9 are presented without a proof sketch. If space is an issue then the last parts of Section 3 can be moved to the appendix. Also, a bit more discussion about the discussion between the paper's techniques and classical sparse recovery results (e.g. the support recovery work of Wainwright '09) may help. \n \n### Other questions\n\nI am a bit confused by a few points but these are likely due to my own lack of understanding:\n* Where does the noise variance $\\sigma_e$ appear in any of the sample complexity bounds? (alternately, is there a assumption that this is bounded?)\n* Where does the $k^2$ dependence come from? As I understand, it comes about due to Lemma 11 and Theorem 14, but more intuition would be helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Summary\n\nIn this paper: \n* the authors introduce a new theoretical framework for studying adversarial attacks on sparse recovery algorithms (such as the Lasso).\n* under this framework, they prove that adversarial learning requires more data: under adversarial perturbations of the data, the sample complexity of support estimation of a $k$-sparse length-$p$ vector using the Lasso is $O(k^2 \\log p)$, as opposed to the standard $O(k \\log p)$ bound for regular recovery,\n* they show that this quadratic dependence on $k$ can be reduced to linear dependence under certain additional assumptions.\n* they support their theoretical results with some basic simulations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Better discussion of the relevant literature. \n* Better intuition of the theoretical analysis (especially the proofs, and the source of the various parameter scalings) in the main paper.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wFsSoNcMkz", "reviewer": "Reviewer_yjy2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nNovel Adversarial Model: The submission introduces a more sophisticated adversarial model that is conditionally dependent on uncorrupted data. This novelty is important because it demonstrates how adversarial perturbations that correlate with the true data structure can significantly increase the difficulty of support recovery. The introduction of zero-mean sub-Gaussian perturbations adds complexity and realism to the attack model compared to simpler methods like FGSM, which only focus on maximizing the loss function.\n\nRigorous Theoretical Contributions: The paper provides a detailed theoretical analysis of support recovery under adversarial attacks, deriving necessary conditions and sample complexity bounds. The result that the new adversarial model demands O(k^2log(p)) samples for support recovery, where k is the support size and p is the feature dimension, adds valuable insights into the robustness of sparse models under attack. This shows a clear improvement over simpler attacks that do not exploit the correlation with uncorrupted data.\n\nChallenging the Effectiveness of FGSM: By showing how attacks that consider correlations with uncorrupted data outperform simple gradient-based methods like FGSM, the paper provides a strong critique of existing methods and suggests avenues for improving the robustness of models. This insight could influence future research in adversarial machine learning.\n\nEmpirical Validation: The authors back their theoretical findings with experiments on both synthetic and real-world data, which is crucial for validating the theoretical results. The demonstration that perfect support recovery is not achievable when the adversarial perturbations correlate with uncorrupted data (i.e., when b!=0) strengthens the claim that these new attacks are more effective.\n\nWeakness:\nSupport Recovery as a Metric: While relevant for sparse models, support recovery may not fully capture adversarial effectiveness, especially in neural networks where the concept of strict support doesn’t apply. The paper could discuss how its findings generalize to broader models.\n\nLimited Practical Relevance: The study focuses on Lasso regression, which may limit its applicability to models like neural networks where all weights contribute. A discussion on generalizing to other model types would strengthen the paper.\n\nAssumptions on Perturbations: The reliance on sub-Gaussian, zero-mean perturbations may not always align with real-world adversarial attacks, which might behave differently.\n\nEmpirical Clarity: More detailed explanations of the empirical setup and generalizability of the attack method could improve the paper’s practical applicability and reproducibility.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a theoretical study on support recovery in Lasso regression under adversarial attacks, focusing on how adversarial perturbations affect the recovery of non-zero coefficients in a sparse regression model. The authors critique existing deterministic adversarial attack models like FGSM, which primarily maximize the loss function and can be countered with few samples, and propose a more challenging adversarial model involving zero-mean sub-Gaussian perturbations that depend on uncorrupted data. The paper derives a necessary condition for support recovery that applies to any algorithm, not just Lasso, identifying key parameters like mutual incoherence and the covariance between adversarial perturbations and uncorrupted data as critical factors. The authors show that sample complexity for support recovery under adversarial attacks is O(k^2log(p)), where k is the size of the support and p is the number of features, and prove that when adversarial perturbations align with the support (i.e., b!=0), perfect support recovery becomes impossible. Empirical validation confirms these findings, demonstrating that when b=0, support recovery can be achieved with a sample complexity that scales logarithmically with p, but with b!=0, recovery is far more challenging. The paper contributes to the understanding of adversarial robustness in sparse models and, while primarily focused on Lasso regression, provides insights that could inspire further research in adversarial machine learning and robustness in more complex models like neural networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Practical Relevance and Generalization to Neural Networks: Given that adversarial attacks are often discussed in the context of neural networks, providing more analysis or discussion on how the proposed adversarial model and results can be generalized to these settings would significantly improve the paper’s broader relevance.\n\nClarify Assumptions on Perturbations: The assumptions regarding sub-Gaussian and zero-mean perturbations should be justified further, or alternative scenarios should be discussed to cover more realistic adversarial conditions.\n\nProvide More Empirical Details: Including more details about how adversarial perturbations are generated and whether the method can be generalized to different datasets would strengthen the empirical validation and improve reproducibility.", "broader_impact_concerns": "There is no impact concern regarding the ethical implications of the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fSrpszZnbY", "reviewer": "Reviewer_7qn5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Theoretical results of the paper seem solid, and well corroborated in experiment\n- Paper is comprehensive and each result is justified\n- Interesting insights are given when interpreting the theoretical findings\n\nWeaknesses:\n- I believe the paper is not citing several works done on Robust Linear Regression addressing this exact type adversarial noise, see for instance Robust and Adaptive Optimization by D. Bertsimas and D. den Hertog, 2022. It would be good to integrate this part of the literature and see how they complement the findings\n- Typos: several typos in the paper (too many to keep track of), making reading hard to follow at times\n- Clarity and rigor: reasonings in proofs are not always easy to follow and not completely rigorous, for instance:\n  - Appendix A section 7: proof unclear, please explicitly explain how the result from the paper cited allows to prove the lemma\n  - Appendix B: assumption that there exists such a case is not proven\n  - Organization of the paper: lemmas introduced are only proven much later", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses theoretical aspects of Lasso regression in the context of an adversarial attack. In particular, it focuses on the support recovery problem, i.e. recovering and estimating all non-zero regression coefficients. The type of attack is chosen to be more general and more challenging than previous results in the literature, as it disturbs both features of the support and outside. \nThe paper claims multiple theoretical properties to allow for the support to be recovered and these coefficient to be suitably estimated with Lasso, including necessary conditions on the adversarial attacks and a lower bound on the regularlization term. The results are also corroborated with numerical experiments on both a synthetic and real-world dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers acknowledge the theoretical insights provided by the manuscript as well as the empirical validation. They note that the results may be of limited practical relevance with a small problem scope.
Decision: Accept (poster)