Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning¶

会议: NeurIPS 2026
arXiv: 2605.07155
论文: https://arxiv.org/abs/2605.07155
领域: 学习理论
关键词: 不可知在线学习、预言机复杂度、动态前缀剪枝、弱一致性预言机、后悔界权衡

一句话总结¶

针对不可知在线学习中经典归约导致预言机查询复杂度双重指数级爆炸的理论瓶颈，本文提出基于弱一致性预言机动态剪枝无效伪标签前缀的 ADEPT 框架，将预言机调用复杂度从 $\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$ 骤降至 $\mathcal{O}(T^{d_{\mathrm{VC}}+1})$，并刻画了查询预算与次线性后悔界之间的紧致权衡与下界。

研究背景与动机¶

在线二分类学习是贯穿序贯决策与博弈论的核心理论基石。在经典的可实现设定下，Littlestone 维数 $d_{\mathrm{LD}}$ 充要刻画了算法的最坏犯错界，标准最优算法（SOA）可达成紧致的 $d_{\mathrm{LD}}$ 次犯错；而在标签可能任意带噪或对抗的不可知（agnostic）设定下，经典工作通过将不可知学习归约到可实现基础学习器（以 SOA 为子程序追踪全部可能的犯错调度），建立了 $\mathcal{O}(\sqrt{T d_{\mathrm{LD}} \log T})$ 的近似最优期望后悔界。然而，这一经典归约在计算上是彻底不可行的：执行 SOA 必须在每轮反复计算受限子类的 Littlestone 维数，该计算即便在概念类与特征空间有限时也已被证明无法常数倍近似，甚至存在有限 Littlestone 维数的递归可枚举类根本不存在可计算的 SOA。

为了打破这种不可计算性障碍，近年来基于离线预言机的高效在线学习范式（Oracle-Efficient Online Learning）引起了广泛关注，其核心思想是限制学习器仅能通过经验风险最小化（ERM）预言机或弱一致性预言机访问概念类。在可实现设定下，基于 ERM 预言机的基础学习器已被证明必须付出犯错界指数级增长的代价，即达到 $M = 2^{\mathcal{O}(d_{\mathrm{LD}})}$ 次犯错。当将这种预言机高效学习器代入经典的 Ben-David 等人（BDPSS 2009）不可知归约框架时，为了跟踪所有可能的犯错时间步组合，算法必须在全局维护高达 $\mathcal{O}(T^M) = \mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$ 个并行专家，导致预言机查询复杂度发生灾难性的双重指数级膨胀 $\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$，令其在计算上形同虚设。

深入剖析该计算瓶颈会发现其核心矛盾在于：经典归约盲目维护了全排列的抽象犯错掩码，所保留的海量伪标签历史中绝大多数根本无法被底层概念类所实现；而根据 Sauer 引理，长度为 $t$ 的任意样本序列在概念类 $\mathcal{C}$ 上诱导的可实现二分切分数量严格受控于多项式阶 $\mathcal{O}(t^{d_{\mathrm{VC}}})$。核心 idea：利用仅需判定样本集是否可实现的弱一致性预言机对在线伪标签生成树进行动态前缀剪枝，通过组合未来容量加权精确等价恢复全量专家对冲分布，从而将预言机查询与内存复杂度从 Littlestone 维数的双重指数级解耦并压制至 VC 维数的多项式阶 $\mathcal{O}(T^{d_{\mathrm{VC}}+1})$。

方法详解¶

整体框架¶

本文提出的自适应动态专家剪枝树（Adaptive Dynamic Expert Pruning Tree, ADEPT）重构了不可知到可实现学习的归约范式。算法不再自始至终显式维护全局 $\mathcal{O}(T^M)$ 个抽象犯错调度掩码，而是转向在每轮动态追踪当前已被验证为严格可实现的有效标签前缀集合 $V_t$。在每个时间步 $t$，针对上一轮保留的每个父前缀 $v \in V_{t-1}$，算法分别探测二进制后继扩展 $b \in \{0,1\}$，依次实施两道动态过滤器：首先调用弱一致性预言机剔除不可实现序列，再利用内部可实现基础学习器模拟犯错计数剔除超出预算 $M$ 的序列。为了确保剪枝后对冲算法（Hedge）聚合预测分布的数学无损性，算法为每个存活前缀计算组合未来容量权重，以此精准折算其所代表的后继合法路径总规模。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入实例 x_t<br/>活跃前缀集合 V_{t-1}"] --> B["1. 显式前缀分支与弱一致性剪枝<br/>查询 Weak Consistency 剔除不可实现序列"]
    B --> C["2. 内部基础学习器犯错预算过滤<br/>模拟预测并剪去累计犯错 k(u) > M 分支"]
    C --> D["3. 组合未来容量加权与对冲聚合<br/>计算 W_t(u) 并聚合得到预测概率 P_t"]
    D --> E["4. 真实标签反馈与损失更新<br/>观测 y_t，更新存活前缀累计损失 L_t(u)"]
    E --> F["输出新活跃集合 V_t<br/>规模严格由 Sauer 引理界定为 O(t^{d_VC})"]

关键设计¶

1. 显式前缀分支与弱一致性实时剪枝：彻底打破不可实现伪标签的组合爆炸 针对经典 BDPSS 归约对底层概念类几何结构完全“无知”而机械枚举 $\binom{T}{\le M}$ 条抽象犯错掩码这一缺陷，ADEPT 将状态表示从静态的长度为 $T$ 的犯错掩码彻底重构为动态拓展的二值标签前缀 $u = (u_1, \dots, u_t) \in \{0,1\}^t$。在接收到新样本 $x_t$ 后，对集合 $V_{t-1}$ 中的每一个存活前缀 $v$，算法试探性地构造 $v \circ 0$ 与 $v \circ 1$ 两个扩展，并立即向弱一致性预言机 $\mathcal{O}$ 发起查询： $$S = \big\{(x_1, v_1), \ldots, (x_{t-1}, v_{t-1}), (x_t, b)\big\} \stackrel{?}{\in} \operatorname{Realizable}(\mathcal{C})$$ 弱一致性预言机仅需回答判定性布尔值，若返回非可实现（UNREALIZABLE），则该分支被即刻永久剪枝。根据 Sauer 引理，对于 VC 维数为 $d_{\mathrm{VC}}$ 的任意概念类，任意 $t-1$ 个点上所能诱导出的合法二分切分（dichotomy）上限为 $\sum_{i=0}^{d_{\mathrm{VC}}} \binom{t-1}{i} = \mathcal{O}(t^{d_{\mathrm{VC}}})$。这意味着活跃节点数从原本不可承受的 $\mathcal{O}(t^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$ 被牢牢锚定在多项式阶 $\mathcal{O}(t^{d_{\mathrm{VC}}})$，一举消除了对 Littlestone 维数的双重指数级依赖。

2. 组合未来容量加权与对冲聚合：零偏差复现全量专家指数权重分布 剪枝使得大量专家在不同历史时刻被剔除，如果直接在存活节点上应用平权或简单的指数权重更新，会导致存活前缀的分支权重与原始全量专家池严重偏离。ADEPT 的核心洞见在于，当前轮存活的每一个前缀 $u \in V_t$，实际上在原始全量专家集合中等价于一个“前缀完全重合的专家簇”（bundle of experts）。为了严密对齐原始 Hedge 算法的概率测度，算法为每个前缀 $u$ 赋予基于帕斯卡恒等式构建的未来容量权重 $W_t(u)$： $$W_t(u) = \sum_{j=0}^{M - k(u)} \binom{T - t}{j}$$ 其中 $k(u) = k(v) + \mathbb{I}[b \neq \mathcal{A}(v, x_t)]$ 记录可实现基础学习器沿该前缀所产生的累积犯错次数。前缀 $u$ 的最终未归一化对冲权重为 $w_t(u) = W_t(u) \cdot \exp(-\eta L_{t-1}(v))$。通过帕斯卡恒等式 $\binom{n}{j} + \binom{n}{j-1} = \binom{n+1}{j}$，未被剪枝的后继分支权重之和与父节点未来容量精确单峰伸缩：$W_{t-1}(v) \ge W_t(v \circ 0) + W_t(v \circ 1)$。这保证了在剪枝过程中势函数单调递减（只剔除非负权重），而后验最优假设 $c^* \in \mathcal{C}$ 因全程严格可实现且犯错数必不超过 $M$ 而百分之百存活，确保理论期望后悔界与未剪枝的全量专家对冲完全一致。

3. 自适应懒惰模拟与回滚机制：平滑插值查询预算与次线性后悔界 当预言机调用预算极其受限、甚至不允许每轮按 $\mathcal{O}(t^{d_{\mathrm{VC}}})$ 充分查询时，本文进一步给出了通过下采样降低预言机调用总量的折中机制。算法引入基于对抗均匀大数定律（Adversarial ULLN）的样本盲（sample-blind）懒惰模拟技术：预先随机抽取大小为 $K = \lfloor T^c \rfloor$ 的更新轮次子集 $I \subset [T]$（参数 $c \in (0,1)$）。在预测前，算法在内部按 $K$ 步 ADEPT 试探性执行扩展与查询并输出预测分布；随后若当前轮 $t \notin I$，则立即执行“状态回滚”（rollback），丢弃所有试探性更新并保持内部已提交状态不变；仅当 $t \in I$ 时才将该步状态正式固化。由于预测时对采样位无感知，且增广损失函数族的 Littlestone 维数受控，算法证明了仅耗费 $\mathcal{O}(T^{1 + c \cdot d_{\mathrm{VC}}})$ 次查询即可保证后悔界保持为次线性的 $\mathcal{O}\big(T^{1 - c/2} \sqrt{d_{\mathrm{LD}} + M \log T}\big)$。

4. 自适应一阶学习率调度：实现对抗到可实现环境的连续插值 除了固定视界参数下的静态学习率 $\eta = \sqrt{8M \ln(eT/M)/T}$，ADEPT 还支持动态调整学习率以自适应任务难易程度。算法实时追踪当前存活集合中最优路径的经验累计损失 $L_{t-1}^* = \min_{u \in V_{t-1}} L_{t-1}(u_{1:t-1})$，并将第 $t$ 轮的学习率设为 $\eta_t = \min\big\{1/2, \sqrt{\ln N / (L_{t-1}^* + 1)}\big\}$。由于组合容量权重 $W_t(u)$ 与学习率解耦，动态学习率依然严格保持对冲分布的边际概率一致性。在全对抗极端下（$L^* \propto T$），算法自适应退化并保证 $\tilde{\mathcal{O}}(\sqrt{T M})$ 的经典无悔界；而在完全可实现或极少噪声环境（$L^* = 0$）下，期望犯错数直接收敛至 $\mathcal{O}(M \log T)$，无缝桥接了在线学习在对抗与良态序列之间的性能差距。

损失函数 / 训练策略¶

算法在每一轮对二值预测 $\hat{y}_t \in \{0,1\}$ 采取随机化预测策略，预测为 1 的概率为所有当前后继位 $u_t = 1$ 的活跃前缀的权重占比： $$P_t(\hat{y}_t = 1) = \frac{\sum_{u \in V_t : u_t = 1} w_t(u)}{\sum_{u \in V_t} w_t(u)}$$ 在观测到真实标签 $y_t$ 后，存活分支更新其实际累计经验损失 $L_t(u) = L_{t-1}(u_{1:t-1}) + \mathbb{I}[u_t \neq y_t]$。定义系统势函数为 $Z_t = \sum_{u \in V_t} W_t(u) \exp(-\eta L_t(u))$。在理论分析中，由于剪枝操作仅将非法分支权重置零，中间态势函数满足 $Z_t' \le Z_{t-1}$；结合 Hoeffding 引理，系统势函数在 $T$ 步后满足 $Z_T \le Z_0 \exp(-\eta \sum_{t=1}^T \ell_t + T \eta^2 / 8)$。结合最优假设存活下界 $Z_T \ge \exp(-\eta L_T(c^*))$，极小化对数差即可闭式解出最优学习率并导出理论上界。

实验关键数据¶

主实验：理论界与复杂度全局对比¶

本文是一篇纯学习理论研究，无数值经验拟合，核心结果由一系列严格证明的极限定理和复杂度上界构成。主实验部分对比了不同归约范式在不可知在线学习中的后悔界、内存状态数以及预言机调用复杂度：

算法框架	依赖预言机类型	可实现基础犯错界 $M$	期望后悔界 $\mathbb{E}[\mathrm{Reg}_T]$	每轮活跃状态数（内存复杂度）	总预言机查询复杂度 $Q_T$
BDPSS 经典归约 (2009) + SOA	无（需精确计算 $d_{\mathrm{LD}}$）	$d_{\mathrm{LD}}$	$\mathcal{O}(\sqrt{T d_{\mathrm{LD}} \log T})$	$\mathcal{O}(T^{d_{\mathrm{LD}}})$	计算不可行（无预言机支持）
BDPSS 经典归约 + ERM 学习器	Agnostic ERM 预言机	$2^{\mathcal{O}(d_{\mathrm{LD}})}$	$\tilde{\mathcal{O}}(\sqrt{T \cdot 2^{\mathcal{O}(d_{\mathrm{LD}})}})$	$\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$	$\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})$（双重指数级）
ADEPT + SOA (本文推论 4.3)	弱一致性（或全可实现检查）	$d_{\mathrm{LD}}$	$\tilde{\mathcal{O}}(\sqrt{T \cdot d_{\mathrm{LD}}})$	$\mathcal{O}(t^{d_{\mathrm{VC}}})$	$\mathcal{O}(T^{d_{\mathrm{VC}}+1})$
ADEPT + 预言机学习器 (本文推论 4.2)	弱一致性预言机 (Weak Consistency)	$2^{\mathcal{O}(d_{\mathrm{LD}})}$	$\tilde{\mathcal{O}}(\sqrt{T \cdot 2^{\mathcal{O}(d_{\mathrm{LD}})}})$	$\mathcal{O}(t^{d_{\mathrm{VC}}})$	$\mathcal{O}(T^{d_{\mathrm{VC}}+1})$（降至多项式阶）
ADEPT 自适应率调度 (本文推论 4.4)	弱一致性预言机	$M$	$\mathcal{O}(\sqrt{L^* M \log T} + M \log T)$	$\mathcal{O}(t^{d_{\mathrm{VC}}})$	$\mathcal{O}(T^{d_{\mathrm{VC}}+1})$

消融与权衡分析：预算限制下的连续插值与下界对比¶

针对不同查询预算 $Q$ 下的后悔界渐近阶数，本文对下采样懒惰模拟参数 $c \in (0,1)$ 的 trade-off 与信息论下界进行了系统刻画：

分析配置 / 场景	查询预算参数化	渐近总预言机调用数 $Q_T$	对应期望后悔界 $\mathbb{E}[\mathrm{Reg}_T]$	渐近收敛性判定
ADEPT 全查询上限 ($c \to 1$)	全局无受限	$\mathcal{O}(T^{d_{\mathrm{VC}}+1})$	$\tilde{\mathcal{O}}(\sqrt{T \cdot M})$	最优次线性界 $\mathcal{O}(T^{1/2})$
权衡上界中间档 ($c = 2/3$)	适度查询约束	$\mathcal{O}(T^{1 + \frac{2}{3} d_{\mathrm{VC}}})$	$\mathcal{O}(T^{2/3} \sqrt{d_{\mathrm{LD}} + M \log T})$	次线性界 $\mathcal{O}(T^{2/3})$
权衡上界低开销档 ($c = 1/2$)	强查询约束	$\mathcal{O}(T^{1 + \frac{1}{2} d_{\mathrm{VC}}})$	$\mathcal{O}(T^{3/4} \sqrt{d_{\mathrm{LD}} + M \log T})$	次线性界 $\mathcal{O}(T^{3/4})$
极限受限下界 (定理 5.1, $d=1$)	$Q = o(\sqrt{T})$（如 $Q \le T^{1/2-\epsilon}$）	$o(\sqrt{T})$	$\Omega(T / Q) \ge \Omega(T^{1/2+\epsilon})$	必然劣于 $\sqrt{T}$ 无悔率
常数查询下界 (定理 5.1, $d=1$)	$Q = \mathcal{O}(1)$ 独立于 $T$	$\mathcal{O}(1)$	$\Omega(T)$	必定产生线性后悔（不可学）

关键发现¶

统计成本与计算成本的本质解耦：不可知在线分类的信息论统计代价（后悔界）本质上由 Littlestone 维数 $d_{\mathrm{LD}}$ 决定，但维持在线专家池的计算与查询代价完全可以解耦并交由可能远小于 $d_{\mathrm{LD}}$ 的 VC 维数 $d_{\mathrm{VC}}$ 决定。
预言机能力要求降阶：以往研究普遍默认需要强大的离线 ERM 优化预言机（求解经验误差全局极小），而 ADEPT 证明仅需仅含判定性功能的弱一致性预言机（返回布尔值代表是否存在可行假设），即可达成多项式查询复杂度。
低查询区间的不可逾越壁垒：定理 5.1 证明了一旦预言机调用次数低于 $o(\sqrt{T})$，无论采取何种对抗性设计，算法都必然蒙受 $\Omega(T/Q)$ 的后悔；对于仅做常数次查询的算法，在线不可知学习是完全不可实现的（线性后悔）。

亮点与洞察¶

剪枝与权重守恒的数学闭环：通过巧妙利用帕斯卡恒等式构建未来容量乘子 $W_t(u)$，论文在动态剪掉指数级数量的非法路径的同时，使存活分支的对冲概率分布严格等价于全量专家池，没有引入任何投影近似误差。
弱一致性预言机足以驱动不可知学习：将原本针对离线 PAC 学习证明充分性的弱一致性原语成功跨界引渡至难度极高的对抗性在线学习中，拓宽了弱预言机在序贯决策领域的理论疆界。
对抗大数定律的惰性模拟运用：巧妙利用 AULLN 建立“样本盲试探-回滚”分析框架，在不泄露采样历史的前提下实现了查询数向任意多项式次幂的平滑压缩。

局限与展望¶

下界与上界之间的理论鸿沟：如图 1 所示，虽然定理 5.1 给出了 $Q = o(\sqrt{T})$ 时后悔下界为 $\Omega(T/Q)$，但在 $Q = \tilde{\mathcal{O}}(\sqrt{T})$ 到 $Q = \mathcal{O}(T^{d_{\mathrm{VC}}+1})$ 之间，当前上界给出的查询-后悔权衡曲线与硬性下界仍存在未闭合的间隙。
多项式中关于 $T$ 的高次幂开销：尽管将指数级 $T^{2^{\mathcal{O}(d_{\mathrm{LD}})}}$ 降至 $T^{d_{\mathrm{VC}}+1}$ 带来了质的飞跃，但当概念类 $d_{\mathrm{VC}} \ge 2$ 时，$T$ 的高阶多项式复杂度在海量数据流下计算依然较为沉重。
多分类与连续动作空间的扩展：当前技术高度依赖二值切分的 Sauer 引理与布尔弱一致性，如何推广至多分类（Natarajan 维数）或回归场景仍是开放难题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破不可知在线学习预言机复杂度的双重指数壁垒，建立优美的维数解耦理论。
理论充分度: ⭐⭐⭐⭐⭐ 涵盖紧致上界、实例自适应界、连续权衡曲线以及尖锐的查询下界，证明完备严密。
写作质量: ⭐⭐⭐⭐⭐ 概念界定清晰，动机构建与数学推导层层推进，逻辑极为严谨。
价值: ⭐⭐⭐⭐⭐ 为预言机高效在线算法提供了全新的分析范式与复杂度标准。

算法框架	依赖预言机类型	可实现基础犯错界 \(M\)	期望后悔界 \(\mathbb{E}[\mathrm{Reg}_T]\)	每轮活跃状态数（内存复杂度）	总预言机查询复杂度 \(Q_T\)
BDPSS 经典归约 (2009) + SOA	无（需精确计算 \(d_{\mathrm{LD}}\)）	\(d_{\mathrm{LD}}\)	\(\mathcal{O}(\sqrt{T d_{\mathrm{LD}} \log T})\)	\(\mathcal{O}(T^{d_{\mathrm{LD}}})\)	计算不可行（无预言机支持）
BDPSS 经典归约 + ERM 学习器	Agnostic ERM 预言机	\(2^{\mathcal{O}(d_{\mathrm{LD}})}\)	\(\tilde{\mathcal{O}}(\sqrt{T \cdot 2^{\mathcal{O}(d_{\mathrm{LD}})}})\)	\(\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})\)	\(\mathcal{O}(T^{2^{\mathcal{O}(d_{\mathrm{LD}})}})\)（双重指数级）
ADEPT + SOA (本文推论 4.3)	弱一致性（或全可实现检查）	\(d_{\mathrm{LD}}\)	\(\tilde{\mathcal{O}}(\sqrt{T \cdot d_{\mathrm{LD}}})\)	\(\mathcal{O}(t^{d_{\mathrm{VC}}})\)	\(\mathcal{O}(T^{d_{\mathrm{VC}}+1})\)
ADEPT + 预言机学习器 (本文推论 4.2)	弱一致性预言机 (Weak Consistency)	\(2^{\mathcal{O}(d_{\mathrm{LD}})}\)	\(\tilde{\mathcal{O}}(\sqrt{T \cdot 2^{\mathcal{O}(d_{\mathrm{LD}})}})\)	\(\mathcal{O}(t^{d_{\mathrm{VC}}})\)	\(\mathcal{O}(T^{d_{\mathrm{VC}}+1})\)（降至多项式阶）
ADEPT 自适应率调度 (本文推论 4.4)	弱一致性预言机	\(M\)	\(\mathcal{O}(\sqrt{L^* M \log T} + M \log T)\)	\(\mathcal{O}(t^{d_{\mathrm{VC}}})\)	\(\mathcal{O}(T^{d_{\mathrm{VC}}+1})\)

分析配置 / 场景	查询预算参数化	渐近总预言机调用数 \(Q_T\)	对应期望后悔界 \(\mathbb{E}[\mathrm{Reg}_T]\)	渐近收敛性判定
ADEPT 全查询上限 (\(c \to 1\))	全局无受限	\(\mathcal{O}(T^{d_{\mathrm{VC}}+1})\)	\(\tilde{\mathcal{O}}(\sqrt{T \cdot M})\)	最优次线性界 \(\mathcal{O}(T^{1/2})\)
权衡上界中间档 (\(c = 2/3\))	适度查询约束	\(\mathcal{O}(T^{1 + \frac{2}{3} d_{\mathrm{VC}}})\)	\(\mathcal{O}(T^{2/3} \sqrt{d_{\mathrm{LD}} + M \log T})\)	次线性界 \(\mathcal{O}(T^{2/3})\)
权衡上界低开销档 (\(c = 1/2\))	强查询约束	\(\mathcal{O}(T^{1 + \frac{1}{2} d_{\mathrm{VC}}})\)	\(\mathcal{O}(T^{3/4} \sqrt{d_{\mathrm{LD}} + M \log T})\)	次线性界 \(\mathcal{O}(T^{3/4})\)
极限受限下界 (定理 5.1, \(d=1\))	\(Q = o(\sqrt{T})\)（如 \(Q \le T^{1/2-\epsilon}\)）	\(o(\sqrt{T})\)	\(\Omega(T / Q) \ge \Omega(T^{1/2+\epsilon})\)	必然劣于 \(\sqrt{T}\) 无悔率
常数查询下界 (定理 5.1, \(d=1\))	\(Q = \mathcal{O}(1)\) 独立于 \(T\)	\(\mathcal{O}(1)\)	\(\Omega(T)\)	必定产生线性后悔（不可学）