# An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 65 references that are in the map.
- First posted on arXiv 29 Jun 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer](https://mlsanity.com/paper/1711.06664/) (2017)
- [Smooth Loss Functions for Deep Top-k Classification](https://mlsanity.com/paper/1802.07595/) (2018)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [A Minimax Approach to Supervised Learning](https://mlsanity.com/paper/1606.02206/) (2016)
- [Stochastic Negative Mining for Learning with Large Output Spaces](https://mlsanity.com/paper/1810.07076/) (2018)
- [Top-k Multiclass SVM](https://mlsanity.com/paper/1511.06683/) (2015)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification](https://mlsanity.com/paper/1612.03663/) (2016)
- [Convex Calibrated Surrogates for the Multi-Label F-Measure](https://mlsanity.com/paper/2009.07801/) (2020)
- [The Lov'asz Hinge: A Novel Convex Surrogate for Submodular Losses](https://mlsanity.com/paper/1512.07797/) (2015)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Weston-Watkins Hinge Loss and Ordered Partitions](https://mlsanity.com/paper/2006.07346/) (2020)
- [The Structured Abstain Problem and the Lov'asz Hinge](https://mlsanity.com/paper/2203.08645/) (2022)
- [On the Consistency of Max-Margin Losses](https://mlsanity.com/paper/2105.15069/) (2021)
- [Consistent Robust Adversarial Prediction for General Multiclass Classification](https://mlsanity.com/paper/1812.07526/) (2018)

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (2022)
- [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (2025)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)
- [Contrasting Cost-Agnostic and Cost-Sensitive Losses under Limited Model Capacity via mathcal H-consistency](https://mlsanity.com/paper/2502.19522/) (2025)
- [Consistency Conditions for Differentiable Surrogate Losses](https://mlsanity.com/paper/2505.13760/) (2025)
- [Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss](https://mlsanity.com/paper/2608.08399/) (2026)
- [Estimation of embedding vectors in high dimensions](https://mlsanity.com/paper/2312.07802/) (2023)
- [Structured Prediction with Abstention via the Lov'asz Hinge](https://mlsanity.com/paper/2505.06446/) (2025)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (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 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 Rd, 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: every discrete loss is embedded by some polyhedral loss, and every polyhedral loss embeds some discrete loss. Moreover, an embedding gives rise to a consistent link function as well as linear surrogate regret bounds. Our results are constructive, as we illustrate with several examples. In particular, our framework gives succinct proofs of consistency or inconsistency for various polyhedral surrogates in the literature, and for inconsistent surrogates, it further reveals the discrete losses for which these surrogates are consistent. We go on to show 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.