High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

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:

  1. Perform an exponential number of queries ($2^{d^{\Omega(1)}}$).
  2. 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:

  1. List-Decoding (Warm Start): Because $\epsilon$ can be large, the algorithm first generates a list of candidate means.
  2. 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.
  3. 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

Abstract

We study mean estimation for a Gaussian distribution with identity covariance in $\mathbb{R}^d$ under a missing data scheme termed realizable $ε$-contamination model. In this model an adversary can choose a function $r(x)$ between 0 and $ε$ and each sample $x$ goes missing with probability $r(x)$. Recent work Ma et al., 2024 proposed this model as an intermediate-strength setting between Missing Completely At Random (MCAR) -- where missingness is independent of the data -- and Missing Not At Random (MNAR) -- where missingness may depend arbitrarily on the sample values and can lead to non-identifiability issues. That work established information-theoretic upper and lower bounds for mean estimation in the realizable contamination model. Their proposed estimators incur runtime exponential in the dimension, leaving open the possibility of computationally efficient algorithms in high dimensions. In this work, we establish an information-computation gap in the Statistical Query model (and, as a corollary, for Low-Degree Polynomials and PTF tests), showing that algorithms must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement our SQ lower bound with an algorithm whose sample-time tradeoff nearly matches our lower bound. Together, these results qualitatively characterize the complexity of Gaussian mean estimation under $ε$-realizable contamination.
BibTeX
@misc{diakonikolas2026high,
  author = {Ilias Diakonikolas and Daniel M. Kane and Thanasis Pittas},
  title = {{High-Dimensional Gaussian Mean Estimation under Realizable Contamination}},
  year = {2026},
  eprint = {2603.16798},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.16798},
}
Figure