我们重新审视在 $d$ 维空间中使用最大选择准则估计 $k$ 条线性回归模型时出现的自选择偏差问题，该准则最初由 Cherapanamjeri、Daskalakis、Ilyas 与 Zampetakis 在 STOC'23 中提出。本文给出了一种时间复杂度为 $\mathrm{poly}(d, k, 1/\varepsilon) + (k \log k)^{O(k)}$ 的算法，显著快于此前 CDIZ23 与 Gaitonde、Mossel 的方法。核心贡献是首次提供了针对自选择问题的局部收敛算法，解决了 CDIZ23 提出的主要开放问题。实现思路是将自选择问题归约为一种称为粗化估计的统计任务——在该任务中只能观测到包含真实样本的划分块而非精确值。粗化估计在实际中常见，例如人为或算法的四舍五入、仪器精度限制以及多智能体系统的时延。与以往仅研究凸划分的工作不同，我们面对的是由自选择结构产生的非凸划分。通过利用自选择问题的几何特性，设计算法绕过了非凸性的困难。这一几何方法突破了传统解析手段的局限，亦有望推广至其他潜变量模型的高效求解。
点评