Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms

Paper: 2602.23341 Authors: Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis, Felix Zhou, Ziyu Zhu Categories: cs.LG, cs.DS, math.ST, stat.ML

Abstract

This paper addresses the problem of estimating the mean of a Gaussian distribution when observations are coarse—that is, when each sample $x$ drawn from a $d$-dimensional Gaussian with identity covariance is only revealed through the partition element containing it. The authors resolve two fundamental open questions: (1) providing a complete characterization of when the mean is identifiable under convex partitions, and (2) establishing that computationally efficient estimation is possible whenever the mean is identifiable. The work introduces polynomial-time algorithms that achieve sample complexity matching information-theoretic lower bounds, bridging the gap between statistical identifiability and computational tractability in coarse data settings.

Key Contributions

• Complete characterization of identifiability for Gaussian mean estimation under convex partitions, resolving an open problem from prior work
• Polynomial-time algorithms for mean estimation that are both sample-efficient and computationally tractable when identifiability holds
• Tight information-theoretic lower bounds showing that the proposed algorithms achieve optimal sample complexity
• Extension of results to handle approximate identifiability and robustness guarantees
• Novel technical tools connecting convex geometry, optimization, and statistical estimation theory

Identifiability Characterization

The paper’s first major contribution is a precise characterization of when the mean $\mu$ of a Gaussian distribution is identifiable from coarse observations. Given a partition $\mathcal{P}$ of $\mathbb{R}^d$ into convex sets, identifiability depends on the geometric relationship between $\mu$ and the partition structure.

The authors show that identifiability is equivalent to a geometric condition: the mean $\mu$ must be the unique point that maximizes a certain potential function derived from the partition geometry. Specifically, for each partition element $P \in \mathcal{P}$, the probability mass $\Pr[x \in P]$ when $x \sim \mathcal{N}(\mu, I)$ must uniquely determine $\mu$.

This characterization is both necessary and sufficient, providing a complete answer to when mean estimation is theoretically possible. The geometric perspective reveals that identifiability fails precisely when multiple means would produce indistinguishable coarse observation distributions—a situation that occurs when the partition lacks sufficient “resolution” relative to the Gaussian’s spread.

Algorithmic Framework

Building on the identifiability characterization, the paper develops polynomial-time algorithms for mean estimation. The key algorithmic insight is to formulate estimation as a convex optimization problem that can be solved efficiently.

The algorithm operates by constructing an empirical loss function based on observed partition memberships. Given $n$ coarse samples (each revealing only which partition element contains the true sample), the estimator solves:

$\hat{\mu} = \arg\min_{\mu \in \mathbb{R}^d} \sum_{i=1}^n \ell(P_i, \mu)$

where $P_i$ is the observed partition element for sample $i$, and $\ell$ is a carefully designed loss function that exploits the convex geometry of the partition.

The authors prove that this optimization can be solved in polynomial time using standard convex programming techniques, and that the resulting estimator achieves sample complexity $O(d/\epsilon^2)$ to estimate $\mu$ within $\ell_2$ error $\epsilon$—matching information-theoretic lower bounds up to constant factors.

Technical Innovation and Analysis

The technical analysis combines tools from several areas. The proof of identifiability uses convex geometry to characterize when the mapping from means to observation distributions is injective. The algorithmic analysis employs concentration inequalities and uniform convergence arguments to bound estimation error.

A particularly elegant aspect is the connection to optimal transport theory. The authors show that the estimation problem can be viewed through the lens of Wasserstein distances between probability measures, providing both intuition and technical leverage for the analysis.

The paper also addresses robustness: when identifiability holds only approximately (e.g., when two different means produce nearly identical observation distributions), the algorithms still provide meaningful estimates with gracefully degrading guarantees. This robustness is crucial for practical applications where perfect identifiability may not hold.

Takeaways

1. Gaussian mean estimation from coarse data is computationally tractable whenever it is information-theoretically possible under convex partitions, closing the gap between statistical and computational feasibility.

2. The identifiability of the mean can be characterized geometrically through the relationship between the unknown mean and the partition structure, providing a practical test for when estimation is possible.

3. Polynomial-time algorithms achieve optimal sample complexity $O(d/\epsilon^2)$, matching information-theoretic lower bounds and demonstrating that no computational-statistical tradeoff exists in this setting.

4. The framework extends beyond exact identifiability to handle approximate settings with robustness guarantees, making it applicable to realistic scenarios with imperfect partition structures.

5. The techniques developed—connecting convex optimization, optimal transport, and statistical estimation—may have broader applications to other problems involving partial or coarse observations.