# Minimizing the Maximal Loss: How and Why?

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2016.

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

- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Sum of Ranked Range Loss for Supervised Learning](https://mlsanity.com/paper/2106.03300/) (2021)
- [Gen-DFL: Decision-Focused Generative Learning for Robust Decision Making](https://mlsanity.com/paper/2502.05468/) (2025)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [DisCO: Reinforcing Large Reasoning Models with Discriminative Constrained Optimization](https://mlsanity.com/paper/2505.12366/) (2025)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity](https://mlsanity.com/paper/2112.14869/) (2021)
- [A Simple Yet Effective Strategy to Robustify the Meta Learning Paradigm](https://mlsanity.com/paper/2310.00708/) (2023)
- [Min-Max Bilevel Multi-objective Optimization with Applications in Machine Learning](https://mlsanity.com/paper/2203.01924/) (2022)
- [Spectral risk-based learning using unbounded losses](https://mlsanity.com/paper/2105.04816/) (2021)
- [AutoMixAlign: Adaptive Data Mixing for Multi-Task Preference Optimization in LLMs](https://mlsanity.com/paper/2506.00569/) (2025)
- [Topology-aware Robust Optimization for Out-of-distribution Generalization](https://mlsanity.com/paper/2307.13943/) (2023)
- [Uncertainty-Aware Robust Learning on Noisy Graphs](https://mlsanity.com/paper/2306.08210/) (2023)
- [Deep Backward and Galerkin Methods for the Finite State Master Equation](https://mlsanity.com/paper/2403.04975/) (2024)
- [A Model-Based Method for Minimizing CVaR and Beyond](https://mlsanity.com/paper/2305.17498/) (2023)
- [A Survey of Learning Criteria Going Beyond the Usual Risk](https://mlsanity.com/paper/2110.04996/) (2021)
- [Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization](https://mlsanity.com/paper/2111.15645/) (2021)
- [Revisiting adversarial training for the worst-performing class](https://mlsanity.com/paper/2302.08872/) (2023)
- [Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport](https://mlsanity.com/paper/2103.05857/) (2021)
- [Minimizing Worst-Case Violations of Neural Networks](https://mlsanity.com/paper/2212.10930/) (2022)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Efficient Online-Bandit Strategies for Minimax Learning Problems](https://mlsanity.com/paper/2105.13939/) (2021)
- [Convergence of the Deep Galerkin Method for Finite State Mean Field Control Problems](https://mlsanity.com/paper/2405.13346/) (2024)
- [UniPROT: Uniform Prototype Selection via Partial Optimal Transport with Submodular Guarantees](https://mlsanity.com/paper/2604.10952/) (2026)
- [OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation](https://mlsanity.com/paper/2606.06096/) (2026)
- [Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe](https://mlsanity.com/paper/2605.15350/) (2026)
- [Fair Graph Machine Learning under Adversarial Missingness Processes](https://mlsanity.com/paper/2311.01591/) (2023)
- [Data-Efficient Training by Evolved Sampling](https://mlsanity.com/paper/2509.23461/) (2025)

## Abstract (arXiv)

A commonly used learning rule is to approximately minimize the average loss over the training set. Other learning algorithms, such as AdaBoost and hard-SVM, aim at minimizing the maximal loss over the training set. The average loss is more popular, particularly in deep learning, due to three main reasons. First, it can be conveniently minimized using online algorithms, that process few examples at each iteration. Second, it is often argued that there is no sense to minimize the loss on the training set too much, as it will not be reflected in the generalization loss. Last, the maximal loss is not robust to outliers. In this paper we describe and analyze an algorithm that can convert any online algorithm to a minimizer of the maximal loss. We prove that in some situations better accuracy on the training set is crucial to obtain good performance on unseen examples. Last, we propose robust versions of the approach that can handle outliers.