Even Sharper Bounds for Transductive Learning and Its Applications¶

会议: NeurIPS2026
arXiv: 2609.28459
论文: https://arxiv.org/abs/2609.28459
领域: 学习理论
关键词: 直推学习、局部复杂度、无放回抽样、修正对数 Sobolev 不等式、核学习
阅读版本: arXiv v2，2026-09-24；纯理论论文

一句话总结¶

本文以交换随机游走上的双参数熵闭合证明 Bernstein 型上确界集中，再用局部复杂度控制直推经验风险最小化，在有界损失及相应局部化条件下同时去掉旧结果的样本量失衡限制与额外置信度对数因子，并给出可实现 VC 分类和经验核谱应用。

研究背景与动机¶

直推学习不是先抽一批训练数据、再面对独立的新测试数据：学习者已经看见一个固定有限集合的全部特征，只随机揭示其中一部分标签，目标是预测余下那些点。训练与测试索引互补，因而两侧经验均值存在依赖。归纳学习中，局部 Rademacher 复杂度能利用低风险函数的较小波动，把全局复杂度界推进到“局部固定点加置信度项”；直接搬用独立抽样的证明，却不能自动获得同样干净的直推界。

论文对准的是既有直推局部复杂度分析的两个不同缺口。文献 [6] 已有固定点加 \(x/\min\{u,m\}\) 的形式，但要求 \(u\gg m^{2}\) 或 \(m\gg u^{2}\)；文献 [7] 去掉这一失衡条件，却留下 \(\log_{2}(4\min\{u,m\}/\delta)\) 乘在置信度项上。本文不提出新的预测器，而是改进对随机划分的集中分析，让任意相对样本量下的局部化证明不再支付这一额外因子。

核心 idea：在保持子集大小不变的交换几何上，同时追踪测试—训练上确界与平方函数辅助过程，用双参数熵闭合处理随机方差，再通过一次集中、几何分层与代理局部化把它转换为 ERM 的超额测试风险界。

方法详解¶

整体框架¶

Sharper Transductive Local Complexity（STLC）是一条证明链，而非网络结构。它依次建立交换集中、规范缩放后的局部化不等式、两固定点 ERM 比较，最后把固定点具体化为 VC 维或经验核谱。这里不把证明章节画成模型流水线。

设完整带标签样本为固定的 \(((\mathbf{x}_{i},y_{i}))_{i=1}^{n}\)，其中 \(n=m+u\)。学习者只观察全部特征及训练索引集 \(\bar Z\) 的标签；\(\bar Z\) 是均匀无放回抽出的 \(m\) 个索引，测试集 \(Z\) 是其补集。相同特征值可以重复，因为抽样对象是索引，不是不同特征值。全文中的主要概率和期望都针对这一划分，不针对重新生成的 i.i.d. 样本。

记 \(\mathcal L_n(h)\)、\(\mathcal L_m(h)\)、\(\mathcal L_u(h)\) 为完整样本、训练集和测试集上函数 \(h\) 的均值，\(T_n(h)=\mathcal L_n(h^2)\) 为完整样本二阶矩，并令 \(N_{u,m}=\min\{u,m\}\geq2\)。集中分析的对象为

\[ g(\mathcal H,Z)=\sup_{h\in\mathcal H}\{\mathcal L_u(h)-\mathcal L_m(h)\}. \]

局部复杂度衡量的是低二阶矩函数类中，子集均值相对于完整样本均值的单侧上确界期望。具体记 \(\mathfrak R_p^\eta(\mathcal A)=\mathbb E\sup_{h\in\mathcal A}\eta\{\mathcal L_p(h)-\mathcal L_n(h)\}\)，其中 \(p\in\{u,m\}\)、\(\eta\in\{+1,-1\}\)。它不是把无放回划分替换为独立训练—测试抽样后的复杂度。

训练 ERM \(\widehat f_m\) 最小化训练损失；测试 oracle \(\widehat f_u\) 最小化测试损失，只是不可访问的比较对象。本文的超额风险是 \(\mathcal E(\widehat f_m)=\mathcal L_u(\ell_{\widehat f_m})-\mathcal L_u(\ell_{\widehat f_u})\)，不是相对于未知总体分布的风险差。通用定理要求完整样本最优解存在，且每个划分的两个经验最小值均可取得；非唯一最优解允许可测选择。

关键设计¶

1. 交换集中与双参数熵闭合：把随机方差留在联合分析中

在所有大小为 \(u\) 的子集上，每一步交换一个测试索引和一个训练索引，得到 Johnson 图上的交换随机游走。其平稳分布正是均匀划分分布，修正对数 Sobolev 不等式将指数函数的熵联系到一步交换的 Dirichlet 型能量。附录 C.1 还核对了文献中的懒惰 down–up 游走与本文非懒惰交换游走的归一化关系，不能忽略自环后直接沿用常数。

难点是上确界并非固定函数的线性平均。作者在每个子集上选择一个近似达到上确界的函数，用同一个函数比较邻居子集，控制只计下降交换的定向方差；再让近似误差趋于零，因此集中定理不需要函数类上的上确界真正取得。若 \(|h(i)|\leq H_0\) 且 \(T_n(h)\leq r\)，这个方差由确定性半径与辅助过程 \(Q(Z)=\sup_{h\in\mathcal H}\{\mathcal L_u(h^2)-T_n(h)\}\) 共同控制。\(Q\) 可以逐点为负，不过 \(Q\geq-r\)，相应方差上界仍然非负。

对辅助过程本身做同样交换估计，就得到一个自控制关系。作者把主过程和辅助过程分别中心化，建立它们的双参数对数矩母函数；指数倾斜下的辅助均值成为该函数的一个偏导数，而不是被粗糙地替换为最大可能值。修正对数 Sobolev 不等式于是给出一阶微分不等式，沿受控的后向特征曲线积分，再用 Chernoff 方法得到尾界。这是去掉额外置信度对数因子的关键，而不是在最终公式上删除一个对数。

定理 IV.1 的完整集中形式为：对每个 \(x>0\)，以至少 \(1-\exp(-x)\) 的划分概率，

\[ g(\mathcal H,Z)\leq\mathbb E g(\mathcal H,Z)+c_0\sqrt{\frac{rx}{N_{u,m}}}+\frac{c_0}{2}\mathfrak R_{N_{u,m}}^+(\mathcal H^2)+\frac{(16H_0+c_0/2)x}{N_{u,m}},\qquad c_0=\sqrt{219}. \]

这里 \(\mathcal H^2=\{h^2:h\in\mathcal H\}\)，而 \(\mathfrak R_{N_{u,m}}^+\) 选择较小一侧的正向复杂度。证明先处理 \(u\leq m\)，另一种情形通过补集和负函数类处理；这就是为何最后出现较小样本量，而不要求极端失衡。平方函数类的复杂度仍然存在，不能将该式称为只含方差的经典单函数 Bernstein 界。

2. 规范缩放与几何分层：避免为每个半径分别支付置信度

低风险函数与高风险函数不能共用一个精细的二阶矩半径。定理 IV.2 允许使用任何确定性的代理泛函 \(\tilde T_n(h)\geq T_n(h)\)，并要求一个 sub-root 上界同时控制训练、测试两侧的正负局部复杂度，以及相同局部约束下的平方类复杂度。sub-root 指非负、单调不减，且 \(\psi(r)/\sqrt r\) 单调不增；其正固定点满足 \(\psi(r_{u,m})=r_{u,m}\)。

证明为每个函数选取不小于其代理半径的最小几何层半径 \(w(h)\)，然后缩放为 \(rh/w(h)\)。整个缩放类都具有二阶矩不超过 \(r\) 的性质，所以只需要对这个类应用一次集中不等式。随后按 \(w(h)\) 分层控制期望复杂度，而不是为各层建立不同高概率事件并做置信度并集。

附录 C-C 取层比 \(\lambda=4\)，利用 sub-root 性质将线性类与平方类的几何级数分别控制为 \(2\psi(r)\) 和 \(8\psi(r)/7\)。固定点把 \(\psi(r)\) 转成 \(\sqrt{rr_{u,m}}\)；校准 \(r\) 后，平方根偏差被吸收到代理半径项和固定点项中。确定性反缩放最终对所有函数同时给出

\[ \mathcal L_u(h)\leq\mathcal L_m(h)+\frac{\tilde T_n(h)}{K_0}+c_1r_{u,m}+\frac{c_2x}{N_{u,m}},\qquad K_0>1. \]

该事件的概率至少为 \(1-\exp(-x)\)。常数为 \(d_0=4+4c_0/7\)、\(c_1=8K_0d_0^2\)、\(c_2=1752K_0+32H_0+\sqrt{219}\)。这些常数并不小，论文主要改进的是依赖结构和阶，而非给出小样本数值最紧的证书。

3. 代理局部化与两固定点 ERM 比较：控制两个随机最优解的差

通用结果假设损失在完整样本上满足 \(0\leq\ell_f(i)\leq L_0\)。令 \(f_n^*\) 为完整样本风险最优解，\(g_f=\ell_f-\ell_{f_n^*}\)。除了最优解存在，还需要经验 Bernstein 条件 \(T_n(g_f)\leq B\mathcal L_n(g_f)\) 对所有 \(f\) 成立。这里右边是完整样本非负超额均值，并非关于未知数据分布的方差条件。

这类条件只围绕 \(f_n^*\) 控制超额损失，但最终比较的是 \(\widehat f_m\) 与 \(\widehat f_u\)，两个函数都依赖随机划分。为此作者在任意损失差 \(h\) 上定义

\[ \tilde T_n(h)=\inf_{\ell_{f_1}-\ell_{f_2}=h}2B\{\mathcal L_n(g_{f_1})+\mathcal L_n(g_{f_2})\}. \]

同一损失差可能有不同表示，取下确界让局部化只依赖函数 \(h\)。由差的平方不超过两项平方之和的两倍，每一种表示都给出二阶矩上界，所以取下确界仍保持 \(T_n(h)\leq\tilde T_n(h)\)；无需假设这个下确界取得。

第一个固定点 \(r_{u,m}\) 控制这种代理局部化下的成对损失差类；第二个 \(r^*\) 控制围绕 \(f_n^*\)、按 \(B\mathcal L_n(g_f)\) 局部化的超额损失类。附录 C.8 在两种划分方向应用局部化不等式，C.10 再利用经验最优性与可吸收系数，控制两个随机最优解各自的完整样本超额损失。最后对它们的损失差应用统一事件，训练 ERM 的最优性使训练风险差非正，代理半径就可由前两个界控制。

定理 IV.4 因而对每个 \(x>0\)、以至少 \(1-3\exp(-x)\) 的划分概率给出

\[ \mathcal E(\widehat f_m)\leq c_1r_{u,m}+\frac{4Bc_\Delta r^*}{K_0}+\frac{c_3x}{N_{u,m}},\qquad c_3=c_2+\frac{4Bc_\Delta}{K_0}. \]

此处 \(H_0=L_0\)，\(c_\Delta\) 仅依赖 \(B,L_0\)。三项失败概率来自最终局部化事件和两侧完整样本比较事件的并集；例如取 \(x=\log(3/\delta)\) 可获得失败概率至多 \(\delta\)，但没有旧结果中额外乘上的 \(\log_2(4N_{u,m}/\delta)\)。固定点仍需证明存在并上界局部复杂度，不是对任意有界学习问题无条件成立的快率。

4. VC 与核谱具体化：把抽象固定点转换为可解释的复杂度

可实现二分类中存在一个函数与全部完整样本标签一致；二元预测的平方损失就是错误指示函数。因此 \(h^2=h\) 且 \(T_n(h)=\mathcal L_n(h)\)，平方类与原类重合，训练 ERM 的损失为零。附录 C-E 用相对 VC 偏差界把完整样本局部化转成辅助有放回样本上的经验 \(L_2\) 局部化，再用收缩与 Dudley 熵积分处理好事件和坏事件。

辅助有放回抽样只是复杂度上界的证明工具：它从固定索引集合的均匀分布抽取，不改变实际的无放回训练协议。由 VC 熵估计得到形如 \(C\sqrt{a_mr}+Ca_m\) 的 sub-root 上界，其中 \(a_m=d^{\mathrm{(VC)}}\log(me/d^{\mathrm{(VC)}})/m\)，固定点是 \(a_m\) 的量级。定理 IV.2 取 \(K_0=2\)，把完整样本误差的一半吸收进测试误差，获得 V.1，而无需通用 ERM 比较中的三个事件。

核学习则令预测类为完整特征集合张成的 RKHS 子空间中半径 \(\mu\) 的球。设 \(\widehat\lambda_1\geq\cdots\geq\widehat\lambda_n\geq0\) 是完整 Gram 矩阵 \(\mathbf K/n\) 的特征值；不是训练子矩阵的谱。除有界损失与最优解存在外，还需 \(L\)-Lipschitz 损失以及预测局部化条件

\[ T_n(f-f_n^*)\leq B'\mathcal L_n(\ell_f-\ell_{f_n^*}),\qquad B'>0. \]

Lipschitz 性将预测二阶矩转换为损失二阶矩，故通用 Bernstein 条件可取 \(B_K=\max\{1,L^2B'\}\)。但 Lipschitz 性本身并不保证上面的预测局部化，不能声称任意核及任意有界损失都满足 V.2。

附录 C.11 沿经验协方差特征基在第 \(Q\) 个方向处分开：谱头用局部经验二阶矩控制，贡献为 \(\sqrt{rQ/p}\)；谱尾用 RKHS 范数控制，贡献为 \(\mu\sqrt{\sum_{q>Q}\widehat\lambda_q/p}\)，其中 \(p\in\{u,m\}\)。在 C-F 中，代理损失半径经预测局部化转为预测半径，收缩控制损失及平方类，再解固定点不等式。两个固定点都被谱表达式控制，且所构造的第二个固定点满足 \(r_{u,m}\leq r^*\leq2r_{u,m}\)。

最终定义

\[ r(u,m,Q)=Q\left(\frac1u+\frac1m\right)+\sqrt{\frac{\sum_{q=Q+1}^{n}\widehat\lambda_q}{u}}+\sqrt{\frac{\sum_{q=Q+1}^{n}\widehat\lambda_q}{m}},\qquad Q\in\{0,\ldots,n\}. \]

定理 V.2 给出 \(\mathcal E(\widehat f_m)\leq c_5\{\min_Qr(u,m,Q)+x/N_{u,m}\}\)，概率至少为 \(1-3\exp(-x)\)，其中 \(c_5\) 仅依赖 \(K_0,B',L_0,L,\mu\)。谱头与谱尾的折中反映有效复杂度，而不是一个需要训练调整的新超参数。奇异 Gram 矩阵允许不同系数表示同一函数；证明仅在正特征值方向作除法，零谱情形单独处理。

实验关键数据¶

原文无经验实验，以下为理论结果与假设比较。

主实验¶

本节的“主实验”对应主要定理，不包含数据集准确率、运行时间或消融数值。

结果	结论	划分概率	必要边界
IV.4：通用 ERM	\(c_1r_{u,m}+4Bc_\Delta r^*/K_0+c_3x/N_{u,m}\)	\(1-3\exp(-x)\)	\(u,m\geq2\)；有界损失、最优解存在、经验 Bernstein 条件及两类局部复杂度上界
V.1：可实现 VC 分类	\(c_0''d^{\mathrm{(VC)}}\log(me/d^{\mathrm{(VC)}})/m+c_1'x/m\)	\(1-\exp(-x)\)	二元函数及标签；完整样本可实现；\(u\geq m\geq d^{\mathrm{(VC)}}\geq2\)
V.1 的下界比较	期望极小极大下界 \((d^{\mathrm{(VC)}}-1)/(16m)\)	期望下界，不是同一高概率声明	上述比较中另需 \(m\geq9\)；上界仍有对数间隙
V.2：直推核学习	\(c_5\{\min_Qr(u,m,Q)+x/N_{u,m}\}\)	\(1-3\exp(-x)\)	RKHS 球、有界损失、Lipschitz 性、预测局部化；常数依赖 \(K_0,B',L_0,L,\mu\)

消融实验¶

没有经验消融；以下以假设和证明机制的作用替代，不能理解为去掉模块后的测量结果。

条件或机制	在证明中的作用	不可越过的结论边界
完整样本固定、索引均匀无放回划分	使交换游走的平稳分布匹配学习协议	不是分布漂移或任意选择标签的保证
\(T_n(h)\leq B\mathcal L_n(h)\)	围绕完整样本最优解把风险半径转换为二阶矩半径	有界损失本身不足以推出通用快率
双参数熵闭合	联合处理上确界及平方函数辅助过程	改进不是单函数尾界的直接套用
一次集中加缩放类分层	在期望复杂度层面累加几何层	不另引入逐层置信度对数因子
可实现二元损失	\(h^2=h\)、训练误差为 \(0\)，允许单事件证明	V.1 不能原样覆盖不可实现分类
核预测局部化与 Lipschitz 性	将损失局部化接到经验谱头—尾界	无条件“任意核都享有该快率”不成立

关键发现¶

通用结果的样本量限制只是 \(u,m\geq2\)，不要求相对增长失衡；VC 应用另有 \(u\geq m\geq d^{\mathrm{(VC)}}\geq2\)，不能混为一谈。
VC 上界达到标准归纳局部复杂度的速率形态，但与引用的期望极小极大下界仍相差对数因子；本文没有去掉 \(\log(me/d^{\mathrm{(VC)}})\)。
核结果去掉旧界在固定点前的 \(n/u\)、\(n/m\) 乘子，不是去掉所有固定点或所有样本量依赖。
附录 D-B 取 \(Q=0\) 得到 \(\min_Qr(u,m,Q)\leq\sqrt{\operatorname{tr}(\mathbf K/n)}(u^{-1/2}+m^{-1/2})\)；若经验谱随完整样本变化，不能仅凭“乘子消失”宣布统一的渐近优势。

亮点与洞察¶

最有复用价值的是对随机方差的处理：平方函数上确界不必先变成一个独立的坏事件，可以与目标上确界一起放进熵分析。这样改善的是置信度成本，不是函数类的表达能力。
缩放类上的一次集中把概率控制与几何分层拆开：分层负责累加期望复杂度，置信度只在统一事件上支付。这比把每个半径都做成独立高概率声明更适合追求精确置信度阶。
代理泛函解决了“围绕固定最优解的条件”与“比较两个随机最优解”的不匹配。对表示取下确界也提醒读者：局部化工具可以是分析量，而不必是学习者可直接计算的训练量。

局限与展望¶

结果针对固定完整样本上的随机划分。与归纳界具有相同固定点结构，不意味着已经证明对未知总体分布中未来新点的相同泛化保证。
通用定理依赖有界性、经验 Bernstein 条件、最小值取得和有效局部复杂度上界。附录 E 将超越有界函数类列为开放方向；重尾损失不能直接套用。
VC 应用限于可实现二分类，且上界与极小极大期望下界还有对数间隙。不可实现情形和去掉此速率对数都不由当前定理解决。
核应用需要额外预测局部化；核谱可由全部特征得到，但验证该条件涉及完整标签与最优解，不能把它当成无条件、无标签可验证的证书。
集中与分层常数较大，文中没有算法实现或经验比较。实际有限样本上界是否更紧，应另比较具体常数、谱及成立的假设。

评分¶

新颖性: 4/5。双参数熵闭合与统一缩放分层对既有直推界提供了明确的置信度改进。
实验充分度: 不适用。纯理论论文，无经验实验；定理与附录证明覆盖通用、VC 和核应用。
写作质量: 4/5。主文路线图与完整证明对应清楚；本地文本含重复数学抽取痕迹，公式需按完整 LaTeX 片段阅读。
价值: 4/5。为一般相对训练—测试规模提供更干净的局部复杂度工具，但强假设与较大常数限制直接数值使用。