论文标题
高维稀疏模型中的强大测试
Robust Testing in High-Dimensional Sparse Models
论文作者
论文摘要
我们考虑了在两个不同的观察模型下坚固测试高维稀疏信号矢量规范的问题。在第一个型号中，我们得到了$ n $ i.i.d。来自分布$ \ Mathcal {n} \ left（θ，i_d \ right）$（带有未知$θ$）的样本，其中一小部分已被任意损坏。在承诺$ \ |θ\ | _0 \ le s $的承诺下，我们要正确区分某些Input参数$γ> 0 $的$ \ | | the | the |> | the我们表明，此任务的任何算法都需要$ n =ω\ left（s \ log \ frac {ed} {s} \ right）$样本，这是紧密的对数因素。我们还将结果扩展到其他常见的稀疏性概念，即，对于任何$ 0 <q <2 $，$ \ |θ\ | _q \ le s $。在我们考虑的第二个观察模型中，数据是根据稀疏线性回归模型生成的，其中协变量为I.I.D。高斯和回归系数（信号）已知为$ s $ -sparse。在这里，我们也假设数据的$ε$分数被任意损坏。我们表明，任何可靠测试回归系数规范的算法都需要至少$ n =ω\ left（\ min（s \ log d，{1}/{1}/{γ^4}）\ right）$样本。我们的结果表明，这两种设置中测试的复杂性在鲁棒性约束下显着增加。这与稳健平均测试和鲁棒协方差测试中最新观察结果一致。
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(θ,I_d\right)$ (with unknown $θ$), of which a small fraction has been arbitrarily corrupted. Under the promise that $\|θ\|_0\le 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=Ω\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, $\|θ\|_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 $ε$-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=Ω\left(\min(s\log 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.
