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. [...]
Figures & tables
Figure 1: Different partitions \mathdutchcalP of R2 . (a) Left: A non-identifiable partition where any μ⋆∈R2 and its translation along the x -axis induce identical distributions of coarse samples. (b) Middle and (c) right: Identifiable partitions of the space.
Figure 2: An illustration of different slabs in direction v in three dimensions. Intuitively, a slab in direction v is formed by taking a 2D shape ((a) square, (b) circle, (c) hexagon in each of the three subfigures) and extending it infinitely in direction v (and −v ).
Figure 3: Illustrations of different friction functions c:R→R . (a) Left: monotone with convex pre-images. (b) Middle: not monotone but has convex pre-images. (c) Right: not monotone and has non-convex pre-images.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Each row shows a distribution (rows 1 and 2: Beta; rows 3 and 4: Gaussian). Columns (1,3): bar plots of empirical variances (red = original, blue = truncated) with variance ratio r=Vartrunc/Varorig annotated. Columns (2,4): histogram overlays (original vs. truncated) for half-line (col. 2) and interval [L,U] truncations (col. 4). In all displayed runs, r<1 , indicating variance reduction under these convex truncations.
Figure 5: Same layout as Figure 4 . Rows 1 and 2: Laplace; rows 3 and 4: Quartic (density ∝e−(x−μ)4/s ). Columns (1,3) report variance bars and r ; columns (2,4) show the corresponding histogram overlays for half-line and interval [L,U] truncations. The observed r<1 across settings provides further evidence of practical variance reduction beyond the Gaussian case.
Department of Data Sciences and Operations, University of Southern California · Department of Statistics and Data Science, Carnegie Mellon University · Department of Computer Science, Stanford University