# Robust Testing in High-Dimensional Sparse Models

arXiv: https://arxiv.org/abs/2205.07488 · HTML: https://mlsanity.com/paper/2205.07488/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 16 May 2022.

## Builds on (most cited first, 9 of 9)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [The Sample Complexity of Robust Covariance Testing](https://mlsanity.com/paper/2012.15802/) (2020)
- [Robust Sparse Estimation Tasks in High Dimensions](https://mlsanity.com/paper/1702.05860/) (2017)

## Built on by (most cited first, 1 of 1)

- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)

## Abstract (arXiv)

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 Nleft(θ,Idright) (with unknown θ), of which a small fraction has been arbitrarily corrupted. Under the promise that |θ|0≤ s, we want to correctly distinguish whether |θ|2=0 or |θ|2>γ, for some input parameter γ>0. We show that any algorithm for this task requires n=Omegaleft(slogfracedsright) samples, which is tight up to logarithmic factors. We also extend our results to other common notions of sparsity, namely, |θ|q≤ 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 ε-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=Omegaleft(min(slog d,1/γ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.