# Surrogate Regret Bounds for Polyhedral Losses

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 26 Oct 2021.

## Builds on (most cited first, 14 of 14)

- [Classification with Rejection Based on Cost-sensitive Classification](https://mlsanity.com/paper/2010.11748/) (2020)
- [On the Calibration of Multiclass Classification with Rejection](https://mlsanity.com/paper/1901.10655/) (2019)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [On the Consistency of Ordinal Regression Methods](https://mlsanity.com/paper/1408.2327/) (2014)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [An Embedding Framework for Consistent Polyhedral Surrogates](https://mlsanity.com/paper/1907.07330/) (2019)
- [Structured Prediction with Projection Oracles](https://mlsanity.com/paper/1910.11369/) (2019)
- [The Lov'asz Hinge: A Novel Convex Surrogate for Submodular Losses](https://mlsanity.com/paper/1512.07797/) (2015)
- [A General Theory for Structured Prediction with Smooth Convex Surrogates](https://mlsanity.com/paper/1902.01958/) (2019)
- [Weston-Watkins Hinge Loss and Ordered Partitions](https://mlsanity.com/paper/2006.07346/) (2020)
- [Binary Excess Risk for Smooth Convex Surrogates](https://mlsanity.com/paper/1402.1792/) (2014)
- [On the Rates of Convergence from Surrogate Risk Minimizers to the Bayes Optimal Classifier](https://mlsanity.com/paper/1802.03688/) (2018)

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [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)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (2022)
- [Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds](https://mlsanity.com/paper/2511.15816/) (2025)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [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)
- [Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses](https://mlsanity.com/paper/2502.04889/) (2025)
- [Contrasting Cost-Agnostic and Cost-Sensitive Losses under Limited Model Capacity via mathcal H-consistency](https://mlsanity.com/paper/2502.19522/) (2025)
- [Adversarial Surrogate Risk Bounds for Binary Classification](https://mlsanity.com/paper/2506.09348/) (2025)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)
- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## Abstract (arXiv)

Surrogate risk minimization is an ubiquitous paradigm in supervised machine learning, wherein a target problem is solved by minimizing a surrogate loss on a dataset. Surrogate regret bounds, also called excess risk bounds, are a common tool to prove generalization rates for surrogate risk minimization. While surrogate regret bounds have been developed for certain classes of loss functions, such as proper losses, general results are relatively sparse. We provide two general results. The first gives a linear surrogate regret bound for any polyhedral (piecewise-linear and convex) surrogate, meaning that surrogate generalization rates translate directly to target rates. The second shows that for sufficiently non-polyhedral surrogates, the regret bound is a square root, meaning fast surrogate generalization rates translate to slow rates for the target. Together, these results suggest polyhedral surrogates are optimal in many cases.