提出首个高效算法解决未知截断区间的线性回归问题。
Linear Regression with Unknown Truncation Beyond Gaussian Features
- 基于子高斯特征假设，设计新子程序学习区间并集
- 运行时间仅为多项式级，达ε精度时为poly(d/ε)
- 适用于无负样本的正例学习，对实际数据更友好
在截断线性回归中，仅当输出值y落在某个生存集S⋆内时才观测到样本(x, y)，目标是估计未知的d维回归系数w⋆。该问题在统计学与机器学习中历史悠久，但以往工作大多局限于已知生存集S⋆的情况。当S⋆未知且需从数据中学习时，现有算法依赖强分布假设（如特征向量服从高斯分布），且运行时间为d^poly(1/ε)才能达到ε精度。本文首次提出一种在仅需特征向量为子高斯分布的前提下，实现poly(d/ε)时间复杂度的算法。其核心在于设计一个新颖子程序，可在仅访问正例、无负例且满足光滑性条件下，高效学习有限个区间的并集。该学习保证扩展了仅有正例的PAC学习研究，可能具有独立意义。
原文摘要 · Abstract (English)
In truncated linear regression, samples $(x,y)$ are shown only when the outcome $y$ falls inside a certain survival set $S^\star$ and the goal is to estimate the unknown $d$-dimensional regressor $w^\star$. This problem has a long history of study in Statistics and Machine Learning going back to the works of (Galton, 1897; Tobin, 1958) and more recently in, e.g., (Daskalakis et al., 2019; 2021; Lee et al., 2023; 2024). Despite this long history, however, most prior works are limited to the special case where $S^\star$ is precisely known. The more practically relevant case, where $S^\star$ is unknown and must be learned from data, remains open: indeed, here the only available algorithms require strong assumptions on the distribution of the feature vectors (e.g., Gaussianity) and, even then, have a $d^{\mathrm{poly} (1/\varepsilon)}$ run time for achieving $\varepsilon$ accuracy. In this work, we give the first algorithm for truncated linear regression with unknown survival set that runs in $\mathrm{poly} (d/\varepsilon)$ time, by only requiring that the feature vectors are sub-Gaussian. Our algorithm relies on a novel subroutine for efficiently learning unions of a bounded number of intervals using access to positive examples (without any negative examples) under a certain smoothness condition. This learning guarantee adds to the line of works on positive-only PAC learning and may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。