论文标题
高斯平均测试变得简单
Gaussian Mean Testing Made Simple
论文作者
论文摘要
我们研究以下基本假设检验问题，我们将其称为高斯平均测试。给定I.I.D. $ \ mathbb {r}^d $上的分布$ p $的样品，任务是在以下情况下以很高的概率区分：（i）$ p $是标准高斯分布，$ \ nathcal {n}（n}（0，i_d）$和（ii _d）$ p $ p $是高斯$ \ Mathcal cov $ \ Mathcal $ for for for for for for for for for for。且平均$μ\ in \ mathbb {r}^d $满足$ \ | | | _2 \geqε$。最近的工作给出了此测试问题的算法，最佳样本复杂性为$θ（\ sqrt {d}/ε^2）$。以前的算法及其分析都非常复杂。在这里，我们通过一页分析给出了一种极其简单的高斯平均测试算法。我们的算法是最佳样品，并在样本线性时间内运行。
We study the following fundamental hypothesis testing problem, which we term Gaussian mean testing. Given i.i.d. samples from a distribution $p$ on $\mathbb{R}^d$, the task is to distinguish, with high probability, between the following cases: (i) $p$ is the standard Gaussian distribution, $\mathcal{N}(0,I_d)$, and (ii) $p$ is a Gaussian $\mathcal{N}(μ,Σ)$ for some unknown covariance $Σ$ and mean $μ\in \mathbb{R}^d$ satisfying $\|μ\|_2 \geq ε$. Recent work gave an algorithm for this testing problem with the optimal sample complexity of $Θ(\sqrt{d}/ε^2)$. Both the previous algorithm and its analysis are quite complicated. Here we give an extremely simple algorithm for Gaussian mean testing with a one-page analysis. Our algorithm is sample optimal and runs in sample linear time.
