# Lexicographically Fair Learning: Algorithms and Generalization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Fairness without Demographics through Adversarially Reweighted Learning](https://mlsanity.com/paper/2006.13114/) (2020)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Two-Player Games for Efficient Non-Convex Constrained Optimization](https://mlsanity.com/paper/1804.06500/) (2018)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Average Individual Fairness: Algorithms, Generalization and Experiments](https://mlsanity.com/paper/1905.10607/) (2019)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Minimax Group Fairness: Algorithms and Experiments](https://mlsanity.com/paper/2011.03108/) (2020)

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

- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Multiaccurate Proxies for Downstream Fairness](https://mlsanity.com/paper/2107.04423/) (2021)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Taking a Moment for Distributional Robustness](https://mlsanity.com/paper/2405.05461/) (2024)

## Abstract (arXiv)

We extend the notion of minimax fairness in supervised learning problems to its natural conclusion: lexicographic minimax fairness (or lexifairness for short). Informally, given a collection of demographic groups of interest, minimax fairness asks that the error of the group with the highest error be minimized. Lexifairness goes further and asks that amongst all minimax fair solutions, the error of the group with the second highest error should be minimized, and amongst all of those solutions, the error of the group with the third highest error should be minimized, and so on. Despite its naturalness, correctly defining lexifairness is considerably more subtle than minimax fairness, because of inherent sensitivity to approximation error. We give a notion of approximate lexifairness that avoids this issue, and then derive oracle-efficient algorithms for finding approximately lexifair solutions in a very general setting. When the underlying empirical risk minimization problem absent fairness constraints is convex (as it is, for example, with linear and logistic regression), our algorithms are provably efficient even in the worst case. Finally, we show generalization bounds -- approximate lexifairness on the training sample implies approximate lexifairness on the true distribution with high probability. Our ability to prove generalization bounds depends on our choosing definitions that avoid the instability of naive definitions.