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

arXiv: https://arxiv.org/abs/2604.27742 · HTML: https://mlsanity.com/paper/2604.27742/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 78 references that are in the map.
- First posted on arXiv 30 Apr 2026.

## Builds on (most cited first, 30 of 38)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Learning with Symmetric Label Noise: The Importance of Being Unhinged](https://mlsanity.com/paper/1505.07634/) (2015)
- [Confidence Scores Make Instance-dependent Label-noise Learning Possible](https://mlsanity.com/paper/2001.03772/) (2020)
- [Learning with Bounded Instance- and Label-dependent Label Noise](https://mlsanity.com/paper/1709.03768/) (2017)
- [Principled Approaches for Learning to Defer with Multiple Experts](https://mlsanity.com/paper/2310.14774/) (2023)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Learning to Reject with a Fixed Predictor: Application to Decontextualization](https://mlsanity.com/paper/2301.09044/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Regression with Multi-Expert Deferral](https://mlsanity.com/paper/2403.19494/) (2024)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer](https://mlsanity.com/paper/2407.13732/) (2024)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [A Two-Stage Learning-to-Defer Approach for Multi-Task Learning](https://mlsanity.com/paper/2410.15729/) (2024)
- [Adversarial Robustness in Two-Stage Learning-to-Defer: Algorithms and Guarantees](https://mlsanity.com/paper/2502.01027/) (2025)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data](https://mlsanity.com/paper/2502.10381/) (2025)
- [Sharp Analysis of Learning with Discrete Losses](https://mlsanity.com/paper/1810.06839/) (2018)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Theory and Algorithms for Learning with Multi-Class Abstention and Multi-Expert Deferral](https://mlsanity.com/paper/2512.22886/) (2025)

## Built on by (most cited first, 2 of 2)

- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

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.