# Minimax risk classifiers with 0-1 loss

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 78 references that are in the map.
- First posted on arXiv 17 Jan 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [A Minimax Approach to Supervised Learning](https://mlsanity.com/paper/1606.02206/) (2016)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Incorporating Unlabeled Data into Distributionally Robust Learning](https://mlsanity.com/paper/1912.07729/) (2019)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [Generalized Maximum Entropy for Supervised Classification](https://mlsanity.com/paper/2007.05447/) (2020)
- [Minimax Classification with 0-1 Loss and Performance Guarantees](https://mlsanity.com/paper/2010.07964/) (2020)
- [Optimally Combining Classifiers Using Unlabeled Data](https://mlsanity.com/paper/1503.01811/) (2015)
- [The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization](https://mlsanity.com/paper/2006.04340/) (2020)
- [Optimal Binary Classifier Aggregation for General Losses](https://mlsanity.com/paper/1510.00452/) (2015)
- [MRCpy: A Library for Minimax Risk Classifiers](https://mlsanity.com/paper/2108.01952/) (2021)
- [General Supervision via Probabilistic Transformations](https://mlsanity.com/paper/1901.08552/) (2019)

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

- [Double-Weighting for Covariate Shift Adaptation](https://mlsanity.com/paper/2305.08637/) (2023)
- [Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees](https://mlsanity.com/paper/2205.15942/) (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)
- [Safe Fairness Guarantees Without Demographics in Classification: Spectral Uncertainty Set Perspective](https://mlsanity.com/paper/2602.11785/) (2026)
- [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)
- [NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision](https://mlsanity.com/paper/2607.08961/) (2026)
- [IIns-VAE+: A Robust Transfer Learning Framework for Environmental Identification in Wireless Sensing](https://mlsanity.com/paper/2609.06131/) (2026)

## Abstract (arXiv)

Supervised classification techniques use training samples to learn a classification rule with small expected 0-1 loss (error probability). Conventional methods enable tractable learning and provide out-of-sample generalization by using surrogate losses instead of the 0-1 loss and considering specific families of rules (hypothesis classes). This paper presents minimax risk classifiers (MRCs) that minize the worst-case 0-1 loss with respect to uncertainty sets of distributions that can include the underlying distribution, with a tunable confidence. We show that MRCs can provide tight performance guarantees at learning and are strongly universally consistent using feature mappings given by characteristic kernels. The paper also proposes efficient optimization techniques for MRC learning and shows that the methods presented can provide accurate classification together with tight performance guarantees in practice.