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 ($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.

When training machine learning models, the choice of loss function, which measures how wrong predictions are penalized, involves a fundamental trade-off. Smooth loss functions (whose curves have no sharp corners) let optimizers converge quickly, but provide weak guarantees on how well surrogate performance translates to actual accuracy. Non-smooth losses (with sharp corners) give much stronger guarantees, but make optimization harder and slower. We introduce Linear-Core Surrogates, a new family of loss functions that resolve this trade-off. The key idea is to stitch a straight-line segment in the critical region near the decision boundary to smooth curved tails farther away. This gives the best of both worlds: the optimization speed of smooth losses and the strong accuracy guarantees of non-smooth ones. To our knowledge, these are the first explicitly defined loss functions to achieve both properties simultaneously. We prove these guarantees for binary classification, multi-class classification, and structured prediction (e.g., sequence tagging). In practice, our loss functions improve robustness to mislabeled data, outperforming the standard Cross-Entropy loss by 2.6% on corrupted image classification, and enable a 23x training speedup on large-vocabulary sequence tagging by replacing expensive exact inference with simple random sampling.