# Unified Binary and Multiclass Margin-Based Classification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2023.

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

- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [A Boundary-Layer Mechanism for One-Third Scaling in Online Softmax Classification](https://mlsanity.com/paper/2605.22341/) (2026)
- [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)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)

## Abstract (arXiv)

The notion of margin loss has been central to the development and analysis of algorithms for binary classification. To date, however, there remains no consensus as to the analogue of the margin loss for multiclass classification. In this work, we show that a broad range of multiclass loss functions, including many popular ones, can be expressed in the relative margin form, a generalization of the margin form of binary losses. The relative margin form is broadly useful for understanding and analyzing multiclass losses as shown by our prior work (Wang and Scott, 2020, 2021). To further demonstrate the utility of this way of expressing multiclass losses, we use it to extend the seminal result of Bartlett et al. (2006) on classification-calibration of binary margin losses to multiclass. We then analyze the class of Fenchel-Young losses, and expand the set of these losses that are known to be classification-calibrated.