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

• URL: http://arxiv.org/abs/2604.27742v1
• Date: Thu, 30 Apr 2026 11:32:25 GMT
• Title: Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction
• Abstract summary: We propose a new family of convex loss functions that resolve this tension by stitching a linear core to a smooth tail.<n>We prove that these surrogates are differentiable everywhere while retaining strict linear $H$-consistency bounds.
• Score: 42.67092904252001
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation [16.106678611834102]
  Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed noise.<n>Existing techniques typically rely on magnitude checks, which fail to distinguish informative geometric signals from outliers.
  arXiv  Detail & Related papers  (2026-06-21T10:57:37Z)
• Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization [0.0]
  Submodular under matroid constraints is a fundamental problem in optimization with applications in sensing, data-marization, active learning, and resource allocation.<n>We propose textitATCG (underlineAdaptive underlineThresholded underlineThresholded underlineGreedy), expanding each agent's active set only when current candidates fail to capture sufficient marginal gain.<n>Experiments on a classbalanced prototype selection problem over a CIFAR-10 animal dataset show that textit
  arXiv  Detail & Related papers  (2026-04-03T19:32:39Z)
• Introducing Fractional Classification Loss for Robust Learning with Noisy Labels [2.312414367096445]
  We introduce Fractional Classification Loss (FCL), an adaptive robust loss that automatically calibrates its robustness to label noise during training.<n>FCL achieves state-of-the-art results without the need for manual hyper parameter tuning.
  arXiv  Detail & Related papers  (2025-08-08T14:20:52Z)
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  We propose a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.<n>By applying our hinge-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution, we achieve a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.
  arXiv  Detail & Related papers  (2025-06-03T06:31:59Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  We show that Prospect, a gradient-based algorithm, enjoys linear convergence for smooth regularized losses. We also show that Prospect can converge 2-3$times$ faster than baselines such as gradient-based methods.
  arXiv  Detail & Related papers  (2023-10-21T00:03:54Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• CoLiDE: Concomitant Linear DAG Estimation [12.415463205960156]
  We deal with the problem of learning acyclic graph structure from observational data to a linear equation. We propose a new convex score function for sparsity-aware learning DAGs.
  arXiv  Detail & Related papers  (2023-10-04T15:32:27Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity [55.29408396918968]
  We study a family of loss functions named label-distributionally robust (LDR) losses for multi-class classification. Our contributions include both consistency and robustness by establishing top-$k$ consistency of LDR losses for multi-class classification. We propose a new adaptive LDR loss that automatically adapts the individualized temperature parameter to the noise degree of class label of each instance.
  arXiv  Detail & Related papers  (2021-12-30T00:27:30Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.