Testable Learning of General Halfspaces under Massart Noise¶

会议: NeurIPS 2026
arXiv: 2602.22300
OpenReview: https://openreview.net/forum?id=IJ6BI72Ruf
领域: 其他
关键词: 可检验学习, 半空间, Massart噪声, 乘性多项式逼近, 统计查询下界

一句话总结¶

针对高斯边际分布与半随机 Massart 标签噪声下的非齐次通用半空间学习，提出了首个复杂度定性匹配非检验 SQ 下界 $d^{\mathrm{polylog}(\min\{1/\gamma,1/\epsilon\})}$ 的可检验学习器，核心依赖全新的符号函数乘性夹逼多项式逼近理论。

研究背景与动机¶

从带噪声样本中高效学习半空间是计算学习理论与统计学习中最基础的课题之一。在无噪声 PAC 模型中半空间可通过线性规划等多项式时间算法学习，但一旦引入标签噪声（如对抗性噪声或半随机 Massart 噪声），分布无关设置下的计算难度便会急剧上升。为了突破硬度瓶颈，大量理论工作聚焦于高斯等结构化边际分布下的抗噪学习。然而，传统分布特异性学习算法存在一个根本性缺陷：当实际数据分布违背底层假设（如边际高斯性或特定的 Massart 噪声条件）时，学习器往往无法给出任何有效保障，甚至可能输出无意义的伪解。

这种局限性催生了可检验学习（Testable Learning）框架：设计一个检验器-学习器对（Tester-Learner pair），当检验器接受（Accept）时，学习器必须输出一个带有近似最优误差保证的假设 $h$；若底层联合分布严格满足设定的分布假设，检验器必须以高概率接受。近期工作已解决了齐次（通过原点）半空间在 Massart 噪声下的可检验学习，然而在无检验的经典学习理论中，从齐次半空间走向带阈值的通用非齐次半空间（General Halfspaces）存在本质的计算复杂度阶跃——非齐次情形已知存在 $d^{\Omega(\log(1/\epsilon))}$ 的统计查询（SQ）下界，且此前的检验技术仅能达到加性逼近误差 $O(1/\epsilon^2)$，导致在极度不平衡或小偏置切片上完全失效。

通用非齐次半空间在不同正交切片上的条件偏差极不均衡，传统的加性夹逼多项式逼近会导致在微小概率区域的逼近误差压倒真实信号。核心 idea：将空间沿候选半空间法向量精细切片，通过正交矩匹配与非负平方和多项式检验逐片认证对抗优势，并利用全新构建的切比雪夫多项式乘性夹逼理论控制极端偏置切片的逼近误差。

方法详解¶

整体框架¶

算法首先在给定的标记样本集上调用非检验 Massart 弱学习子程序得到一个候选半空间 $h(\mathbf{x})=\mathrm{sign}(\mathbf{w}\cdot\mathbf{x}-t)$，随后在沿候选法向 $\mathbf{w}$ 划分的一系列窄切片上执行三重验证：(1) 切片概率质量检验（Slice Mass Test），(2) 正交方向高斯矩匹配检验（Orthogonal Moment Matching Test），以及 (3) 基于截断 Hermite 多项式的半正定平方和非负性检验（Non-negativity Certificate）。

整个可检验学习器的判定流程图如下所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入分布样本 D<br/>(x, y) ~ D"] --> B["阶段1：候选半空间生成<br/>调用非检验学习器获得 h(x)=sign(w·x-t)"]
    B --> C["阶段2：法向正交切片划分<br/>沿 w 方向划分为宽度 Δ 的窄切片 S_i"]
    C --> D["阶段3：切片质量检验<br/>验证经验切片质量与高斯质量偏差 ≤ τ_p"]
    D -->|未通过| R["拒绝 (Reject)"]
    D -->|通过| E["阶段4：正交高斯矩匹配检验<br/>在 w^⟂ 空间验证 l 阶 Hermite 矩偏差 ≤ τ_m"]
    E -->|未通过| R
    E -->|通过| F["阶段5：半正定非负性证书检验<br/>检验经验矩阵 M_hat ⪰ 0 认证期望优势"]
    F -->|未通过| R
    F -->|通过| G["接受并输出假说 (Accept, h)"]

关键设计¶

1. 空间正交切片分解与逐片优势认证：消除阈值耦合带来的多半空间交集逼近难题

直接在全空间验证候选半空间 $h$ 对任意竞争半空间 $f$ 的优势，等价于对二者的分歧区域 $\mathbb{I}(f(\mathbf{x})\neq h(\mathbf{x}))$ 进行多项式拟合，但这构成了两个半空间的交集，需要极高次数的多项式。算法采用几何正交切片思想，沿法向 $\mathbf{w}$ 将 $\mathbb{R}^d$ 划分为宽度为 $\Delta=\epsilon^2$ 的切片 $S_i$。在每一个非尾部切片内，$h(\mathbf{x})$ 保持恒定符号，此时分歧区域退化为在正交子空间 $\mathbf{w}^\perp$ 上的单个半空间。通过这种方式，算法将全局多元交集逼近问题降维为在每个切片内的单个线性阈值函数（LTF）的逼近问题，极大降低了所需的多项式阶数。

2. 乘性夹逼多项式逼近（Multiplicative Sandwiching Polynomials）：攻克大阈值偏置下的指数级误差衰减

在非齐次情形下，竞争半空间 $f$ 在切片 $S_i$ 上诱导的截距 $s(\mathbf{w}\cdot\mathbf{x})$ 可高达 $\Theta(\sqrt{\log(1/\gamma)})$。若使用经典文献中的加性夹逼多项式，误差界形如 $\mathbb{E}[p_+ - p_-] \le \epsilon_{\mathrm{add}}$，要达到低于目标分歧质量的精度需要多项式次数高达 $\Omega(1/\gamma^2)$，导致指数级样本复杂度。本工作利用奇数阶切比雪夫多项式 $T_m(x)$ 构建显式的高次幂“凹凸”多项式核，通过与区间卷积构造出满足乘性误差保证的多项式对 $p_-, p_+$： $$p_-(x) \leq \mathbb{I}(x \geq t) \leq p_+(x), \quad \mathbb{E}_{x\sim\mathcal{N}(0,1)}[p_+(x) - p_-(x)] \leq \alpha\,\mathbb{E}_{x\sim\mathcal{N}(0,1)}[\mathbb{I}(x \geq t)]$$ 其所需多项式次数仅为 $\deg(p_\pm) = O((|t|+1)^6 \log^2(1/\alpha)/\alpha^2)$。这一多项式逼近结果保证了在任何偏置水平下，逼近误差始终与真实分歧质量成固定比例，成功将全局复杂度压低至拟多项式阶。

3. 半正定矩阵非负性测试与矩匹配联立：利用平方和证书防范对抗噪声欺骗

为在未知且可能对抗的数据分布 $D$ 上保证学习器的有效性，算法在正交基 $\mathbf{U} \in \mathbb{R}^{d\times(d-1)}$ 上构建总次数至多为 $l$ 的多元 Hermite 多项式向量 $H(\mathbf{U}^\top \mathbf{x})$。在每个切片内，算法构造经验相关矩阵： $$\widehat{\mathbf{M}} \coloneqq \mathbb{E}_{(\mathbf{x},y)\sim\widehat{D}}\left[H(\mathbf{U}^\top\mathbf{x})H^\top(\mathbf{U}^\top\mathbf{x}) (y h(\mathbf{x}) - \beta + \epsilon) \mid \mathbf{x}\in S\right]$$ 若 $\widehat{\mathbf{M}} \succeq \mathbf{0}$，则对于任意低度多项式 $q$，必有 $\mathbb{E}[(q(\mathbf{U}^\top\mathbf{x}))^2 (y h(\mathbf{x}) - \beta + \epsilon)\mid S] \ge 0$。由于一元正多项式必然是平方和（SOS），因此正的夹逼多项式 $p_+^{(2)}$ 自然满足该非负条件。结合切片内 $l$ 阶矩匹配 $|\widehat{m}_{\alpha,S} - \mathbb{E}_{\mathcal{N}^d}[He_\alpha]| \le \tau_m$，学习器成功将多项式期望从经验分布转移到高斯分布，从而数学上严格闭合了对任意竞争半空间 $f$ 的优势认证链条。

损失函数 / 训练策略¶

算法是严格的有限步检验组合策略，无需梯度反向传播。首先设定噪声偏置 $\beta = 1 - 2\eta$ 及偏置下界 $\gamma \leftarrow \max(\gamma, \epsilon)$。多项式最高次数设为 $l = C \log^3(1/\gamma) \log^2(1/\beta)/\beta^2$，切片间距 $\Delta = \epsilon^2$，矩容差与质量容差均设定为 $\tau_m = \tau_p = \epsilon^C / d^l$。算法在抽取的 $N = d^{\tilde{O}(\beta^{-2})\mathrm{polylog}(\min\{1/\epsilon,1/\gamma\})}\mathrm{poly}(1/\epsilon)\log(1/\delta)$ 个样本上，计算各切片样本均值与经验矩阵特征值，若任意切片不满足半正定性或矩偏差超标，则立即中断并输出 Reject；若所有切片全部通过，则以至少 $1-\delta$ 的置信度 Accept 并交付 $h$。

实验关键数据¶

主实验¶

本文是一篇纯理论机器学习论文，核心贡献通过严格的数学定理与计算复杂度上界给出。下表对比了半空间学习在不同噪声与检验设定下的复杂度理论极限：

设定与概念类	边际分布假设	噪声类型	算法模式	计算与样本复杂度
齐次半空间 ($\gamma=1/2$)	标准高斯分布	$\eta$-Massart	非检验 (Non-testable)	$\mathrm{poly}(d/\epsilon)$
齐次半空间 ($\gamma=1/2$)	标准高斯分布	$\eta$-Massart	可检验 (Testable)	$(d/\epsilon)^{\mathrm{poly}(1/\beta)}$
通用半空间 ($\gamma$-Biased)	标准高斯分布	无噪声 (Realizable)	可检验 (Testable)	$\mathrm{poly}(d, 1/\epsilon)$
通用半空间 ($\gamma$-Biased)	标准高斯分布	对抗噪声 (Agnostic)	可检验 (Testable)	$d^{O(1/\epsilon^2)}$
通用半空间 ($\gamma$-Biased)	标准高斯分布	$\eta$-Massart	非检验 (Non-testable)	$d^{O(\log(\min\{1/\gamma, 1/\epsilon\}))}\mathrm{poly}(1/\epsilon)$
本文 (Theorem 1.4)	标准高斯分布	$\eta$-Massart	可检验 (Testable)	$d^{\tilde{O}(\beta^{-2})\mathrm{polylog}(\min\{1/\gamma, 1/\epsilon\})}\mathrm{poly}(1/\epsilon)$

消融实验¶

为论证各组件与下界关系的紧密性，下表对检验器各模块策略及多项式阶数假设进行理论消融与性质对比：

逼近/检验策略配置	多项式次数 $\deg(p)$	判定优势类型	偏置切片适应性	样本复杂度阶数	说明
经典加性夹逼 (Additive)	$\Theta(1/\gamma^2)$	加性界 $\pm \epsilon$	差 (偏置 $\gamma$ 极小时失效)	$d^{\Omega(1/\gamma^2)}$	退化至不可行的指数级复杂度
软化+泰勒展开 (Mollifier)	无法收敛	局部高斯尾部发散	极差 (原点附近误差 $\gg e^{-t}$)	无法获得保证	经典光顺卷积因高斯权发散失效
本文切比雪夫乘性夹逼	$O(\frac{(t+1)^6 \log^2(1/\alpha)}{\alpha^2})$	相对乘性界 $\alpha \mathbb{E}[g]$	极佳 (自动匹配高斯衰减率)	$d^{\tilde{O}(\beta^{-2})\mathrm{polylog}(1/\gamma)}$	首创拟多项式阶乘性逼近
猜想最优乘性逼近	猜想 $\Theta(t^2)$	相对乘性界 $\alpha \mathbb{E}[g]$	极佳	$d^{O_\beta(\log(\min\{1/\epsilon,1/\gamma\}))}$	理论上可完全匹配非检验 SQ 界

关键发现¶

拟多项式阶具有内禀必然性：根据文章 Appendix E 建立的统计查询（SQ）下界，任何在检验设定下学习偏置 Massart 半空间的算法都至少需要 $d^{\tilde{\Omega}(\beta^{-2})}$ 的复杂度；在非检验设定下也必须承受 $d^{\Omega(\log(1/\epsilon))}$，这表明本文所获拟多项式上界在阶数上是本原且定性匹配的。
未知偏置自适应性（Bias-Agnostic）：传统非检验学习器必须事先获知目标半空间的偏置参数 $\gamma$，否则复杂度恶化；结合本文的检验器后，可通过网格搜索结合可检验认证，实现对未知偏置 $\gamma$ 的全自适应学习。

亮点与洞察¶

显式切比雪夫乘性核构造：突破了逼近论中利用光滑核软化（mollifier）无法兼顾高斯测度尾部指数衰减的死穴，首次利用切比雪夫多项式与幂运算构造出显式的乘性单边逼近。
切片降维与 SOS 证书耦合：将全空间交集逼近巧妙退化为一维+正交切片结构，结合平方和非负多项式直接检验标签内积，开辟了半随机分布测试的新分析范式。

局限与展望¶

高斯边际假设依赖：当前矩匹配与 Hermite 多项式正交性深度绑定标准高斯边际，推广至对数凹（log-concave）或仿射变换分布仍面临严峻的代数障碍。
多项式次数与下界的对数多项式差距：目前多项式次数为 $O(t^6)$，导致指数上含有 $\mathrm{polylog}$ 因子，未能完全达到猜想的 $\Theta(t^2)$ 及精确的 $O(\log(1/\epsilon))$。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出符号函数的乘性夹逼多项式逼近理论并成功解决通用半空间可检验学习难题。
实验充分度: ⭐⭐⭐⭐ 纯理论工作，完备证明了 Soundness 与 Completeness 并给出了严丝合缝的 SQ 下界。
写作质量: ⭐⭐⭐⭐⭐ 概念动机脉络清晰，几何直觉与代数推导组织严整。
价值: ⭐⭐⭐⭐⭐ 推动了可靠机器学习与可检验学习理论从齐次原型走向通用半空间的重要里程碑。

设定与概念类	边际分布假设	噪声类型	算法模式	计算与样本复杂度
齐次半空间 (\(\gamma=1/2\))	标准高斯分布	\(\eta\)-Massart	非检验 (Non-testable)	\(\mathrm{poly}(d/\epsilon)\)
齐次半空间 (\(\gamma=1/2\))	标准高斯分布	\(\eta\)-Massart	可检验 (Testable)	\((d/\epsilon)^{\mathrm{poly}(1/\beta)}\)
通用半空间 (\(\gamma\)-Biased)	标准高斯分布	无噪声 (Realizable)	可检验 (Testable)	\(\mathrm{poly}(d, 1/\epsilon)\)
通用半空间 (\(\gamma\)-Biased)	标准高斯分布	对抗噪声 (Agnostic)	可检验 (Testable)	\(d^{O(1/\epsilon^2)}\)
通用半空间 (\(\gamma\)-Biased)	标准高斯分布	\(\eta\)-Massart	非检验 (Non-testable)	\(d^{O(\log(\min\{1/\gamma, 1/\epsilon\}))}\mathrm{poly}(1/\epsilon)\)
本文 (Theorem 1.4)	标准高斯分布	\(\eta\)-Massart	可检验 (Testable)	\(d^{\tilde{O}(\beta^{-2})\mathrm{polylog}(\min\{1/\gamma, 1/\epsilon\})}\mathrm{poly}(1/\epsilon)\)

逼近/检验策略配置	多项式次数 \(\deg(p)\)	判定优势类型	偏置切片适应性	样本复杂度阶数	说明
经典加性夹逼 (Additive)	\(\Theta(1/\gamma^2)\)	加性界 \(\pm \epsilon\)	差 (偏置 \(\gamma\) 极小时失效)	\(d^{\Omega(1/\gamma^2)}\)	退化至不可行的指数级复杂度
软化+泰勒展开 (Mollifier)	无法收敛	局部高斯尾部发散	极差 (原点附近误差 \(\gg e^{-t}\))	无法获得保证	经典光顺卷积因高斯权发散失效
本文切比雪夫乘性夹逼	\(O(\frac{(t+1)^6 \log^2(1/\alpha)}{\alpha^2})\)	相对乘性界 \(\alpha \mathbb{E}[g]\)	极佳 (自动匹配高斯衰减率)	\(d^{\tilde{O}(\beta^{-2})\mathrm{polylog}(1/\gamma)}\)	首创拟多项式阶乘性逼近
猜想最优乘性逼近	猜想 \(\Theta(t^2)\)	相对乘性界 \(\alpha \mathbb{E}[g]\)	极佳	\(d^{O_\beta(\log(\min\{1/\epsilon,1/\gamma\}))}\)	理论上可完全匹配非检验 SQ 界