随机预览可让在线分类摆脱最坏情况复杂性束缚。
Adversarial Online Classification with a Preview
- 用随机预览部分数据，缓解对抗性在线学习困境。
- 二分类误差率随预览比例提升呈1/p衰减，理论最优。
- 适合研究在线学习与统计复杂度的学者参考。
最坏情况下的在线分类受序列复杂度（如Littlestone维数）制约，即使统计简单（如VC维为1的阈值类）也可能无法实现。本文研究一种预览模型：盲区对手固定长度为T的完整标签序列，随机提前揭示其中pT个样本，剩余(1−p)T个样本按原始对抗顺序呈现。针对在未揭示样本上表现最佳的全序列假设，我们刻画了预览率p的影响：对于VC维为d的二分类问题，最优过失损失为Θ(d/p + √(dT))，上限为T；多分类情况下，得到对应˜O(d_DS/p + √(d_Nat T))界，且不依赖标签数量。因此，随机预览可将最坏情况序列复杂度替换为经典统计维度，无需随机化在线顺序。为达到精确的二分类界，所提出的ChainedPrediction算法采用在线版本的链式结构，以多尺度聚合实现，而非仅作为分析工具。
原文摘要 · Abstract (English)
Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$ bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。