# Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 102 references that are in the map.
- First posted on arXiv 14 May 2025.

## Builds on (most cited first, 30 of 50)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [On Symmetric Losses for Learning from Corrupted Labels](https://mlsanity.com/paper/1901.09314/) (2019)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [The Elements of Differentiable Programming](https://mlsanity.com/paper/2403.14606/) (2024)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [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)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [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)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [Convex Calibrated Surrogates for the Multi-Label F-Measure](https://mlsanity.com/paper/2009.07801/) (2020)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Bounds](https://mlsanity.com/paper/1702.02030/) (2017)
- [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)

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

- [Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction](https://mlsanity.com/paper/2604.27742/) (2026)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)

## Abstract (arXiv)

Surrogate regret bounds, also known as excess risk bounds, bridge the gap between the convergence rates of surrogate and target losses. The regret transfer is lossless if the surrogate regret bound is linear. While convex smooth surrogate losses are appealing in particular due to the efficient estimation and optimization, the existence of a trade-off between the loss smoothness and linear regret bound has been believed in the community. Under this scenario, the better optimization and estimation properties of convex smooth surrogate losses may inevitably deteriorate after undergoing the regret transfer onto a target loss. We overcome this dilemma for arbitrary discrete target losses by constructing a convex smooth surrogate loss, which entails a linear surrogate regret bound composed with a tailored prediction link. The construction is based on Fenchel--Young losses generated by the convolutional negentropy, which are equivalent to the infimal convolution of a generalized negentropy and the target Bayes risk. Consequently, the infimal convolution enables us to derive a smooth loss while maintaining the surrogate regret bound linear. We additionally benefit from the infimal convolution to have a consistent estimator of the underlying class probability. Our results are overall a novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.