mlsanityData to 7 Oct 2026

On Structured Prediction Theory with Calibrated Convex Surrogate Losses

arXiv 1703.02403 ↗First posted 7 Mar 2017cs.LG stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

We provide novel theoretical insights on structured prediction in the context of efficient convex surrogate loss minimization with consistency guarantees. For any task loss, we construct a convex surrogate that can be optimized via stochastic gradient descent and we prove tight bounds on the so-called "calibration function" relating the excess surrogate risk to the actual risk. In contrast to prior related work, we carefully monitor the effect of the exponential number of classes in the learning guarantees as well as on the optimization complexity. As an interesting consequence, we formalize the intuition that some task losses make learning harder than others, and that the classical 0-1 loss is ill-suited for general structured prediction.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 2; 2024: 5; 2025: 4; 2026: 6.

23 papers.

Sort:

By area:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
  2. 2021Risk Bounds and Calibration for a Smart Predict-then-Optimize Methodcited by 28
  3. 2024A Universal Growth Rate for Learning with Smooth Surrogate Lossescited by 24
  4. 2024H-Consistency Guarantees for Regressioncited by 21
  5. 2021Contextual Inverse Optimization: Offline and Online Learningcited by 20
  6. 2024Enhanced H-Consistency Boundscited by 18
  7. 2021Surrogate Regret Bounds for Polyhedral Lossescited by 15
  8. 2022An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogatescited by 14
  9. 2022Learning Energy Networks with Generalized Fenchel-Young Lossescited by 8
  10. 2022The Structured Abstain Problem and the Lov'asz Hingecited by 7
  11. 2024Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Losscited by 7
  12. 2023Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernelscited by 5
11 more
  1. 2024Proper losses regret at least 1/2-ordercited by 3
  2. 2025Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Lossescited by 2
  3. 2026Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Predictioncited by 2
  4. 2026Tailoring Strictly Proper Scoring Rules for Downstream Tasks: An Application to Causal Inferencecited by 1
  5. 2025Self-Supervised Penalty-Based Learning for Robust Constrained Optimizationcited by 0
  6. 2025Structured Prediction with Abstention via the Lov'asz Hingecited by 0
  7. 2025Some Robustness Properties of Label Cleaningcited by 0
  8. 2026Though Language Models Err While They Strive: Conformal Prediction for Self-Correcting Scientific Generationcited by 0
  9. 2026When Do Surrogate Updates Improve Decisions? A Local Theory of Trajectory-Wise Transfercited by 0
  10. 2026Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classificationcited by 0
  11. 2026Geometric Identification in Predict-Then-Optimize Learningcited by 0