The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination

Abstract. We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samples. We focus on the relative power of different adversaries and show that, in contrast to the common wisdom in robust statistics, there exists a strict separation between adaptive adversaries (strong contamination) and oblivious ones (weak contamination) for this task. Specifically, we resolve both the information-theoretic and computational landscapes for robust mean testing. In the exponential-time setting, we establish the tight sample complexity of testing [Formula: see text] against [Formula: see text], where [Formula: see text], with an [Formula: see text]-fraction of oblivious adversarial corruptions, to be [Formula: see text], while the complexity against adaptive adversarial corruptions is [Formula: see text], which is strictly worse for a large range of vanishing [Formula: see text]. To the best of our knowledge, ours is the first separation in sample complexity between the strong and weak contamination models. In the polynomial-time setting, we close a gap in the literature by providing a polynomial-time algorithm against adaptive adversaries achieving the above sample complexity [Formula: see text], and a low-degree lower bound (which complements an existing reduction from planted clique) suggesting that all efficient algorithms require this many samples, even in the oblivious-adversary setting.