Authors: Clément Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, and Shyam Narayanan Date: July 21, 2023
Introduction
Gaussian mean testing is a fundamental problem in high-dimensional statistics and signal processing. Given $n$ samples in $d$ dimensions, the objective is to determine whether they originate from a standard Gaussian distribution $\mathcal{N}(0, I)$ or a shifted Gaussian $\mathcal{N}(\mu, I)$ where the shift is significant, specifically $\|\mu\|_2 \geq \alpha$.
In practical scenarios, data is rarely pristine. Robust statistics addresses this by assuming an $\epsilon$-fraction of samples are adversarially corrupted. Traditionally, two types of adversaries are considered: Adaptive (Strong) adversaries, who can see all data before choosing which samples to corrupt, and Oblivious (Weak) adversaries, who must choose which indices to corrupt before observing the data. While it was long believed that this distinction did not affect the fundamental difficulty of mean estimation, this paper demonstrates a sharp separation in the context of testing.
The Adversarial Gap
The core contribution of this work is overturning the "common wisdom" that adaptivity does not matter in robust statistics. The authors prove that it is strictly easier to detect a signal when the adversary is oblivious rather than adaptive.
In the adaptive model, an adversary can strategically correlate corrupted points with "good" points to effectively cancel out the signal $\mu$. An oblivious adversary, lacking knowledge of the specific sample values, cannot perform this correlation. This lack of coordination allows for more efficient testing using fewer samples, provided the algorithm can exploit this weakness.
Methodology
To map this new landscape, the authors combined novel algorithm design with rigorous information-theoretic lower bounds:
- Obliviousness-Preserving Filtering: Standard robust filtering algorithms typically use the entire dataset to identify outliers, which inadvertently introduces dependencies that destroy the "oblivious" nature of the noise. The authors developed a sample splitting technique to identify suspicious directions in one subset and apply them to another, maintaining the statistical independence necessary to exploit oblivious noise.
- The Sum+Variance Tester: For the oblivious setting, the authors designed a tester that monitors two specific signals: the norm of the empirical mean (the "Sum") and the variance of the samples in the direction of that mean.
- Information-Theoretic Bounds: Using $\chi^2$-divergence and refined second-moment methods, the authors established lower bounds showing that no algorithm can distinguish the hypotheses below specific sample thresholds.
- Low-Degree Polynomial Method: To investigate the computational limits, they employed the "low-degree method" to rule out a wide class of efficient algorithms, including spectral methods and Sum-of-Squares (SoS).
Key Results: The Four-Phase Landscape
The research reveals that the sample complexity for oblivious testing is not a single formula but a complex landscape consisting of four distinct phases, depending on the relationships between the dimension $d$, the corruption rate $\epsilon$, and the signal strength $\alpha$.
Sample Complexity Comparison
- Adaptive Sample Complexity: The authors confirm a tight bound of $\tilde{\Theta}(\max(\frac{\sqrt{d}}{\alpha^2}, \frac{d\epsilon^2}{\alpha^4}))$.
- Oblivious Sample Complexity: The new, lower complexity for oblivious adversaries is established as: $$\tilde{\Theta}\left(\max\left(\frac{\sqrt{d}}{\alpha^2}, \frac{d\epsilon^3}{\alpha^4}, \min\left(\frac{d^{2/3}\epsilon^{2/3}}{\alpha^{8/3}}, \frac{d\epsilon}{\alpha^2}\right)\right)\right)$$
Statistical-Computational Gaps
A significant finding of the paper is the existence of a statistical-computational gap. While it is theoretically possible to achieve lower sample complexity against an oblivious adversary, the authors prove that any polynomial-time algorithm is restricted to the higher sample complexity required for the adaptive case ($\Omega(\frac{d\epsilon^2}{\alpha^4})$). Essentially, computational efficiency comes at the cost of being unable to exploit the adversary's lack of adaptivity.
Conclusion and Future Work
This work provides the first known sharp separation between oblivious and adaptive contamination in robust statistics. It establishes that while oblivious noise is fundamentally "weaker," harvesting that weakness requires exponential time.
Future research directions include extending these results to broader distribution classes beyond Gaussians, such as heavy-tailed or sub-Gaussian distributions, and resolving the remaining gap in the Huber model (i.i.d. noise), where a matching upper bound for the conjectured lower bound is still needed.
Summary updated