Minimax Optimization for Worst Case Group Fairness

160 concepts103 papers1 proposal

Standard machine learning models are utilitarian by design. When we train a model using Empirical Risk Minimization (ERM), we instruct the optimization algorithm to minimize the average loss across the entire dataset. While this strategy maximizes global utility, it introduces a dangerous vulnerability: the "tyranny of the majority." If a specific demographic subgroup represents only a small fraction of the population, the model can suffer catastrophic error rates on that minority group while still achieving an excellent global average.

To bridge this fairness divide, a rapidly growing body of research shifts the optimization paradigm from average-case utility to worst-case equity. Rooted in the Rawlsian philosophy of distributive justice, Minimax Fairness Optimization reframes model training to prioritize the welfare of the most disadvantaged group. Instead of asking how well a model performs on average, minimax optimization asks: How poorly does the model perform on its worst-served group, and how can we minimize that maximum harm?


The Intuition: From Averages to the Worst Case

To understand why minimax fairness works, consider a classification problem where the population is divided into several demographic groups $G$. Under standard ERM, the objective is to minimize the expected loss over all individuals:

$$\min_{\theta} \sum_{g \in G} P(g) \cdot \mathcal{L}_g(\theta)$$

If a marginalized group $g_{\text{minority}}$ has a very small prior probability $P(g_{\text{minority}})$, its contribution to the gradient updates is negligible. The model will gladly sacrifice accuracy on this subgroup to eke out minor performance gains on a larger majority group.

Minimax optimization eliminates the population weight $P(g)$ from the core objective. It reformulates the training process as a two-player zero-sum game between the model developer and an adversarial critic. The critic examines the model's performance across all groups and isolates the group experiencing the highest loss. The model developer must then adjust the parameters $\theta$ to minimize the loss of that specific group. The mathematical objective becomes:

$$\min_{\theta} \max_{g \in G} \mathcal{L}_g(\theta)$$

By focusing entirely on the maximum loss across all sub-populations, this framework ensures that model updates directly benefit the groups with the highest error rates. As Usman Gohar et al. note in their survey on intersectional fairness, this mechanism naturally extends to intersectional groups (e.g., combinations of race and gender), where data sparsity often causes standard models to fail completely.


Leveling Up vs. Leveling Down

A common critique of traditional algorithmic fairness metrics—such as statistical parity or equalized odds—is that they often enforce fairness through "leveling down." If Group A has an accuracy of 95% and Group B has an accuracy of 70%, a strict parity constraint can be satisfied by intentionally degrading the performance of Group A down to 70%. This satisfies the mathematical definition of equality, but it harms the majority without helping the minority.

Minimax optimization inherently avoids this ethical and practical pitfall. Because the objective is to minimize the maximum loss, the optimizer is only incentivized to improve the absolute performance of the worst-off group.

As demonstrated by Jacob Abernethy et al. in Active Sampling for Min-Max Fairness, the minimax objective only impacts high-performing groups when resource constraints or model capacity limits make it strictly necessary to trade off performance to reduce the maximum loss. In their work on black-box model adaptation, Kulin Shah et al. show that prioritizing the worst-off group allows models to achieve substantial fairness gains without experiencing the arbitrary performance degradation typical of parity-based constraints.


Algorithmic Mechanisms: How Minimax Models Learn

Optimizing a minimax objective is computationally challenging because the $\max$ operator introduces non-differentiability. Researchers have developed several distinct strategies to make minimax optimization tractable and efficient.

1. Adaptive and Active Sampling

Rather than modifying the loss function directly, one intuitive approach is to modify the data distribution the model sees during training. If a model is performing poorly on a specific group, the system should actively collect or sample more data from that group to force the model to adapt.

[Uniform Dataset] ──> [Evaluate Group Losses] ──> [Identify Highest Loss Group]
         ▲                                                     │
         └────────────────── [Adjust Sampling Weights] ────────┘

Shubhanshu Shekhar developed an adaptive sampling framework based on Upper Confidence Bounds (UCB) to dynamically allocate data collection resources to harder-to-classify minority groups in Adaptive Sampling for Minimax Fair Classification. Similarly, the active sampling method by Jacob Abernethy et al. adaptively pulls batches from the group currently suffering the highest loss, accelerating convergence toward the minimax optimal solution.

2. Differentiable Relaxations and Tail-Risk Control

When demographic labels are unavailable or the group structure is fluid, optimizing the strict maximum loss becomes impossible. To circumvent this, researchers leverage smooth relaxations that focus on the "tail" of the loss distribution.


Refining the Objective: Excess Risk and Pareto Efficiency

While the pure minimax objective ($\min \max \mathcal{L}_g$) is powerful, it suffers from two major theoretical limitations in real-world applications: the problem of inherent difficulty and the problem of unoptimized majorities.

Accounting for Inherent Difficulty via Excess Risk

Imagine a scenario where Group A is highly predictable (e.g., clean data, clear patterns), while Group B is inherently noisy (e.g., low-resolution sensors). Even an optimal model specifically trained on Group B might only achieve a minimum error rate of 30%. A pure minimax optimizer will get stuck spending all its capacity trying to lower Group B's loss below 30%, completely ignoring Group A, even if Group A's performance could be easily improved.

To solve this, Dingzhi Yu demonstrates in Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond that it is often superior to optimize for minimax excess risk. Excess risk measures the gap between a group's current performance and its best possible achievable performance ($\mathcal{L}_g(\theta) - \mathcal{L}_g^*$). By minimizing the maximum excess risk, the optimizer accounts for inherent task difficulties across sub-populations.

Ensuring Efficiency via Blind Pareto Fairness

A second limitation occurs when the minimax optimizer successfully minimizes the loss of the worst-off group, but hits a fundamental bottleneck. Once the worst-off group cannot be improved any further, a standard minimax algorithm stops optimizing, leaving the remaining groups with sub-optimal performance.

Pure Minimax:   Stops optimizing once the worst group hits a bottleneck.
Pareto Minimax: Continues optimizing other groups *if* it doesn't hurt the worst group.

To resolve this, Martin Andres Bertran et al. proposed Blind Pareto Fairness (BPF) in Blind Pareto Fairness and Subgroup Robustness. BPF integrates Pareto efficiency into the minimax framework. It ensures that improvements for low-risk, majority groups are continuously pursued during training, provided that these updates do not increase the risk or loss experienced by the most vulnerable segments of the population.


Generalization Beyond Classification

The mathematical elegance of the minimax framework allows it to generalize far beyond standard classification tasks into diverse machine learning domains:

By shifting the core objective of machine learning from global averages to worst-case guarantees, minimax optimization provides a mathematically rigorous foundation for building systems that refuse to leave minority populations behind.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 105 papers
  2. Version 1 · 2026-10-04 · 199 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_minimax_fairness_optimization_f0f4d83a,
  title = {minimax fairness optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimax-fairness-optimization/rdr_f0f4d83a97b049c98cc5d32d3f049231},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_minimax_fairness_optimization_f0f4d83a_v2,
  title = {minimax fairness optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimax-fairness-optimization/rdr_f0f4d83a97b049c98cc5d32d3f049231/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake