High-Arity Sample Compression¶

会议: NeurIPS 2026
arXiv: 2605.12465
领域: 学习理论
关键词: 样本压缩方案、高元学习理论、PAC可学习性、鞅差序列、Azuma不等式

一句话总结¶

本文将经典学习理论中的样本压缩方案推广至笛卡尔积空间上的高元学习设置（含分部与非分部两种范式），证明了存在次线性压缩方案即可通过构造 Doob 鞅与 Azuma 集中不等式严格推导出高元 PAC 可学习性，并给出了明确的样本复杂度上界。

研究背景与动机¶

在经典统计学习理论中，样本压缩方案（Sample Compression Schemes）与 PAC 可学习性、有限 VC 维之间存在深刻的等价关系。经典理论指出，若一个概念类存在非平凡的样本压缩方案（即只需选取大小为 $o(m)$ 的子样本辅以少量额外信息即可精确重构原标签），则该类不仅是 PAC 可学习的，而且压缩规模能进一步通过 Boosting 压缩到 $O(\ln m \cdot \ln \ln m)$。这一等价闭环构成了基于数据驱动假设压缩的统计泛化基石。

然而，随着高元学习理论（High-Arity Learning Theory）的发展，学习问题被置于乘积空间 $X_1 \times \cdots \times X_k$ 之上，所学习的目标是高阶张量或超图上的多元关系而非单个样本点。在此结构下，数据点以各个坐标轴的边缘分布独立采样后组合而成，导致网格上的 $m^k$ 个 $k$ 元组标签天然具备强烈的代数与几何相关性，彼此不再独立同分布（non-i.i.d.）。传统依赖于 Chernoff、Bernstein 等独立和集中不等式的泛化分析工具在多维网格结构前彻底失效，高维张量切片诱导的组合复杂度也使得经典样本压缩的收敛性分析无法直接搬移。

面对标签强相关性带来的统计障碍，高元理论亟需回答：高元样本压缩是否依然足以保证高元 PAC 泛化？本文切入的角度在于，尽管高元组标签全局纠缠，但若沿各个输入坐标的样本点暴露过程逐步建立信息过滤，依然可以精确控制单点扰动对经验风险的边际影响。核心 idea：通过针对分部与非分部乘积空间分别建立两套高元样本压缩与重构范式，构造坐标轴逐步展开的 Doob 鞅差序列，并利用 Azuma-Hoeffding 不等式克服非独立标签相关性，严格证明非平凡高元压缩方案能够蕴涵高元 PAC 可学习性，且样本复杂度直接受控于压缩子集规模与头部信息量。

方法详解¶

整体框架¶

本文构建了一套完备的高元选择与压缩架构，分别涵盖分部（Partite）与非分部（Non-partite）设置。在分部设置中，算法面对 $k$ 个不同的样本空间 $X_1, \ldots, X_k$，从各自边缘分布 $\mu_i$ 抽取 $m$ 个样本后形成 $m^k$ 个标签网格；在非分部设置中，各坐标空间相同且分布一致，学习算法只观测单一样本集在无重复元组（injective tuples）上的标签。整体机制包括输入网格的样本索引选择、辅助重构头部信息提取、基于压缩核的假设重构，以及通过 Doob 鞅进行真假风险偏差控制。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: k 元高阶样本网格<br/>分部 m^k 或非分部 (m)_k 标签"] --> B["高元样本选择机制<br/>提取子样本索引与额外头部信息"]
    B --> C["高元假设重构映射<br/>压缩核解码生成全局假设 H"]
    C --> D["坐标轴展开 Doob 鞅分析<br/>逐步暴露单点变量控制鞅差有界性"]
    D --> E["Azuma 集中收敛界推导<br/>消解非 i.i.d. 标签网格相关性"]
    E --> F["输出: PAC 泛化误差界<br/>证明高元 PAC 可学习性成立"]

关键设计¶

1. 分部与非分部高元样本压缩方案：解耦网格点索引与额外头部信息

经典样本压缩仅需在 $m$ 个样本中挑选 $s_m$ 个点；而高元压缩需要处理多元关系。在 $k$ 分部设置中，选择映射 $\sigma_m$ 在每个坐标分量上各自挑出长度为 $s_m$ 的下标置换向量，即 $\sigma_m(x, y) \in \prod_{i=1}^k ([m])_{s_m}$，同时头部映射 $\eta_m$ 输出离散辅助信息 $\eta_m(x, y) \in [h_m]$。在非分部设置中，样本属于单一域 $X$，此时 $\sigma_m \in ([m])_{s_m}$ 挑选公共样本索引，并且需要引入对 $k$ 元子集排列方式的定向映射（order choice）以消除无序性。无论哪种设置，压缩过程将原本规模巨大的多维张量数据紧缩为子样本 $(\sigma^\#(x), \sigma^\#(y))$ 与标头 $\eta$。重构映射 $\rho_m$ 随后利用这些紧缩信息输出一个属于假设空间 $\mathcal{H}'$ 的预测函数 $H$，并在可实现性假设下实现对原样本网格的经验零损失（Zero Empirical Loss）： $$L_{x, y, \ell}\left(\rho_m(\kappa_m(x, y))\right) = 0$$ 当有限标签集 $|Y|$ 时，压缩位长 $b_{\mathcal{S}}(m) = \log_2(h_m \cdot |Y|^{s_m^k})$ 或 $h_m \cdot |Y|^{(s_m)_k}$ 刻画了算法对原数据集的有效信息抽取率。

2. 坐标逐点过滤的 Doob 鞅构造：驯服网格标签依赖性

高元样本网格的根本难点在于标签 $y_\alpha = F(x_{\alpha_1}^1, \ldots, x_{\alpha_k}^k)$ 相互缠绕：同一采样点 $x_v^i$ 参与了多达 $m^{k-1}$ 个 $k$ 元组的取值判定，打破了经典学习理论中样本对之间互相独立的先决条件。为解决这一难题，本文将样本分为用于压缩提取的子样本（不妨对称设为最后 $s_m$ 个点）和剩余未被压缩的 $n = m - s_m$ 个自由样本点。在未被压缩的自由点构成的子网格上，令假设 $H = \rho_m(\sigma^\#(x, y), \eta)$，它是纯粹由压缩子集决定的可测函数。为了追踪 $H$ 在未见样本上的经验风险向真实泛化风险 $L_{\mu, F, \ell}(H)$ 的收敛性，本文设计了沿坐标轴单步逐步展开的滤子序列 $(\mathcal{F}_t)$。以分部设置为例，总步长为 $k \cdot n$ 步，每一步暴露且仅暴露一个单点变量 $(x_{i_t})_{v_t}$，构造条件期望 Doob 鞅： $$Z_t = \mathbb{E}\left[L_{x', F_n^*(x'), \ell}(H) \;\middle|\; \mathcal{F}_t\right], \quad t = 0, 1, \ldots, k \cdot n$$ 其中起点 $Z_0 = L_{\mu, F, \ell}(H)$ 正是全分布期望泛化损失，终点 $Z_{k \cdot n} = L_{x', F_n^*(x'), \ell}(H)$ 为自由网格上的经验损失。

3. 鞅差有界性与 Azuma 集中不等式：突破经典独立性限制

在建立 Doob 鞅后，必须对步进鞅差 $|Z_t - Z_{t-1}|$ 的最坏跳变幅度进行严格限制。考虑第 $t$ 步揭示样本点 $(x_{i_t})_{v_t}$ 时，在由 $n^k$ 个元组构成的总损失求和项中，只要一个多维坐标 $\alpha \in [n]^k$ 满足 $\alpha_{i_t} \neq v_t$，其对应的损失项由于与当前新变量条件独立，在做条件期望差分时便完全抵消为零。在全部 $n^k$ 个元组中，包含该指定点 $(x_{i_t})_{v_t}$ 的元组数目恰好只有 $n^{k-1}$ 个。利用损失函数的有界性 $\|\ell\|_\infty < \infty$，差分幅度被严格截断： $$|Z_t - Z_{t-1}| \leq \frac{n^{k-1}}{n^k} \|\ell\|_\infty = \frac{\|\ell\|_\infty}{n}$$ 这一极为对称而紧凑的有界性使得 Azuma-Hoeffding 不等式得以施展。通过累加 $k \cdot n$ 个差分项平方和： $$\sum_{t=1}^{k \cdot n} \left(\frac{\|\ell\|_\infty}{n}\right)^2 = \frac{k \cdot \|\ell\|_\infty^2}{n}$$ 最终得到的集中概率上界呈现为形如 $\exp\left(-\frac{\widetilde{\varepsilon}^2 \cdot (m - s_m)}{2 k \|\ell\|_\infty^2}\right)$ 的指数衰减衰减形式。这一机制不仅在非分部设置下同样成立（差分界为 $\frac{k}{n}\|\ell\|_\infty$，步长为 $n$），而且彻底绕开了对标签独立性的依赖。

损失函数 / 训练策略¶

在学习范式设定上，对于分部高元问题，损失函数定义为 $\ell: (\prod_{i=1}^k X_i) \times Y \times Y \to \mathbb{R}_{\geq 0}$；非分部问题则需对全置换对称群 $S_k$ 上的预测结果进行联合惩罚，形式为 $\ell: X^k \times Y^{S_k} \times Y^{S_k} \to \mathbb{R}_{\geq 0}$。若压缩方案的规模满足非平凡条件： $$\ln(h_m^{\mathcal{S}}) + k \cdot s_m^{\mathcal{S}} \cdot \ln(m) \leq o(m)$$ 通过对所有可能的子样本选取方式（共 $(m)_{s_m}^k$ 种单射组合）和所有可能的头部信息 $h_m$ 应用联合界（Union Bound），整体失败概率被严格控制在 $\delta$ 之内，从而给出高元学习算法 $\mathcal{A}(x, y) = \rho_m(\kappa_m(x, y))$ 达到误差 $\varepsilon$ 所需的充分样本复杂度。

实验关键数据¶

主实验¶

作为纯理论学习理论研究，本文的核心结论在于推导出两套设定下非平凡样本压缩导出 PAC 可学习性的精确样本复杂度解析界（Sample Complexity Bounds）。下表总结了分部与非分部设置下从样本压缩条件导出的高元 PAC 样本复杂度对比：

设置类型 (Setting)	压缩非平凡条件 (Sufficient Condition)	鞅步数与单步鞅差界 (Martingale Bounds)	极限样本复杂度上界 $m^{\mathrm{PAC}}(\varepsilon, \delta)$	经典对比 ($k=1$)
$k$-分部设置 (Partite)	$\ln(h_m) + k s_m \ln m \leq o(m)$	步数 $k(m-s_m)$, 差分 $\frac{\\|\ell\\|_\infty}{m-s_m}$	$(1+o(1)) \cdot \frac{2 k \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \max\{1, \ln(\frac{1}{\delta})\}$	退化为经典独立 PAC 样本界
$k$-分部加强压缩	满足 $\leq (1+o(1))\sqrt{2km}\ln m$	方差和 $\frac{k \\|\ell\\|_\infty^2}{m-s_m}$	$(1+o(1)) \cdot \frac{2 k \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \ln(\frac{1}{\delta})$	达到与经典紧界同阶的渐近速率
$k$-元非分部设置	$\ln(h_m) + s_m \ln m \leq o(m)$	步数 $m-s_m$, 差分 $\frac{k \\|\ell\\|_\infty}{m-s_m}$	$(1+o(1)) \cdot \frac{2 k^2 \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \max\{1, \ln(\frac{1}{\delta})\}$	$k^2$ 因子反映置换对齐复杂度
$k$-元非分部加强压缩	满足 $\leq (1+o(1))\sqrt{2m}\ln m$	方差和 $\frac{k^2 \\|\ell\\|_\infty^2}{m-s_m}$	$(1+o(1)) \cdot \frac{2 k^2 \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \ln(\frac{1}{\delta})$	保持对置换无序性的精确控制

消融实验¶

为了剖析样本压缩各参数（子样本规模 $s_m$、头部信息 $h_m$、元数 $k$）对泛化误差上界构成的具体制约机制，下表给出了不同阶次压缩能力所导出的理论性质消融对比：

压缩方案规模假设	头部信息限制 $h_m$	联合界增长阶次	是否蕴涵高元 PAC	渐近样本复杂度主导项
平凡压缩基线 ($s_m = m, h_m = 1$)	$0$	$k m \ln m$ (分部)	❌ 否 (退化无泛化)	$\infty$ (界发散)
弱非平凡压缩 ($s_m = o(m)$)	$\ln h_m \leq o(m)$	$o(m)$	✅ 是 (弱 PAC 可学习)	取决于具体 $s_m$ 衰减速度
次根号紧凑压缩 ($s_m = O(m^{1/2-\gamma})$)	$h_m = O(1)$	$O(m^{1/2-\gamma} \ln m)$	✅ 是 (标准 PAC)	$O\left(\frac{k \\|\ell\\|_\infty^2}{\varepsilon^2} \ln(1/\delta)\right)$
强压缩方案 ($s_m = O(\ln m \cdot \ln \ln m)$)	$h_m = \mathrm{poly}(m)$	$O(\ln^2 m)$	✅ 是 (高效 PAC)	达到信息论最优速率 $\Theta(1/\varepsilon^2)$
经验近似压缩 ($L_{emp} \leq \varepsilon_m$)	$\ln h_m \leq o(m)$	$o(m)$	✅ 是 (近似 PAC 可学)	需额外累加近似误差 $\varepsilon_m$

关键发现¶

元数 $k$ 的几何代价明确：在分部设置中，由于各坐标轴是对称独立的，最终样本复杂度仅随元数 $k$ 呈线性增长；而在非分部设置中，由于单一样本集在元组排列中存在 $S_k$ 阶置换对称，鞅差跳变上界被放大为 $\frac{k}{n}$，最终导致样本复杂度上界引入了 $k^2$ 的依赖项。
子样本与原样本网格的覆盖率差距极小：分析表明，当 $s_m \leq o(m)$ 时，全网格 $m^k$ 与扣除压缩集后的未见网格 $(m - s_m)^k$ 的比值差距为 $1 - (1 - s_m/m)^k \leq O(k s_m / m) = o(1)$，说明在理论极限下，极小规模的压缩子集不会在未观测网格上产生不可控的经验偏差。
与标签基数无关的有界性：只要标头比特长度满足 $b_{\mathcal{S}}(m) \leq o(m / \ln m)$，无论标签集合是二值还是任意有限集，甚至对于任意紧致测度空间下的有界损失函数，压缩蕴涵 PAC 的结论均严格成立。

亮点与洞察¶

构造 Doob 鞅完美化解高元标签的非 i.i.d. 危机：传统集中不等式在矩阵/张量学习中常因元组重叠相关性受挫，本文巧妙利用“单点采样变量逐一暴露”将全网格损失差分约束在 $n^{k-1}/n^k = 1/n$ 的极小局部扰动内，展现了鞅方法在处理高阶代数结构数据时的极佳契合度。
统一分部与非分部两个平行的理论分支：高元理论长期因分部（多域独立采样）与非分部（单域无序采样）的结构差异导致证明方法割裂，本文通过精细定义无重复元组和标准方向（order choice），以同一套鞅论核心一并攻克了两种设置。
为高元 Boosting 与组合维数对偶提供潜在桥梁：经典理论中从样本压缩到 Boosting 再到 VC 维有着紧密循环。本文确立了从“高元样本压缩 $\implies$ 高元 PAC”这一半壁江山，指出了未来探索反向蕴涵（PAC $\implies$ 压缩）的核心障碍在于高元 Minimax 定理中乘积测度的不封闭性。

局限与展望¶

反向蕴涵存在本质博弈论阻碍：经典 David-Moran-Yehudayoff 证明“PAC 可学蕴涵样本压缩”极度依赖 von Neumann 极大极小定理与混合策略。而在高元理论中，学习者与对手受限于必须在乘积测度上进行分布博弈，多重线性收益函数不再具备准凹/准凸性质，导致反向猜想尚未获证。
仅限有界损失与有限标头假定：目前的集中性证明强依赖于损失函数的全局上界 $\|\ell\|_\infty$；对于无界损失（例如高斯噪声下的平方误差回归）或无限连续参数标头，该鞅差截断界无法直接闭合。
计算效率未作要求：与经典样本压缩类似，定理仅给出了统计意义上（信息论层面）压缩与泛化界的存在性，未探讨在多项式时间内寻找该子样本 $\sigma_m$ 与重构映射 $\rho_m$ 的算法复杂度。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次在高元学习理论中形式化定义分部与非分部样本压缩方案，填补了现代学习理论在高维超图结构上的关键空白。
实验充分度: ⭐⭐⭐⭐ 纯理论数学证明工作，构造性地给出了两套 Doob 鞅与精细渐近复杂度分析，推导严丝合缝。
写作质量: ⭐⭐⭐⭐⭐ 论文概念界定极其清晰，测度论基础严密，定理条件与推导节奏层次分明。
价值: ⭐⭐⭐⭐⭐ 为高维关系学习、超图神经网络泛化分析以及高元理论的核心猜想提供了基础性理论工具。

设置类型 (Setting)	压缩非平凡条件 (Sufficient Condition)	鞅步数与单步鞅差界 (Martingale Bounds)	极限样本复杂度上界 \(m^{\mathrm{PAC}}(\varepsilon, \delta)\)	经典对比 (\(k=1\))
\(k\)-分部设置 (Partite)	\(\ln(h_m) + k s_m \ln m \leq o(m)\)	步数 \(k(m-s_m)\), 差分 \(\frac{\\|\ell\\|_\infty}{m-s_m}\)	\((1+o(1)) \cdot \frac{2 k \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \max\{1, \ln(\frac{1}{\delta})\}\)	退化为经典独立 PAC 样本界
\(k\)-分部加强压缩	满足 \(\leq (1+o(1))\sqrt{2km}\ln m\)	方差和 \(\frac{k \\|\ell\\|_\infty^2}{m-s_m}\)	\((1+o(1)) \cdot \frac{2 k \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \ln(\frac{1}{\delta})\)	达到与经典紧界同阶的渐近速率
\(k\)-元非分部设置	\(\ln(h_m) + s_m \ln m \leq o(m)\)	步数 \(m-s_m\), 差分 \(\frac{k \\|\ell\\|_\infty}{m-s_m}\)	\((1+o(1)) \cdot \frac{2 k^2 \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \max\{1, \ln(\frac{1}{\delta})\}\)	\(k^2\) 因子反映置换对齐复杂度
\(k\)-元非分部加强压缩	满足 \(\leq (1+o(1))\sqrt{2m}\ln m\)	方差和 \(\frac{k^2 \\|\ell\\|_\infty^2}{m-s_m}\)	\((1+o(1)) \cdot \frac{2 k^2 \\|\ell\\|_\infty^2}{\varepsilon^2} \cdot \ln(\frac{1}{\delta})\)	保持对置换无序性的精确控制

压缩方案规模假设	头部信息限制 \(h_m\)	联合界增长阶次	是否蕴涵高元 PAC	渐近样本复杂度主导项
平凡压缩基线 (\(s_m = m, h_m = 1\))	\(0\)	\(k m \ln m\) (分部)	❌ 否 (退化无泛化)	\(\infty\) (界发散)
弱非平凡压缩 (\(s_m = o(m)\))	\(\ln h_m \leq o(m)\)	\(o(m)\)	✅ 是 (弱 PAC 可学习)	取决于具体 \(s_m\) 衰减速度
次根号紧凑压缩 (\(s_m = O(m^{1/2-\gamma})\))	\(h_m = O(1)\)	\(O(m^{1/2-\gamma} \ln m)\)	✅ 是 (标准 PAC)	\(O\left(\frac{k \\|\ell\\|_\infty^2}{\varepsilon^2} \ln(1/\delta)\right)\)
强压缩方案 (\(s_m = O(\ln m \cdot \ln \ln m)\))	\(h_m = \mathrm{poly}(m)\)	\(O(\ln^2 m)\)	✅ 是 (高效 PAC)	达到信息论最优速率 \(\Theta(1/\varepsilon^2)\)
经验近似压缩 (\(L_{emp} \leq \varepsilon_m\))	\(\ln h_m \leq o(m)\)	\(o(m)\)	✅ 是 (近似 PAC 可学)	需额外累加近似误差 \(\varepsilon_m\)