# A General Theory for Structured Prediction with Smooth Convex Surrogates

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

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

- [Sample Efficient Learning of Predictors that Complement Humans](https://mlsanity.com/paper/2207.09584/) (2022)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Lower-Bounded Proper Losses for Weakly Supervised Classification](https://mlsanity.com/paper/2103.02893/) (2021)
- [A Statistical Learning Take on the Concordance Index for Survival Analysis](https://mlsanity.com/paper/2302.12059/) (2023)
- [Open Problem: Learning with Variational Objectives on Measures](https://mlsanity.com/paper/2306.11928/) (2023)
- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## Abstract (arXiv)

In this work we provide a theoretical framework for structured prediction that generalizes the existing theory of surrogate methods for binary and multiclass classification based on estimating conditional probabilities with smooth convex surrogates (e.g. logistic regression). The theory relies on a natural characterization of structural properties of the task loss and allows to derive statistical guarantees for many widely used methods in the context of multilabeling, ranking, ordinal regression and graph matching. In particular, we characterize the smooth convex surrogates compatible with a given task loss in terms of a suitable Bregman divergence composed with a link function. This allows to derive tight bounds for the calibration function and to obtain novel results on existing surrogate frameworks for structured prediction such as conditional random fields and quadratic surrogates.