# Trading off Consistency and Dimensionality of Convex Surrogates for the Mode

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 16 Feb 2024.

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

- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [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)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Solving Marginal MAP Problems with NP Oracles and Parity Constraints](https://mlsanity.com/paper/1610.02591/) (2016)
- [Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogates](https://mlsanity.com/paper/2102.08218/) (2021)
- [Quantifying Learning Guarantees for Convex but Inconsistent Surrogates](https://mlsanity.com/paper/1810.11544/) (2018)

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

- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)

## Abstract (arXiv)

In multiclass classification over n outcomes, the outcomes must be embedded into the reals with dimension at least n-1 in order to design a consistent surrogate loss that leads to the "correct" classification, regardless of the data distribution. For large n, such as in information retrieval and structured prediction tasks, optimizing a surrogate in n-1 dimensions is often intractable. We investigate ways to trade off surrogate loss dimension, the number of problem instances, and restricting the region of consistency in the simplex for multiclass classification. Following past work, we examine an intuitive embedding procedure that maps outcomes into the vertices of convex polytopes in a low-dimensional surrogate space. We show that full-dimensional subsets of the simplex exist around each point mass distribution for which consistency holds, but also, with less than n-1 dimensions, there exist distributions for which a phenomenon called hallucination occurs, which is when the optimal report under the surrogate loss is an outcome with zero probability. Looking towards application, we derive a result to check if consistency holds under a given polytope embedding and low-noise assumption, providing insight into when to use a particular embedding. We provide examples of embedding n = 2d outcomes into the d-dimensional unit cube and n = d! outcomes into the d-dimensional permutahedron under low-noise assumptions. Finally, we demonstrate that with multiple problem instances, we can learn the mode with fracn2 dimensions over the whole simplex.