# Minimax Classification with 0-1 Loss and Performance Guarantees

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2020.

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

- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [MRCpy: A Library for Minimax Risk Classifiers](https://mlsanity.com/paper/2108.01952/) (2021)
- [Deep Neural Network Classifier for Multi-dimensional Functional Data](https://mlsanity.com/paper/2205.08592/) (2022)
- [Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees](https://mlsanity.com/paper/2205.15942/) (2022)
- [Solving Constrained Variational Inequalities via a First-order Interior Point-based Method](https://mlsanity.com/paper/2206.10575/) (2022)
- [Efficient Learning of Minimax Risk Classifiers in High Dimensions](https://mlsanity.com/paper/2306.06649/) (2023)
- [Minimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees](https://mlsanity.com/paper/2310.15974/) (2023)
- [On the Hypomonotone Class of Variational Inequalities](https://mlsanity.com/paper/2410.09182/) (2024)
- [Reliable Programmatic Weak Supervision with Confidence Intervals for Label Probabilities](https://mlsanity.com/paper/2508.03896/) (2025)
- [Efficient Large-Scale Learning of Minimax Risk Classifiers](https://mlsanity.com/paper/2511.17626/) (2025)
- [Minimax Generalized Cross-Entropy](https://mlsanity.com/paper/2603.19874/) (2026)

## Abstract (arXiv)

Supervised classification techniques use training samples to find classification rules with small expected 0-1 loss. Conventional methods achieve efficient learning and out-of-sample generalization by minimizing surrogate losses over specific families of rules. This paper presents minimax risk classifiers (MRCs) that do not rely on a choice of surrogate loss and family of rules. MRCs achieve efficient learning and out-of-sample generalization by minimizing worst-case expected 0-1 loss w.r.t. uncertainty sets that are defined by linear constraints and include the true underlying distribution. In addition, MRCs' learning stage provides performance guarantees as lower and upper tight bounds for expected 0-1 loss. We also present MRCs' finite-sample generalization bounds in terms of training size and smallest minimax risk, and show their competitive classification performance w.r.t. state-of-the-art techniques using benchmark datasets.