Abstract
We study mean estimation for a Gaussian distribution with identity covariance in $\mathbb{R}^d$ under a missing data scheme termed the realizable $\epsilon$-contamination model. In this model, an adversary can choose a function $r(x) \in [0, \epsilon]$ such that each sample $x$ goes missing with probability $r(x)$. While recent work established that the mean is information-theoretically identifiable even when $\epsilon > 0.5$, the proposed estimators required runtime exponential in the dimension. In this work, we establish a fundamental information-computation gap in the Statistical Query (SQ) model, showing that any computationally efficient algorithm must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement this with a spectral algorithm whose sample-time tradeoff nearly matches our lower bound, qualitatively characterizing the complexity of Gaussian mean estimation under systematic missingness.
Introduction
In classical statistics, missing data is often handled under the assumption of "Missing Completely At Random" (MCAR), where the probability of a data point being missing is independent of its value. However, real-world data frequently exhibits "Missing Not At Random" (MNAR) patterns, where missingness is tied to the values themselves—such as high-income individuals declining to report their earnings. MNAR is notoriously difficult because it can lead to non-identifiability, where the true parameters cannot be recovered regardless of sample size.
This paper focuses on the realizable $\epsilon$-contamination model, a middle ground between the simplicity of MCAR and the intractability of general MNAR. In this model, an adversary can hide any sample $x$ with a probability $r(x) \leq \epsilon$. Unlike Huber’s contamination model, where an adversary adds malicious outliers, here the adversary only removes data. This distinction allows the mean to remain identifiable even when more than half the data is missing ($\epsilon > 0.5$). The central challenge addressed here is whether this identification can be performed efficiently in high dimensions.
The Information-Computation Gap
The primary contribution of this work is the identification of a sharp "information-computation gap." While $O(d)$ samples are sufficient to identify the mean given infinite computational resources, polynomial-time algorithms face a much steeper requirement.
Statistical Query Lower Bounds
To prove this hardness, the authors utilize the Statistical Query (SQ) framework. They construct a "hard" one-dimensional distribution that matches the first $m$ moments of a standard Gaussian. By embedding this distribution along a hidden direction in high-dimensional space, they demonstrate that any SQ algorithm must either:
- Perform an exponential number of queries ($2^{d^{\Omega(1)}}$).
- Require a sample complexity of $d^{\Omega(k)}$, where $k$ is a parameter related to the desired estimation accuracy $\delta$.
This result implies that high-dimensional mean estimation under systematic missingness is fundamentally more difficult than under random missingness, where efficient estimation is straightforward.
Algorithmic Framework
To complement the lower bounds, the paper introduces a new spectral algorithm that achieves a near-optimal tradeoff between samples and time. The algorithm leverages higher-order moments to "certify" the mean, following a three-stage process:
- List-Decoding (Warm Start): Because $\epsilon$ can be large, the algorithm first generates a list of candidate means.
- Dimension Reduction via Hermite Tensors: The algorithm computes empirical Hermite tensors (higher-order generalizations of the covariance matrix). These tensors help identify a low-dimensional subspace $V$ where the true mean is most likely to deviate from a candidate mean.
- Subspace Estimation: The authors prove that the dimension of this critical subspace $V$ depends only on the contamination level $\epsilon$ and the error tolerance $\delta$, and is independent of the ambient dimension $d$. This allows for a more computationally intensive estimation step to be performed only within the small subspace $V$.
Key Results and Implications
The study establishes that the sample complexity for a polynomial-time algorithm is approximately $n = (kd)^{O(k)}/\epsilon^2$. This nearly matches the SQ lower bound, effectively mapping the complexity landscape of the problem.
One significant insight is that this model serves as an unsupervised version of "Massart noise," a well-studied concept in supervised learning. Furthermore, the work demonstrates that while the information-theoretic limit is governed by the "tails" of the distribution (where the adversary is most likely to hide data), higher-order moments can serve as a proxy to detect and correct for this systematic bias.
Limitations and Future Directions
While this work characterizes the complexity for Gaussian distributions with identity covariance, several avenues remain open:
- General Covariance: Extending these results to Gaussians with unknown or non-identity covariance matrices ($N(\mu, \Sigma)$) is a natural next step.
- Distributional Robustness: The current proofs rely heavily on Gaussian properties. Exploring whether similar guarantees hold for broader classes, such as subgaussian distributions, remains an open question.
- Refining the Tradeoff: While the algorithm is polynomial in $d$, the exponential dependence on the moment order $k$ suggests that high-precision estimation in this model will always be computationally expensive in high dimensions.
Summary updated