# Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms

arXiv: https://arxiv.org/abs/2602.23341 · HTML: https://mlsanity.com/paper/2602.23341/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Snorkel: Rapid Training Data Creation with Weak Supervision](https://mlsanity.com/paper/1711.10160/) (2017)
- [Learning a Deep ConvNet for Multi-label Classification with Partial Labels](https://mlsanity.com/paper/1902.09720/) (2019)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Provably Consistent Partial-Label Learning](https://mlsanity.com/paper/2007.08929/) (2020)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Partial Label Learning with Self-Guided Retraining](https://mlsanity.com/paper/1902.03045/) (2019)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning](https://mlsanity.com/paper/2012.12137/) (2020)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Predictive Inference with Weak Supervision](https://mlsanity.com/paper/2201.08315/) (2022)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness](https://mlsanity.com/paper/2506.04194/) (2025)
- [Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases](https://mlsanity.com/paper/2504.07133/) (2025)

## Abstract (arXiv)

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. [...]