Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction

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 (C1, and even C2 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× speedup over Structured SVMs on large-vocabulary sequence tagging tasks.