Gaussian Mean Testing Made Simple

2022/10/25 by Ilias Diakonikolas, Daniel M. Kane, Diakonikolas, Ilias +3 · 2 citations
Computer Science · Decision Sciences · #Machine Learning and Algorithms #Advanced Statistical Process Monitoring #Gaussian Processes and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.2210.13706

Abstract

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,I_d), and (ii) p is a Gaussian N(μ,Σ) for some unknown covariance Σ and mean μ∈ ℝ^d satisfying ‖μ‖₂ ≥ ε. Recent work gave an algorithm for this testing problem with the optimal sample complexity of Θ(√(d)/ε²). 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.

Cited by

• Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins
• Testing and estimation in orthosymmetric Gaussian sequence model

Related

• Gaussian Mean Testing under Truncation
• Testing Gaussian Process with Applications to Super-Resolution
• Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins
• The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
• Sub-Gaussian Error Bounds for Hypothesis Testing