技术摘要：去除伪相关是否总是可学习的？

1. 问题形式化

本文探讨了机器学习中**去除伪相关（spurious correlation removal）的挑战，特别是在不变学习（invariant learning）**的语境下。模型往往会利用在训练数据中成立但在分布偏移下失效的相关性。虽然不变学习旨在识别那些在多个环境中其与标签之间的预测关系保持稳定的特征，但实证结果显示，即使在理论上可以识别不变结构的情况下，性能表现仍不一致。

作者将该问题形式化为在多环境数据下的**不变子空间恢复（invariant subspace recovery）**问题（采用线性高斯设定）：

• 实例： 一个数据集由 $d$ 维特征 $X$ 组成，这些特征被分解为一个不变子空间 $V_{inv}$（维度为 $k$）和一个伪相关子空间 $V_{sp}$。
• 条件： 条件机制 $P_e(Y | X_{inv})$ 在所有环境 $e \in E$ 中是相同的，而伪相关特征的条件分布 $P_e(X_{sp} | X_{inv})$ 则随环境而变化。
• 目标： 在给定所有环境样本的情况下，恢复不变子空间 $V_{inv}$。
• 关键指标： 环境多样性通过分离参数 $\gamma$ 来量化，该参数衡量了环境对伪相关进行扰动的差异程度。

2. 方法论与理论框架

本文建立了一个关于伪相关去除的计算-统计分离（computational-statistical separation），区分了什么是统计可学习的（具有无限计算能力时）以及什么是高效可学习的（在多项式时间内）。

2.1 计算硬度（条件下界）

作者构建了一个“困难”的多环境实例族，以证明不变子空间恢复在统计上是可行的，但在计算上是难以处理的。

• 原语（Primitive）： 这种硬度依赖于一个黑盒可采样监督稀疏恢复原语（假设 3.2）。该原语受平均情况下的稀疏恢复归约（例如 Planted Clique）启发，但被视为一种条件假设，而非直接从现有的稀疏 CCA 结果中推导而来。
• 构造： 该原语被嵌入到一个多环境设定中，其中不变方向对应于该原语的隐藏稀疏向量。伪相关特征被构造为在不同环境下发生变化，从而模拟非不变方向的特性。
• 结果：
  • 统计可学习性： 通过穷举搜索（指数时间）可以用多项式数量的样本恢复不变子空间。
  • 计算硬度： 任何实现常数精度恢复的多项式时间算法，都将意味着能够解决底层平均情况下的稀疏恢复问题，这与硬度原语相矛盾。
  • 启示： 存在一个差距：即在拥有足够样本的情况下，不变结构是可识别且可学习的，但如果没有指数级的时间，没有任何高效算法能找到它。

2.2 统计基础（极小极大速率与相变）

本文分析了在具有足够环境多样性的情况下的样本复杂度与估计误差。

• 可识别性： 当且仅当环境多样性足够时，可以通过不变性间隙（invariance-gap）准则识别不变子空间。具体而言，如果分离参数 $\gamma = 0$（环境并未导致伪相关均值的可区分变化），则无论样本量多大，不变子空间都是不可识别的。
• 极小极大风险（Minimax Risk）： 在局部高斯正则性和充足多样性（$\gamma > 0$）的条件下，估计不变子空间的极小极大风险为：
  $$\mathbb{E}[\text{dist}(\hat{V}, V_{inv})^2] = \Theta\left(\frac{k(d-k)}{n|E|}\right|$$
  其中 $n$ 是每个环境的样本数，$|E|$ 是环境数量。
• 相变： 在结构化的标签诱导偏移（label-induced shift）机制下，在临界样本量 $n^*$ 处会发生剧烈的相变：
  $$n^* \propto \frac{k(d-k)}{|E|\gamma^2}$$
  在 $n^*$ 以下，估计误差被限制在非零水平；在 $n^*$ 以上，误差随 $O(1/(n|E|\gamma^2))$ 缩放。这强调了多样性 ($\gamma$) 比单纯增加样本量更为关键；少量多样化的环境比许多相似的环境更具信息量。

2.3 可行性条件

作者确定了多项式时间方法可以达到近乎最优速率的结构性条件，这解释了为什么不变学习在实践中通常是有效的，尽管存在最坏情况下的硬度：

1. 稀疏不变结构： $V_{inv}$ 具有稀疏基。
2. 谱分离： 一个可高效计算的对比矩阵（contrast matrix）在不变方向和伪相关方向之间存在谱间隙。
3. 低阶矩可识别性： 伪相关方向会导致相关性或矩的可检测变化。
4. 环境内不相关性： 不变特征与伪相关特征在每个环境内是不相关的。

3. 主要贡献

1. 计算-统计差距： 首次构建了展示不变子空间恢复存在条件计算-统计差距的案例，表明去除伪相关在统计上可行，但在计算上可能难以处理。
2. 量化多样性： 引入了分离参数 $\gamma$ 来量化环境多样性，并将其直接与可识别性、极小极大风险和样本复杂度转换联系起来。
3. 相变分析： 推导了在标签诱导偏移机制下，临界样本量与 $1/\gamma^2$ 成比例的缩放关系，预示了多样性是学习的限制因素。
4. 可行性区间： 确定了允许高效算法取得成功的特定结构性条件（如稀疏性、谱间隙等），为不变学习在某些基准测试上的成功提供了理论依据。

4. 实验结果

作者通过合成数据集和真实世界数据集（ColoredMNIST, CelebA, Waterbirds）验证了其理论预测。

• 计算-样本差距： 在合成的困难实例上，为了达到相同的特征选择精度，穷举搜索所需的样本量显著低于最优的多项式时间方法（最高达 $27\times$）。
• 相变现象： 实验证实，随着样本量的增加，多项式时间方法会出现从失败到成功的剧烈转变，这与理论中的 $n^*$ 一致。穷举搜索在整个范围内始终保持接近最优。
• 多样性的必要性： 当 $\gamma = 0$ 时性能较差，而随着多样性增加，性能显著提升。在真实数据集上，增加伪相关偏差的多样性（例如在 ColoredMNIST 中）会显著提高分布外（OOD）和最差组（worst-group）的准确率。
• 诊断工具： 在 ERM 特征上计算的表示空间多样性代理指标 ($\hat{\gamma}_{repr}$) 与下游的最差组性能相关，这提供了一个用于诊断不变学习失败的实用工具。

5. 意义与主张

本文声称解决了不变学习性能不一致的问题，即确立了即使在不变性是可识别的情况下，不变性也不总是高效可学习的。

• 诊断价值： 该框架有助于从业者区分是统计限制（样本不足或缺乏环境多样性）还是计算障碍（问题结构困难）。
• 实践指导： 作者提出，当不变学习失效时，从业者应首先估计环境多样性。如果多样性较低，收集更多多样化的环境比收集更多来自相似分布的样本更有效。如果多样性较高但性能仍然较差，则问题可能在于计算上的不可行性或优化限制。
• 谦逊立场： 作者强调，他们的硬度结果是最坏情况下的且是基于特定稀疏恢复原语的条件结果。他们并不声称典型的基准数据集在计算上是困难的；相反，他们提供了一个理论解释，说明为什么不变学习有时会失败，并给出了其成功的条件。

这项工作表明，观察到的不变学习中的“不一致性”（有时有效，有时无效）甚至可以在理想化的、不变性可识别的设定下发生，这主要是由于环境多样性与计算约束之间的相互作用造成的。