Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper focuses on two problems within the domain of robust statistics:
1. 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)$.
2. 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$.
In both problems we have that an $\epsilon$ fraction of samples are arbitrarily corrupted by an adversary.

The 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).
The non-robust versions of these questions show a dependence of the following form (when $q=0$):
1. $\Theta\left(s\log(1+d/s^2)\right)$ if $s < \sqrt{d}$,
2. $\Theta\left(\sqrt{d} \right)$ if $s \ge \sqrt{d}$.
In 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.

In addition to the $q=0$ setting, the authors also provide upper and lower bounds to these problems to the $q \in (0,2)$ settings.
The main message of the story remains quite similar in the sparse linear regression testing problem as well.
Among 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.
strengths_and_weaknesses: **Strengths:**
1. Sparsity and robustness are two important sub-fields within Statistics research today which the paper focuses on.
2. The paper's contributions are original. In addition, the paper is well written and clear to read.
3. 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.


**Weaknesses:**
1. 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.
2. 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.
questions: **Questions:**
1. What are the dependences of the bounds on $\epsilon,\gamma$ in Theorems 4 and 5? How tight are these?
2. It would be nice to see some discussion around the setting of non identity covariance matrices and testing between two Gaussians with different covariances.
3. 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?

**Suggestions:**
1. "Upper bounds of [Li17] and Theorem 2 are computationally inefficient...” – present the computational complexity in terms of $d, s, \gamma$ here.
2. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

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

Clarity: The paper is well-written. The sketch in Section 1 is clear in conveying the high-level approach. 

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

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

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: .
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

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

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

The 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.
strengths_and_weaknesses: *Strengths*:
- 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$. 
- While the techniques employed are all fairly standard, they are integrated in a clean and modular fashion. 
- 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$.

*Weaknesses*:
- 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].

*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.
questions: *Questions*:
- Do the lower bound techniques get the right $\gamma$ scaling as well? If not, where are the bottlenecks in the argument that preclude this?
- Is Brennan-Bresler's lower bound for robust SLR also a lower bound against robust SLR testing?

*Minor typos*:
- P. 3 Line 98: no longer present*s*
- P. 4 Line 124: "for some $\delta$" -> "for any $\delta$"?
- P. 4 Line 135: semicolon should be comma, similarly on P. 5 Line 185
- P. 4 Line 138: we note that in order
- P. 5 Line 186: *a* suitable event

limitations: The authors have adequately addressed the limitations, and I don't see any potential negative societal impact from this work.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: *Strengths*

1- The paper seems technically sound with original technics to derive the sample complexity.

2- The sample complexity derived makes some sense and provides some intuition into statistical tests under robustness conditions

*Weaknesses*

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

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

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

questions: 1- In line 43 , $p_{0}^n$ seems not to be defined

2- Line 108 "we note that for in"

3-Line 169 $\tilde{\mathcal{D}}$ seems not defined

4- The single MGF seems not defined 

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

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

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

2- The motivation of such a study notably for application is lacking to some extent.

3- Experiments are not provided and could be an important asset to support the theory.

4- Some algorithms that reach the sample complexity would be more than welcome.
review_title: null

Meta-review: metareview: The reviewers and I agree that this result is a solid, if not groundbreaking, result in the theory of robust statistics. It considers a very natural testing problem, and when the fraction of corrupted samples is constant, completely settles the statistical complexity of the problem. There are some concerns that its immediate practical impact is limited, but overall, the consensus is that the paper represents a solid technical contribution, and will be of interest to the robust statistics community, and the learning theory community at large. Therefore, we believe this paper is above the bar for acceptance at NeurIPS.
confidence: Certain
Decision: Accept