Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms

Authors	Alkis Kalavasis et al.
Year	2026
Field	Machine Learning
arXiv	2602.23341
PDF	Download
Categories	cs.LG, cs.DS, stat.ML

Abstract

Coarse data arise when learners observe only partial information about samples; namely, a set containing the sample rather than its exact value. This occurs naturally through measurement rounding, sensor limitations, and lag in economic systems. We study Gaussian mean estimation from coarse data, where each true sample $x$ is drawn from a $d$-dimensional Gaussian distribution with identity covariance, but is revealed only through the set of a partition containing $x$. When the coarse samples, roughly speaking, have ``low'' information, the mean cannot be uniquely recovered from observed samples (i.e., the problem is not identifiable). Recent work by Fotakis, Kalavasis, Kontonis, and Tzamos [FKKT21] established that sample-efficient mean estimation is possible when the unknown mean is identifiable and the partition consists of only convex sets. Moreover, they showed that without convexity, mean estimation becomes NP-hard. However, two fundamental questions remained open: (1) When is the mean identifiable under convex partitions? (2) Is computationally efficient estimation possible under identifiability and convex partitions? This work resolves both questions. [...]

---

Engineering Breakdown

Plain English

This paper tackles the problem of estimating the mean of a Gaussian distribution when you only observe coarse data—sets that contain the true samples rather than exact values. This happens in real systems through measurement rounding, sensor quantization, and time lags in economic data. The authors characterize when mean estimation is theoretically possible (identifiability conditions) and provide sample-efficient algorithms that work when the mean is identifiable. The key finding is that sample complexity depends on how 'informative' the coarse data partition is, and they show efficient recovery is achievable under reasonable information-theoretic conditions.

Core Technical Contribution

The paper's core novelty is a complete characterization of the identifiability landscape for Gaussian mean estimation under coarse observations—establishing exactly when unique recovery is possible and when it fails. They provide two main algorithmic contributions: (1) a method for recovering the mean when sufficient information exists in the partition structure, and (2) sample complexity bounds that match information-theoretic lower bounds up to logarithmic factors. The technical insight is that the problem reduces to a structured linear system recovery problem where the partition geometry directly determines whether the true mean can be distinguished from other candidates. This extends prior work (FKKT21) by providing both necessary and sufficient conditions plus practical algorithms, not just existence results.

How It Works

The setup begins with $d$-dimensional Gaussian samples $x \sim \mathcal{N}(\mu, I_d)$ where $\mu$ is unknown. Instead of observing $x$ directly, the learner sees only a partition cell $C_i$ that contains $x$—a coarse set that could come from quantization, sensor thresholds, or temporal aggregation. The algorithm proceeds in two phases: first, estimate the partition structure and cell membership probabilities from observed coarse samples; second, solve a constrained optimization problem or linear system to recover $\mu$ from the estimated cell probabilities. The identifiability condition boils down to whether the partition geometry and Gaussian distribution interact in a way that makes different means produce distinguishable observed distributions. The key technical step is showing that when cells are 'well-separated' relative to the Gaussian variance, the partition structure preserves enough information for unique recovery.

Production Impact

Engineers building systems with coarse measurements—quantized sensors, binned economic data, or rounded system metrics—can now principally determine whether mean estimation is recoverable and how many samples are needed. This directly applies to signal processing pipelines where sensors naturally produce binned outputs (e.g., low-resolution temperature sensors, discrete satisfaction scores), and to time-series systems where data arrives aggregated by time window. In production, this means you can run an identifiability check on your data partition structure before investing in data collection; if the partition is too coarse, no algorithm will recover the mean. The sample complexity bounds let you size your data collection budget—you now know how many coarse samples compensate for not having exact values. Trade-offs include: added computational cost for the partition-aware recovery algorithm (typically polynomial in $d$ but with large constants), need to know or learn the partition structure, and degraded accuracy compared to exact Gaussian data.

Limitations and When Not to Use This

The paper assumes Gaussian distributions with identity covariance, which doesn't cover heavy-tailed or multimodal data common in real systems; extending to unknown or non-identity covariance matrices remains open. The identifiability characterization is tight for the specific partition model studied, but real coarse data often has measurement noise, misspecified partitions, or overlapping bin boundaries that the theory doesn't address. The algorithms require knowing the partition structure (boundaries and cells); in practice, discovering or learning an unknown partition adds significant complexity not covered here. Additionally, the sample complexity bounds use polynomial dependence on dimension $d$, which becomes prohibitive in very high-dimensional settings (>1000 dimensions), suggesting this approach works best for moderate-dimensional problems.

Research Context

This work directly extends Fotakis et al. (FKKT21) by moving from 'can we recover the mean in principle?' to 'what are necessary and sufficient conditions and how efficient are the algorithms?' It contributes to the broader literature on learning from quantized, coarse, or partial information—a classical problem in robust statistics and sensor networks that has seen renewed interest in differentially private learning. The problem sits at the intersection of identifiability theory (when is a parameter estimable?) and sample-efficient learning, connecting to recent work on learning with abstained supervision and set-valued observations. The partition-based framing opens directions for studying other distribution families (non-Gaussian, mixture models) under coarse observations and for understanding how partition refinement affects statistical hardness.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →