# Binary Excess Risk for Smooth Convex Surrogates

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2014.

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

- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds](https://mlsanity.com/paper/2511.15816/) (2025)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Adversarial Surrogate Risk Bounds for Binary Classification](https://mlsanity.com/paper/2506.09348/) (2025)

## Abstract (arXiv)

In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by attaining an it optimal convergence rate for optimization, and in a statistical sense- by providing an improved it optimistic rate for generalization bound. In this paper we investigate the smoothness property from the viewpoint of statistical consistency and show how it affects the binary excess risk. We show that in contrast to optimization and generalization errors that favor the choice of smooth surrogate loss, the smoothness of loss function may degrade the binary excess risk. Motivated by this negative result, we provide a unified analysis that integrates optimization error, generalization bound, and the error in translating convex excess risk into a binary excess risk when examining the impact of smoothness on the binary excess risk. We show that under favorable conditions appropriate choice of smooth convex loss will result in a binary excess risk that is better than O(1/√n).