High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas; Daniel M. Kane; Thanasis Pittas

cs.LGMar 17, 2026

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Authors: Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

Organizations: University of Wisconsin-Madison · University of California, San Diego

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.

Explore similar work

May 2, 2026stat.ML

Mean Testing under Truncation beyond Gaussian

We characterize the fundamental limits of high-dimensional mean testing under arbitrary truncation, where samples are drawn from the conditional distribution

P(\cdot \mid S)

for an unknown truncation set

S

that may hide up to an

\varepsilon

-fraction of the probability mass. For distributions with

p

-th directional moments of magnitude at most

ν_{P,p}

, truncation induces a bias of order

O(ν_{P,p}\varepsilon^{1-1/p})

. This bias creates a sharp information-theoretic detectability floor: when the signal

α

falls below this threshold, the null and alternative hypotheses are indistinguishable even with infinite data. Above this floor, we prove that a simple second-order test achieving near-optimal sample complexity

n = O\!\left(\frac{\|Σ_P\|}{(α-4ν_{P,p}\varepsilon^{1-1/p})^2}\sqrt{d}\right)

. We further identify a structural escape from this finite-moment bias barrier. Under a directional median regularity assumption, truncation bias improves to linear order

O(\varepsilon)

. This reveals an intermediate regime in which estimation requires

Θ(d)

samples for uniform recovery, while testing recovers the classical

Θ(\sqrt d)

rate once truncation bias is eliminated. Together, our results provide a unified framework for mean testing under truncation, connecting finite-moment, sub-Gaussian, and median-regular structural regimes.

Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis

Truncation Regularity 3D Gaussian Splatting

Ask PDF

Apr 19, 2024stat.ML

Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models

In this paper, we study the problem of learning one-dimensional Gaussian mixture models (GMMs) with a specific focus on estimating both the model order and the mixing distribution from independent and identically distributed (i.i.d.) samples. This paper establishes the optimal sampling complexity for model order estimation in one-dimensional Gaussian mixture models. We prove a fundamental lower bound on the number of samples required to correctly identify the number of components with high probability, showing that this limit depends critically on the separation between component means and the total number of components. We then propose a Fourier-based approach to estimate both the model order and the mixing distribution. Our algorithm utilizes Fourier measurements constructed from the samples, and our analysis demonstrates that its sample complexity matches the established lower bound, thereby confirming its optimality. Numerical experiments further show that our method outperforms conventional techniques in terms of efficiency and accuracy.

Xinyu Liu, Hai Zhang

Gaussian Mixture Models Sample Complexity Estimators Model Selection Fourier

Ask PDF

Jun 25, 2026cs.DS

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy

\varepsilon > 0

and dimension

d

we give an efficient algorithm that uses

n = \tilde{O}(d^2/\varepsilon^2)

samples and learns the underlying Gaussian to error

\varepsilon

in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of

d

and

\varepsilon

even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1

Optimal Sample Complexity Gaussian Mixture Models Truncation 3D Gaussian Splatting Gradient Descent

Ask PDF