提出新型平滑损失函数,兼具快速优化与最优一致性保证。
Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction
- 用线性核心加光滑尾部构造可微损失函数
- 在三类任务中实现线性一致性边界,优于已有方法
- 适合追求理论保证与实际效率的机器学习研究者
分类理论中存在平滑性与统计效率的固有矛盾:光滑代理损失(如逻辑损失)支持快速 $O(1/T)$ 优化,但仅提供缓慢的平方根 $H$-一致性界;而分段线性损失(如铰链损失)虽达最优线性 $H$-一致性率,却不可微。本文提出线性核心(LC)代理损失,首个显式构造的凸损失族,可同时满足全局可微($C^1$,甚至 $C^2$ 条件下)与严格线性 $H$-一致性。该性质在二分类、多分类和结构化预测三类设置中均被证明。据我们所知,这是首个在任一场景中同时实现光滑性与线性 $H$-一致性的确切构造。实践中,多分类任务中其靠近决策边界的恒定梯度特性带来对实例相关标签噪声的自然鲁棒性,在损坏的 CIFAR-10 上比交叉熵高出 2.6%;在结构化预测中,其光滑性允许无偏随机梯度估计,避免了精确推理的 $O(|Y|^2)$ 每步复杂度,使大规模词汇序列标注任务速度提升 23 倍。
原文摘要 · Abstract (English)
A fundamental dichotomy in the theory of classification sets smoothness against statistical efficiency: smooth surrogate losses such as the logistic loss enable fast $O(1/T)$ optimization but yield slow square-root $H$-consistency bounds, while piecewise-linear losses like the Hinge loss achieve optimal linear $H$-consistency rates but are non-differentiable. We introduce Linear-Core (LC) Surrogates, the first family of explicit convex loss functions that provably resolve this tension. By stitching a linear core to a smooth tail, we construct surrogates that are differentiable everywhere ($C^1$, and even $C^2$ under mild conditions) while retaining strict linear $H$-consistency bounds, the strongest known form of consistency guarantee. We establish these linear bounds across three increasingly complex settings: binary classification, multi-class classification, and structured prediction. To our knowledge, this is the first explicit construction to simultaneously achieve smoothness and linear $H$-consistency in any of these settings. Beyond their theoretical appeal, Linear-Core Surrogates offer practical advantages. In multi-class classification, their constant gradient profile near the decision boundary provides natural robustness to instance-dependent label noise, outperforming Cross-Entropy by 2.6% on corrupted CIFAR-10. In structured prediction, their smoothness enables an unbiased stochastic gradient estimator that bypasses the $O(|Y|^2)$ per-step complexity of exact inference, yielding a 23$\times$ speedup over Structured SVMs on large-vocabulary sequence tagging tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。