# An Embedding Framework for Consistent Polyhedral Surrogates

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

## Key facts

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

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (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)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Regression with Cost-based Rejection](https://mlsanity.com/paper/2311.04550/) (2023)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (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)
- [Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds](https://mlsanity.com/paper/2511.15816/) (2025)
- [On Classification-Calibration of Gamma-Phi Losses](https://mlsanity.com/paper/2302.07321/) (2023)
- [On the Consistency of Max-Margin Losses](https://mlsanity.com/paper/2105.15069/) (2021)
- [Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogates](https://mlsanity.com/paper/2102.08218/) (2021)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Learning from Positive and Unlabeled Data with Augmented Classes](https://mlsanity.com/paper/2207.13274/) (2022)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)
- [Consistency Conditions for Differentiable Surrogate Losses](https://mlsanity.com/paper/2505.13760/) (2025)
- [Using Property Elicitation to Understand the Impacts of Fairness Regularizers](https://mlsanity.com/paper/2309.11343/) (2023)
- [Structured Prediction with Abstention via the Lov'asz Hinge](https://mlsanity.com/paper/2505.06446/) (2025)
- [SentAttack: A Sentence-Level Black-Box Adversarial Attack Method for Dense Retrieval Models](https://mlsanity.com/paper/2607.03456/) (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)

## Abstract (arXiv)

We formalize and study the natural approach of designing convex surrogate loss functions via embeddings, for problems such as classification, ranking, or structured prediction. In this approach, one embeds each of the finitely many predictions (e.g. rankings) as a point in ℝd, assigns the original loss values to these points, and "convexifies" the loss in some way to obtain a surrogate. We establish a strong connection between this approach and polyhedral (piecewise-linear convex) surrogate losses. Given any polyhedral loss L, we give a construction of a link function through which L is a consistent surrogate for the loss it embeds. Conversely, we show how to construct a consistent polyhedral surrogate for any given discrete loss. Our framework yields succinct proofs of consistency or inconsistency of various polyhedral surrogates in the literature, and for inconsistent surrogates, it further reveals the discrete losses for which these surrogates are consistent. We show some additional structure of embeddings, such as the equivalence of embedding and matching Bayes risks, and the equivalence of various notions of non-redudancy. Using these results, we establish that indirect elicitation, a necessary condition for consistency, is also sufficient when working with polyhedral surrogates.