# Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogates

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 34 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [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)

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

- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [A Survey of Learning Criteria Going Beyond the Usual Risk](https://mlsanity.com/paper/2110.04996/) (2021)
- [OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression](https://mlsanity.com/paper/2105.13271/) (2021)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)

## Abstract (arXiv)

Given a prediction task, understanding when one can and cannot design a consistent convex surrogate loss, particularly a low-dimensional one, is an important and active area of machine learning research. The prediction task may be given as a target loss, as in classification and structured prediction, or simply as a (conditional) statistic of the data, as in risk measure estimation. These two scenarios typically involve different techniques for designing and analyzing surrogate losses. We unify these settings using tools from property elicitation, and give a general lower bound on prediction dimension. Our lower bound tightens existing results in the case of discrete predictions, showing that previous calibration-based bounds can largely be recovered via property elicitation. For continuous estimation, our lower bound resolves on open problem on estimating measures of risk and uncertainty.