用VC维设计更鲁棒的在线分类算法，突破传统误差边界限制。
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
- 以平滑最优性为基准，替代传统最坏情况下的二元损失
- 首次实现仅依赖VC维与实例空间复杂度的后悔界，对广义间隔γ仅呈对数依赖
- 适用于关注模型鲁棒性与泛化能力的研究者
我们重新审视在线二元分类问题，将竞争目标从最优分类器的精确二元误差，转向能容忍小输入扰动、在高斯平滑下表现良好或保持指定输出边距的松弛基准。以往此类研究多局限于合页损失，本文方法首次建立仅依赖于VC维与实例空间复杂度（如度量熵）的后悔界，且对广义间隔γ仅呈现O(log(1/γ))的对数依赖，显著优于现有通常具有的多项式依赖。我们还给出了匹配的下界。分析融合了对抗鲁棒性与平滑在线学习的最新思想。
原文摘要 · Abstract (English)
We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notions of optimality. Instead of measuring regret relative to the exact minimal binary error -- a standard approach that leads to worst-case bounds tied to the Littlestone dimension -- we consider comparing with predictors that are robust to small input perturbations, perform well under Gaussian smoothing, or maintain a prescribed output margin. Previous examples of this were primarily limited to the hinge loss. Our algorithms achieve regret guarantees that depend only on the VC dimension and the complexity of the instance space (e.g., metric entropy), and notably, they incur only an $O(\log(1/γ))$ dependence on the generalized margin $γ$. This stands in contrast to most existing regret bounds, which typically exhibit a polynomial dependence on $1/γ$. We complement this with matching lower bounds. Our analysis connects recent ideas from adversarial robustness and smoothed online learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。