mlsanityData to 7 Oct 2026

Gaussian Mean Testing Made Simple

arXiv 2210.13706 ↗First posted 25 Oct 2022math.ST cs.DS cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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(μ,Sigma) for some unknown covariance Sigma and mean μ ∈ ℝd satisfying |μ|2 ≥ ε. Recent work gave an algorithm for this testing problem with the optimal sample complexity of Theta(√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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 16 of its 26 references that are in the map. First posted on arXiv 25 Oct 2022.

Builds on

16 of 26 references.

References · 16

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  3. 2015Optimal Testing for Properties of Distributionscited by 36
  4. 2018Learning and Testing Causal Models with Interventionscited by 29
  5. 2016Testing Ising Modelscited by 23
  6. 2016Testing Bayesian Networkscited by 23
  7. 2017Testing Conditional Independence of Discrete Distributionscited by 22
  8. 2014Testing Identity of Structured Distributionscited by 19
  9. 2017Optimal Identity Testing with High Probabilitycited by 19
  10. 2020Optimal Testing of Discrete Distributions with High Probabilitycited by 15
  11. 2019Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioningcited by 13
  12. 2020Learning and Testing Junta Distributions with Subcube Conditioningcited by 13
4 more
  1. 2015Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributionscited by 11
  2. 2015Testing Shape Restrictions of Discrete Distributionscited by 9
  3. 2017Near-Optimal Closeness Testing of Discrete Histogram Distributionscited by 7
  4. 2018Testing Identity of Multidimensional Histogramscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  2. 2025Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioningcited by 2
  3. 2025Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confoundingcited by 0