# A Minimax Approach to Supervised Learning

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2016.

## Built on by (most cited first, 30 of 33)

- [Invariant Information Bottleneck for Domain Generalization](https://mlsanity.com/paper/2106.06333/) (2021)
- [Understanding and Constructing Latent Modality Structures in Multi-modal Representation Learning](https://mlsanity.com/paper/2303.05952/) (2023)
- [Lossy Compression for Lossless Prediction](https://mlsanity.com/paper/2106.10800/) (2021)
- [SimMMDG: A Simple and Effective Framework for Multi-modal Domain Generalization](https://mlsanity.com/paper/2310.19795/) (2023)
- [On Learning Contrastive Representations for Learning with Noisy Labels](https://mlsanity.com/paper/2203.01785/) (2022)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Conditional Supervised Contrastive Learning for Fair Text Classification](https://mlsanity.com/paper/2205.11485/) (2022)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning](https://mlsanity.com/paper/2206.01132/) (2022)
- [Time-series Generation by Contrastive Imitation](https://mlsanity.com/paper/2311.01388/) (2023)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (2022)
- [Nash Equilibria, Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization](https://mlsanity.com/paper/2303.03900/) (2023)
- [Double-Weighting for Covariate Shift Adaptation](https://mlsanity.com/paper/2305.08637/) (2023)
- [Tackling Distribution Shifts in Task-Oriented Communication with Information Bottleneck](https://mlsanity.com/paper/2405.09514/) (2024)
- [Timely Communications for Remote Inference](https://mlsanity.com/paper/2404.16281/) (2024)
- [The Age of Correlated Features in Supervised Learning based Forecasting](https://mlsanity.com/paper/2103.00092/) (2021)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [When Chosen Wisely, More Data Is What You Need: A Universal Sample-Efficient Strategy For Data Augmentation](https://mlsanity.com/paper/2203.09391/) (2022)
- [Deep Neural Network Classifier for Multi-dimensional Functional Data](https://mlsanity.com/paper/2205.08592/) (2022)
- [How Does Data Freshness Affect Real-time Supervised Learning?](https://mlsanity.com/paper/2208.06948/) (2022)
- [Greedy Modality Selection via Approximate Submodular Maximization](https://mlsanity.com/paper/2210.12562/) (2022)
- [The Maximum von Neumann Entropy Principle: Theory and Applications in Machine Learning](https://mlsanity.com/paper/2602.02117/) (2026)
- [A Local Geometric Interpretation of Feature Extraction in Deep Feedforward Neural Networks](https://mlsanity.com/paper/2202.04632/) (2022)
- [Minimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees](https://mlsanity.com/paper/2310.15974/) (2023)
- [Estimating Joint Interventional Distributions from Marginal Interventional Data](https://mlsanity.com/paper/2409.01794/) (2024)
- [The Wyner Variational Autoencoder for Unsupervised Multi-Layer Wireless Fingerprinting](https://mlsanity.com/paper/2303.15860/) (2023)
- [A representation-learning game for classes of prediction tasks](https://mlsanity.com/paper/2403.06971/) (2024)
- [Measuring Stochastic Data Complexity with Boltzmann Influence Functions](https://mlsanity.com/paper/2406.02745/) (2024)
- [Robust Multispectral Semantic Segmentation under Missing or Full Modalities via Structured Latent Projection](https://mlsanity.com/paper/2604.15856/) (2026)

## Abstract (arXiv)

Given a task of predicting Y from X, a loss function L, and a set of probability distributions Gamma on (X,Y), what is the optimal decision rule minimizing the worst-case expected loss over Gamma? In this paper, we address this question by introducing a generalization of the principle of maximum entropy. Applying this principle to sets of distributions with marginal on X constrained to be the empirical marginal from the data, we develop a general minimax approach for supervised learning problems. While for some loss functions such as squared-error and log loss, the minimax approach rederives well-knwon regression models, for the 0-1 loss it results in a new linear classifier which we call the maximum entropy machine. The maximum entropy machine minimizes the worst-case 0-1 loss over the structured set of distribution, and by our numerical experiments can outperform other well-known linear classifiers such as SVM. We also prove a bound on the generalization worst-case error in the minimax approach.