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. We design both new testing algorithms and new lower bounds to show that robust testing in the presence of an oblivious adversary requires strictly fewer samples than in the presence of an adaptive one. Joint work with Clement Canonne, Jerry Li, Allen Liu, and Shyam Narayanan, to appear in FOCS 2023.

Bio: Sam Hopkins is a mathematician and computer scientist. He is an Assistant Professor at MIT, in the Theory of Computing group in EECS, where he holds the Jamieson Career Development Chair.

Previously, he was a Miller fellow in the theory group at UC Berkeley, hosted by Prasad Raghavendra and Luca Trevisan. Before that, he received his PhD at Cornell, advised by David Steurer.