# Efficient Large-Scale Learning of Minimax Risk Classifiers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 18 Nov 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [The role of regularization in classification of high-dimensional noisy Gaussian mixture](https://mlsanity.com/paper/2002.11544/) (2020)
- [Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization](https://mlsanity.com/paper/1907.04371/) (2019)
- [A Survey on Large-scale Machine Learning](https://mlsanity.com/paper/2008.03911/) (2020)
- [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)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Solving L1-regularized SVMs and related linear programs: Revisiting the effectiveness of Column and Constraint Generation](https://mlsanity.com/paper/1901.01585/) (2019)
- [MRCpy: A Library for Minimax Risk Classifiers](https://mlsanity.com/paper/2108.01952/) (2021)
- [Efficient Learning of Minimax Risk Classifiers in High Dimensions](https://mlsanity.com/paper/2306.06649/) (2023)

## Abstract (arXiv)

Supervised learning with large-scale data usually leads to complex optimization problems, especially for classification tasks with multiple classes. Stochastic subgradient methods can enable efficient learning with a large number of samples for classification techniques that minimize the average loss over the training samples. However, recent techniques, such as minimax risk classifiers (MRCs), minimize the maximum expected loss and are not amenable to stochastic subgradient methods. In this paper, we present a learning algorithm based on the combination of constraint and column generation that enables efficient learning of MRCs with large-scale data for classification tasks with multiple classes. Experiments on multiple benchmark datasets show that the proposed algorithm provides upto a 10x speedup for general large-scale data and around a 100x speedup with a sizeable number of classes.