用弱一致性预言机实现近优后悔值，大幅降低查询复杂度。
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
- 通过动态剪枝非可实现标签序列，将预言机查询次数降至O(T^{d_VC+1})
- 在保持近最优期望后悔值的同时，实现比之前方法低得多的查询复杂度
- 适合资源受限场景下的在线学习，尤其关注预言机调用成本的研究者
经典元学习方法将广义在线学习归约为可实现情形，但其核心算法（SOA）在单轮中即难以计算。近期工作改用仅依赖离线经验风险最小化（ERM）预言机的可实现基学习器，虽达到近优期望后悔值，但预言机复杂度高达$O(T^{2^{O(d_ ext{LD})}})$，其中$T$为轮次数，$d_ ext{LD}$为Littlestone维数。本文提出更弱的弱一致性预言机，仅需判断给定标注数据集是否可实现。核心是自适应的广义到可实现还原机制，动态剪枝不可行标签序列，并利用VC维数($d_ ext{VC}$)控制活跃路径数量，使总查询复杂度降至$O(T^{d_ ext{VC}+1})$，同时保持近优期望后悔值。该方法还显著降低内存开销。我们进一步形式化了后悔值与预言机复杂度之间的权衡，给出上界并证明：若查询次数$Q = o(\ oot\of{T}\,)$，则期望后悔值必为$Ω(T/Q)$。
原文摘要 · Abstract (English)
Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of $O\big(T^{2^{O(d_\mathrm{LD})}}\big)$, where $d_\mathrm{LD}$ is the Littlestone dimension and $T$ is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension ($d_\mathrm{VC}$) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to $O(T^{d_\mathrm{VC}+1})$ while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to $Q = o(\sqrt{T})$ queries must suffer an expected regret of $Ω(T/Q)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。