# On Structured Prediction Theory with Calibrated Convex Surrogate Losses

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

## Key facts

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

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [The Structured Abstain Problem and the Lov'asz Hinge](https://mlsanity.com/paper/2203.08645/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction](https://mlsanity.com/paper/2604.27742/) (2026)
- [Tailoring Strictly Proper Scoring Rules for Downstream Tasks: An Application to Causal Inference](https://mlsanity.com/paper/2606.03332/) (2026)
- [Self-Supervised Penalty-Based Learning for Robust Constrained Optimization](https://mlsanity.com/paper/2503.05175/) (2025)
- [Structured Prediction with Abstention via the Lov'asz Hinge](https://mlsanity.com/paper/2505.06446/) (2025)
- [Some Robustness Properties of Label Cleaning](https://mlsanity.com/paper/2509.11379/) (2025)
- [Though Language Models Err While They Strive: Conformal Prediction for Self-Correcting Scientific Generation](https://mlsanity.com/paper/2607.16704/) (2026)
- [When Do Surrogate Updates Improve Decisions? A Local Theory of Trajectory-Wise Transfer](https://mlsanity.com/paper/2608.01130/) (2026)
- [Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classification](https://mlsanity.com/paper/2608.27203/) (2026)
- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## 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.