Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination¶

会议: NeurIPS 2025
arXiv: 2510.10665
代码: 无
领域: 统计学习理论/鲁棒优化
关键词: 信息-计算权衡, 鲁棒线性回归, Oblivious Contamination, Statistical Query, 计算下界

一句话总结¶

对无噪声线性回归在Oblivious污染模型下，形式化证明任何高效Statistical Query算法都需要 \(\tilde{\Omega}(d^{1/2}/\alpha^2)\) 的VSTAT复杂度，给出了 \(1/\alpha\) 的二次依赖对高效算法具有本质性的计算下界证据。

研究背景与动机¶

问题设定¶

考虑如下无噪声线性回归问题：给定 \(n\) 个i.i.d.样本 \((x_i, y_i)\)，其中： - \(x \sim \mathcal{N}(0, \mathbf{I}_d)\)（高斯协变量） - \(y = x^\top \beta + z\)，其中 \(z\) 独立于 \(x\)，来自未知分布 \(E\) - 关键假设：\(\mathbb{P}_E[z=0] = \alpha > 0\)（有 \(\alpha\) 概率的样本是"干净"的）

目标：准确恢复回归系数 \(\beta\)，使 \(\ell_2\) 误差尽量小。

信息-计算差距¶

这一问题存在一个显著的信息-计算差距（Information-Computation Gap）：

信息论上限：不考虑计算效率时，\(O(d/\alpha)\) 个样本就足够恢复 \(\beta\)
已知高效算法：多项式时间算法需要 \(\Omega(d/\alpha^2)\) 个样本
差距：\(1/\alpha\) vs \(1/\alpha^2\)，差距为 \(1/\alpha\) 倍

这种二次差距是偶然的（现有算法不够好），还是本质的（高效算法不可能做得更好）？

动机¶

Oblivious污染模型是鲁棒统计学中的基础模型之一，介于无污染和对抗污染之间。理解其计算复杂性有助于： 1. 划定鲁棒估计的计算可行性边界 2. 指导算法设计——如果下界是紧的，就不必追求更优的多项式时间算法 3. 深化对信息-计算权衡这一基础现象的理解

方法详解¶

整体框架¶

本文的核心技术贡献是建立Statistical Query (SQ) 下界，证明在SQ计算模型下，恢复 \(\beta\) 需要的查询复杂度（VSTAT复杂度）至少为 \(\tilde{\Omega}(d^{1/2}/\alpha^2)\)。

技术路线： 1. 将回归问题归约到区分假设检验问题 2. 利用SQ下界的标准框架（基于统计距离/卡方散度） 3. 构造"难"的Oblivious污染分布族，使得区分需要大量SQ查询

关键设计¶

1. SQ模型与VSTAT

SQ模型是分析计算-统计权衡的标准工具： - 算法不能直接访问样本，只能提出形如"\(\mathbb{E}[\phi(x,y)]\) 是多少"的统计查询 - VSTAT(\(n\)) oracle：对每个查询返回一个答案，精度为 \(O(1/n)\) - VSTAT复杂度衡量算法需要多少"有效样本" - 许多已知的多项式时间算法都可以在SQ模型中实现

2. 困难分布族的构造

核心技术困难在于构造一族Oblivious污染分布，使得： - 每个分布对应不同的 \(\beta\) - 任何两个分布在SQ意义下"难以区分" - 区分所需的VSTAT复杂度达到目标下界

具体构造利用了高维几何和高斯分布的特殊性质： - 将 \(\beta\) 嵌入到高维球面上 - 精心设计污染分布 \(E\) 的矩结构，使其"隐藏"了 \(\beta\) 的信息 - 关键引理：当 \(\alpha\) 较小时，区分不同 \(\beta\) 对应的联合分布需要 \(\Omega(1/\alpha^2)\) 的精度

3. 卡方散度分析

下界证明的核心是bound住困难分布族上的平均卡方散度： - 证明 \(\chi^2\)-divergence 在低精度SQ下足够小 - 由此推出所需的VSTAT复杂度下界 - 技术上需要处理高维高斯积分和矩的精细分析

损失函数 / 训练策略¶

本文为理论工作，不涉及训练。核心定理：

定理（主结果）：任何SQ算法若要从上述模型中恢复 \(\beta\) 到常数 \(\ell_2\) 误差，需要 VSTAT 复杂度至少为：

\[\tilde{\Omega}\left(\frac{d^{1/2}}{\alpha^2}\right)\]

实验关键数据¶

理论结果对比¶

本文是纯理论工作，"实验"以定理形式呈现。核心结果汇总：

算法类型	样本复杂度	多项式时间？	来源
信息论最优	\(O(d/\alpha)\)	否（穷举搜索）	已知结果
Filter-based	\(O(d/\alpha^2)\)	是	Diakonikolas et al.
Robust regression	\(O(d/\alpha^2)\)	是	已知结果
SQ下界	\(\tilde{\Omega}(d^{1/2}/\alpha^2)\)	—	本文

与相关下界的对比¶

问题	信息论	已知高效	SQ下界	差距
Gaussian均值估计（Oblivious）	\(O(d/\alpha)\)	\(O(d/\alpha^2)\)	\(\tilde{\Omega}(d/\alpha^2)\)	已关闭
线性回归（对抗污染）	\(O(d/\epsilon)\)	\(O(d/\epsilon^2)\)	\(\tilde{\Omega}(d/\epsilon^2)\)	已关闭
线性回归（Oblivious）	\(O(d/\alpha)\)	\(O(d/\alpha^2)\)	\(\tilde{\Omega}(d^{1/2}/\alpha^2)\)	部分关闭

本文的下界在 \(1/\alpha\) 的依赖上匹配已知上界（二次），但在 \(d\) 的依赖上存在 \(d^{1/2}\) vs \(d\) 的差距。

关键发现¶

\(1/\alpha^2\) 的二次依赖是本质的：不存在多项式时间SQ算法能以 \(O(d/\alpha^{2-\delta})\) 样本解决此问题
\(d\) 的依赖尚有差距：下界中的 \(d^{1/2}\) 弱于上界中的 \(d\)，关闭此差距是开放问题
Oblivious vs 对抗污染：尽管Oblivious模型比对抗污染更弱，但计算复杂性同样具有二次依赖

亮点与洞察¶

填补理论空白：Oblivious线性回归的信息-计算差距此前缺乏形式化证据，本文首次给出SQ下界
证明技术的创新：需要处理乘积结构（\(y = x^\top\beta + z\)）中的复杂依赖关系，比标准的均值估计下界证明更困难
问题的基础性：Oblivious污染是半参数统计中的经典模型，结果对更广泛的鲁棒估计问题有指导意义
清晰的开放问题：明确指出 \(d\) 依赖的差距为后续工作提供方向

局限与展望¶

\(d\) 依赖的差距：下界 \(d^{1/2}/\alpha^2\) vs 上界 \(d/\alpha^2\)，中间有 \(\sqrt{d}\) 的差距待关闭
SQ模型的局限性：SQ下界不排除非SQ类型算法（如基于SOS hierarchy）打破下界的可能
仅考虑高斯协变量：对于非高斯或亚高斯协变量，下界是否仍成立？
常数 \(\ell_2\) 误差：未给出恢复到 \(\epsilon\) 精度时的细粒度样本-误差权衡
理论结果缺乏数值验证实验

评分¶

新颖性：⭐⭐⭐⭐（首个Oblivious线性回归SQ下界）
技术深度：⭐⭐⭐⭐⭐（证明技术含量高）
实验充分度：⭐⭐⭐（纯理论，无数值验证）
实用性：⭐⭐（纯理论结果）
写作质量：⭐⭐⭐⭐