Computationally Efficient Replicable Learning of Parities and Applications¶

会议: NeurIPS 2026
arXiv: 2602.09499
OpenReview: https://openreview.net/forum?id=lJzvyZGkHM
论文: https://arxiv.org/abs/2602.09499
领域: 学习理论
关键词: 可复制性学习, 奇偶校验函数, 差分隐私, 统计查询模型, 稳定划分

一句话总结¶

提出了首个在任意数据分布下多项式时间可复制学习奇偶校验（Parities）函数的算法，打破了此前高效可复制学习局限于 SQ 可学习任务的壁垒，并证明了多项式时间内将可复制算法泛化转化为纯差分隐私算法必然损失样本复杂度。

研究背景与动机¶

算法稳定性（Algorithmic Stability）是现代可信机器学习与泛化理论的核心支柱，衍生出泛化界保证、差分隐私（Differential Privacy, DP）以及可复制性（Replicability）等诸多核心概念。在统计意义上，差分隐私与可复制学习已被证明是等价的，且二者均严格强于统计查询（Statistical Query, SQ）模型。然而在计算复杂性维度上，三者的能力边界长期模糊不清：虽然已知任意高效的 SQ 学习算法均可转化为高效的可复制学习算法，但在此前所有已知的高效（多项式时间）可复制算法，其求解范围要么严格受限于 SQ 可学习问题，要么依赖于均匀分布等强先验假设。

奇偶校验函数学习（Parity Learning）是理论计算机科学中区分统计与计算界限的试金石。经典结论表明，奇偶校验问题在 SQ 模型下是信息论/计算不可行的，但在纯差分隐私（Pure DP）下却存在多项式样本与多项式时间的高效算法。对于可复制学习而言，虽然在均匀分布下利用高斯消元法可以保证解的唯一性从而自然满足可复制性，但面对任意未知分布，常规线性代数方法（如高斯消元）由于极度脆弱的过拟合倾向——偶发采样的尾部稀疏样本会导致解空间的跨度剧烈跳变，从而彻底破坏独立运行输出一致性的要求。此前工作仅能在分布的决策树复杂度为常数时保持多项式运行，一般分布下高效可复制学习奇偶校验函数是否可行长期悬而未决。

面对任意未知分布带来的非稳定性屏障，本文的关键切入点在于将有监督奇偶校验问题转化为增广几何空间中高重数子空间的稳定识别。核心 idea：利用稳定划分（Stable Partition）将高维向量集合自适应贪心分解为嵌套独立子集链，借助均匀随机阈值过滤轻量级非稳定维度以构建可复制线性张成算法（RepLinearSpan），再通过正交补代数判定剔除矛盾标签并重构一致假设。

方法详解¶

整体框架¶

算法的整体目标是：给定任意未知分布 $\mathcal{D}$ 上独立采样的标记样本序列 $S=\{(x_i,y_i)\}_{i=1}^m \in (\mathbb{F}_2^d \times \mathbb{F}_2)^m$，在多项式时间内输出一个奇偶校验假设 $f_w(x)=\langle w, x\rangle$（或判定为不可实现并输出 $\bot$），要求在相同算法随机数 $r$ 下对两个独立数据集 $S_1, S_2 \sim \mathcal{D}^m$ 输出完全相同结果的概率至少为 $1-\rho$。

整体流程分为三个主要阶段： 1. 增广向量映射与稳定划分：将每个样本 $(x_i,y_i)$ 视作 $\mathbb{F}_2^{d+1}$ 中的向量 $v_i=(x_i,y_i)$。调用稳定划分（Stable Partition）子程序，贪心地将输入向量序列递归切分为线性无关子集族 $\mathcal{P}_S = \{A_1, \dots, A_M\}$，诱导出至多 $d+1$ 个严格嵌套的子空间链。 2. 重数估计与随机阈值截断（RepLinearSpan）：统计各划分块所张成子空间的重数 $n_S(V)$。在理论设定的最大上界区间 $(0, T_{\max}]$ 内均匀抽取随机阈值 $t$，保留所有满足 $n_S(V) \ge t$ 的“重子空间”，并选取其中维数最大的子空间作为最终可复制张成子空间 $U^*$。 3. 正交补代数相容性判定与解抽取：检查最后一个标准基向量 $e_{d+1}=(0,\dots,0,1)$ 是否落入 $U^*$。若落入则证明子空间中存在矛盾样本组合，算法确定性返回 $\bot$；否则过滤出落在 $U^*$ 内的一致子样本集 $S_{U^*}$，通过解齐次线性方程组在正交补中利用算法共享随机数均匀采样并输出 $w$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入样本集合<br/>S = {(x_i, y_i)} ∈ (F_2^d × F_2)^m"] --> B["阶段1：增广空间稳定划分<br/>向量映射至 F_2^{d+1} 并贪心切分子集族"]
    B --> C["阶段2：随机阈值重数过滤<br/>采样阈值 t 提取极大重子空间 U*"]
    C --> D{"代数相容性检测<br/>判断 e_{d+1} ∈ U* ?"}
    D -->|是：不可实现/标签矛盾| E["阶段3：可实现性验证与正交补解采样<br/>输出空符号 ⊥"]
    D -->|否：过滤子集 S_{U*}| F["阶段3：可实现性验证与正交补解采样<br/>正交补 C_{U*} 中均匀采样输出权重向量 w"]

关键设计¶

1. 增广空间稳定划分：打破常规数据独立划分的固有不稳定性

在任意未知分布下，固定大小或随机切分数据子集的方法存在根本缺陷：作者构造了最坏分布反例（Proposition 1），将标准基向量划分到具有指数级递减概率的若干块中，证明了常规子采样在任意样本量下两独立运行所得张成空间的对称差维数均以常数概率达到 $\Omega(\sqrt{d})$，两个空间完全相等的概率随 $\sqrt{d}$ 指数衰减。为克服该困难，算法引入了基于拟阵（Matroid）独立集思想的稳定划分技术。算法维护输入向量序列，迭代进行贪心扫描：在每一轮迭代中，贪心选取与当前子集保持线性无关的向量加入集合 $A_j$，直到无法再添加任何向量，随后将 $A_j$ 从序列中移除并开启下一轮。该算法天然生成至多 $d$ 个严格降序嵌套的子空间： $$V_1 \supseteq V_2 \supseteq \cdots \supseteq V_\ell \quad (\ell \le d)$$ 每个划分块的线性张成必严格等于这 $\ell$ 个子空间之一。更重要的是，该划分具备极低敏感度：修改单个样本时，任意子空间重数 $n_S(V)$ 的 $\ell_\infty$ 敏感度不超过 1，且在所有可能子空间上的 $\ell_1$ 敏感度之和不超过 2。

2. 随机阈值重数过滤：多样本偏差界与全局一致子空间提取

获得了重数统计 $n_S(V) := |\{j: \mathrm{span}(A_j) = V\}|$ 之后，关键挑战在于：差分隐私只需抵御单样本替换，而可复制性要求在两个完全独立重采样的样本集 $S_1, S_2 \sim \mathcal{D}^m$ 上保持输出一致。此时两个样本集在每个子空间上的重数偏差 $|n_{S_1}(V) - n_{S_2}(V)|$ 会随全体样本累积。本文建立了核心技术引理（Lemma 1）：结合 McDiarmid 不等式与对称化（Symmetrization）技术，借助 Efron-Stein 方差不等式将期望偏差约束到 $\ell_1$ 与 $\ell_\infty$ 敏感度的乘积上，证明了对任意分布均有： $$\Pr_{S_1, S_2 \sim \mathcal{D}^m}\left[\sup_{V \subseteq \mathbb{F}^d} |n_{S_1}(V) - n_{S_2}(V)| \ge 3\sqrt{m\ln(1/\delta)}\right] \le \delta$$ 算法在区间 $(0, T_{\max}]$ 内均匀抽取随机阈值 $t$（其中 $T_{\max} = \frac{12d}{\rho}\sqrt{m\log(2/\rho)}$）。由于所有出现的非零重数候选子空间总数不超过 $2d$，只要阈值 $t$ 不落入任何一个子空间的重数漂移间隙 $[n_{S_1}(V), n_{S_2}(V)]$ 中，两轮独立执行所判定的重子空间集合 $\mathcal{P}_{\text{heavy}} := \{V: n_S(V) \ge t\}$ 就会完全相同。在保证两运行提取相同重子空间集合的前提下，取维数最大的子空间 $V^* = \arg\max_{V \in \mathcal{P}_{\text{heavy}}} \dim(V)$。根据嵌套结构，所有未被 $V^*$ 覆盖的向量必属于维数更高的子空间，其重数均小于 $t \le T_{\max}$，由此严格推导出未覆盖样本比例不超过 $\varepsilon$。

3. 可实现性代数判定与正交补解采样：消除非可实现分布下的不可控随机漂移

标准 PAC 学习仅要求在可实现分布上保证低泛化误差，但可复制性定义具有普遍量词（Universally quantified over distributions），要求在任意分布（包括标签充满对抗性噪声的非可实现分布）下两独立执行依然必须输出相同假设。为解决这一难题，算法将标记对 $(x_i,y_i)$ 视作 $\mathbb{F}_2^{d+1}$ 中的向量并送入 RepLinearSpan 得到子空间 $U^*$。论文给出了精妙的代数特征充要条件（Claim 3）：样本集在奇偶校验函数类下可实现，当且仅当最后一个坐标的标准基向量 $e_{d+1} = (0,\dots,0,1)$ 不属于样本集的线性张成。由此，算法直接检验 $e_{d+1} \in U^*$ 是否成立。若成立，两独立执行因 $U^*$ 的可复制性而同时确定性返回 $\bot$；若不成立，则过滤出 $S_{U^*} = S \cap U^*$，根据代数对偶理论，所有满足方程组 $\langle w, x_i\rangle = y_i$ 的解集精确等价于正交补中的仿射切片： $$C_{U^*} = \{w \in \mathbb{F}_2^d : (w,1) \in (U^*)^\perp\}$$ 由于两轮执行得到的 $U^*$ 高概率完全相同，解空间 $C_{U^*}$ 亦完全恒等。算法利用共享的伪随机种子在非空有限集合 $C_{U^*}$ 中均匀采样唯一的解 $w$，彻底规避了高斯消元在欠定自由元选择上的不一致性。

实验关键数据¶

主实验¶

论文在附录 E 中对所提出的可复制奇偶校验学习器（Replicable Parity Learner）与经典的经验风险最小化高斯消元法（Naive ERM via Gaussian Elimination）在偏置非均匀分布下进行了对比评测。实验设定问题维度 $d=20$，目标可复制性失效率 $\rho=0.05$（即目标可复制率 95%），测试集包含 5000 个样本。采用 Proposition 1 的指数衰减偏置分布 $\mathcal{D}(e_i) = 2^{-i}$（$1 \le i \le d$，其余质量赋给零向量），在不同样本量 $m \in [50, 1000]$ 下进行 100 次独立双运行比对实验。

算法	样本量 $m$	测试泛化准确率 (%)	经验可复制率 (%)	理论运行时间界	适用分布范围
Gaussian Elimination (ERM)	100	~99.8	~22.0	$O(md^2)$	仅限均匀分布保证可复制
Gaussian Elimination (ERM)	400	~100.0	~25.5	$O(md^2)$	仅限均匀分布保证可复制
Gaussian Elimination (ERM)	1000	100.0	28.0 ± 4.5	$O(md^2)$	仅限均匀分布保证可复制
Replicable Learner (本文)	100	~62.0	~70.0	$O(m^2 d^3)$	任意未知分布
Replicable Learner (本文)	400	~78.5	~85.0	$O(m^2 d^3)$	任意未知分布
Replicable Learner (本文)	1000	88.0 ± 3.2	90.0 ± 3.0	$O(m^2 d^3)$	任意未知分布

消融与理论下界分离分析¶

为了展示理论复杂度以及各个稳定性机制在转化过程中的损失，论文深入对比了奇偶校验学习任务在经典 PAC、SQ 模型、纯差分隐私（Pure DP）、近似差分隐私（Approx DP）以及可复制学习（Replicable Learning）下的计算与样本复杂度特性。

学习框架 / 算法模型	样本复杂度关于 $\delta$ 的依赖	样本复杂度关于 $d$ 的依赖	计算效率 (任意分布)	SQ 困难性突破
经典 PAC (无稳定性限制)	$O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$	$O(d)$	多项式时间 $O(md^2)$	否 (直接访问样本)
统计查询模型 (SQ)	N/A (查询容差 $\tau$)	$2^{\Omega(d)}$ (查询复杂度)	指数级下界	无法学习
纯差分隐私 (Pure $\alpha$-DP, Kasiviswanathan et al.)	$O(\frac{d}{\alpha \varepsilon}\log\frac{1}{\delta})$	$O(d)$	多项式时间	是
纯差分隐私多项式下界 (Georgiev & Hopkins, 假设 $\text{RP}\neq\text{NP}$)	$\omega(\frac{1}{\alpha \varepsilon}\log\frac{1}{\delta})$	无法消除对 $d$ 依赖	无法达到最优对数置信度	是
可复制学习 (本文算法)	$O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$ (可加项)	$O(d^6)$	多项式时间 $O(m^2 d^3)$	是 (首个突破 SQ 限制)

关键发现¶

高斯消元的可复制性坍塌：在非均匀分布下，高斯消元法贪心拟合样本中偶发的低频基向量，导致求解出的线性流形剧烈波动，两轮独立采样的输出重合率始终停留在 20%~30% 的低谷，随着样本量增长并无实质收敛；而本文算法通过截断轻量级子空间，经验可复制率稳步提升至 90% 左右。
准确率与稳定性的内在权衡：可复制学习器为了保证输出不变，主动放弃了覆盖发生概率极低的长尾基向量，因而在 $m=1000$ 时测试准确率约为 88%，表现出清晰的“稳定性-精度”权衡（Trade-off）。
向纯 DP 转化的下界不可行性：本文算法在失败概率 $\delta$ 上实现了最优的加性对数依赖 $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$；而在假设 $\text{RP} \neq \text{NP}$ 下，任何高效纯 DP 奇偶校验学习算法在 $\delta$ 上的依赖严格为 $\omega(\frac{1}{\alpha \varepsilon}\log\frac{1}{\delta})$。这直接证明了不存在任意保持样本依赖的高效通用转化子程序将可复制算法转化为纯差分隐私算法。

亮点与洞察¶

突破 SQ 模型的计算壁垒：首次给出了在任意未知分布下多项式时间可复制学习 SQ 难问题的正向结果，确立了高效可复制学习在计算能力上严格超越高效统计查询学习。
全局重数偏差的 Efron-Stein 对称化界：将原本用于分析单样本敏感度的稳定划分技术，通过 McDiarmid 与 Efron-Stein 方差不等式的耦合推广至两个全新重采样数据集之间，成功给出了 $O(\sqrt{m \log(1/\delta)})$ 的极值上界，为后续算法设计提供了通用的代数工具。
正交补一致采样设计：巧妙利用代数对偶将一致解集转化为仿射子空间切片 $C_{U^*} = \{w : (w,1) \in (U^*)^\perp\}$，不仅使得验证条件化为单向量属于性判定 $e_{d+1} \in U^*$，更使得解空间的均匀采样完全由共享伪随机数驱动，无需任何启发式消元规则。

局限与展望¶

样本复杂度的高阶多项式依赖：算法在维度 $d$ 上的样本复杂度为 $O(d^6 / (\rho^2 \varepsilon^2))$，计算复杂度为 $O(m^2 d^3)$，在超高维场景下的实际落地仍面临较大的计算与样本开销。
局限于可实现性设置（Realizable Setting）：由于不可知（Agnostic）奇偶校验学习本身是 NP-hard 的，且在带随机噪声（LPN）下的学习被广泛视作具有密码学硬度，本文结果严格受限于可实现样本。
后续优化方向：探索是否可以通过更紧致的拟阵剖分性质将样本复杂度的维度指数从 $d^6$ 缩减至近线性或平方阶，并将类似技术推广到带限噪声分类或更广义的环/有限域代数学习任务。

评分¶

新颖性: ⭐⭐⭐⭐⭐ (首次解决任意分布下高效可复制学习奇偶校验的公开难题，建立了可复制性与 SQ/DP 间的计算分离)
实验充分度: ⭐⭐⭐⭐☆ (理论推导严密完备，附录提供了清晰的数值仿真验证，若能在更广泛的高维任务或实际衍生应用上展开更大规模验证则更佳)
写作质量: ⭐⭐⭐⭐⭐ (技术论证层层递进，代数动机与集中不等式证明阐述严谨清晰)
价值: ⭐⭐⭐⭐⭐ (对学习理论中的稳定性动物园提供了关键的计算复杂性拼图，深化了可复制性与差分隐私的本质联系)

学习框架 / 算法模型	样本复杂度关于 \(\delta\) 的依赖	样本复杂度关于 \(d\) 的依赖	计算效率 (任意分布)	SQ 困难性突破
经典 PAC (无稳定性限制)	\(O(\frac{1}{\varepsilon}\log\frac{1}{\delta})\)	\(O(d)\)	多项式时间 \(O(md^2)\)	否 (直接访问样本)
统计查询模型 (SQ)	N/A (查询容差 \(\tau\))	\(2^{\Omega(d)}\) (查询复杂度)	指数级下界	无法学习
纯差分隐私 (Pure \(\alpha\)-DP, Kasiviswanathan et al.)	\(O(\frac{d}{\alpha \varepsilon}\log\frac{1}{\delta})\)	\(O(d)\)	多项式时间	是
纯差分隐私多项式下界 (Georgiev & Hopkins, 假设 \(\text{RP}\neq\text{NP}\))	\(\omega(\frac{1}{\alpha \varepsilon}\log\frac{1}{\delta})\)	无法消除对 \(d\) 依赖	无法达到最优对数置信度	是
可复制学习 (本文算法)	\(O(\frac{1}{\varepsilon}\log\frac{1}{\delta})\) (可加项)	\(O(d^6)\)	多项式时间 \(O(m^2 d^3)\)	是 (首个突破 SQ 限制)