# Adaptive Sampling for Minimax Fair Classification

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 1 Mar 2021.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Model Cards for Model Reporting](https://mlsanity.com/paper/1810.03993/) (2018)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Age Progression/Regression by Conditional Adversarial Autoencoder](https://mlsanity.com/paper/1702.08423/) (2017)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Improving fairness in machine learning systems: What do industry practitioners need?](https://mlsanity.com/paper/1812.05239/) (2018)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [Lessons from Archives: Strategies for Collecting Sociocultural Data in Machine Learning](https://mlsanity.com/paper/1912.10389/) (2019)
- [Fair Active Learning](https://mlsanity.com/paper/2001.01796/) (2020)

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

- [Representation Bias in Data: A Survey on Identification and Resolution Techniques](https://mlsanity.com/paper/2203.11852/) (2022)
- [Minimax AUC Fairness: Efficient Algorithm with Provable Convergence](https://mlsanity.com/paper/2208.10451/) (2022)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Certifying Some Distributional Fairness with Subpopulation Decomposition](https://mlsanity.com/paper/2205.15494/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [Falcon: Fair Active Learning using Multi-armed Bandits](https://mlsanity.com/paper/2401.12722/) (2024)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [Achieving Representative Data via Convex Hull Feasibility Sampling Algorithms](https://mlsanity.com/paper/2204.06664/) (2022)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Fair Active Learning in Low-Data Regimes](https://mlsanity.com/paper/2312.08559/) (2023)
- [Learning Fairer Representations with FairVIC](https://mlsanity.com/paper/2404.18134/) (2024)
- [Fairness Testing through Extreme Value Theory](https://mlsanity.com/paper/2501.11597/) (2025)
- [Fair Robust Active Learning by Joint Inconsistency](https://mlsanity.com/paper/2209.10729/) (2022)
- [A Differentiable Distance Approximation for Fairer Image Classification](https://mlsanity.com/paper/2210.04369/) (2022)
- [From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs](https://mlsanity.com/paper/2601.11890/) (2026)
- [Benchmarking Multi-Domain Active Learning on Image Classification](https://mlsanity.com/paper/2312.00364/) (2023)
- [To Pool or Not To Pool: Analyzing the Regularizing Effects of Group-Fair Training on Shared Models](https://mlsanity.com/paper/2402.18803/) (2024)
- [Dataset Representativeness and Downstream Task Fairness](https://mlsanity.com/paper/2407.00170/) (2024)
- [Adaptive Recruitment Resource Allocation to Improve Cohort Representativeness in Participatory Biomedical Datasets](https://mlsanity.com/paper/2408.01375/) (2024)
- [FairSHAP: Preprocessing for Fairness Through Attribution-Based Data Augmentation](https://mlsanity.com/paper/2505.11111/) (2025)
- [Mind the Gaps: Auditing and Reducing Group Inequity in Large-Scale Mobility Prediction](https://mlsanity.com/paper/2510.26940/) (2025)
- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)
- [FairBED: A Bayesian Experimental Design Approach to Gathering Fairer Data](https://mlsanity.com/paper/2606.23515/) (2026)

## Abstract (arXiv)

Machine learning models trained on uncurated datasets can often end up adversely affecting inputs belonging to underrepresented groups. To address this issue, we consider the problem of adaptively constructing training sets which allow us to learn classifiers that are fair in a minimax sense. We first propose an adaptive sampling algorithm based on the principle of optimism, and derive theoretical bounds on its performance. We also propose heuristic extensions of this algorithm suitable for application to large scale, practical problems. Next, by deriving algorithm independent lower-bounds for a specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general. We then validate the benefits of adaptively constructing training sets via experiments on synthetic tasks with logistic regression classifiers, as well as on several real-world tasks using convolutional neural networks (CNNs).