# Minimax Regret Optimization for Robust Machine Learning under Distribution Shift

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 51 references that are in the map.
- First posted on arXiv 11 Feb 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [A Survey on Deep Transfer Learning](https://mlsanity.com/paper/1808.01974/) (2018)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [The Risks of Invariant Risk Minimization](https://mlsanity.com/paper/2010.05761/) (2020)
- [Invariant Risk Minimization Games](https://mlsanity.com/paper/2002.04692/) (2020)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [Doubly Robust Policy Evaluation and Optimization](https://mlsanity.com/paper/1503.02834/) (2015)
- [Distributionally Robust Language Modeling](https://mlsanity.com/paper/1909.02060/) (2019)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Does Invariant Risk Minimization Capture Invariance?](https://mlsanity.com/paper/2101.01134/) (2021)
- [Doubly robust off-policy evaluation with shrinkage](https://mlsanity.com/paper/1907.09623/) (2019)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Empirical or Invariant Risk Minimization? A Sample Complexity Perspective](https://mlsanity.com/paper/2010.16412/) (2020)
- [Class-Weighted Classification: Trade-offs and Robust Approaches](https://mlsanity.com/paper/2005.12914/) (2020)
- [Kernel Distributionally Robust Optimization](https://mlsanity.com/paper/2006.06981/) (2020)

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

- [Out-of-distribution Detection with Implicit Outlier Transformation](https://mlsanity.com/paper/2303.05033/) (2023)
- [A Short Survey on Importance Weighting for Machine Learning](https://mlsanity.com/paper/2403.10175/) (2024)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Minimax Regret Learning for Data with Heterogeneous Subgroups](https://mlsanity.com/paper/2405.01709/) (2024)
- [Causality Pursuit from Heterogeneous Environments via Neural Adversarial Invariance Learning](https://mlsanity.com/paper/2405.04715/) (2024)
- [Strategic Distribution Shift of Interacting Agents via Coupled Gradient Flows](https://mlsanity.com/paper/2307.01166/) (2023)
- [Geometry-Calibrated DRO: Combating Over-Pessimism with Free Energy Implications](https://mlsanity.com/paper/2311.05054/) (2023)
- [Minimax Regret Estimation for Generalizing Heterogeneous Treatment Effects with Multisite Data](https://mlsanity.com/paper/2412.11136/) (2024)
- [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (2025)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [Distributionally Robust Learning for Multi-source Unsupervised Domain Adaptation](https://mlsanity.com/paper/2309.02211/) (2023)
- [Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning](https://mlsanity.com/paper/2401.12216/) (2024)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [Robust Offline Policy Learning with Observational Data from Multiple Sources](https://mlsanity.com/paper/2410.08537/) (2024)
- [Maximum Risk Minimization with Random Forests](https://mlsanity.com/paper/2512.10445/) (2025)
- [On the Stability and Generalization of Triplet Learning](https://mlsanity.com/paper/2302.09815/) (2023)
- [HAR-DoReMi: Optimizing Data Mixture for Self-Supervised Human Activity Recognition Across Heterogeneous IMU Datasets](https://mlsanity.com/paper/2503.13542/) (2025)
- [Wasserstein Distributionally Robust Regret Optimization](https://mlsanity.com/paper/2504.10796/) (2025)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [Towards Independence Criterion in Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2403.08124/) (2024)
- [Taking a Moment for Distributional Robustness](https://mlsanity.com/paper/2405.05461/) (2024)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)
- [Anchor PCA](https://mlsanity.com/paper/2606.06233/) (2026)
- [Robust Learning of a Group DRO Neuron](https://mlsanity.com/paper/2601.18115/) (2026)
- [Maximin Relative Improvement: Fair Learning as a Bargaining Problem](https://mlsanity.com/paper/2602.04155/) (2026)
- [Risk-Averse Wasserstein Distributionally Robust Online Learning](https://mlsanity.com/paper/2602.20403/) (2026)
- [Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2605.00155/) (2026)

## Abstract (arXiv)

In this paper, we consider learning scenarios where the learned model is evaluated under an unknown test distribution which potentially differs from the training distribution (i.e. distribution shift). The learner has access to a family of weight functions such that the test distribution is a reweighting of the training distribution under one of these functions, a setting typically studied under the name of Distributionally Robust Optimization (DRO). We consider the problem of deriving regret bounds in the classical learning theory setting, and require that the resulting regret bounds hold uniformly for all potential test distributions. We show that the DRO formulation does not guarantee uniformly small regret under distribution shift. We instead propose an alternative method called Minimax Regret Optimization (MRO), and show that under suitable conditions this method achieves uniformly low regret across all test distributions. We also adapt our technique to have stronger guarantees when the test distributions are heterogeneous in their similarity to the training data. Given the widespead optimization of worst case risks in current approaches to robust machine learning, we believe that MRO can be a strong alternative to address distribution shift scenarios.