Search papers, labs, and topics across Lattice.
Linear-Core (LC) Surrogates are introduced as a novel family of convex loss functions that combine a linear core with a smooth tail, aiming to leverage the benefits of both smooth and piecewise-linear losses. The key result is that LC Surrogates achieve differentiability while maintaining strict linear H-consistency bounds, thereby uniting the optimization advantages of smoothness with the statistical efficiency of margin-based losses. In structured prediction, this smoothness enables an unbiased stochastic gradient estimator, bypassing the quadratic complexity of exact inference and achieving significant speedups.
Get the best of both worlds: Linear-Core Surrogates offer the fast optimization of smooth losses and the statistical efficiency of margin-based losses, without sacrificing differentiability.
The choice of loss function in classification involves a fundamental trade-off: smooth losses (like Cross-Entropy) enable fast optimization rates but yield slow square-root consistency bounds, while piecewise-linear losses (like Hinge) offer fast linear consistency rates but suffer from non-differentiability. We propose Linear-Core (LC) Surrogates, a new family of convex loss functions that resolve this tension by stitching a linear core to a smooth tail. We prove that these surrogates are differentiable everywhere while retaining strict linear $H$-consistency bounds, effectively combining the optimization benefits of smoothness with the statistical efficiency of margin-based losses. In the structured prediction setting, we show that this smoothness unlocks a massive computational and energy advantage: it allows for an unbiased stochastic gradient estimator that bypasses the quadratic complexity $O(|\mathscr{Y}|^2)$ of exact inference (e.g., Viterbi). Empirically, our method achieves a 23$\times$ speedup over Structured SVMs on large-vocabulary sequence tagging tasks and demonstrates superior robustness to instance-dependent label noise, outperforming Cross-Entropy by 2.6% on corrupted CIFAR-10.
