Robust Testing in High-Dimensional Sparse Models
Authors: Anand Jerry George
Clement Louis Canonne
Venue: NeurIPS 2022 Accept (2022)
Keywords: Robust hypothesis testing
Sparse mean testing
Sparse linear regression

Abstract: We consider the problem of robustly testing the norm of a high-dimensional sparse signal vector under two different observation models. In the first model, we are given $n$ i.i.d. samples from the distribution $\mathcal{N}\left(\theta,I_d\right)$ (with unknown $\theta$), of which a small fraction has been arbitrarily corrupted. Under the promise that $\|\theta\|_0\le s$, we want to correctly distinguish whether $\|\theta\|_2=0$ or $\|\theta\|_2>\gamma$, for some input parameter $\gamma>0$. We show that any algorithm for this task requires $n=\Omega\left(s\log\frac{ed}{s}\right)$ samples, which is tight up to logarithmic factors. We also extend our results to other common notions of sparsity, namely, $\|\theta\|_q\le s$ for any $0 < q < 2$. In the second observation model that we consider, the data is generated according to a sparse linear regression model, where the covariates are i.i.d. Gaussian and the regression coefficient (signal) is known to be $s$-sparse. Here too we assume that an $\epsilon$-fraction of the data is arbitrarily corrupted. We show that any algorithm that reliably tests the norm of the regression coefficient requires at least $n=\Omega\left(\min(s\log d,{1}/{\gamma^4})\right)$ samples. Our results show that the complexity of testing in these two settings significantly increases under robustness constraints. This is in line with the recent observations made in robust mean testing and robust covariance testing.

Robust Testing in High-Dimensional Sparse Models
Anand Jerry George
Clément L. Canonne
School of Computer and Communication Sciences Écoole Polytechnique Fédérale de Lausanne (EPFI.) anand. Seanddggorgg@eepl.co
School of Computer Science
The University of Sydney clement. canonne@sydney edu.
Abstract
We consider the problem of robustly testing the norm of high-dimensional sparse signal vector under two different observation models. In the first model, we are given n i..d. samples from the distribution .N' (0, La) (with unknown 0), of which small fraction has been arbitrarily corrupted. Under the promise that |@llu S s, we want correctly distinguish whether ||@]|, 0 or |[0|, > 7 for some input parameter > 0. We show that any algorithm for this task requires " = [s log ed) samples, which is tight up to logarithmic factors. We also extend our results to other common notions of sparsity, namely, ||0|1, I 8 for any < q < 2. the second observation model that we consider, the data is generated according
sparse linear regression model, where the covariates i..dd. Gaussian and the regression coefficient (signal) is known to be s-sparse. Here too assume that an e-fraction of the data is arbitrarily corrupted. We show that any algorithm that reliably tests the norm of the regression coefficient requires at least Q( min(s log d, 1/> samples. Our results show that the complexity of testing in these two settings significantly increases under robustness constraints. This is in line with the recent observations made in robust mean testing and robust covariance testing.
Introduction
Hypothesis testing a fundamental task in statistics and a staple of the scientific method, in which we seek to test the validity of pre-specified hypothesis based empirical observations. In this work, we are concerned with the problem testing whether a given high-dimensional sparse signal vector zero under two common and well-studied observation models: 1) the Gaussian location model and 2) the Gaussian linear regression model. Specifically, the Gaussian location model, we observe ii.d. samples from d-dimensional spherical Gaussian distribution with an unknown sparse mean vector, and seek to detect whether its & norm is large (equivalently, we observe a set of measurements subject to white noise, and seek to determine whether there exists underlying (sparse) signal). Similarly, in the Gaussian linear regression model we seek to detect whether the & norm of the sparse regression coefficient is large. We further assume that samples are imperfect corrupted, allowing an adversary to arbitrarily tamper with up to an E-fraction of the observations. Our objective is characterize the minimum number of samples required to perform these testing tasks, and, crucially, to understand the effect that requiring robustness to this adversarial corruption has on the complexity of the problems.
is known DKSI7 DK21 that, for variety of high- diteemmmeniin tasks, robust testing becomes as costly (in terms of sample complexity) the corresponding estimation task. This is in contrast the non-robust version, where testing is typically much more efficient - often by a quadratic factor in the dimension. However, it is unclear how sparsity enters the picture, and for instance if robustness only starts becoming "costly" when the signal vector sufficiently dense - i.e., whether the problem
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

exhibits a phase transition. This is particularly relevant, as the non-robust versions of the problems we consider are known to present such phase transition at sparsity s 2 vd.
How does robustness affect the sample and computational complexities of testing norm of the signal vector in high-dimensional sparse models? Does testing remain eusier than learning?
This type of question, framed in a minimax setting, sits at the intersection of theoretical computer science (where it is captured under the framework of distribution testing) and robust statistics. Specifically, for @ C Rdd let {Ps J jeee be a family of distributions and Po be a reference distribution (simple null hypothesis-in our case the standard Gaussian). Then, we say that an algorithm T reliably tests the fo-norm of if it satisfies the condition
max
Pr [T(X) reject], sup X-P6
Pr X-pp
[T(X) accept S
(1)
A 001222
where 5 (0, 1] is the failure probability, which following the literature we will hereafter set 1/3 The quantity of interest here is the sample complexity, that is the minimum number of samples required by any algorithm to solve the problem.
The above task, however, assumes access to "perfect" samples from the unknown distribution Ps. This is often unrealistic assumption, a fraction of the samples could be imperfect or corrupted. This motivates the setting of robust testing. The problem is then similar to the formulation in [ with crucial difference: the algorithm T does not have access to the i..d samples X x= (X1, ................................ X,) E gdxa, but instead to a "contaminated" version X = (X1,... X,,) E Rdx= obtained by arbitrarily modifying up to en of the X, 's (i.e., an e-fraction). We will refer to this as the e-corruption model.
In this work we consider two instances of the general testing task ( the robust testing setting. First, let us introduce some notation common to the problems. For (0, let B.,g == {0 E Re [10|1, S {} be the l ball of radius in Idd For g 0, we get the usual notion of sparsity, and will simply write B, for 0 S s S d. Let (0, La) denote the d-dimensional Gaussian with mean @ R" and identity covariance.
Sparse Gaussian mean testing. The first problem that consider is the sparse Gaussian mean testing, in which, given an e-corrupted dataset of n samples from N (6, Ia), where 0 E Ba.g is unknown, our goal is robustly distinguish between (1) ||0||2 = 0 and (2) ||0|| y (equivalently, the total variation distance between. N (0, Ia) and the standard Gaussian N (0, Ia) is M(r)), for some input parameter ? (0, 1].
Testing in sparse linear regression model. This is the second problem that we consider. In the sparse linear regression model the data is generated according to the following process: Let X1, X2, ... Xn, be i..dd samples from N (0, la). Let 0 B, be unknown and let e be i.i.d. samples from .V (0, 1) (and independent from the X, for < i S Then, the y; 's are generated as follows:
y/ (X,,0) + & for all 1 S S
Ta 4T
Note that for a given 8, the joint distribution of (x) is A (0, Eg), where Eg =
+ ||e|
Our aim is robustly distinguish between (1) |00|| 0, and (2) |00|] 7. given an e-corrupted version of the observations 11), (X2, (2),,"., .Xn,
Note that for both the problems, one restrict themselves to the case 7 2 otherwise the problem becomes trivially -hoooation impossible.
1.1 Our contributions
Our main contributions are the characterization the sample complexity of robust sparse Gaussian mean testing for range of notions of sparsity, and lower bound the sample complexity of robust
'The choice of the value 1/3 here is arbitrary, and any fixed value greater than 1/2 would suffice, one can amplify the success probability 1 8, for any 8 > 0, using standard majority vote.

---

testing in the sparse linear regression model. Together, these results fully answer the above question. and provide more evidence to the belief that "robustness requirements make the testing tasks hard as the corresponding estimation tasks." To establish our lower bounds, we draw upon and combine variety of methods from the literature, order to upper bound the xi-divergence between a point and mixture distribution before concluding by Le Cam's two-point method. We elaborate further on those aspects below.
Sparse Gaussian mean testing, It is known [CCTI7] that, in the non-robust setting described in the sample complexity of sparse Gaussian mean testing is
θ log (1 + ) if < vd
no(s,
if 2 vd
for q 0, and, for g (0,2),
m log ( + m
if m < vd m 2 vd
ng(s, d,
where m := maxfu E [d] 7-2u uu I }²} is the effective sparsity. In particular, both sample complexities present phase transition at vd, after which the sparsity longer helps decreasing the sample complexity of the problem, which defaults to the "folklore" non-sparse bound of @(v
Our main result in this setting lower bound on robust sparse mean testing, which shows significantly different landscape:
Theorem (Informal; see Theorems 4 and 5. For every constant s, 7 the sample complexity of robust sparse Gaussian mean testing in the e-corruption model is
2 s log
ed
for q = O, and ((m log m) for q E (0, 2), where m max(u E [d] 2 S s2}
Moreover, our bound for standard s-sparsity is tight. in view of the known O [ log ed sample complexity bound for robust sparse mean estimation L17 DK 19] (which implies the same bound for robust testing). This not only shows that the robust testing problem is much harder than its non-robust counterpart especially in the dense regime (and actually as hard as the robust estimation problem), but also that the robust setting longer presents any threshold phenomenon. If we set d, further recover the result in (DKS17) that robustness requirement increases the sample complexity of Gaussian mean testing. Figure I Gaussian mean testing as function of the sparsity.
illustrates the sample complexity of robust and non-robust sparse
The tightness of our bound, however, only follows from previous work in the case q == 0 (standard sparsity). We provide (near) matching upper bound for the case q E (0, which essentially resolves the question: showing that the aforementioned hardness and disappearance of a phase transition apply to all types of sparsity.
Theorem 2 (Informal; see Theorem 6p. For every 6,7, the sample complexity of robust sparse Gaussian mean testing in the e-corruption model is
0
m log
ed
2
for q E (0, where m = max(u@ E [d] u < 52).
Note that, for constant 7, our upper bound only differs from the lower bound of Theorem | by logarithmic dependence on the effective sparsity m. Finally, we note that while the upper bounds from Li17 and Theorem 2 are achieved by computationally inefficient algorithms (time complexity exponential s), this is actually inherent; indeed, (BB20) recently proved that any computationally efficient algorithm for robust sparse mean estimation must have much higher sample complexity, namely ((=²). simple inspection of their proof shows that this result extends to the robust testing problem.
3

---

Non-robust Robust
Sample Complexity, nts, d.
Sparsity, 5
Figure Sample complexity as function of sparsity for non-robust and robust sparse Gaussian mean testing (the behavior applies testing in the sparse regression model as well).
Testing in sparse linear regression model. From the results [CCC 19 we can deduce that the sample complexity of non-robust testing in the sparse linear regression model is given by
min
log (1 1 #)) if vd
(s 7)
min
if 8 2 Vd.
This expression looks very similar to the sample complexity of sparse Gaussian mean testing, except for additional 1/>4 term. This term is essentially due the fact that can ignore the observations X;'s and estimate just by using y/s ss since their variance is 1 + + This would require (11/r") samples. Nevertheless, the testing in sparse linear regression still exhibits a phase transition at V as was observed in the sparse Gaussian mean testing. It thus natural to wonder whether the parallels between these two problems extend to the robust setting well. We show that this is indeed the case: the sample complexity testing sparse linear regression significantly increases when introducing the robustness condition.
Theorem 3 (Informal; see Theorem
7. For any sufficiently small x > 0, E = 2 for sufficiently
large C. and s = é'-ó for any (0, 1). the sample complexity of testing in sparse linear regression under E-corruption model is
22 min 8 log d, 72 ))
The tightness of this bound follows from results in [LSCC2) Theorem 2.1] which states that any algorithm for robust sparse mean estimation can be used for robust sparse linear regression with polylog(1/7) increase in the sample complexity, Hence the agnostic hypothesis selection via tournaments algorithm in [Li17), which is statistically optimal algorithm for robust sparse mean estimation works this case as well.
1.2 Our techniques
To establish the lower bounds in Theorem I we combine a range tools from information theory and the literature robust estimation. First, argue that it is enough to consider the standard sparsity case (q = 0), as this will imply the analogous result for (0, 2). Indeed, the definition of effective sparsity will enable us to deduce that any x E Rd with | = m and ||~//|
belong to
the set Bs.g. letting establish the lower bound given in Theorem I for general g from the 0 case. In this discussion, we therefore focus on standard sparsity, and assume that our observations are from distribution for which the unknown parameter is in the set B..
To simplify further, we note that order to establish the desired lower bound suffices to consider the weaker H-Huber contamination model instead of the (more general) e-corruption model [DK19). In

---

the the E-Huber contamination model, n ii.d. samples from a distribution p are, after contamination,
modeled as a set of n ii.d. samples from a distribution (1 - E)p + =N, where N is an arbitrary and unknown probability distribution (that is, the adversary is "oblivious:" limited to choosing, ahead of time, a "bad" mixture component N to fool the algorithm). We thus can restrict ourselves, for our lower bound, to the setting where the n i.i.d. samples are from some distribution in {(1
E)W (0, Id) + =Ne,0 |01|o < s); where {(1-E)N (0, +a) llllo I s; ||@l|2 2 7) denote the set of E- E-Huber contaminated versions of Gaussian distributions whose mean has lg norm greater than y. Our goal can be rephrased as choosing as suitable set of parameters ④ and corresponding ensemble of distributions {qo Joee S Cg. and argue that no algorithm can distinguish n samples drawn from a (randomly chosen) element qo from samples drawn from A (0, Id).
get to design the distributions Ne.0- Let C2
To do so, define the mixture q := TSा Eo qg. (equivalently q = Eg-uu (E)) Le Cam's two-point method allows us to reduce the above indistinguishabiiity problem to showing that o(1), for which, in view of the standard inequality, drv(q, p) I
dry (q. .V (0, Ta)")
ix"(q p), it suffices to show that xa || N (0, Ta)") = o(1). ). By the Ingster-Susling method,
this x" diverggge between point and a mixture distribution can then be simplified as
1 x² la)) 1 XN((ula)" (Ba [ Egr [q Ea [(1 XV (go,)))))
(3)
where 0, 0 ~ ue, and Xp q') == f " - 1 is the "x"-correlation" between q and q' with dp
respect to p. Thus, the challenge is to design an ensemble {ęo} that yields good upper bound for the r.h.s. of (3). while still being simple enough to analyze.
Building upon previous works [DKS]] BB20],
define our ensemble {タo} as follows: let
11011 = }
1 V$
(4)
V8"
and, for 0 E O, q0 = (1 (W (70, Ia) + eN (no, Ia). where si is chosen such that (1
eu1o + Suz = O. Note that indeed, for all 0 E O. qo E C, and |0]] = 1. This choice of qa
combined with the above outline will enable us to prove Theorem I by carefully upper bounding Eg.0 [(1 XNV(o.a)) (go;
(0..)....))) )o.)) as function of n, d, and
One can attempt to prove Theorem 3 (the lower bound for testing in the sparse linear regression model) in similar vein. By restricting ourselves to the e-Huber contamination model (which only strengthens the resulting lower bound by constraining the adversary), we get the following set of distributions in the sparse linear regression problem: {(1 -) (0, Ea) eNs,0
1101|o S s),
La TT
0
where Me
1 + 101]]
Further defining D. {(1 e)W (0, Ex) eNN 1101|o s
s. |101,2 2 7). as earlier our problem boils down to finding an ensemble {qo} S D. such that xa ll / (0, Ia+)))) = o(1) for q == @ E. q
Notice that in the sparse linear regression model, y has marginal distribution A( + [|0|²) and conditioned ys the distribution of X, is given by A ( [1+|op
v.0
/
0g
This observation,
I+ 0
along with the indistinguishabiiiy result established while proving Theorem encourage us to choose è as in 4 and qo in the following manner:
(o(v)) = N (0, + 72)
00T
00
Vifto
qo (X, I y:) = (1 - s)N
+ +NN
[
1 1+
[+
1 1+ ++73)
where μe chosen such that (1- + EH4 = Again, note that qo E D. Although this setup looks promising in giving us the right lower bound, it turns out that certain tail events can cause x²(q || N (0, Ia41)") ))) to blow up to infinity. To circumvent this, one of the remedies available in the literature is to use the conditional second moment method [RXZ19 WX18). In this method,
one carefully conditions out the rare events that preclude us from evaluating the x² divveregee Specifically, we define an event & generated by the random variables (y1, y2. ,y,) such that
5

---

q(E0) = o[)). We then define of as the distribution q conditioned on the "good" event &. That is,
(xx,)) = E. Eolgo(XX, 1)
(5)
((E)
Note that we have the relation q = q(E) + q(E0) The convexity of total variation distance consequently gives
drv(q. (0,,NNo,,aaa (0, S ((E) dr .N (0,1)"))) + drv(( ,N (O, S drr(( .N (0, la+1)") + 9(E))
Thus, in view of the fact that q(E = o(1), deriving lower bound reduces to showing that drv(q .N (0, Ia+1) )" is small, for which we saw earlier that it was sufficient (and more convenient) to show that x² (q NI (0, la+1)") = o(1). This is the roadmap we will follow - first, defining a suitable event &, before showing that x² (a I|
(0, Ia+1)") = o(1).
The above outlines our approach to proving Theorems 1 and []] To establish the upper bound in Theorem 2 we show that the "Agnostic hypothesis selection via Tournaments" algorithm [DKK* 16) achieves the stated sample complexity. The argument, in turn, is very similar to the proof of the upper bound for robust sparse mean estimation given Li17
1.3 Related work
The study of high- high-dimensional signals with sparse underlying structure has enjoyed significant amount of attention in statistics and signal processing for the past few decades. This line of research has led to the discovery of surprising phenomena such as phase transitions and computational hardness in problems involving sparse signals. The main motivation to study sparse signals is that the sample complexity of statistical tasks involving sparsity is typically significantly smaller than that of dense signals, leading to much more data-efficient algorithms. This yields significant savings whenever the problem is expected to exhibit such a sparse structure, e.g., for physical or biological reasons, or due to a specific design choice when engincering a system. Yet. practical scenarios seldom involve foree-free or perfect signals, which effectively destroys the sparsity of the signal one would have capitalized on. This led to the study of these questions under various noise models, in order to understand if one could still see the same type of sample size savings in these settings.
There is a large body of work on the estimation and detection of signals with a sparse structure under noise (e.g., [D144 Bar02]] [erl2)). Most recently, [CCT17 gave the tight characterization of minimax rates of estimating linear and quadratic functionals of sparse signals under Gaussian noise. The authors also derived the minimum detection level required for reliably testing the E norm of sparse signals under Gaussian noise. Another prominent sparse signal model studied in the literature is that of sparse linear regression [ITVIO Ver12 RXZI9). In the non-asymptotic setting, |CCC 19 established the tight sample complexity of testing in the sparse linear regression model. However, these line of works focused on random noise, and not the more challenging types of noise allowing for adversarial corruptions- - what is commonly known as seeking robust algorithms.
The systematic study of the robustness of statistical procedures was initiated in the foundational works of Huber [Hub64] and Tukey [Tuk60]. Several statistically optimal procedures were found to break down even under slight model misspecification or sample contamination. Although there was substantial progress the field of robust statisties, surprisingly, computationally efficient procedures remained elusive until recently, even for simple tasks such as high-dimensional mean estimation.
In this regard, the past few years witnessed an incredible progress in algorithmic robust statistics. A line of work initiated by [DKK 16) and [LRVI6] provided computationally efficient optimal robust estimators for various estimation tasks in high dimension [DKK + 19). The surprising upshot from these papers is that even with robustness requirements, the sample complexity of many high- dimensional estimation tasks remains essentially the same, at no extra computational cost: i.e., that robustness and computational efficiency are not at odds for those estimation tasks. And still, a subsequent result of [DKS17] shows that, surprisingly, imposing robustness constraints does significantly increase the sample complexity of the Gaussian mean lesting problem, and makes the sample complexity as large as that of Gaussian mean estimation: that is, for testing, robustness comes at very high cost, and negates the usual savings that testing allows over estimation. Extending their

---

results on mean testing, [D221] shows the analogue in the case of Gaussian covariance testing under the Frobenius norm. Yet, those striking results focus on testing dense parameters; our work seeks to combine the two lines of work - inference under sparsity guarantees, and robustness to understand an analogous jump in sample complexity occurs for testing in high-dimensional sparse models.
We further note that several works have shown evidence for the existence of statistical-compuatiie gaps in estimation problems with sparse signal structure [BR13 CW20). [DKS17] gave the first evidence for the presence of an s to s² statistical-computatii gap in robust sparse mean estimation, in the form of Statistical Query (SQ) lower bound (i.e.. for restricted type of algorithms). This was complemented by [Li77] and [BLLI17, which gave computationally efficient algorithms for robust sparse estimation achieving O
sample complexity. Finally, [BB20] recently used average- case reductions to prove the algorithmic hardness of robust sparse mean estimation and robust sparse linear regression.
1.4 Preliminaries and notation
Given a probability distribution p and integer n 2 1, we denote by p" the n-fold product distribution
with marginals p. and given a set of distributions DD write D = { p" p E D J. For 0 < q S 2 and r > O, we let B = {0 E R ||0]l S r the by ball of radius r. We say a vector O E R is s-sparse if |0011- s; for g E (0, 2]. we will accordingly say that 0 is s-sparse in lg norm whenever I I s (note that s need not be an integer). We denote the uniform distribution over a set S by us. The delta measure (point mass) at an element x denoted by 6g. The total variation distance between two distributions and μ is defined as: drv μJ) ʃ Idv dul which is to be interpreted as 5 dv du dA, where À is any distribution dominating both and jr; equivalently, drv(u, po) ax
(up)( (()) where the supremum is over all measurable sets S. The x² -dvveergee between and μ is given by (2 |I p) = s dudv dp 1, and satisfies drv (v, S 2V |1 p.). Finally, given a reference probability measure the x2 -"-corretation between and X with respect to is defined as (1( A) = yodp note that x² x²(v || 14) = Xu(v,v).
We will also rely in several occasions on the following technical lemma due to Cai, Ma, and Wu, which helps us bound the moment generating function of the square of random sum of Rademacher random variables, which will arise when we consider sparse priors in our lower bounds.
Lemma 1 (Lemma 1 in (CMW15).. Fix d N and [d]. Let H Hypergoometric(d, s, s), and let E1, E2, ... E. be ii.d Rademacher. Define Y = Σ
Et. Then there exists a function 1) + 00) with r(0+)=1, such that for any 0 < b < I T: (0, 36
H
and == log ed.
36.
E eexp (AY S T(b).
2 Main results
In this section, we formally state and give proofs for the theorems outlined informally in Section 1.1 Recall that a lower bound or the hardness of hypothesis testing between two distributions p and q can be characterized by the total variation distance between them. Indeed, by the -eymann lemma, if there exists test which successfully distinguishes between two distributions p., and qu (which in our case will correspond to distributions over n tuples of i.i.d. samples) with probability at least 2/3, then one must have drv qn) 2 1/3. Hence, to prove indistinguishabiliy for given n, it suffices to show dry (Pn. 9n) = o(1); since dry 9n) < 1 (4n P.,), one can then focus on showing X (q, P..) o(1)
Sparse Gaussian mean testing. We now state and prove our results related to sparse Gaussian mean testing. First, we derive the lower bounds in Theorem [ using the techniques outlined in Section 1.2 and then show matching upper bound (up to logarithmic factors) for q > 0 case.
Theorem Let E,Y > 0 be fixed. Let X2, Xn be i..d. samples from an unknown distribution P. Moreover, suppose an e-fraction of these n samples are arbitrarily corrupted. Then, if there exists an algorithm that distinguishes between the cases P N' (0, Ia) and
E (A, : ||01l2 2 7, 1101 S s} with probability greater than 2/3, we must have
Ω (slog ed)
7

---

To prove this theorem, we will require the following lemma due to Diakonikolas, Kane, and Stew- art [KSI7]] Lemma 2 ((DKS17 Lemma 6.9]). Fix 0, E ER (0,1/3, and let qo be defined as
qo = (1 - -1- + eN (-11-) 0, Ia
Then,
(0. 872
+ (x (go qo S exp
E²
With this in hand, we are now able to establish Theorem
Proof of Theorem For the purpose of deriving lower bound, is enough to consider the weaker e- e-Huber model for the corruption of samples, as then lower bound on the sample complexity of the hypothesis testing problem this setting will also be a lower bound for robust sparse Gaussian mean testing in the adversarial one.
Ho X; NO Ia)
H1 X; ~ (1-E)N =0, Ia) + ENe. s. ||0|| 2 and ||0|| S
for Sis Here the distributions Ne.0 need be chosen appropriately.
Let B = (3 E 0,1, 11811, s] and 8 ~ ug. We can think of ,3 as being generated according to the following process: First pick element uniformly from the set {b 134, |bblo =8} and then set the non-zero elements to be i.i.d. Rademacher random variables.
Define θ = / B and == J. so that ||0|| = 1. Define qo as
q (1 e)W((0,, Ia) + +N (- [[(--)
10,
E
It is immediate to see that qo E H, for all 0 E θ. Let q := Bs (961. Then by
3
1 1+x || N (0, Ia)") = Bo,0r [[1 + XA (9)
By Lemma we get
(0,00') ed
13,
1 + (Wo, ) S exp
exp
Ed72
Hence,
ny (B, (1, e4g2
1 1+ (o, S E3,9
exp
(6)
Now by symmetry of the problem, it suffices evaluate the expectation for any fixed 8r, say to 80 = (1.1. (1,1,...,,1,,, 0, ,0.. We can characterize (8, Bo) as follows: let H be random
variable with distribution Hypergeometric(d.. s, and let &1, Ez, ........................ E. i.i.d. Rademacher random variables independent H. Then, we have Y := (3, Bn) = Σ Ei where can be thought as symmetric random walk with Hypergeometric stopping time. We then rewrite (6)
1 x N 1a)) < exp
e4g2
By Lemma if < of 8 slog for sufficiently small (e.g., c << 1/36 suffices),
]
(a N (0, a2) < exp
- s T(()) 7(c)-1 1
Since 7 is continuous 0+, we can choose > to make r(c) - arbitrarily small. This implies that impossible to distinguish between Ho and Hi with high probability = os log od establishing the theorem.

---

Next, we extend this lower bound to other sparsity notions, namely, with respect to the lg no-noms.
Theorem 5. Let 7, > O be fixed, and q E (0, 2). Let X2,...... Xn be i..d. samples from an unknown distribution p. Moreover, suppose an e-fraction of these samples are arbitrarily corrupted. Then, if there exists an algorithm that distinguishes between the cases - (0, Ia)
and p E (0, 110122 2 7. 1001, S $} with probability greater than 2/3, we must have n 5 (m log ) where m is the effective sparsity defined as: m == max vu E [d] : 2 S }
Proof. The parameter set of the alternative hypothesis in this problem is θ = (0 E Rd 100 S and ||0|| 2 7). To conclude, it suffices to show that every m-sparse (in to sense) vector with Eg norm equal to y belongs to O and then appeal to the proof of Theorem (whose hard instances had mean with magnitude exactly y). To do so, let E Idd be m-sparse such that ||x|||2 7. Then,
d Σ
(convexity)
= 171 2 (a)
||||| =
2 m
7 S s
where (a) is due to the definition of m. and the convexity step follows from S 1. Hence x E + Thus the lower bound in Theorem 4 holds here with m replacing
We will now proceed to show that the lower bounds in Theorems 4 and are tight up to logarithmic factor. First, we note that the lower bound given in Theorem 4 is optimal due to the result that the sample complexity of robust sparse Gaussian mean estimation is upper bounded by the same value [K19 [iT7], and the folklore fact that testing is no harder than estimation. So we need to prove the upper bound only for the cases where 9 >> O. We will show that the sample complexity lower bound given in Theorem is tight by proving that the algorithm for robust sparse Gaussian mean estimation given in [Li17] works in the lg -oorm constrained case well (and so, again, the upper bound for testing will follow from the upper bound for estimation), in the regime y = (s)). Intuitively, this is because all but m coordinates of vector I would be small if [|0|,, g s and ||0||2 7. Our proof is similar to the proof of [Li77] Fact A. with a minor modification. We defer its proof to the supplemental.
Theorem 6. Let > and, q E (0.2) be fixed. Let X2,...... Xx, be i.i.d. samples from an unknown distribution N (H,, Ia), where || S s. Moreover, suppose an e-fraction of these samples are arbitrarily corrupted. Then, there exists an algorithm that, for n = 0 (m log d + log t)). upon being given the X1..... Xn outputs μl such that I| Hll2 S ( with probability 1 6.
Here m is the effective sparsity defined as: max|u E [d] e2 < )²).
Testing in sparse linear regression model. Lastly, we state the formal version of Theorem 3 and provide outline of its proof (see supplementary for complete proof).
Theorem 7. Let y > O be sufficiently small, = è for sufficiently large C, and s = d''6 for some 8 E 1). Let (1,, (X2,
(X,,, yn) be i..dd. samples obtained from the sparse linear regression model described in ②) Moreover, suppose e-fraction of these samples are arbitrarily corrupted. Then, if there exists an algorithm that distinguishes hetween the cases [|01|2 = 0 and
|10]]2 2 y with probability greater than 2/3, we must have n = Ω (2mmi|| log d, 7
Proof outline. Let X denote (X1, X2.... ... , Xx) and Y denote (y11 1/2, ... Mn.) Let θ = {0 E Vz: 0, ,d
3=)d: |101|u = 8) and p = 1-s We define hypotheses Ho and H4 as follows:
Ho: (X,, v1)
Lid.
~ p = N (0, Ia+1)
Hi : 0 ~ (0) = uue
yi
iid ~
q(v:) = -N (0, +772)
by:70
72007
]. where b ~ (1 - =60 + eō pp-
0) = oo (X lu:) = Es W
1
1 + 72
1 1+72)
Here, we denote the probability distribution under the hypotheses Ho by and Hi by q. Notice
La
70 and thus a
that qs is an e-Huber contaminated version of N/ (0, E.,)), where Vi =
00"
1 72

---

lower bound on the sample complexity of this hypothesis testing task would be a lower bound for the robust testing in sparse linear regression model. A natural approach to prove the impossibility of detection between Ho and Hi would be to try and show that x || p) = o( However, as previously discussed, this method does not yield useful lower bound for this problem, due to low-probability events which cause ( p) to blow up. Instead, as alluded to in Section 1.2 we evaluate x² (a p), where we define an event as
E= YERR
log log dl 2
f
n
and the probability distribution q is given by 5). Evaluating x² 24 p) gives
( 2
qo qx(X (XlY) p(X)²
1 x |p) = {()) Bao Byup
E Ex~p
Lotr]
(8)
We compute Eg,or [Z] by splitting it into two cases depending on whether [ (0, 1 7 or (0, 0')
where
4eq² log This leads to the result that (² p) = o(1) if
n = of min llog d. 1 )) We then show that is asymptotically a high-probability event, which allows us argue that drv (p. q) = o(1), thereby proving Theorem 7
Discussion and Future Work
In this section, discuss some of the limitations of results, which we believe ground for possible future work. Firstly, we suspect that our lower bounds are not tight with respect to the parameters " and The dependence on y and in Theorems 4 and [ is R(E*/>*). While the exact dependence on these parameters still an open problem even for robust Gaussian mean testing (non-sparse), conjecture that the actual dependence and hence believe that our dependence on these parameters is suboptimal. In the current proof, the bottleneck appears while obtaining Subber-contaminated distributions, and we suspect that more advanced techniques might be required get the right dependence on 7 and
these parameters should scale as e² /²/1/,
upper bound for the chi-squared correlation between two
Furthermore, we restricted ourselves to the case when the covariance the Gaussian distributions under consideration are identity matrices ("spherical Gaussians"); of course, handling the case of arbitrary covariances is a natural and important question. We believe that deriving the sample complexity in the case of non-identity (and unknown) covariance matrices would require significant additional effort, as well as new techniques and ideas. is worth pointing out that we are not aware of any work addressing the sample complexity results for non-identity covariances in the non-robust (but sparse) setting.
References
[Bar02]
Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5):577-608 2002.
[BB20]
Matthew Brennan and Guy Bresler. Reducibility and statistical statistical-computaiie computational gaps from secret leakage. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 648-847. PMLR, 09-12 Jul 2020.
[BDLS17] Sivaraman Balakrishnan, Simon S. Du, Jerry Li. and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceed- ings of Machine Learning Research, pages 169-212. PMLR, 07-10 Jul 2017.
[BR13] Quentin Berthet and Philippe Rigollet. Optimal detection of sparse principal components in high dimension. Ann. Statist., 41(4): 2013.
10

---

[CCC+19] 19] A. Carpentier, O. Collier, L. Comminges, A. B. Tsybakov, and Yu. Wang. Minimax rate of testing in sparse linear regression. Autom, Remote Control, 80(10):1817-134, oct 2019.
[CCT17] Olivier Collier, Laëtitia Comminges, and Alexandre B. Tsybakov. Minimax estimation of linear and quadratic functionals on sparsity classes. Ann. Statist., 45(3):923-958, 2017.
[CMW15] Tony Cai, Zongming Ma, and Yihong Wu. Optimal estimation and rank detection for sparse spiked covariance matrices. Probab. Theory Related Fields, 161(3-4)7711-855, 2015.
[CW20]
T. Tony Cai and Yihong Wu. Statistical and computational limits for sparse matrix detection. Ann. Statist., 48(3):1593-1614 2020.
[DJ04]
David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. Ann. Statist., 32(3):96,-994, 2004.
[DK19]
Ilias Diakonikolas and Daniel M. Kane. Recent advances in algorithmic high-dimensional robust statistics, 2019, arXiv: 1911.05911.
[DK21] Ilias Diakonikolas and Daniel M. Kane. The sample complexity of robust covariance testing. Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1511-1521. PMLR, 15-19 Aug 2021.
[6KK*16] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In 57th Annual IEEE Symposium on Foundations of Computer Science- FOCS 2016, pages 655-664. IEEE Computer Soc., Los Alamitos, CA, 2016.
[DKK 19] Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlier-robust high-dimensional sparse estimation via iterative filtering. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-diimessoon Gaussians and Gaussian mixtures (extended abstract). In 58th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2017, pages 73-84. IEEE Computer Soc., Los Alamitos, CA, 2017.
[Hub64]
Peter Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73 101, 1964.
[TTV10]
Yuri I. Ingster, Alexandre B. Tsybakov, and Nicolas Verzelen. Detection boundary in sparse regression. Electron. J. Stat., 4:1476-1526, 2010.
[Li17]
Jerry Li. Robust sparse estimation tasks in high dimensions, 2017, arXiv: 1702.05860.
[LRV16]
Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 57th Anmual IEEE Symposium on Foundations of Computer Science- FOCS 2016, pages 665-6744 IEEE Computer Soc., Los Alamitos, CA, 2016.
[LSLC20] Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 41 411-421. PMLR, 26-28 Aug 2020.
[RXZ19]
Galen Reeves, Jiaming Xu, and Ilias Zadik. The all-or-nothing phenomenon in sparse linear regression. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2652-2663. PMLR, 25-28 Jun 2019.
[Tuk60]
John W. Tukey. A survey of sampling from contaminated distributions. In Contributions to probubility and stafistics, pages 448-485. Stanford Univ. Press, Stanford, Calif., 1960.
[Ver12]
Nicolas Verzelen. Minimax risks for sparse regressions: ultra-high dimensional phe- nomenons. Electron. J. Stat., 6:38-90, 2012.
[WX18] Yihong Wu and Jiaming Xu. Statistical problems with planted structures: Information- theoretical and computational limits, 2018, arXiv: 1806.00118 18.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work focuses on theoretical aspects of statistical estimation and high-dimensional testing. and such is remote enough from direct applications that its societal impacts are impossible to assess.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "ozLDMBNOq_G", "reviewer": "Reviewer_jAix", "summary": "The paper focuses on two problems within the domain of robust statistics:\n1. Sparse Gaussian mean testing: the goal is to robustly testing whether the mean of a Gaussian is zero or far from zero when we are guaranteed that the mean vector $\\theta$ satisfies some form of sparsity codified as $\\|\\theta\\|_q = s$ for some $q \\in [0,2)$.\n2. Testing in the sparse linear regression model: given $x \\sim \\mathcal{N}(0,I_d)$ and a sparse $\\theta$ we have $y = x^\\top \\theta + \\epsilon_i$ and our goal is to test whether $\\|\\theta\\|_2 = 0$ or $\\|\\theta\\|_2 \\ge \\gamma$.\nIn both problems we have that an $\\epsilon$ fraction of samples are arbitrarily corrupted by an adversary.\n\nThe main results of the paper are information theoretic lower bounds for the above tasks which depend on $s,d$ (the authors focus on the regime where $\\gamma,\\epsilon$ are constants and the dependence of the bounds on these quantities is not focused upon).\nThe non-robust versions of these questions show a dependence of the following form (when $q=0$):\n1. $\\Theta\\left(s\\log(1+d/s^2)\\right)$ if $s < \\sqrt{d}$,\n2. $\\Theta\\left(\\sqrt{d} \\right)$ if $s \\ge \\sqrt{d}$.\nIn particular, the testing version of the problem can always be solved more efficiently than the learning/estimation version. However, in the robust variant of these problems the results of this paper show that this is no longer the case. Irrespective of $s$, the robust sparse Gaussian mean testing problem requires $\\Omega(s\\log(d/s))$ samples.\n\nIn addition to the $q=0$ setting, the authors also provide upper and lower bounds to these problems to the $q \\in (0,2)$ settings.\nThe main message of the story remains quite similar in the sparse linear regression testing problem as well.\nAmong the techniques used by the authors are the well-known Le Cam's two point method, some inequalities connecting different distance metrics to each other, and some inequalities which help bound the $\\chi^2$ distance of a product of a mixture of distributions with another product distribution.", "questions": "**Questions:**\n1. What are the dependences of the bounds on $\\epsilon,\\gamma$ in Theorems 4 and 5? How tight are these?\n2. It would be nice to see some discussion around the setting of non identity covariance matrices and testing between two Gaussians with different covariances.\n3. The sparse testing problem exhibits a phase transition in its sample complexity as a function of sparsity. Namely, we only see benefits of sparsity until the sparsity parameter reacher $\\sqrt{d}$. It is intriguing that a similar phase transitionary behavior doesn't occur here and the situation seems to linearly degrade with $s$ for all ranges of $s$. Is there any high-level intuition on what causes the phase transitionary behavior in the non-robust setting and why this is no longer the case in the robust setting?\n\n**Suggestions:**\n1. \"Upper bounds of [Li17] and Theorem 2 are computationally inefficient...” – present the computational complexity in terms of $d, s, \\gamma$ here.\n2. Line 138 of supplementary typo:  “note that for in order to”", "limitations": "The authors adequately addressed the potential negative societal impact of their work. They also adequately address the limitations of their results.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. Sparsity and robustness are two important sub-fields within Statistics research today which the paper focuses on.\n2. The paper's contributions are original. In addition, the paper is well written and clear to read.\n3. The authors provide a thorough and complete theoretical analysis of the problem leading to a tight understanding of the sample complexity along with an extensive survey of all related work.\n\n\n**Weaknesses:**\n1. Even within the scope of robustly testing a sparse Gaussian the paper focuses on a specific niche problem of mean testing. It would be nice to see some discussion around the setting of non identity covariance matrices and testing between two Gaussians with different covariances.\n2. The paper presents a nice overview of the techniques used and has a number of results. But it is not fully clear where the main technical challenges arise in this setting. In particular, it is hard for me to understand why the problems in the robust setting do not exhibit a phase transitionary behavior in the sample complexity. Given this, I am a little unsure on the significance of the results of the current paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UIZLfgwUH8R", "reviewer": "Reviewer_2TQX", "summary": "This paper is interested in determining whether the norm of the mean (supposed to be sparse) of a Gaussian distribution is zero or not based on samples drawn from this distribution. The difficulty of the setting considered comes from the addition of a robustness condition which imposes that a fraction of the data available for the test is corrupted. The authors are interested in determining the minimum number of samples (sample complexity) needed to perform such a task. The authors hope through the study to show the impact of robustness on pre-existing results on the sample complexity of the testing the norm of sparse gaussian vectors. In particular, they show that the robustness constraints significantly increase the complexity of the test. It should be noted that an additional study to test the norm of a regression vector in a sparse linear regression context is also proposed and theoretically analyzed with the same consequences.", "questions": "1- In line 43 , $p_{0}^n$ seems not to be defined\n\n2- Line 108 \"we note that for in\"\n\n3-Line 169 $\\tilde{\\mathcal{D}}$ seems not defined\n\n4- The single MGF seems not defined \n\n5- It would be interesting to have a bunch of experiments to illustrate the theory. In particular, could the authors provide a set of baselines algorithms and their sample complexity and how the proposed sample complexity behaves with respect to this empirical sample complexities?\n\n6- The presentation can be improved by summarizing the main ingredients of the proofs more shortly and focusing more on interpretation, and visualization of the main theoretical results to increase readability, and make the paper more understandable.\n\n7- Do they exist some robustness algorithms that could reach the proposed sample complexity?", "limitations": "1- The paper didn't discuss really the limitations or openings of the works.\n\n2- The motivation of such a study notably for application is lacking to some extent.\n\n3- Experiments are not provided and could be an important asset to support the theory.\n\n4- Some algorithms that reach the sample complexity would be more than welcome.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n1- The paper seems technically sound with original technics to derive the sample complexity.\n\n2- The sample complexity derived makes some sense and provides some intuition into statistical tests under robustness conditions\n\n*Weaknesses*\n\n1- The work needs to be better motivated by giving concrete examples of the usefulness of testing the norm of a high dimensional sparse Gaussian vector.\n\n2- Some experiments would have been welcome. Do some robust statistical tests exist to show empirically what are their sample complexities and how it relates to the derived theoretical sample complexity?\n\n3- The structure of the paper could be improved by providing more opening and conclusions to the work, by insisting more on insights drawn more than the technical proofs which could be deferred to the supplementary materials. Furthermore, a notation section would be welcome to introduce some notation conventions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JydQ_ggJr3I", "reviewer": "Reviewer_8QBu", "summary": "The paper studies the sample complexity of robust sparse Gaussian mean testing and linear regression. Motivated by prior work saying that the number of samples required for testing versions of various inference tasks becomes as high as that required for the learning version of the problems (i.e., the sample complexity experiences an information-theoretic gap when corruptions are introduced), the paper asks whether the same is true in the sparse setting. For the robust $s$-sparse Gaussian mean testing problem, it shows a lower bound of $\\Omega(s \\log(d/s))$ for the sample complexity, which means that, in contrast to the non-robust setting, the sample complexity does not default to $\\sqrt{d}$ when $s \\geq \\sqrt{d}$. The result extends to a more general notion of sparsity, for which the paper also obtains upper bounds on the sample complexity. Finally, they show qualitatively similar results for the sparse linear regression setting (in the usual notion of sparsity). The approach for the mean testing result involves defining a family of $\\epsilon$-corrupted Gaussians (in the Huber’s contamination model) with large mean  and considering the binary hypothesis testing problem that asks for distinguishing this family from the standard Gaussian (i.e., zero-mean). The proof is based on Le Cam's method and utilizes a lemma of [DKS17] to bound the chi-square distance between the standard Gaussian and the uniform mixture over the aforementioned family. The linear-regression result has to take care of the additional complication regarding some low-probability events that cause the chi-square divergence to blow up.", "questions": "Is it entirely accurate to say that the testing is ``much harder than its non-robust counterpart'',  given that the sample complexity agree in the very sparse regime $s < \\sqrt{d}$ ?", "limitations": ".", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Significance: Testing means of Gaussians and linear regressors are one of the most fundamental problems in statistics and this work completes the characterization of the sample complexity for the robust version.\n\nQuality: The arguments seem to be overall correct. To the extent that I checked the proofs in the supplementary material, I do not have issues regarding soundness.\n\nClarity: The paper is well-written. The sketch in Section 1 is clear in conveying the high-level approach. \n\nOriginality: The techniques for proving the lower bounds are based on Le Cam’s method and [DKS17]. The definition of the hard distribution class is somewhat natural, and the approach does not need to significantly deviate from the prior established technology. The linear regression result however requires more substantial work at the technical level. The upper bound in Theorem 7 follows by modification of standard arguments.\n\nThe paper fills the gap in our understanding regarding the sample complexity for robust sparse testing. Although the problems do not require substantial originality in terms of new techniques, the solution is non-trivial and the results are of interest to the robust statistics community. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HYlynQ6B8vj", "reviewer": "Reviewer_PDuZ", "summary": "The submission considers the well-known question of testing whether the mean of a $d$-dimensional identity-covariance Gaussian is zero or a sparse vector $\\gamma$-far from zero, and the related question of testing whether the coefficient vector in an instance of sparse linear regression is zero or far from zero. \n\nIn this review, we will focus on the usual $L_0$ notion of sparsity, though their results for mean testing also extend to any $L_q$-based sparsity for $0 < q < 2$. For mean testing, classically it is known that the optimal sample complexity, up to log factors, scales as $\\min(s,\\sqrt{d})/\\gamma^2$ where $s$ is the sparsity of the alternative hypothesis, and a qualitatively similar picture holds for SLR testing. In particular, there is a phase transition at $s = \\sqrt{d}$ such that above this, testing is easier than estimation and, more specifically, the sample complexity does not grow with $s$ and at worst scales as $\\sqrt{d}/\\gamma^2$.\n\nThe present work considers a twist on this setup where some small constant fraction $\\epsilon$ of the samples that the tester sees have been adversarially corrupted. They show that in this model, the abovementioned phase transition does not occur, and testing is no easier than estimation regardless of $s$. That is, they show that for any constant $\\epsilon,\\gamma$, the sample complexity for *robust* Gaussian mean testing scales linearly in $s$, and similarly for robust SLR testing. Note that this result was already known in the case of $s = d$ [DKS17].\n\nThe proofs are via the Ingster-Suslina method, which amounts to designing a mixture over alternatives and controlling the tails of the pairwise correlation between the distributions over samples under two random alternatives relative to the null hypothesis. In the robust setting, there is the additional freedom of choosing how the adversary corrupts the data: for mean testing, e.g., they consider an adversary (the same as in [DKS17]) that, for every sample, with probability $\\epsilon$ replaces the sample with a draw from another Gaussian such that the mixture of the \"clean Gaussian\" and this Gaussian has zero mean.", "questions": "*Questions*:\n- Do the lower bound techniques get the right $\\gamma$ scaling as well? If not, where are the bottlenecks in the argument that preclude this?\n- Is Brennan-Bresler's lower bound for robust SLR also a lower bound against robust SLR testing?\n\n*Minor typos*:\n- P. 3 Line 98: no longer present*s*\n- P. 4 Line 124: \"for some $\\delta$\" -> \"for any $\\delta$\"?\n- P. 4 Line 135: semicolon should be comma, similarly on P. 5 Line 185\n- P. 4 Line 138: we note that in order\n- P. 5 Line 186: *a* suitable event\n", "limitations": "The authors have adequately addressed the limitations, and I don't see any potential negative societal impact from this work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n- It is nice that this paper gives an essentially complete answer to the question they set out to solve, up to log factors and dependence on $\\epsilon,\\gamma$. \n- While the techniques employed are all fairly standard, they are integrated in a clean and modular fashion. \n- Conceptual novelty: while there has been a lot of work on the estimation version of the problems this paper studies, as far as I know this is the first to propose studying robust SLR testing, even for $s = d$.\n\n*Weaknesses*:\n- For the mean testing result, a lot of the technical heavy lifting, namely the pairwise correlation calculations (Lemma 2) and the choice of adversary, comes directly from [DKS17]. Similarly, the upper bound for $L_q$-sparse mean testing is a minor modification of the proof in [Li17].\n\n*Assessment*: I would recommend acceptance because of the comprehensive nature of the result: while dense mean testing was already understood, it is quite cool that they managed to demonstrate that the phase transition for non-robust mean testing disappears altogether.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept