提出首个自选择问题的局部收敛算法，提升计算效率并拓展应用范围。
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond
- 将自选择问题转化为粗化统计推断，利用几何特性突破传统方法瓶颈。
- 算法时间复杂度为多项式级，比之前最优算法快至少指数级。
- 适用于拍卖数据、传感器误差等现实场景，适合机器学习与统计学者参考。
我们重新研究了在 d 维空间中通过最大选择准则估计 k 个线性回归器的自选择偏差问题，该问题由 Cherapanamjeri 等人 [CDIZ23, STOC'23] 提出。本文的主要成果是设计了一个运行时间为 $\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$ 的算法，显著优于 [CDIZ23] 与 [GM24, arXiv] 的现有方法。通过首次构建自选择问题的局部收敛算法，解决了 [CDIZ23] 中的核心开放问题。核心思路是将自选择问题归约到一个看似无关的统计问题——粗化（coarsening），即仅观测到样本所在集合而非精确值。该归约基于自选择问题的几何结构，避免了以往分析方法的局限。为验证其普适性，我们进一步给出了另一种自选择准则下线性回归的局部收敛算法，该准则与第二价格拍卖数据相关。此外，我们首次提出在凸划分生成样本条件下，粗化高斯均值估计的多项式时间局部收敛算法。此前仅有样本高效算法，由 Fotakis 等人 [FKKT21, COLT'21] 提出。
原文摘要 · Abstract (English)
We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a $\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$ time algorithm for this problem, which yields an improvement in the running time of the algorithms of [CDIZ23] and [GM24, arXiv]. We achieve this by providing the first local convergence algorithm for self-selection, thus resolving the main open question of [CDIZ23]. To obtain this algorithm, we reduce self-selection to a seemingly unrelated statistical problem called coarsening. Coarsening occurs when one does not observe the exact value of the sample but only some set (a subset of the sample space) that contains the exact value. Inference from coarse samples arises in various real-world applications due to rounding by humans and algorithms, limited precision of instruments, and lag in multi-agent systems. Our reduction to coarsening is intuitive and relies on the geometry of the self-selection problem, which enables us to bypass the limitations of previous analytic approaches. To demonstrate its applicability, we provide a local convergence algorithm for linear regression under another self-selection criterion, which is related to second-price auction data. Further, we give the first polynomial time local convergence algorithm for coarse Gaussian mean estimation given samples generated from a convex partition. Previously, only a sample-efficient algorithm was known due to Fotakis, Kalavasis, Kontonis, and Tzamos [FKKT21, COLT'21].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。