揭示了不变学习在特定条件下无法被高效算法实现的计算瓶颈
Is Spurious Correlation Removal Always Learnable?
- 基于稀疏恢复原语，构造出可采样的多环境学习实例
- 当环境多样性足够时，最小风险与样本数、维度成反比关系
- 提出简单诊断工具，帮助识别实际数据中的环境差异不足问题
即使不变结构在统计上可识别，不变学习仍可能失败。我们揭示了一个条件性计算障碍：在由平均情况稀疏恢复归约启发的黑箱可采样监督稀疏恢复原语下，存在可采样的多环境实例，其预测不变子空间为一维（k=1），可通过穷举搜索用多项式样本量学习，但任何多项式时间的常数精度恢复算法将违反该原语。我们进一步通过分离参数γ量化环境多样性，该参数控制可识别性及不变目标的曲率。在充分多样性与局部高斯正则条件下，极小极大风险满足𝔼[dist(ˆV, V_inv)²] = Θ(k(d−k)/(n|ℰ|))；在标签驱动的分布偏移下，当n* ∝ k(d−k)/(|ℰ|γ²)时出现相变，估计误差缩放与1/γ²成正比。合成与真实数据集验证了预测的差距与相变现象，并推动了简单的多样性诊断方法。
原文摘要 · Abstract (English)
Invariant learning can fail even when the invariant structure is statistically identifiable. We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive motivated by average-case sparse-recovery reductions, there exist \emph{samplable} multi-environment instances with a one-dimensional predictive invariant subspace ($k=1$) that are learnable with polynomial samples by exhaustive search, while any polynomial-time constant-accuracy recovery algorithm would contradict the primitive. We further quantify environment diversity by a separation parameter $γ$, which controls identifiability and the curvature of invariance objectives. Under sufficient diversity and local Gaussian regularity, the minimax risk is $\mathbb{E}[\dist(\hat{V},V_{\mathrm{inv}})^2]=Θ(k(d-k)/(n|\mathcal{E}|))$, and under label-induced shifts a phase transition occurs at $n^*\propto k(d-k)/(|\mathcal{E}|γ^2)$ with refined estimation error scaling proportional to $1/γ^2$. Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。