自选择偏差线性回归迎来多项式时间算法
Linear Regression with Self-Selection Bias in Polynomial Time
一帮理论计算机科学家把自选择偏差下的线性回归从指数时间压到了多项式时间，连相关的 max-affine 回归也一并解决。核心技巧是 Hermite 矩加张量分解，跳过了旧方法的子空间穷举。做统计学习理论或潜变量模型的人值得翻翻原文。
一篇 arXiv 论文研究了带自选择偏差的线性回归估计问题：在 n 维空间中估计 k 个线性回归子，目标误差为 ε，沿用 CDIZ23（STOC）提出的最大自选择准则。作者给出了 poly(n,k,1/ε) 时间的未知索引变体算法，优于 Gaitonde-Mossel（GM24）和 Kalavasis-Mehrotra-Zhou（KMZ26, COLT）此前对 k 呈指数依赖的算法。算法还支持回归子之间存在相关噪声的情形，因此同时给出了 max-affine 回归的首个多项式时间算法，改进 GPGR22（IEEE Trans. Inf. Theory）与 GM24 的指数依赖结果。
技术路径上，此前工作穷举回归子张成的 k 维子空间，用响应变量的条件矩检验候选；新算法改为利用协变量矩的结构：筛选响应值较大的观测后，度数为 log n 的 Hermite 矩近似分解为回归子张量幂之和。第一步对隐式表示的高阶张量做张量分解，输出平行于回归子的单位向量；第二步用普通最小二乘的变体提取回归子估计。作者认为该矩分析思路可迁移到其他潜变量问题的高效算法设计。
Linear Regression with Self-Selection Bias in Polynomial Time
We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.
本条情报归属 AITOP「论文」核心栏目，重点聚焦北美前沿实验室与硅谷科技巨头。涉及核心实体与技术议题包括：线性回归、张量分解、max-affine回归、Hermite矩，读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明：本文原始线索采编自「arXiv cs.LG」（@Felix Zhou），经 AITOP 多维评分管线结构化提炼。