# Proper losses regret at least 1/2-order

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 83 references that are in the map.
- First posted on arXiv 15 Jul 2024.

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

- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Understanding Emergent Abilities of Language Models from the Loss Perspective](https://mlsanity.com/paper/2403.15796/) (2024)
- [Better Uncertainty Calibration via Proper Scores for Classification and Beyond](https://mlsanity.com/paper/2203.07835/) (2022)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Structured Prediction with Projection Oracles](https://mlsanity.com/paper/1910.11369/) (2019)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Surrogate regret bounds for generalized classification performance metrics](https://mlsanity.com/paper/1504.07272/) (2015)
- [Two-temperature logistic regression based on the Tsallis divergence](https://mlsanity.com/paper/1705.07210/) (2017)
- [A Tunable Loss Function for Binary Classification](https://mlsanity.com/paper/1902.04639/) (2019)
- [Being Properly Improper](https://mlsanity.com/paper/2106.09920/) (2021)
- [Pairwise Supervision Can Provably Elicit a Decision Boundary](https://mlsanity.com/paper/2006.06207/) (2020)
- [Beyond Strictly Proper Scoring Rules: The Importance of Being Local](https://mlsanity.com/paper/2012.12499/) (2020)
- [Unified Binary and Multiclass Margin-Based Classification](https://mlsanity.com/paper/2311.17778/) (2023)
- [The Geometry and Calculus of Losses](https://mlsanity.com/paper/2209.00238/) (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)
- [Convex Risk Minimization and Conditional Probability Estimation](https://mlsanity.com/paper/1506.04513/) (2015)
- [Consistency and Finite Sample Behavior of Binary Class Probability Estimation](https://mlsanity.com/paper/1908.11823/) (2019)

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

- [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)
- [Brenier Isotonic Regression](https://mlsanity.com/paper/2603.10452/) (2026)

## Abstract (arXiv)

A fundamental challenge in machine learning is the choice of a loss as it characterizes our learning task, is minimized in the training phase, and serves as an evaluation criterion for estimators. Proper losses are commonly chosen, ensuring minimizers of the full risk match the true probability vector. Estimators induced from a proper loss are widely used to construct forecasters for downstream tasks such as classification and ranking. In this procedure, how does the forecaster based on the obtained estimator perform well under a given downstream task? This question is substantially relevant to the behavior of the p-norm between the estimated and true probability vectors when the estimator is updated. In the proper loss framework, the suboptimality of the estimated probability vector from the true probability vector is measured by a surrogate regret. First, we analyze a surrogate regret and show that the strict properness of a loss is necessary and sufficient to establish a non-vacuous surrogate regret bound. Second, we solve an important open question that the order of convergence in p-norm cannot be faster than the 1/2-order of surrogate regrets for a broad class of strictly proper losses. This implies that strongly proper losses entail the optimal convergence rate.