Timezone: »
Poster
Robust Testing in HighDimensional Sparse Models
Anand Jerry George · Clément L Canonne
We consider the problem of robustly testing the norm of a highdimensional 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.
Author Information
Anand Jerry George (EPFL)
Clément L Canonne (IBM Research)
More from the Same Authors

2023 Poster: Private Distribution Learning with Public Data: The View from Sample Compression »
Shai BenDavid · Alex Bie · Clément L Canonne · Gautam Kamath · Vikrant Singhal 
2023 Poster: Unified Lower Bounds for Interactive Highdimensional Estimation under Information Constraints »
Jayadev Acharya · Clément L Canonne · Ziteng Sun · Himanshu Tyagi 
2022 Poster: NearlyTight Bounds for Testing Histogram Distributions »
Clément L Canonne · Ilias Diakonikolas · Daniel Kane · Sihan Liu 
2022 Poster: Independence Testing for Bounded Degree Bayesian Networks »
Arnab Bhattacharyya · Clément L Canonne · Qiping Yang 
2020 Poster: Private Identity Testing for HighDimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou 
2020 Spotlight: Private Identity Testing for HighDimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou