Gaussian Mean Testing Made Simple
Gaussian Mean Testing Made Simple
复制标题
高斯均值测试变得简单
DOI：
10.48550/arxiv.2210.13706
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ankit Pensia
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Ankit Pensia
我们研究以下基本假设检验问题，我们将其称为高斯平均测试。给定I.I.D. $ \ mathbb {r}^d $上的分布$ p $的样本是在以下情况下以很高的概率区分：（i）$ p $是标准高斯分布，$ \ nathcal {n }（0，i_d）$，（ii）$ p $是高斯$ \ mathcal {n}（\ mu，\ sigma）$协方差$ \ sigma $ and Mean $ \ mu \ in \ mathbb {r}^d $满足$ \ | \ | \ mu \ | _2 \ geq \ epsilon $。最近的工作给出了此测试问题的算法，其最佳样本复杂性为$ \ theta（\ sqrt {d}/\ epsilon^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}(\mu,\Sigma)$ for some unknown covariance $\Sigma$ and mean $\mu \in \mathbb{R}^d$ satisfying $\|\mu\|_2 \geq \epsilon$. Recent work gave an algorithm for this testing problem with the optimal sample complexity of $\Theta(\sqrt{d}/\epsilon^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.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
and Automata
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Peebles, John;Price, Eric
通讯作者：
Price, Eric
高维分布的随机限制和子立方条件的均匀性测试
DOI：
10.5555/3458064.3458085
发表时间：
2021
期刊：
Proceedings of the 32th Annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Canonne, Clement;Chen, Xi;Kamath, Gautam;Levi, Amit;Waingarten, Erik
通讯作者：
Waingarten, Erik
通过干预学习和测试因果模型
DOI：
--
发表时间：
2018
期刊：
32nd Annual Conference on Neural Information Processing Systems
影响因子：
--
作者：
Acharya, Jayadev;Bhattacharyya, Arnab;Daskalakis, Constantinos;Kandasamy, Saravanan
通讯作者：
Kandasamy, Saravanan
DOI：
10.1145/3406325.3450997
发表时间：
2021
期刊：
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Kane, Daniel M.;Peebles, John;Price, Eric
通讯作者：
Price, Eric