Gaussian Mean Testing Made Simple
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia · Society for Industrial and Applied Mathematics eBooks · 2023
We study the following fundamental hypothesis testing problem, which we term Gaussian mean testing. Given i.i.d. samples from a distribution p on ℝd, the task is to distinguish, with high probability, between the following cases: (i) p is the standard Gaussian distribution, N(0, Id), and (ii) p is a Gaussian N(μ, Σ) for some unknown covariance Σ and mean μ ∈ ℝd satisfying ||μ||2 ≥ ε. Recent work gave an algorithm for this testing problem with the optimal sample complexity of . 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.