在粗粒度数据下，如何高效估计高斯均值并判断可识别性。
Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
- 通过凸划分判断均值是否可识别，给出理论刻画。
- 提出高效算法，在可识别条件下实现样本与计算双优。
- 适用于传感器、经济系统等信息受限场景的统计推断。
粗粒度数据指观测者仅获知样本所属集合而非精确值，常见于测量舍入、传感器限制及经济系统延迟。本文研究从粗粒度数据中估计高维高斯分布（单位协方差）的均值问题，其中每个真实样本 $x$ 来自 $d$-维高斯分布，但仅以包含 $x$ 的划分集合形式呈现。当粗粒度样本信息过低时，均值不可唯一恢复（即不可识别）。此前工作 [FKKT21] 表明：若划分由凸集构成且均值可识别，则存在样本高效的估计方法；否则，估计问题变为 NP-hard。本文解决两个核心开放问题：(1) 在凸划分下均值可识别的充要条件；(2) 可识别情况下是否存在高效计算算法。答案均为肯定，并给出完整理论刻画与多项式时间算法。
原文摘要 · Abstract (English)
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. [...]
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。