技术摘要：未知截断下的线性回归与高斯特征之外

1. 问题定义

本文解决了截断线性回归问题，其中截断（或“生存”）集是未知的。在此设定下，学习者观察到的样本 $(x, y)$ 生成过程如下：

1. 特征向量 $x \in \mathbb{R}^d$ 从未知分布 $\mathcal{D}$ 中抽取。
2. 标签 $y$ 计算为 $y = x^\top w^\star + \xi$，其中 $w^\star$ 是未知的回归系数，$\xi \sim \mathcal{N}(0, 1)$ 是高斯噪声。
3. 仅当且仅当 $y \in S^\star$ 时，样本才会被观察到，其中 $S^\star \subseteq \mathbb{R}$ 是未知的“生存集”。否则，样本将被丢弃。

目标是估计 $w^\star$ 以达到 $\varepsilon$ 精度。主要挑战在于，标准估计量（如普通最小二乘法）会因选择偏差而失效，且针对该问题的先前高效算法要么需要已知 $S^\star$，要么需要对特征分布做出强假设（具体而言，即假设 $\mathcal{D}$ 是高斯分布）。

作者关注的是 $S^\star$ 未知且为最多 $k$ 个区间的并集这一实际相关情形。他们的目标是在更弱的假设下实现这一目标，即假设特征分布 $\mathcal{D}$ 是次高斯的，而非严格的高斯分布。

2. 方法论

所提出的算法（算法 1）分为两个不同的阶段：

阶段 I：学习截断集 $S^\star$

由于 $S^\star$ 未知，算法首先学习一个近似 $\hat{S} \approx S^\star$。

• 仅正例学习：学习 $S^\star$ 的问题被构建为仅从正例（即 $y \in S^\star$ 的样本）中学习一个概念（集合 $S^\star$），而无法访问负例。
• 平滑性假设：为了使这一学习在信息论上可行，作者利用了一个“平滑”学习框架。他们构建了一个辅助分布 $\mathcal{D}$，该分布相对于 $y$ 的真实未截断边缘分布（记为 $\mathcal{D}^\star_+$）是“平滑”的。
• 关键引理（平滑性）：作者证明，如果特征分布 $\mathcal{D}$ 是次高斯的，那么对于任何接近 $w^\star$ 的参数向量 $w$，由 $w$ 生成的 $y$ 的分布（记为 $\mathcal{D}_y(w)$）相对于真实分布 $\mathcal{D}_y(w^\star)$ 是平滑的。这使得利用“热启动” $b_w$（$w^\star$ 的初始估计）构建必要的辅助分布成为可能。
• 算法：他们采用了一种贪心过程（算法 3）来学习 $k$ 个区间的并集。这涉及对正样本进行排序，识别它们之间的区间，并丢弃包含来自辅助分布样本最多的区间。该过程在一维集合上可在多项式时间内运行。

阶段 II：通过投影随机梯度下降 (PSGD) 进行参数估计

一旦获得近似集 $\hat{S}$，算法便开始估计 $w^\star$。

• 扰动目标函数：由于 $\hat{S} \neq S^\star$，标准的负对数似然 (NLL) 在通常意义上既未良好定义也不凸。作者最小化一个扰动 NLL 目标函数 $\mathcal{L}_{\hat{S}}(w)$，该函数在数据生成部分使用估计集与真实集的交集定义，但在模型似然部分使用估计集。
• 投影集：为了确保收敛，优化过程被限制在一个投影集 $\mathcal{P}$ 内（即围绕热启动 $b_w$ 的常数半径球体）。
  • 作者证明，$w^\star$ 以高概率位于 $\mathcal{P}$ 内。
  • 他们确立了在集合估计误差足够小的前提下，$\mathcal{L}_{\hat{S}}$ 在 $\mathcal{P}$ 内是强凸的。
• 有偏梯度采样：一个关键的技术障碍是为 $\mathcal{L}_{\hat{S}}$ 采样梯度。精确采样是不可行的。作者设计了一种近似梯度采样器，可产生有偏梯度。他们证明偏差是有界的，并且可以通过使集合估计误差 $\varepsilon$ 足够小来控制该偏差。
• 收敛性：他们分析了使用这些有偏梯度的 PSGD，表明该算法收敛到接近 $\mathcal{L}_{\hat{S}}$ 最小值点的解，而该点又接近 $w^\star$。

3. 主要贡献

1. 首个针对未知截断的多项式时间算法：本文提出了首个算法，当生存集 $S^\star$ 未知且为 $k$ 个区间的并集时，能在 $\text{poly}(d, k, 1/\varepsilon)$ 时间内学习 $w^\star$。
2. 放宽分布假设：与先前工作（如 Lee, Mehrotra 和 Zampetakis [LMZ24]）要求特征分布为高斯分布不同，该算法仅要求特征是次高斯的。这显著扩大了其在现实世界数据中的适用性，因为在现实世界中高斯性往往是不切实际的假设。
3. 高效的仅正例学习：作者提供了一个高效的算法，用于在平滑性条件下从仅正例中 PAC 学习区间的并集。这一子程序对学习理论社区具有独立的兴趣。
4. 处理有偏梯度：该工作在截断回归的背景下引入了针对带有有偏梯度估计量的 PSGD 的新颖分析，证明了即使在无法进行精确梯度采样的情况下也能实现收敛。

4. 结果

• 定理 3.1（主要结果）：在假设 1（生存概率）、假设 2（次高斯性）和假设 3（可识别性）下，存在一种算法，给定 $n = \text{poly}(d, k, 1/\varepsilon)$ 个样本，输出估计值 $\hat{w}$，使得 $\|\hat{w} - w^\star\|_2 \leq \varepsilon$ 的概率为 $1-\delta$。
• 复杂度：样本复杂度和运行时间均随维度 $d$、区间数量 $k$ 和逆精度 $1/\varepsilon$ 呈多项式增长。
• 比较：在特征为高斯分布的特殊情况下，作者将最先进方法 [LMZ24] 的运行时间从 $d^{\text{poly}(k/\varepsilon)}$（关于 $d$ 指数级）改进为 $\text{poly}(d, k, 1/\varepsilon)$。
• 模拟：在合成数据（10 维高斯混合模型，5 个区间）上的实验表明，所提出的算法收敛到真实 $w^\star$ 的速度与已知 $S^\star$ 的理想化算法相当，并且显著优于 OLS 以及使用错误截断集的 PSGD。

5. 意义与主张

本文声称解决了截断回归中长期存在的一个开放问题：在截断集未知的情况下，无需对特征做出高斯分布的严格假设即可实现计算效率。

• 实际相关性：作者强调，现实世界中的截断集（例如在天文学或计量经济学中）通常是复杂的区间并集，且很少被明确知晓。此外，这些领域的特征分布很少是严格高斯的。
• 理论进展：通过将假设从高斯特征扩展到次高斯特征，该工作弥合了理论可处理性与实际数据特征之间的差距。
• 谦逊声明：作者承认其算法依赖于 $S^\star$ 是有界数量区间（$k$）的并集这一假设。他们指出，如果 $S^\star$ 已知，则可以完全避免关于 $d$ 的指数依赖关系，但在未知情况下，必须依赖 $d$（具体体现在集合学习的样本复杂度指数中，尽管运行时间仍保持多项式）。他们还指出，他们的方法专门针对响应变量 $y$ 上的截断，这与先前处理 $x$ 和 $y$ 上高维截断但要求高斯性的工作不同。

该工作被呈现为迈向处理高维回归中系统性选择偏差的基础性步骤，且无需依赖关于协变量的参数化假设。